c) Покажите, что двойственная задача не имеет ограниченного решения.
d) На основе примеров задач из предыдущих упражнений найдите соотношение между свойствами недопустимости и неограниченности прямой и двойственной задач ЛП.
3. Дана следующая задача линейного программирования.
Максимизировать z = Ьхх + 12х2 + 4х3
при ограничениях
2xi -х2 + Зх3 = 2, хх + 2х2 + х3 + хл = 5, Ху7 x2t х3, х4 - 0.
a) Сформулируйте и запишите двойственную задачу.
b) В каждом из следующих случаев сначала проверьте, что приведенный базис В является допустимым для прямой задачи. Затем, используя формулу Y = CSB \ вычислите значения переменных двойственной задачи. Кроме того, определите, является ли данное решение прямой задачи оптимальным.
а)В = (Р4,Р3). в)В-(Р„Р,).
б)В = (Р2,Р3). г) В = (Р,, Р4).
4. Дана следующая задача линейного программирования.
Максимизировать z = 2хх + 4х2 + 4х3 - 3xt при ограничениях
х, + 4х2 + xt = 8, xv х2, х3, х4>0.
a) Сформулируйте и запишите двойственную задачу.
b) Путем вычисления разностей г. - су для всех небазисных Ру проверьте, что базис В = (Р2, Р3) соответствует оптимальному решению.
c) Найдите оптимальное решение двойственной задачи.
5. Модель ЛП содержит две переменные хг и х2 и три ограничения типа "<". Соответствующие дополнительные (остаточные) переменные обозначены как х3, хА и ху Предположим, что B = (Pj, Р2, Р3)- оптимальный базис, а соответствующая обратная матрица имеет следующий вид.
,0 -1 О В4 = 0 1 о
,1 1 -.
Ниже представлены оптимальные решения прямой и двойственной задач.
Хя*/ = (2,6, 2)т, Y = U/„</2,</3) = (0, 3, 2). Найдите оптимальное значение целевой функции.
6. Докажите следующее соотношение между оптимальными решениями прямой и двойственной задач:
где Св = (с„ с2, .... cj иР, = (au, a2t, атк)т для = 1, 2, п, (ВРД - /-Й элемент вектора В Рк.
7. Запишите задачу, двойственную к следующей.
Максимизировать z = {СХ АХ = b, X - свободные переменные}
8. Покажите, что задача, двойственная к задаче
максимизировать z = {СХ АХ < b, 0<L<X<U< <*>}, всегда имеет допустимое решение.
7.6. ПАРАМЕТРИЧЕСКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Параметрическое линейное программирование - это расширение техники анализа чувствительности, которую мы рассмотрели в разделе 4.5. Здесь исследуются изменения в оптимальном решении задачи ЛП, являющиеся результатом предопределенных непрерывных изменений коэффициентов целевой функции и значений правых частей ограничений.
Пусть задача ЛП определена следующим образом.
Максимизировать z = jcx£PjxJ= b, X>oj.
В параметрическом программировании задаются изменения коэффициентов целевой функции и правых частей ограничений. Для этого используются функции С(£) и Ь(£), зависящие от параметра изменения t. Для определенности полагаем, что t > 0.
Основная идея параметрического анализа заключается в следующем. Вначале находится оптимальное решение задачи ЛП при t = 0. Затем на основании условий оптимальности и допустимости симплекс-метода определяется интервал 0 < t < tx значений параметра t, для которых решение, полученное при t = 0, остается оптимальным и допустимым. Значение t, называется критическим. Затем определяются следующие критические значения параметра t и соответствующие им оптимальные допустимые решения. Процесс заканчивается, когда будет найдено такое значение tr, что при любых значениях t > tr последнее решение остается неизменным либо решения не существует.
7.6.1. Параметрическое изменение коэффициентов целевой функции
Пусть Х„ , В, и С„ (0 - элементы оптимального решения, соответствующего
критическому значению tt (вычисления начались при t0 = 0 с оптимальным базисом В0). Далее определяем следующее критическое значение и соответствующий ему оптимальный базис, если он существует. Поскольку изменения в векторе коэффициентов целевой функции влияют только на оптимальность решения, текущее решение Хя = B~b останется оптимальным при t > tt до тех пор, пока будет выполняться условие оптимальности
z.(f) - с jit) = С„ (ОВГР, - c{t) > 0 для всех
Очередное критическое значение tM определяется как наибольшее t, t > tt, при котором выполняются все условия оптимальности.
Отметим, что приведенное неравенство не требует, чтобы вектор С(0 был линейной функцией от t; допустима функциональная зависимость любого вида - как линейная, так и нелинейная. Трудность использования нелинейных функций заключается лишь в том, что численное решение системы неравенств может быть очень трудоемким. (В упражнении 7.6.1.5 рассмотрен случай нелинейной функции.)
Пример 7.6.1
Рассмотрим задачу ЛП.
Максимизировать г = (3 - 60 х, + (2 - 2t) х2 + (5 + 50 х. при ограничениях
х, + 2х2 + х3< 40, Зхх + 2х3<60, х1 + 4х2 < 30,
Здесь С(0 = (3 - 6t, 2 - 2t, 5 + 50, t > 0. Введем дополнительные (остаточные) переменные х4, х5 и х6.
Оптимальное решение при t0 = 0.
Хйо - (х2, х3, х/ = (5, 30, 10f СВо(/) =(2-2t, Ъ + Ы, 0),
i -10
в- =
Условия оптимальности для текущих небазисных векторов Р,, Р4 и Р5 имеют вид {<:„(/)В-Ру - с )}.= о = (4 + Ш, 1 - t, 2 + 3t) > 0.
Таким образом, решение остается оптимальным до тех пор, пока выполняются неравенства
4 + 14t>0,
1 -t>0,
2 + 3t> 0.