Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

Симметричные двойственные задачи

Каждой ЗЛП можно поставить в соответствие задачу, называемую двойственной к исходной задаче.
Рассмотрим задачу об использовании ресурсов. Предположим, что предприятие А производит n видов продукции, величина выпуска которых определяется переменными x1, x2,…,xn. В производстве используются m различных видов ресурсов, объем которых ограничен величинами b1, b2,…bn. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие матрицу

,
а также стоимость единицы продукции каждого вида c1, c2,…cn. Требуется организовать производство так, чтобы предприятию А была обеспечена максимальная прибыль. Задача сводится к нахождению неотрицательных переменных x1, x2,…,xn, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигнет максимума. В математической форме задача записывается следующем виде:

L = c1x1 + c2x2 +…+cnxn → max (1)

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

Если обозначить через y1, y2,…,yn цены, по которым предприятие В покупает ресурсы у предприятия А, то задача сводится к следующему: найти такие значения переменных y1, y2,…,ym, при которых стоимость ресурсов, расходуемых на единицу любого вида продукции не меньше прибыли (цены) за эту единицу продукции, а общая стоимость ресурсов достигает минимума. В математической форме задача записывается в виде:

L = b1y1+b2y2 + ... + bmym → min (3)

при условии (4)
Задачи (1) – (3) и (3) – (4) образуют пару взаимодвойственных задач, любая из которых может рассматриваться как исходная. Решение одной задачи дает оптимальный план производства продукции., решение другой – оптимальную систему оценок сырья, используемого для производства этой продукции.

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

максимизировать сTx при условиях:
Ax≤b;
x≥0;

минимизировать bTy при условиях:
ATy≥c;
y≥0.

Переменные y1,y2,…,ym двойственной задачи иногда называют теневыми ценами.

Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

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

Пример. По исходной задаче требуется построить двойственную.
Исходная задача: L = 10x1 + 6x2 – 4x3 →min


Приведем все неравенства системы ограничений исходной задачи к одному знаку:


Двойственная задача. L=2y1+3y2 → max

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

Решение симметричных двойственных задач

Первая теорема двойственности. Если одна из двойственных задач имеет оптимальное решение, то оптимальное решение имеет и другая задача, при этом значения целевых функций задач равны между собой. Если целевая функция одной из задач не ограничена, то другая задача вообще не имеет решения.
Метод одновременного решения пары двойственных задач.Двойственную пару задач (1) – (2) и (3) – (4) приведем к каноническому виду.
Исходная задача: L = c1x1 + c2x2 +…+ cnxn →min


Двойственная задача:


Число переменных в задачах одинаково и равно m + n. В исходной задаче базисными переменными являются вспомогательные неотрицательные переменные xn+1, xn+2,…,xn+m, а в двойственной задаче – вспомогательные неотрицательные переменные ym+1. ym+2,…, ym+n. Можно показать, что базисным переменным одной задачи соответствуют свободные переменные другой задачи, и наоборот, то есть:


Установив соответствие между переменными пары двойственных задач, и решив одну из них табличным симплексным методом, можно получить решение другой задачи. Значения базисных переменных исходной задачи определяются L строкой оптимальной симплексной таблицы двойственной задачи, и, наоборот, значения базисных переменных двойственной задачи определяются L строкой оптимальной симплексной таблицы исходной задачи.
Пример 1. Найти решение пары двойственных задач.
Исходная задача: Двойственная задача:
L = 4x1 + 6x2 → max L = y1 + 2y2 + 3y3 → min

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

Баз. x1 x2 x3 x4 x5 Cвоб. члены
x2 2 5 1 0 0 1
x4 3 1 0 1 0 2
x5 -1 2 0 0 1 3
L -4 -6 0 0 0 0

Баз. x1 x2 x3 x4 x5 Cвоб. члены
x1 1 2,5 0,5 0 0 0,5
x4 0 -6,5 -1,5 1 0 0,5
x5 0 4,5 0,5 0 1 3,5
L 0 4 2 0 0 2

Решение исходной задачи: X=(0.5; 0; 0; 0.5; 3.5).
Решение двойственной задачи: Y=(2; 0;0;0; 4).
L=L = 2

Пример 2. Для исходной задачи составить двойственную и найти решение пары двойственных задач.

L = 3x1 – x2 + x3 + 9 → max

Приведем данную задачу линейного программирования к виду, допускающему применение симплексного метода. Для этого, используя метод Жордана-Гаусса, приведем ЗЛП к единичному базису.

Баз. x1 x2 x3 x4 x5 Cвоб.
члены
4 -3 -1 1 1 6
1 4 1 0 1 15
2 -4 -1 -1 0 -3
L -3 1 -1 0 0 9
Баз. х1 х2 х3 х4 х5 Cвоб. члены
х5 4 -3 -1 1 1 6
3 -7 -2 1 0 -9
2 -4 -1 1 0 -3
L -3 1 -1 0 0 9
Баз. x1 x2 x3 x4 x5 Cвоб. члены
x5 1 4 1 0 1 15
x4 3 -7 -2 1 0 -9
-1 3 1 0 0 6
L -3 1 -1 0 0 9
Баз. x1 x2 x3 x4 x5 Cвоб. члены
x5 2 1 0 0 1 9
x4 1 -1 0 1 0 3
x3 -1 3 1 0 0 6
L -4 4 0 0 0 15

После преобразований методом Жордана-Гаусса ЗЛП можно записать в виде: L = 4x1 – 4x2 + 15 → max

или

L = 4x1 – 4x2 + 15 → max

Для данной исходной задачи линейного программирования двой­ственная будет иметь вид: L = 9y1+3y2+6y3+15 → min


Установим связь между переменными прямой и двойственной задачами


Решим исходную задачу линейного программирования табличным симплексным методом и найдем решение обеих задач. Результирующая таблица Жордана-Гаусса совпадает с исходной симплексной таблицей, определяющей первое допустимое решение X=(0;0;6;3;9), L=15. Это решение не является оптимальным, поскольку в строке L имеется отрицательная оценка. Используя алгоритм симплексного метода, улучшим данное решение.

Баз. x1 x2 x3 x4 x5 Cвоб. члены
x5 2 1 0 0 1 9
x4 1 -1 0 1 0 3
x3 -1 3 1 0 0 6
L -4 4 0 0 0 15
Баз. x1 x2 x3 x4 x5 Cвоб. члены
x5 0 1 0 -2 1 3
x1 1 -1 0 1 0 3
x3 0 2 1 1 0 9
L 0 0 0 4 0 27

Результирующая симплексная таблица определяет оптимальное решение, так как в строке L нет отрицательных оценок. Итак, X=(3;0;9;0;3), L=27. Используя соответствие между переменными прямой и двойственной задачами, найдем решение двойственной задачи Y=(0;4;0;0;0), L=27

Пример 3. Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.

L = x1 + x2 → min

В случае нахождения минимума целевой функции система ограничений должна иметь знак «≥». Исходная ЗЛП примет вид:

L = x1 + x2 → min


Соответствующая ей двойственная задача запишется в виде:
L = -8y1+4y2+6y3 → max

Исходную ЗЛП решим двойственным симплексным методом и графическим методом, а двойственную ЗЛП решим табличным симплексным методом и сравним решения.
Для решения исходной задачи двойственным симплексным методом
приведем ее к виду: L – x1 – x2 = 0

Используя алгоритм двойственного симплексного метода, найдем решение исходной ЗЛП.

Баз. x1 x2 x3 x4 x5 Cвоб. члены
x3 1 1 1 0 0 8
x4 -1 1 0 1 0 -4
x5 -1 -2 0 0 1 -6
L -1 -1 0 0 0 0
Баз. x1 x2 x3 x4 x5 Cвоб. члены
x3 1/2 0 1 0 1/2 5
x4 -3/2 0 0 1 1/2 -7
x2 1/2 1 0 0 -1/2 3
L -1/2 0 0 0 -1/2 3
Баз. x1 x2 x3 x4 x5 Cвоб. члены
x3 0 0 1 1/3 2/3 8/3
x1 1 0 0 -2/3 -1/3 14/3
x2 0 1 0 1/3 -1/3 2/3
L 0 0 0 -1/3 -2/3 16/3

Результирующая таблица определяет допустимое оптимальное решение исходной ЗЛП: X (14/3; 2/3; 8/3; 0; 0), L=16/3.
Решение двойственной задачи получим из строки L результирующей таблицы с учетом соответствия между переменными исходной и двойственной задач: Y = (0; 1/3; 2/3; 0; 0), L=16/3.
Для решения двойственной ЗЛП табличным симплексным методом, приведем ее к виду: L+8y1-4y2-6y3=0


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

Баз. y1 y2 y3 y4 y5 Cвоб. члены
y4 -1 1 1 1 0 1
y5 -1 -1 2 0 1 1
L 8 -4 -6 0 0 0
Баз. y1 y2 y3 y4 y5 Cвоб. члены
y2 -1 1 1 1 0 1
y5 -2 0 3 1 1 2
L 4 0 -2 4 0 4
Баз. y1 y2 y3 y4 y5 Cвоб. члены
y2 -1/3 1 0 2/3 -1/3 1/3
y3 -2/3 0 1 1/3 1/3 2/3
L 8/3 0 0 14/3 2/3 16/3

Получили оптимальное решение двойственной ЗЛП: Y=(0; 1/3; 2/3; 0; 0), L=16/3. Из последней симплексной таблицы из строки L получим решение исходной ЗЛП: X = (14/3; 2/3; 8/3; 0; 0), L=16/3.
Исходную ЗЛП решим графическим методом.


Найдем координаты точки Amin, решив систему уравнений
Итак, Amin = (14/3; 2/3), L = 16/3.

Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн