17, 18. Критерии оптимальности

Теорема 1: Опорный план Х*=(х1*, х2*, 0,…, 0) задачи (1) – (3) является оптимальным, если ∆j ≥0, j = 1, n.

Теорема 2: Если ∆k< 0 для некоторого j=k и среди чисел aik нет положительных (aik ≤ 0), то целевая функция (1) задачи (1) – (3) не ограничена на множестве ее планов.

Теорема 3: Если ∆k < 0 и опорный план Х задачи (1) – (3) не вырожден, но среди чисел aik есть положительные (не все aik ≤ 0), то существует опорный план Х’ такой что Z(X’) >Z(X)

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

19. Метод невязок.

Часто при решении задачи линейного программирования используется искусственный базис. Метод решения при помощи искусственного базиса называется методом невязок. Рассмотрим в качестве примера задачу линейного программирования с пятью неизвестными:

Z = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 (max) (1)

a1x1 + a2x2 + a3x3 + a4x4 + a5x5 = a

b1x1 + b2x2 + b3x3 + b4x4 + b5x5 = b (2)

c1x1 + c2x2 + c3x3 + c4x4 + c5x5 = c

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 (3)

a ≥ 0, b ≥ 0, c ≥ 0 (4)

Если одно или несколько условий (4) не выполняются, например a < 0, то, умножив обе части первого равенства на -1, получим уравнение, в котором свободный член больше. нуля.

Наряду с исходной задачей (1) – (4) рассмотрим другую задачу линейного программирования, которая является вспомогательной:

Т = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 + М (V1 + V2 + V3) (max)

при условиях

a1x1 + a2x2 + a3x3 + a4x4 + a5x5 + V1 = a

b1x1 + b2x2 + b3x3 + b4x4 + b5x5 + V2 = b

c1x1 + c2x2 + c3x3 + c4x4 + c5x5 + V3 = c

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, V1 ≥ 0, V2 ≥ 0, V3 ≥ 0

где М – некоторое число.

Эта задача называется М-задачей. Неизвестными в ней являются x1, x2, x3, x4, x5, V1, V2, V3. При этом неизвестные V1, V2, V3 называются искусственными.

При решении задачи линейного программирования используется следующая теорема:

• Если в оптимальном решении М-задачи все искусственные переменные равны нулю, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи.

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

• Если М-задача не имеет оптимального решения, то исходная задача не разрешима.

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

С каждой задачей ЛП тесным образом связана, строящаяся определенным образом задача, называемая двойственной по отношению к исходной. Прямая и двойственная к ней задачи удовлетворяют следующим условиям:

• число переменных двойственной задачи равно числу условий ограничений прямой задачи (не считая условий неотрицательности переменных) и наоборот число условий ограничений двойственной задачи равно числу переменных исходной задачи;

• коэффициентами целевой функции двойственной задачи служат свободные члены системы ограничений прямой задачи, а свободными членами системы ограничений двойственной задачи – коэффициенты целевой функции исходной задачи;

• матрицей коэффициентов при переменных двойственной задачи будет транспонированная матрица из коэффициентов при переменных системы ограничений исходной задачи;

• если исходная задача решается на max и ее неравенства приведены к виду ≤ то двойственная к ней задача решается на min и ее неравенства в системе ограничений должны быть вида ≥ (целевая установка);

• каждому i-ому ограничению-неравенству прямой задачи соответствует в двойственной задачи условие неотрицательности i-ой переменной (yi ≥ 0), а ограничению-равенству соответствует переменная без ограничений. И наоборот, неотрицательной переменной прямой задачи соответствует в двойственной задачи k-ое ограничение-неравенство, а произвольной переменной – ограничение-равенство.

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

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

Исх. задача: составить план выпуска продукции, обеспечить ее max выпуск в стоимостном выражении.

Двойственная: какова должна быть цена единицы каждого из ресурсов для минимизации общей стоимости затрат.

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

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

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), a Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е. F(x)≤F*(Y) или j=1Σn CjXj ≤ i=1Σm biyi.

Лемма 2. Если для некоторых планов X* и Y* задач (43) – (45) и (46), (47), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.

22-23. Симметричные и несимметричные двойственные задачи. Нахождение оптимального решения. Пример.

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

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

Z = c₁x₁ + c₂x₂ + … + c_nx_n (max)

x₁x₁ + … + a_nx_n b₁

…

a_nx₁ + … + a_mnx_n b_m

x_j 0; j=1,n

a_n … a_m b₁ a_n … am₁ c₁

… …

A am₁…a_mn b_m A^T a_m … a_mn c_n

c₁ … c_n Zmax b₁ … b_m Zmax

T + biyi + … + amiyn (min)

a_ny_i + … a_mj c₁

…

a_iny_i + … + a_mny_n c_n

y_i 0; i=1,m

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

Далее решают задачу симплекс-методом.

Далее находят решение двойственной задачи по решению исходной.

Если задачи симметричны, то решение двойственной находят по строке последней симплекс-таблице решенной задачи.

исходные балансовые

x1 x2 x3 x4 x5 x6

y4 y5 y6 y1 y2 y3

1 2 3 4 5 5

Если задачи несимметричны, то решение находят по формуле Y_опт = Сб Вб^-1 где Сб – матрица-строка (вектор) коэффициентов при базовых переменных целевой функции в оптимальном решении исходной задачи, Вб^-1 – обратная матрица матрицы коэффициентов базовых переменных уравнений системы ограничений исходной задачи в оптимальном решении.