korobov

71

нет. Если же это решение не является неотрицательным, то задача не имеет решения, так как оптимальный план должен быть неотрицательным, а имеющееся единственное решение таковым не является.

Приведение задач линейного программирования к стандартной форме

Иногда задачу линейного программирования целесообразно бывает представить в стандартной форме. При этом число переменных в эквивалентной стандартной задаче уменьшается.

Общая задача линейного программирования (2.2.1) — (2.2.3) может быть приведена к стандартной форме следующим образом. Система уравнений (2.2.2) разрешается относительно некоторых неизвестных; полученные выражения подставляются в линейную форму, в систему неравенств (2.2.3), а также в условия неотрицательности неизвестных хj≥0 при всех j. В результате задача принимает стандартную форму (2.2.7) — (2.2.8). Аналогичным образом приводится каноническая задача линейного программирования к эквивалентной стандартной задаче.

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

Последние условия (2.2.21) выражают неотрицательность переменных x1, x2, x3, x4. Приведем систему (2.2.19) к системе с единичным базисом, соответствующим, например, базисным неизвестным x3 и х4. Как это делается, нам известно (см. часть 1;

2.1.9).

Оформляем расширенную матрицу системы (2.2.19) в виде таблицы столбцов ее по отношению к единичному базису:

Переходим к таблице векторов по отношению к базису А3А4.

72

Так как переменные х3 и x4 должны быть неотрицательными, то уравнения (2.2.22), а значит и система (2.2.19), переходят в систему неравенств с двумя переменными х1 и х2:

Выразим из уравнений (2.2.22) переменные x3 и x4 через переменные x1 и х2:

Полученные результаты (2.2.24) подставляем в линейную форму (2.2.18) и в ограничение-неравенство (2.2.20).

Тогда задача (2.2.18) — (2.2.21) перейдет в эквивалентную стандартную задачу,

Стандартная задача (2.2.25) — (2.2.27) легко решается графическим методом; x1 =0,

х2 = 0 — есть оптимальное решение этой задачи и zмакс=13.

Чтобы получить решение исходной задачи (2.2.18) — (2.2.21), надо подставить найденное решение задачи (2.2.25) — (2.2.27) в равенства (2.2.24) и найти переменные х3 и

х4.

Таким образом,

x1=0, x2=0, x3=5/3, x4=8/3,

— есть оптимальное решение, или оптимальный план, общей задачи линейного программирования (2.2.18) — (2.2.21).

Пример 2. Следующую каноническую форму задачи привести к стандартной форме. Найти неотрицательные числа x1, x2, x3, x4,х5, максимизирующие целевую функцию

где Ат. — транспонированная матрица А.

Задача (2.2.37) — (2.2.39) называется двойственной, или сопряженной, задаче (2.2.34) — (2.2.36). Задача (2.2.34) — (2.2.36) называется прямой. Если считать задачу (2.2.37) —(2.2.39) прямой, то двойственная ей будет задача (2.2.34) — (2.2.36). Таким образом, стандартной задаче максимизации соответствует двойственная стандартная задача минимизации и, наоборот, стандартной задаче минимизации соответствует двойственная стандартная задача максимизации. Поэтому прямую и двойственную стандартные задачи называют двойственной, или взаимосопряженной, парой стандартных задач линейного программирования.

Можно доказать, но на этом мы останавливаться не будем, что или обе

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

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

75

Ограничения-неравенства прямой задачи называют также строчечными ограничениями, а ограничения-неравенства двойственной задачи — столбцовыми. Всякому строчечному ограничению АiХ ≤bi соответствует условие yi ≥ 0, а столбцовому

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

Двойственная пара (2.2.40) называется строчечной, а пара (2.2.41) — столбцовой. Пример. Дана задача: найти неотрицательные числа х1, x2, x3, х4, максимизирующие

Составить задачу, двойственную данной задаче. Взаимосвязь между обеими задачами представляется

следующей таблицей (см. табл.2.2.1)

Табл.2.2.2

Пользуясь этой таблицей, получаем формулировку двойственной задачи. Требуется найти неотрицательные числа y1, y2, обращающие в минимум целевую функцию

z=2y1+y2

при условиях:

y1 + y2 ≥ 1;

≥ 3; y2 y1 + 4y2 ≥ 0;

2y1 − 2y2 ≥ 1

76

Напомним, что неотрицательные векторы X и Y называются допустимыми, если они соответственно удовлетворяют условиям прямой и двойственной задач.

Имеют место следующие теоремы.

Теорема 1. Если векторы X и Y допустимы для сопряженных задач вида (2.2.34) —

и теорема доказана.

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

Теорема 2 (признак оптимальности). Если для некоторых допустимых решений X0

то векторы Х0 и Y0 являются оптимальными решениями соответствующих задач.

Д о к а з а т е л ь с т в о. Пусть X произвольный другой допустимый вектор задачи (2.2.34)—(2.2.36). Тогда, по теореме 1,

СХ ≤ СХ0, а это значит, что вектор Х0 является оптимальным решением прямой задачи. Аналогично

доказывается оптимальность вектора Y0 двойственной задачи. Теорема доказана.

Теорема 2 устанавливает достаточность условия (2.2.47) для оптимальности допустимых векторов Х0 и Y0, т. е. если для некоторых допустимых решений взаимосопряженных задач их целевые функции совпадают по величине, то допустимые решения являются оптимальными.

Можно доказать, но на этом мы останавливаться не будем, что условие (2.2.47) является также и необходимым условием для оптимальности допустимых векторов Х0 и

Y0, т. е. если допустимые векторы Х0 и Y0 оптимальны, то целевые функции для этих

векторов совпадают по величине.

Обратим внимание на неравенство (2.2.46). Если допустимые векторы X и Y оптимальны, то неравенство (2.2.46) должно быть равенством. Обратно, если неравенство (2.2.46) является равенством для некоторых допустимых векторов X и У взаимосопряженных задач, то эти векторы оптимальны.

Итак, для оптимальности допустимых векторов X и Y необходимо и достаточно

Равенства (2.2.49) напишем еще в виде

77

Имеет место следующая интересная теорема.

Теорема 3 (теорема равновесия). Допустимые векторы X и Y прямой и

двойственной задач являются оптимальными в том и только в том случае, если в парах их двойственных условий (2.2.40) и (2.2.41) одно условие является равенством, как только

второе — строгим неравенством.

П о я с н е н и е. Строгое неравенство имеет знак > вместо ≥ или < вместо ≤..

Д о к а з а т е л ь с т в о. Прежде докажем достаточность условий теоремы. Предположим, что условия теоремы выполнены, т. е. что в некоторых парах двойственных условий (2.2.40)

или

CX=BY,

поэтому, в силу теоремы 2, векторы X и Y являются оптимальными решениями взаимосопряженных задач.

Теперь докажем необходимость условий теоремы. Предположим, что векторы X и Y являются оптимальными; тогда должны иметь место равенства (2.2.50). Из равенств (2.2.50) следует:

79

Из теоремы равновесия следует, что если допустимое решение (2.2.62) является оптимальным, то при оптимальном решении (y1, y2, y3) двойственной задачи (2.2.63) — (2.2.64) первые три неравенства (2.2.64), соответствующие положительным значениям х1, х2, х3, должны быть уравнениями, т. е.

При значениях y1 (2.2.66) четвертое ограничение-неравенство в системе ограничений (2.2.64) является строгим неравенством:

8 /17 + 5 2 /17 = 18/17 > 1, которое соответствует x4 = 0.

Значениям y1 (2.2.66), отличным от нуля, соответствуют ограничения (2.2.61), которые при значениях хj (2.2.62) обращаются в равенства.

Итак, в каждой паре двойственных условий взаимосопряженных задач (2.2.60) — (2.2.61) и (2.2.63) — (2.2.64) при значениях неизвестных (2.2.62) и (2.2.66) одно условие является равенством, как только второе — строгим неравенством.

Следовательно, по теореме равновесия, допустимые решения (2.2.62) и (2.2.66) являются оптимальными.

Для оптимального решения (2.2.66) имеем следующее значение целевой функции (2.2.63):

Wmin=9 8/17+5 13/17+8 2/17=9.

Мы видим, что значения zмax=9 и wмin =9, соответственно задач (2.2.60) — (2.2.61) и (2.2.63) — (2.2.64), совпадают, что, в силу теоремы 2, еще раз убеждает нас в том, что допустимые решения (2.2.62) и (2.2.66) оптимальны.

Задача, двойственная канонической задаче линейного программирования

Всякое ограничение-равенство f = 0 может быть заменено парой неравенств вида f≤0 и -f≤0. Поэтому каноническую задачу (2.2.67) — (2.2.68) можно сформулировать в форме следующей стандартной задачи линейного программирования.