- •Глава 2 Линейные методы оптимального управления
- •§ 2.1. Математические оптимизационные модели.
- •Общая постановка задачи линейного программирования.
- •Графический метод решения задачи линейного
- •Программирования
- •Математические оптимизационные модели.
- •1 Этап. Выбор критерия эффективности.
- •2 Этап. Определение параметров условия.
- •3 Этап. Выбор параметров управления.
- •4 Этап. Составление системы ограничений.
- •5 Этап. Выражение целевой функции через параметры условия и параметры управления.
- •Количество решений задачи, решаемой графическим методом.
- •§ 2.2. Графический метод решения задачи линейного программирования (случай n переменных)
- •§ 2.3. Симплексный метод решения задачи линейного программирования
- •§ 2.4. Двойственные задачи линейного программирования
- •§ 2.5. Основные задачи дискретного программирования. Транспортная задача
- •§ 2.6 Целочисленное программирование. Графический метод. Метод Гомори Целочисленное программирование
§ 2.4. Двойственные задачи линейного программирования
Рассмотрим задачу о производстве продукции из ограниченного количества сырья: производитель производит n видов продукции из m видов сырья в количестве b1, b2, …, bm. Известны расходы каждого вида сырья на каждый вид продукции аij, i = 1,…, n; j = 1,…, m, а также прибыль от реализации продукции каждого вида сj , j =1,…, m. Составить план выпуска продукции x1, …, xn , при котором суммарная прибыль от реализации была бы наибольшей.
Математическая модель данной задачи имеет вид:
xj 0, j= 1,2…n.
Данной задаче поставим в соответствие следующую задачу: второй производитель хочет перекупить сырье, имеющееся у первого производителя. По какой минимальной цене первый производитель может его продать, чтобы выручка от продажи не уступала бы прибыли от производства.
Составим математическую модель задачи:
Целевая функция: выручка от продажи сырья (или затраты на покупку сырья) стремиться к минимуму.
Параметры управления: у1,…,уm продажная цена товара. Тогда
а11у1 – стоимость сырья первого вида, которое расходуется на одно изделие первого тип, а21у2 – стоимость сырья второго вида, которое расходуется на одно изделие первого типа и т.д. тогда
– стоимость сырья всех видов, расходуемых на единицу первого вида продукции. Естественно, что первый производитель продаст сырье в том случае, если суммарная стоимость сырья превосходит цену единицы продукции
.
Рассуждая аналогично для остальных видов продукции, получим систему ограничений
Целевая функция имеет функциональное выражение вида:
.
Математические модели двух изложенных выше задач называются двойственными. Такая пара моделей является симметричной парой двойственных задач.
Составим двойственную задачу для задачи из предыдущего параграфа:
.
Система ограничений двойственной задачи имеет транспонированную матрицу по сравнению с прямой задачей. В качестве столбца свободных членов используются коэффициенты целевой функции, а в качестве коэффициентов целевой функции – столбец свободных членов. Знаки неравенств меняются, целевая функция стремится к минимуму. Обратим внимание, что для построения симметричной задачи все неравенства должны быть однотипные, если же в системе ограничений есть противоположное неравенство, то необходимо его умножить на –1.
F=500у1+380у2 min.
Система ограничений и целевая функция содержат две переменные, следовательно, задача может быть решена графически. Построим прямые и отметим полуплоскости, являющиеся решениями каждого неравенства.
Рис.
2.7.
Построим опорную прямую:
500y1 + 380y2 = 0 и укажем направление градиента целевой функции
grad F=(500;380).
На рис. 2.7 отмечена область допустимых неотрицательных решений системы ограничений обратной задачи. Точкой «входа» прямой L в ОДР является точка А – точка пересечения первой и второй прямых. Найдем ее координаты.
Решим систему методом Крамера:
у1= 6 д.е.; у2 = 6 д.е. F = 5006+3806 = 5280 д.е.
Итак, наименьшая цена, за которую первый продавец может продать сырье первого типа – 6 д.е.; сырье второго типа – 6 д.е. При этом он получит 5280 д.е.
Обратим внимание, что при решении прямой задачи в § 2.3 значение целевой функции было такое же. Это является иллюстрацией первой теоремы двойственности:
Если одна из пары задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение, причем значения целевых функций задач на них совпадают. Если же одна из них не имеет оптимального решения, то у другой система ограничений будет несовместна.
По решению двойственной задачи можно восстановить решение исходной задачи. Для этого используют вторую теорему двойственности:
Если при подстановке оптимального решения в систему ограничений i-ое ограничение выполняется как строгое неравенство, то i -ая координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i -ая координата оптимального решения двойственной задачи отлична от нуля то, i-ое ограничение исходной задачи выполняется как равенство.
Подставим решение (6; 6) в систему ограничений, так как обе координаты отличны от нуля, то в исходной задаче оба ограничения выполняются как равенства
Первые два ограничения выполняются как равенства, вторые два – как строгие неравенства (этот результат виден также из рисунка). По теореме третья и четвертая координаты исходной задачи равны нулю. Подставим получившийся результат в систему ограничений исходной задачи:
Решим систему методом Крамера:
Получили то же оптимальное решение, что и в предыдущем параграфе симплексным методом.