Изложение двойственного симплекс-метода.
Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного программирования (МКЗЛП), которая формулируется таким образом:
Найти вектор x = (x1...,xn), что минимизирует линейную функцию
L(x)= c1x1 + ... + cnxn (4.1)
и удовлетворяет систему линейных ограничений
xi + ai,m+1 xm+1 + ... + ainxn = ai0,i=1...,m (4.2)
xj³0, j=1...,n (4.3)
(компоненты ai0 вектора ограничений A0 могут быть отрицательными) при дополнительном условии: относительные оценки (симплекс - разницы) Dj переменных xj неотъемлемые.
Вектор x=(x1...,xn) называется почти допустимым базисным решением (МДБР) МКЗЛП, если его компоненты удовлетворяют ограничение (4.2), и ненулевым компонентам xj отвечают линейно независимые векторы условий Aj.
Базис и базисная матрица МДБР определяются подобно тому, как это делается для СЗЛП.
МКЗЛП является случаем части СЗЛП. Существуют методы сведения произвольной ЗЛП к почти каноничному виду.
Признак оптимума: Если на некотором шаге ДСМ компоненты МДБР x* неотъемлемые, то x* — оптимальное решение МКЗЛП.
Признак отсутствия решения: Оптимального решения МКЗЛП не существует, если на каком-либо шаге ДСМ в строке с ai0<0 все компоненты aij³0, j=1...,n. В этом случае допустимое множество решений МКЗЛП пустое.
Алгоритм двойственного симплекс-метода.
На каждом шагу ДСМ выполняются такие действия (расчетные формулы наводятся лишь для первого шага).
1. Рассматривается МДБР x=(a10...,am0,0,...,0).
Вычисляются относительные оценки (симплекс - разницы) Dj небазисных переменных xj, j=m+1...,n, за формулой:
Dj=cj– (cб, Aj)
где cб=(c1...,cm), Aj — вектор условий, что отвечает переменной xj (относительные оценки базисных переменных равняются нулю).
Если для всех i=1...,m выполняется условие ai0³0, то МДБР xбудет оптимальным решением МКЗЛП. Конец вычислений.
Если существует такое и, что ai0<0, а коэффициенты aij³0, j=1...,n, то МКЗЛП не имеет допустимых решений. Конец вычислений.
2. Если существуют индексы и, для которых ai0<0, а среди соответствующих компонент aij, j=1...,n, есть отрицательные, то находят l:
l=argmin ai0
и: ai0<0
вычисляют отношение gj=–Dj/alj для всех alj<0 и определяют k:
k=argmin gj.
и: alj<0
3. Переходят к новому МДБР, исключая из базиса вектор Al и вводя к базису вектор Ak. Упомянутый переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса с ведущим элементом alk) над элементами расширенной матрицы условий. Переход к пункту 1.
Программное обеспечение.
Обучающий модуль, с помощью которого ЗЛП Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
Решить двойственным симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.
Во всех задачах, которые предлагаются дальше, все переменные неотъемлемые.
1) | 6 x1 + 4 x2 ® min | 2) | 2 x1 + 3 x2 ® min | 3) | –6 x1 – 4 x2 ® max |
2 x1 + x2 ³ 3 | x1 + 5 x2 ³ 16 | 2 x1 + x2 ³ 3 | |||
x1 – x2 £ 1 | 3 x1 + 2 x2 ³ 12 | x1 – 2 x2 £ 2 | |||
– x1 + 2 x2 ³ 1; | 2 x1 + 4 x2 ³ 16; | 3 x1 + 2 x2 ³ 1; |
4) | 6 x1 + 4 x2 ® min | 5) | 7 x1 + x2 ® min | 6) | 7 x1 + 10 x2 ® min |
2 x1 + x2 ³ 3 | x1 + x2 ³ 3 | 2 x1 + 28 x2 ³ 17 | |||
3 x1 + 2 x2 ³ 1 | 5 x1 + x2 ³ 5 | x1 + 2 x2 ³ 3; | |||
– x1 – x2 ³ 6; | x1 + 5 x2 ³ 5; | x1 + 17 x2 ³ 19; |
7) | x1 + x2 + 2 x3 ® min | 8) | –15x1 – 33 x2 ® max |
2 x1 – x2 – 3 x3 + x4 = – 3 | 3 x1 + 2 x2 ³ 6 | ||
x1 – 3 x2 – 4 x3 + x5 = – 1; | 6 x1 + x2 ³ 6; |
9) | x1 + 2 x2 ® min | 10) | 78 x1 + 52 x2 ® min | 11) | 5 x1 + 4 x2 ® min |
2 x1 + x2 £ 18 | 6 x1 + 2 x2 ³ 9 | x1 + x2 £ 6 | |||
x1 + 2 x2 ³ 14 | -10 x1 + 14 x2 ³13 | 2 x1 + x2 ³ 9 | |||
x1 – 2 x2 £ 10; | 11 x1 - x2 ³ 6; | 3 x1 + x2 ³ 11. |
Ответы:
1) x* = (1; 1), L(x*)= 10.
2) x* = (2; 3), L(x*)= 13.
3) x* = (1.5; 0), L(x*)= -9.
4) Решения нет ( D = Æ ).
5) x* = (0; 5), L(x*)= 5.
6) x* = (0; 1.5), L(x*)= 15.
7) x* = (0; 0; 1; 0; 3), L(x*)= 2.
8) x* = (2; 0), L(x*)= -30.
9) x* = (7.33; 3.33), L(x*)= 14.
10) x* = (0.96; 1.62), L(x*)= 159.12.
11) x* = (4.5; 0), L(x*)= 22.5.
Лабораторная работа 5.