Рисунок 6 – Геометрическая интерпретация анализа изменения коэффициентов целевой функции

Увеличение с1 или уменьшение с2

Чтобы проиллюстрировать сказанное, рассмотрим, каким образом можно найти допустимый интервал изменения с₁, при котором точка В остается оптимальной. Исходное значение коэффициента с₂ = 45 оставим неизменным. Из рисунка 6 видно, что значение с₁ можно увеличивать до тех пор, пока прямая F не совпадет с прямой (III), или уменьшать, пока прямая F не совпадет с прямой (II). Эти крайние значения коэффициента с₁ можно определить из равенства наклонов прямой F и прямой (II) (минимальное значение с₁) и равенства наклонов прямой F и прямой (III) (максимальное значение с₁).

Так как тангенс угла наклона для прямой F равен с₁/45, а для прямых (II) и (III) соответственно 1/2 и 2, минимальное значение с₁ определяем из равенства с₁/45 = 1/2, а максимальное значение из равенства с₁/45 = 2. Получаем min с₁ = 22,5; max с₁ = 90.

Для нахождения пределов изменения коэффициента с₂ неизменным оставим значение коэффициента с₁ = 35. Крайние значения коэффициента с₂ можно определить из равенства наклонов прямой F и прямой (II) (максимальное значение с₂) и равенства наклонов прямой F и прямой (III) (минимальное значение с₂). Получаем 35/с₂ = 1/2, 35/с₂ = 2, отсюда min с₂ = 17,5; max с₂ = 70.

Таким образом, при 22,5 ≤ с₁ ≤ 90 и 17,5 ≤ с₂ ≤ 70 точка В по-прежнему остается единственной оптимальной точкой.

Можно заметить, что как только коэффициент с₁ окажется меньше 22,5 (или коэффициент с₂ окажется больше 70), третий ресурс становится недефицитным, второй ресурс остаётся дефицитным. Аналогично, как только коэффициент с₁ окажется больше 90 (или коэффициент с₂ окажется меньше 17,5), второй ресурс становится недефицитным, а третий ресурс остаётся дефицитным.

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

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной.

Понятие двойственности рассмотрим на примере задачи об использовании ресурсов (см. пункт 2.2.1): среди неотрицательных решений системы линейных неравенств

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n ≤ b₁,

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n ≤ b₂,

……………………………..

a_m1x₁ + a_m2x₂ + … + a_mnx_n ≤ b_m

найти решение, обеспечивающее максимум функции

F = c₁x₁ + c₂x₂ + … + c_nx_n → max.

В приведенной модели b_i (i = 1, 2, …, m) обозначают запас ресурса S_i; a_ij – число единиц ресурса S_i, потребляемого при производстве единицы продукции P_j (j = 1, 2, …, n); с_j – прибыль (выручка) от реализации единицы продукции P_j (или цена продукции P_j).

Предположим, что некоторая организация решила закупить ресурсы S₁, S₂, …, S_m предприятия и необходимо установить оптимальные цены на ресурсы y₁, y₂, …, y_m.

Покупающая организация заинтересована в том, чтобы затраты на все ресурсы b₁, b₂, …, b_m по ценам соответственно y₁, y₂, …, y_m были минимальны

Z = b₁y₁ + b₂y₂ + … + b_my_m → min.

С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которое предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции P₁ расходуется a₁₁ единиц ресурса S₁, a₂₁ единиц ресурса S₂ и так далее. По ценам y₁, y₂, …, y_m ресурсы надо продавать, если выручка от продажи ресурсов, затрачиваемых на единицу продукции P₁ будет больше выручки от реализации единицы продукции с₁

a₁₁y₁ + a₂₁y₂ + … + a_m1y_m ≥ c₁.

Аналогично можно составить ограничения по каждому виду продукции.

Получаем следующую формулировку двойственной задачи: найти такой набор цен (оценок) ресурсов Y = (y₁, y₂, …, y_m) при котором общие затраты на ресурсы будут минимальными

Z = b₁y₁ + b₂y₂ + … + b_my_m → min

при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

a₁₁y₁ + a₂₁y₂ + … + a_m1y_m ≥ c₁,

a₁₂y₁ + a₂₂y₂ + … + a_m2y_m ≥ c₂,

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

a_1ny₁ + a_2ny₂ + … + a_mny_m ≥ c_n.

Кроме того, цены на ресурсы не могут быть отрицательными y₁ ≥ 0, y₂ ≥ 0, …, y_m ≥ 0.

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

1) В одной задаче ищут максимум линейной функции, в другой – минимум.

2) Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.

3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «», а в задаче минимизации – неравенства вида «».

4) Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.

5) Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6) Условия неотрицательности переменных имеются в обеих задачах.

Связь между оптимальными решениями двойственных задач устанавливается с помощью первой (основной) теоремы двойственности.

Теорема. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны F_max = Z_min.