«Экономико-математические методы» (стр. 2 )

Тема 2. Линейное программирование

Задачами линейного программирования (ЛП) называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств неравенств и для которых методы математического анализа оказываются непригодными. ЛП представляет собой наиболее часто используемый метод оптимизации.

Рассмотрим систему уравнений и неравенств с переменными (неизвестными):

(1)

и линейную функцию:

(2)

Требуется найти решение системы (1) при котором целевая функция принимает оптимальное значение (максимальное или минимальное).

Такая задача называется задачей линейного программирования в общем виде. Система (1) называется системой ограничений (областью допустимых решений). Функция (2) называется целевой функцией.

Оптимальным решением задачи ЛП называется решение системы ограничений (2), при котором целевая функция принимает оптимальное значение.

Рассмотрим задачу ЛП в стандартной форме для случая двух переменных :

(9)

(10)

Пусть система неравенств (10) совместна (имеет хотя бы одно решение). Любое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия не отрицательности определяют полуплоскости с соответственными граничными прямыми и.

Так как система совместна, то полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность всех этих точек называется многоугольником решений. Это может быть точка, отрезок, луч, прямая, замкнутый многоугольник, неограниченная многоугольная область.

Решение ЗЛП геометрически представляет собой поиск такой точки многоугольника решений, координаты которой доставляют целевой функции наибольшее (наименьшее) значение. Причем допустимым решением являются все точки многогранника.

Рассмотрим так называемую линию уровня целевой функции z, то есть линию, вдоль которой эта функция принимает одно и то же фиксированное значение : или

Алгоритм решения задачи линейного программирования графическим методом (число переменных ).

1. Строится многоугольная область допустимых решений на плоскости соответствующая ограничениям. Затем строится вектор-градиент

целевой функции z в любой точке область допустимых решений.

2. Прямая (линия уровня функции z), перпендикулярная вектору-градиенту, передвигается параллельно самой себе в направлении вектора-градиента в случае задачи на максимум (и в противоположном направлении - в случае задачи на минимум) до тех пор, пока она не покинет область допустимых решений. Предельная точка (или точки) области являются оптимальными точками.

3. Для нахождения координат оптимальной точки, надо решить систему уравнений, которая соответствует прямым, пересечение которых образует эту точку. Значение целевой функции в этой точке будет оптимальным, а сами координаты точки будут являться решением задачи ЛП.

Замечание. В случае большего числа аргументов (n>2) задача линейного программирования решается симплекс-методом.

Контрольное задание №2.

Решить графически и симплекс-методом задачу линейного программирования:

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.

Тема 3. Динамическое программирование

Динамическое программирование - это метод оптимизации, приспосо6ленный к операциям, в которых процесс принятия решений может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Динамическое программирование дает возможность принять ряд последовательных решений (многошаговый процесс), обеспечивающих оптимальность развития процесса в целом.

Рассмотрим управляемый процесс. Пусть управление можно разбить на шагов, т. е. решения принимаются последовательно на каждом шаге, а управление, переводящее систему из состояния в состояние представляет собой совокупность пошаговых управлений.

Пусть - управление на -ом шаге и удовлетворяет некоторым ограничениям и в этом смысле называется допустимым, где - число, точка, функция, качественный признак. - управление, переводящее систему из состояния в состояние . - состояние системы после -го шага управления. - целевая функция, показатель эффективности рассматриваемой управляемой операции. Целевая функция зависит от начального состояния системы и управления Х.

Предположим:

1. Состояние зависит только от предыдущего состояния и управления на предыдущем шаге и не зависит от предшествующих состояний и управлений. Это требование называется «отсутствие последствий»: - уравнение состояний.

2. Целевая функция является аддитивной от показателей эффективности на каждом шаге. Обозначим показатель эффективности - го шаге через: Тогда

Задача динамического программирования (пошаговой оптимизации) формулируется следующим образом: определить такое допустимое управление Х, переводящее систему из состояния в состояние при котором целевая функция принимает наибольшее (наименьшее) значение.

Экономические задачи, которые наиболее эффективно решаются на основе динамического программирования, должны удовлетворять следующим условиям.

1. Задача оптимизации интерпретируется как -шаговый процесс управления.

2. Целевая функция равна сумме целевых функций на каждом шаге.

3. Выбор управления на ом шаге зависит от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).

4. Состояние системы после го шага зависит только от предшествующего состояния системы и управления (нет последствий).

5. На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров.

В соответствии с указанными условиями задача динамического программирования принимает следующий вид:

.

Второе функциональное соотношение называется уравнением состояния и обычно оно связывается с ограничениями экономической задачи.

Принцип оптимальности Беллмана состоит в следующем: каково бы ни было состояние системы в результате какого либо числа шагов, на ближайшем шаге надо выбирать управление так, чтобы оно в совокупности с оптимальными управлениями на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

Основное требование принципа оптимальности состоит в том, что процесс управления должен быть без обратных связей, то есть управление на каждом шаге не должно оказывать влияние на предшествующие шаги. При оптимальном управлении, утверждается, что любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого процесс а по отношению к исходному состоянию этого процесса. Следовательно, решение на каждом шаге является наилучшим с точки зрения управления в целом.

Функциональные уравнения Беллмана - это математическая формулировка принципа оптимальности Беллмана. Предположим, что ищется максимум целевой функции.

На -ом шаге: т. е. выигрыш на - ом шаге зависит только от управления на этом шаге. На - ом шаге: , т. е. на - ом шаге надо так подобрать управление , чтобы сумма выигрышей на - ом шаге и на - ом шаге была максимальна и т. д. На - ом шаге

, т. е. на - ом шаге надо так подобрать управление , чтобы сумма выигрышей на - ом шаге и на последующих шагах была максимальной.

Алгоритм решения задач динамического программирования.

Определяем все состояния системы при переходе из начального состояния в конечное состояние . На каждом шаге целевые функции имеют вид: и определено уравнение состояния: Из уравнения Беллмана для по находим оптимальное управление на ом шаге По и определяем состояние системы после го шага: Из уравнения Беллмана для находим оптимальное управление на ом шаге По и определяем состояние системы после го шага: и так далее. Условно этот процесс можно представить в виде:

Контрольное задание №3

Предприятие планирует открыть филиалы в Михайловке, Урюпинске и Котельниково, для чего выделяются средства в размере 5 млн. руб.

По расчетам экономистов, каждый филиал при инвестировании в него х тыс. руб. приносит прибыль φi(х) тыс. руб. Эти данные приведены в таблице.

Необходимо выбрать оптимальное распределение выделенных средств между филиалами, обеспечивающее максимальную прибыльность всего проекта.

Вариант 1

Вложенные средства (x млн. руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ1(х)	φ2(х)	φ3(х)
1	1,10	1,40	1,50
2	1,20	1,45	2,20
3	1,30	1,55	2,50
4	1,40	1,60	3,00
5	1,50	1,65	3,10

Вариант 2

Вложенные средства (x млн. руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ1(х)	φ2(х)	φ3(х)
1	0,50	0,40	0,20
2	0,60	0,45	0,40
3	0,80	0,55	0,50
4	0,90	0,60	0,70
5	1,00	0,65	0,90

Вариант 3

Вложенные средства (x млн. руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ1(х)	φ2(х)	φ3(х)
1	0,35	0,50	0,20
2	0,45	0,90	0,40
3	0,50	1,00	0,50
4	0,55	1,10	0,70
5	0,60	1,25	0,90

Вариант 4