Пример 7.5.1

В следующей задаче ЛП оптимальный базис равен В = (Р Р4). Сформулируем двойственную задачу и найдем ее оптимальное решение, используя оптимальный базис прямой задачи.

Максимизировать z = Зх, + Ъх2

при ограничениях

х, + 2х2 + х3 = 5, ~х1 + Зх2 + xt = 2,

Х - 0.

Двойственная задача имеет следующий вид.

Минимизировать w = 5(/, + 2у2

при ограничениях

У\~Уг - 3> 2(/, + 3(/2>5,

/,. /, поимеем В = (лс x4)r, тогда Св = (3, 0). Оптимальный базис и его обратная матрица равны следующему.

ч: з-ct)-

Переменные прямой и двойственной задач имеют следующие значения.

(x1,x/ = B-1b = (5, 7f,

((/l,y2) = CBB,=(3(0).

Оба решения допустимы и 2 = w = 15 (проверьте!). Таким образом, решения оптимальны.

УПРАЖНЕНИЯ 7.5.2

1. Проверьте правильность формулировки двойственной задачи в примере 7.5.1. Проверьте графически, что прямая и двойственная задачи не имеют недопустимых решений.

2. Дана следующая задача линейного программирования.

Максимизировать z = 50х, + 30 х2 + 10х3 при ограничениях

2хх + х2 1, 2х2 - -5, 4x, + x3 = 6, * х2, х3>0.

a) Сформулируйте и запишите двойственную задачу.

b) Покажите с помощью непосредственной проверки, что прямая задача не имеет допустимого решения.

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 для всех