Двойственные задачи

С каждой задачей линейного программирования тесно связана другая задача линейного программирования - двойственная задача (их так и называют - пара двойственных задач):

а₁₁х₁ + а₁₂х₂+……а_1nх_n ≤ в₁ а₁₁у₁ + а₂₁у₂+……а_m1y_m ≥ c₁

а₂₁х₁ + а₂₂х₂+……а_2nх_n ≤ в₂ а₁₂y₁ + а₂₂y₂+……а_m2y_m ≥ c₂

…………………………… ……………………………

а_m1х₁ + а_m2х₂+……а_mnх_n ≤ в_m а_1ny₁ + а_2ny₂+……а_mny_n ≥ c_n

x_i ≥ 0, i = 1,n y_i ≥ 0, i = 1,m

F = c₁х₁ + c₂х₂+……c_nх_n → max G = b₁y₁ + b₂y₂+……b_m y_m → min

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

Пример:

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

-2х₁ + х₂ ≤ 2 -2у₁ + у₂ + у₃ ≥ 1

х₁ – 2х₂ ≤ 2 у₁ – 2у₂ + у₃ ≥ -1

х₁ + х₂ ≤ 5

х₁, х₂ ≥ 0 у₁,у₂,у₃ ≥ 0

F= x₁ – x₂ → max G = 2y₁ +2y₂ +5y₃ → min

Оказывается, решение одной из задач может быть получено непосредственно из решения другой. Кроме того, двойственные задачи позволят дополнить экономический анализ из раздела 5.

Теоремы двойственности:

а) Если одна из двойственных задач имеет оптимальное решение, то симметричная ей двойственная задача также имеет оптимальное решение, причем сами оптимальные значения совпадают: F_max = G_min.

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

в) Если в оптимальном решении одной из задач значение переменной больше нуля, то соответствующее ограничение двойственной задачи обращается в равенство. Если при оптимальном решении одно из ограничений обращается в строгое неравенство, то соответствующая переменная двойственной задачи равна 0.

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

д) Если одна из двойственных задач решена табличным симплекс методом, то оптимальное решение симметричной двойственной задачи легко находится по последней симплекс- таблице - достаточно найти абсолютные значения балансовых переменных. Так, в разделе 4 оптимальное решение двойственной задачи (2/3, 10/3, 0). Впрочем, ниже мы получим тот же результат из других соображений.

Экономическая интерпретация двойственной задачи.

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

Вновь вернемся к модели из раздела 4 (ресурсы: труд, сырье, оборудование).

6х₁ + 5х₂ + 4х₃ ≤ 120 6у₁ +3у₂ + 5у₃ ≥ 9

3х₁ + 2х₂ + 4х₃ ≤ 96 5у₁ +2у₂ + 3у₃ ≥ 10

5х₁ + 3х₂ + 3х₃ ≤ 180 4у₁ +4у₂ + 3у₃ ≥ 16

х₁, х₂, х₃ ≥ 0 у₁, у₂, у₃ ≥ 0

1) F= 9х₁ + 10х₂ + 16х₃ → max G = 120y₁ + 96у₂ + 180y₃ → min

Напомним, что х _опт = (0, 8, 20), F_max = 400

1) Из любого ограничения двойственной задачи следует, что размерность у_i совпадает с размерностью правой части (рубли/ ед. ресурса). Поэтому у_i имеют смысл цены единицы ресурса. Их так и называют – теневые цены ресурсов. Речь, конечно, идет не о реальных ценах ресурсов, по которым осуществляется их закупка. Это лишь некоторая экономическая мера, характеризующая ценность ресурса относительно полученного оптимального решения.

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

Выше мы отметили, что у₁ = 2/3, у₂=10/3. Таким образом, дополнительные средства выгоднее вкладывать в закупку сырья.

2) Отметим, что F_max = 400, G_min = 120* (2/3) + 96* (10/3) +180 *(0)=400.

Таким образом, пункт а) теоремы двойственности выполнен!

Отметим экономический смысл: предприятию безразлично- выпускать продукцию следуя оптимальному плану или быть, может взять да продать ресурсы по теневым ценам и, тем самым, возместить понесенные затраты.

3) Так как х₂ > 0 и х₃ > 0, то в силу п. в)

5у₁ +2у₂ + 3у₃ = 10

4у₁ +4у₂ + 3у₃ = 16

А так как третье ограничение исходной задачи обращается при оптимальном решении в строгое неравенство, то у₃ = 0.

Итак, у₁ =2/3, у₂ =10/3.→ у_опт = (2/3, 10/3, 0)

4) Подчеркнем, что у₃ = 0 означает не дефицитность третьего ресурса,

у₁ =2/3, у₂ =10/3 - дефицитность первых двух ресурсов.

5) В силу г) увеличение запаса сырья на одну ед. приведет к увеличению прибыли на 10/3 у.е.

Дата добавления: 2014-12-27