МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.

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

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

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

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

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

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

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

Dj[s]= cj – (u[s], Aj)

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

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

k=argminDj[s].

j: Dj[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.