Модифицирован симплекс-метод

Изложение модифицированного симплекс-метода.

Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенаправленное перебирание ДБР, к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.

В МСМ в отличие от СМ симплекс-превращение применяются только к базисной части матрицы условий А.

Признак оптимума и условия отсутствия оптимального решения ЗЛП для МСМ и СМ одинаковые.

Алгоритм модифицированного симплекс-метода.

На s-у шаге МСМ выполняются такие действия:

1. Вычисляются относительные оценки (симплекс - разницы)

D j[s]= cj – (u[s], Aj)

где u[s] = c б[s] В_об[s] — вектор симплекс - множителей, В_об[s] — матрица, обратная к базисной, cб[s] — базисная часть вектора c. Если D j[s] ³ 0 для всех j=1...,n, то конец: текущее базисное решение оптимальное. Если существует j такое, что D j[s]<0, то перейти к пункту 2.

2. Выбирается k за формулой

k=argmin D j[s].

j: D j[s] < 0

Вычисляются векторы Ak[s] = В_об[s] Ak и A0[s]=В_об[s] A0.

Если Ak[s] £ 0, то конец: целевая функция неограниченна снизу на допустимом множестве. Если существуют и такие, что a_ik[s]>0, то перейти к пункту 3.

3. Вычисляются отношения qи[s]=ai0[s]/a_ik[s] для всех a_ik[s]> 0 но выбирается l так, что

l=argminqи[s].

и: a_ik[s] > 0

Вектор Ak принадлежит ввести к базису, а вектор, что является базисным в l- му непрямом ограничении, должен быть выведенным из базиса.

4. Матрица В_об [ s+1 ] вычисляется за матрицей В_об[s] с помощью обычных симплекс - превращений с использованием ведущего элемента a_lk[s]. Подобным образом может быть определен и вектор A₀ [s+1]. Для КЗЛП В_об[0] — единичная матрица размерности m ´ m.

Программное обеспечение.

Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить модифицированным симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1 – №9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.

1)	x1 – x2 + 3x4 + x5 ® min	2)	3 x1 + x2 + x4 + x5 ® min
	x1 + 2x2 + 3x3 + 3x4 + x5 = 15		2 x1 – x2 + x4 – x5 = 9
	2 x1 – x2 – 3x3 + x4 – x5 = 4		4 x1 – x2 – x3 – x5 = 4
	2 x1 – 2x2 – x3 + 2x5 = 8;		x1 – x2 – x3 – x5 = 6;

3)	x1 – 2x2 + 2x3 + x4 + 2x5 ® max	4)	x1 + 2x2 + x3 – x4 ® min
	–x1 + x2 – 2x3 + 3x4 + x5 = 2		–x1 + 5x2 + x3 + x4 + x5 = 10
	–x1 + 2x2 – x3 + 2x4 = 3		2x1 – x2 + x3 – 3x4 = 6
	2x1 + 3x2 + x4 – x5 = 6;		10x2 + x3 + 2x4 + 3x5 = 25;

5)	x1 – x2 + x3 + x4 – x5 ® min	6))	x1 – x2 + x3 + 2x4 ® max
	x1 + x4 + 6 x5 = 9		x1 + x2 + x3 + 2x4 + 3x5 = 7
	3 x1 + x2 – 4 x3 + 2 x5 = 2		x1 + 2x2 + 2x3 + 3x4 + 2x5 = 12
	x1 + 2 x2 + 2 x5 = 6;		2x1 + 3x2 + 4x3 + 4x4 – x5 = 22;

7)	x1 + 2 x2 – x3 – x4 ® min	8)	x1 – x2 + x3 + x4 + x5 – x6 ® min
	x1 + x2 + 2 x3 – x4 = 2		4x1 + x2 – 4x3 + x4 + 8x6 = 15
	x1 + 2 x2 – 3 x3 + x4 = 6		4x1 + x2 – 2x3 + x5 + 4x6 = 8
	x1 + x2 + x3 + x4 = 7;		5x1 + x2 – 2x3 + x4 + x5 + 10x6 = 21;

9)	x1 + 2x2 + 3x3 + x4 + x5 ® max	10))	x1 – x2 + x3 – 3x4 + 2x5 ® min
	x1 + x2 + 4x3 – x4 + x5 = 1		x1 +2x2 – x3 + 2x4 + x5 ³ 8
	x1 + x2 – 2x3 + x4 + x5 = 1		–x1 – x2 + x3 – 3x4 – 2x5 = 10
	–x1 + x2 – 6x3 + x4 + x5 = 1;		2x1 – x2 + 3x3 – x4 + 2x5 £ 4.

Ответы:

1) x* = (5.11; 3.67; 0; 0; 2.56), L (x*)= 4.

2) Решения нет (D = Æ).

3) Решения нет (целевая функция неограниченна сверху на допустимом множестве).

4) x* = (1; 0; 4; 0; 7), L (x*)= 5.

5) x* = (0; 1.5; 0.63; 0; 1.5), L (x*)= -2.38.

6) x* = (1; 0; 4; 1; 0), L (x*)= 7.

7) x* = (4.13; 0; 1.25; 2.62), L (x*)= 1.25.

8) x* = (0; 1; 0.83; 0; 0; 2.17), L (x*)= -2.33.

9) x* = (0; 1; 0; 0; 0), L (x*)= 2.

10) Решения нет (D = Æ).

Лабораторная работа 4.