Двойственный симплекс-метод и доказательство теоремы двойственности
у1 = — 19/3 + 0 = — 19/3; y2 = -11/3 + 0 = -11/3; у3 = -1/3+0 = -1/3. При этом плане max f = -46/3.
3. Симметричные двойственные задачи
Разновидностью двойственных задач линейного , программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0
и минимизирует линейную функцию Z = СХ.
Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA C, Y 0 и максимизирует линейную функцию f = YA0.
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях
2x1
+ 2x2
- x3
2,
x1 - x2 - 4x3 -3, xi 0 (i=1,2,3)
x1 + x2 - 2x3 6,
2x1 + x2 - 2x3 3,
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.
Двойственная задача. Найти максимум линейной функции f = 2y1+ 3y2 + 6y3 + 3y4 при ограничениях
2
y1
-
y2
+ y3
+ 2y4
1,
2y1 + y2 + y3 + y4 2,
-y1+ 4y2 - 2y3 - 2y4 3,
Для решения исходной задачи необходимо ввести четыре дополнительные переменные и после преобразования системы - одну искусственную. Таким образом, исходная симплексная таблица будет состоять из шести строк и девяти столбцов, элементы которых подлежат преобразованию.
Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.
Двойственную задачу решаем симплексным методом (табл. 1.3).
Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2.
Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2.
Т а б л и ц а 1.3
|
i |
Базис |
С базиса |
A0 |
2 |
3 |
6 |
3 |
0 |
0 |
0 |
||||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
||||||||
|
1 2 3 |
A5 A3 A7 |
0 0 0 |
1 2 3 |
2 2 -1 |
-1 1 4 |
1 1 -2 |
2 -1 -2 |
1 0 0 |
0 1 0 |
0 0 1 |
||||
|
m + 1 |
Zi - Cj |
0 |
-2 |
-3 |
-6 |
-3 |
0 |
0 |
0 |
|||||
|
1 2 3 |
A3 A6 A7 |
6 0 0 |
1 1 5 |
2 0 3 |
-1 2 6 |
1 0 0 |
2 -1 2 |
1 -1 2 |
0 1 0 |
0 0 1 |
||||
|
m + 1 |
Zi - Cj |
6 |
10 |
-9 |
0 |
9 |
6 |
0 |
0 |
|||||
|
1 2 3 |
A3 A2 A7 |
6 3 0 |
3/2 Ѕ 2 |
2 0 3 |
0 1 0 |
1 0 0 |
3/2 -1/2 4 |
Ѕ -1/2 5 |
Ѕ Ѕ 3 |
0 0 1 |
||||
|
m + 1 |
Zi - Cj |
21/2 |
10 |
0 |
0 |
9/2 |
3/2 |
9/2 |
0 |
|||||
4. Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.
Н е с и м м е т р и ч н ы е з а д а ч и
(1) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX = A0; YA С.
X 0.
(2) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX = A0; YA С.
X 0.
С и м м е т р и ч н ы е з а д а ч и
(3) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX A0; YA С.
X 0. Y 0.
(4) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX A0; YA С.
X 0. Y 0.
Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Запишем, например, математическую модель двойственной задачи для следующей исходной.
Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях
x
1
– x2
– x3
4,
x1 – 5x2 + x3 5, xj 0 (j = 1, 2, 3).
2x1 – x2 + 3x3 6,
Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель должна иметь вид (3). Переход осуществляется умножением первого неравенства на -1.
Исходная задача:
Zmin = 2x1 + x2 + 5x3 при ограничениях
-
x1
+ x2
+ x3
-4,
x1 – 5x2 + x3 5, xj 0 (j = 1, 2, 3).
2x1 – x2 + 3x3 6,
Двойственная задача:
fmin = -4x1 + 5x2 + 6x3 при ограничениях
-
y1
+ y2
+ 2y3
2,
y1 – 5y2 - y3 1, yi 0 (i = 1, 2, 3).
2y1 + y2 + 3y3 5,
Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
Если i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.
5. Двойственный симплексный метод
В п. 2 и п. 3 настоящего параграфа было показано, что для получения решения исходной задачи можно перейти к двойственной и используя оценки ее оптимального плана, определить оптимальное решение исходной задачи.
Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана исходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит название двойственного симплексного метода,
Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA С. Допустим, что выбран такой базис D = (A1, А2, ..., Аi, ..., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ..., xi, ..., xm) отрицательная (например, xi < 0), но для всех векторов Aj выполняется соотношение Zj – Cj 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.
Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствующий отрицательной оценке,— включить в базис двойственной задачи.
Для выбора вектора, включаемого в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем 0j= min (xi/xij) 0 и определяем вектор, соответствующий max 0j(Zj — Cj) при решении исходной задачи на минимум и min 0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой.
Если 0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за разрешающий элемент только в том случае, если xij > 0. Такой выбор разрешающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X. Процесс продолжаем до получения Х 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.
В процессе вычислений по алгоритму двойственного симплексного метода условие Zj – Cj 0 можно не учитывать до исключения всех хi < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все хi < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо 0j определить не по минимуму, а по максимуму отношений, т. е. 0j= max (xi/xij) > 0.
Двойственным симплексным методом можно решать задачи линейного программирования, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размеры симплексной таблицы.
Список используемой литературы
Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.