Постановка задачи линейного программирования
в стандартной форме (СЗЛП).
Найти вектор x=(x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 + ... + cnxn (2.1)
и удовлетворяет систему ограничений
a11x1 + . . . + a1n xn = a10
. . . . . . . . . . . . . . . . . . . . . . . (2.2)
am1x1 + . . . + amnxn = am0
xj³0, j=1...,n. (2.3)
В задаче (2.1)–(2.3) будем называть матрицу A=||aij||, i=1...,m, j=1...,n, матрицей условий; вектор-столбец Aj=(a1j...,amj) т, j=1...,n — j-м вектором условий; вектор A0=(a10...,am0) т— вектором ограничений.
Основные определения.
Вектор x=(x1...,xn) называется допустимым решением ЗЛП, если его компоненты удовлетворяют ограничение (2.2)–(2.3).
Ненулевое допустимое решение x — базисный (ДБР), если его положительным компонентам xj отвечают линейно независимые векторы условий Aj. (Нулевое допустимое решение будем всегда считать базисным).
Система m линейно независимых векторов условий, что включает указанные векторы Aj, называется базисом.
Векторы базиса образуют базисную матрицу.
Изложение симплекс-метода.
Симплекс-метод (СМ) непосредственно применяется к развязыванию каноничной задачи линейного программирования (КЗЛП) и осуществляет целеустремленное перебирание допустимых базисных решений (ДБР) (вершин допустимого многогранника решений ЗЛП, что определяется ограничениями (2.2)–(2.3)), к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.
ЗЛП — каноничная, если ее ограничения (2.2) имеют каноничную форму:
xi + ai,m+1 xm+1 + ... + ainxn = ai0, ai0³0, i=1...,m
то есть, матрица условий A=||aij||, i=1...,m, j=1...,n, заключает в себе единичную подматрицу размера m´m и вектор ограничений A0=(a10...,am0) т— неотъемлемый.
КЗЛП элементарно определяет такие основные в линейном программировании конструкции:
· некоторый ДБР — x(0)=(a10...,am0,0,...,0);
· его базис — m-мерные единичные векторы (1,0...,0) т, (0,1...,0) т..., (0...,0,1) т;
· его базисную матрицу B — единичную матрицу размера m´m;
· базисные переменные — x1...,xm.
Стандартная ЗЛП (2.1)–(2.3) сводится в общем случае к каноничной ЗЛП добавлением искусственных неотъемлемых переменных к левым частям ограничений (2.2) и введением этих же переменных с достаточно большим коэффициентом М>0 к целевой функции (2.1) (М-метод).
М-задача имеет вид:
L(x)= c1x1 + ... + cnxn + M(y1 + ... + ym) ® min
a11x1 + . . . + a1n xn + y1 = a10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . ,
am1x1 + . . . + amnxn + ym = am0
xj³0, j=1...,n, yi³0, i=1...,m
ai0³0, i=1...,m.
Признак оптимума: Если на некотором шаге СМ симплекс - разницы (см. алгоритм) ДБР x* незначительные, то x* — оптимальное решение КЗЛП.
Условия отсутствия решения:
1. ЗЛП не имеет оптимального решения, если на каком-либо шаге хотя бы один вектор условий Aj с отрицательной оценкой Djне имеет положительных компонент;
2. ЗЛП не имеет решений, если хотя бы одна искусственная переменная положительная в случае, когда выполняется признак оптимума.
Алгоритм симплекс-метода.
На каждом шагу СМ выполняются такие действия (расчетные формулы наводятся лишь для первого шага).
1. Рассматривается ДБР x=(a10...,am0,0,...,0).
Вычисляются относительные оценки (симплекс - разницы) Dj небазисных переменных xj, j=m+1...,n, за формулой:
Dj=cj– (cб, Aj)
где cб=(c1...,cm), Aj — вектор условий, что отвечает переменной xj (относительные оценки базисных переменных приравняются нулю).
Если для всех j=1...,n, выполняется условие Dj³0, то ДБР xявляется оптимальным решением КЗЛП. Если к тому же все искусственные переменные равняются нулю, то, отбрасывая их, получим оптимальное решение исходной ЗЛП; иначе исходная ЗЛП не имеет решений (ее допустимая область пустая).
Если существует такое j, что Dj<0, а вектор условий Aj не имеет положительных компонент, то ЗЛП не имеет оптимального решения (ее целевая функция L(x) не ограничена снизу на допустимом многограннике решений). Конец вычислений.
2. Если существуют индексы j, для которых Dj<0, а соответствующие векторы условий Aj имеют положительные компоненты, то находят k за формулой
k=argminDj
j: Dj<0
и, вычисляя для aik>0 отношения qi=ai0/aik, определяют l, что удовлетворяет соотношение
l=argminqи.
и: aik>0
3. Переходят к новому ДБР, путем введения к базису вектора Ak и выведения из базиса вектора Al. Такой переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса) с ведущим элементом alk над элементами расширенной матрицы условий (2.2). Переход к пункту 1.
Программное обеспечение.
Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО. Геометрическая интерпретация задачи линейного программирования осуществляется модулем, который вызывается из того же самого раздела.
Задание.
Решить симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1-№9), а также следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.
| 1) | x1 + x2 + x3 ® min | 2) | 2 x1 + x2 – x3 – x4 ® min |
| x1 – x4 – 2 x6 = 5 | x1 + x2 + 2 x3 – x4 = 2 | ||
| x2 + 2 x4 – 3 x5 + x6 = 3 | 2 x1 + x2 – 3 x3 + x4 = 6 | ||
| x3 + 2 x4 – 5 x5 + 6 x6 = 5; | x1 + x2 + x3 + x4 = 7; |
| 3) | x1 – 2x2 + 3x3 ® min | 4) | 2x1 – 3x2 ® max | 5)) | 6 x1 + 4 x2 ® min |
| 2x1 + 3x2 + 4x3 = 1 | 5x1 + 2x2 ³ 10 | 2 x1 + x2 ³ 3 | |||
| –2x1 + x2 + 3x3 = 2; | x1 + 3x2 £ 12; | x1 – x2 £ 1; |
| 6) | 2 x1 – 4 x2 ® min | 7) | 7 x1 + 5 x2 ® max | 8) | 3 x1 + 2 x2 ® max |
| 8 x1 – 5 x2 £ 16 | 7 x1 + 5 x2 ³ 7 | 4 x1 + 2 x2 ³ 12 | |||
| x1 + 3 x2 ³ 2 | 7 x1 – 5 x2 ³ 35 | x1 + 2 x2 £ 10 | |||
| 2 x1 + 7 x2 £ 9; | x1 – x2 £ 0; | 2 x1 + 2 x2 = 6; |
| 9) | 4 x1 + 5 x2 + 9 x3 + 11 x4 ® max | 10) | 2 x1 + x2 – x3 – x4 ® min |
| x1 + x2 + x3 + x4 £ 15 | x1 + x2 + 2 x3 – x4 = 2 | ||
| 7 x1 + 5 x2 + 3 x3 + 2 x4 £ 80 | 2 x1 + x2 – 3 x3 + x4 = 6 | ||
| 3 x1 + 5 x2 + 10 x3 + 15 x4 £ 60; | x1 + x2 + x3 + x4 = 7; |
| 11) | 4x1 + x2 – 2x3 – x4 – x5 ® min | 12) | x1 + 2 x2 + 3 x3 – x4 ® max |
| x3 – x4 + x5 = 1 | x1 + 2 x2 + 3 x3 = 15 | ||
| x2 + 2x4 – x5 = 1 | 2 x1 + x2 – 3 x3 = 20 | ||
| x1 + 2x2 + 2x5 = 4; | x1 + 2 x2 + x4 = 10. |
Ответы:
1) x* = (7.1; 0; 0; 1.3; 0; 0.4), L(x*)= 7.1.
2) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.
3) Решения нет ( D = Æ ).
4) x* = (12; 0), L(x*)= 24.
5) x* = (1.33; 0.33), L(x*)= 9.33.
6) x* = (0; 1.29), L(x*)= -5.14.
7) Решения нет (целевая функция неограниченна сверху на допустимом множестве).
8) x* = (3; 0), L(x*)= 9.
9) x* = (10.16; 0; 2.95; 0), L(x*)= 67.21.
10) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.
11) x* = (0; 0; 0.5; 1.5; 2), L(x*)= -4.5.
12) Решения нет ( D = Æ ).
Лабораторная работа 3.