Симплекс-метод решения задач линейного программирования

Симплекс-метод является наиболее распространенным универсальным методом. Идея метода состоит в последовательном продвижении по  опорным планам задачи, т.е. в последовательном улучшении планов задачи по определенному критерию, до тех пор, пока не будет получено оптимальное решение.

Необходимо предварительно выполнить следущие этапы:

-         привести математическую модель к каноническому виду;

-         определить начальное допустимое базисное решение задачм;

 

 

Пример:

 

L=3x₁+2x₂Rmax

   x₁-x₂£2,

  2x₁+x₂£6,

  x₁,x₂³0

Приведем заданную модель к каноническому виду, введя свободные переменные x₃ и x₄, превращающие неравенства в равенства. Переменные x₃ и x₄ входят в уравнение с коэффициентом единица и только один раз:

 L=3x₁+2x₂Rmax

   x₁-x₂+x₃=2,

   2x₁+x₂+x₄=6,

   x_j³0

где x₃ , x₄ - дополнительные переменные, x₁ , x₂ - свободные переменные, A₃ , A₄ - начальный базис, A₀ -вектор ограничений.

Составим симплекс - таблицу, соответствующую каноническому виду, :

 

Табл. 0			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	0	A3	2	1	-1	1	0	2Ümin
2	0	A4	6	2	1	0	1	3
	D		0	-3	-2	0	0
	Z		0	0	0	0	0
				Ýmin

 

              

Элементы строки D расчитываем по формулам:

Для базисных переменных оценки всегда равны нулю.

Значение критерия для данного начального базиса будет равно нулю:

L=åc_ia_i0=0*2+0*6=0;

Так как имеются D_j<0 приступаем к улучшению плана.

 

Первая итерация

В базис вводим вектор A₁, которому соответствует минимальное значение D_j. Из базиса выводим вектор A₃, так как минимальное q достигается при i=3.

Таким образом, элемент a₃₁ будет направляющим(в таблице выделен зеленым цветом).

Заполняем таблицу, соответствующую новому базисному решению.

Все элементы   a_ij таблицы определяются по следущему рекуррентному соотношению:

где a_kr - направл-щий элемент,  l -номер итерации

 

Табл. 1			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	3	A1	2	1	-1	1	0	---
2	0	A4	2	0	3	-2	1	2/3Ümin
	D		6	0	-5	3	0
	Z		6	3	-3	3	0
					Ýmin

 

Приведем расчет нескольких элементов таблицы:

Элемент a₄₂=3 является направляющим(в таблице выделен зеленым цветом).

Так как в строке оценок полученного нового плана имеется отрицательное значение D_j , приступаем ко второй итерации, продолжая улучшать план.

Вторая итерация

 

Табл. 2			0	3	2	0	0	q
i	Csi	базис	A0	A1	A2	A3	A4
1	3	A1	8/3	1	0	1/3	1/3	8
2	2	A2	2/3	0	1	-2/3	1/3	---
	D		28/3	0	0	-1/3	5/3
	Z		28/3	3	2	-1/3	5/3
						Ýmin

;

Элемент a₁₃ =1/3 является направляющим(в таблице выделен зеленым цветом).

Третья итерация

 

Табл. 3			0	3	2	0	0
i	Csi	базис	A0	A1	A2	A3	A4
1	0	A3	8	3	0	1	1
2	2	A4	6	2	1	0	1
	D		12	1	0	0	2
	Z		12	4	2	0	2

 

 

Поскольку все D_j³0, то план представленный в данной таблице будет оптимальным.

 

Ответ:  x₁ =0; x₂=6; x₃=8; x₄=0; L=12;

 

 

 

Если в системе ограничений имеются неравенствами вида > и/или = , начальный план не может быть найден так же просто, как в рассмотренном проимере. В таких случаях начальный  план отыскивают с помощью искусственных переменных.

 

Пример: Найти максимум функции

               L=2x₁+3x₂-5x₃;

при ограничениях:

               2x₁+x₂-x₃³7,

               x₁+2x₂+x₃³6,

               x₁+4x₂=8,

               x_j³0

 Вводим в систему три искусственные переменные: x₆ , x_{7 ,} x₈, позволяющие получить начальный базис.

Для исключения из базиса этих переменных последние вводятся в целевую функцию с большим отрицательным коэффициентом М (в задаче минимизации - с положительным М)

             L¢=L-M*x₆-M*x₇-M*x₈Rmax

при ограничениях

            2x₁+x₂-x₃-x₄+x₆=7,

            x₁+2x₂+x₃-x₅+x₇=6,

            x₁+4x₂+x₈=8,

            x_j³0

Выбрав в качестве начального базиса векторы A₆ , A₇ , A₈, решаем полученную задачу с помощью табличного симплекс-метода.

Если в оптимальном решении такой задачи нет искусственных переменных, это и есть оптимальное решение исходной задачи.

Если же в оптимальном решении данной задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача не разрешима.

 

Табл 0		0	2	3	-5	0	0	-M	-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7	A8
-M	A6	7	2	1	-1	-1	0	1	0	0	7
-M	A7	6	1	2	1	0	-1	0	1	0	3
-M	A8	8	1	4	0	0	0	0	0	1	2Ümin
	D	-21M	-4M -2	-7M -3	5	M	M	0	0	0
				Ýmin

 

 

Элемент a₈₂=4  является направляющим( в таблице выделен зеленым цветом).

Столбцы, соответствующие искусственным переменным по мере вывода из базиса из расчета исключаются.

 

 

Табл 1		0	2	3	-5	0	0	-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7
-M	A6	5	7/4	0	-1	-1	0	1	0	20/7Ümin
-M	A7	2	1/2	0	1	0	-1	0	1	4
3	A2	2	1/4	1	0	0	0	0	0	8
	D	-7M+6	-9М/4-3/4	0	M+5	M	M	0	0
			Ýmin

 

Элемент a₆₁=7/4 является направляющим( в таблице выделен зеленым цветом).

 

Табл 2		0	2	3	-5	0	0	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6
2	A1	20/ 7	1	0	-4/ 7	-4/ 7	0	0	---
-M	A7	4/ 7	0	0	9/ 7	2/ 7	-1	1	4/9Ümin
3	A2	9/ 7	0	1	1/ 7	1/ 7	0	0	9
	D	-4M/ 7 +67/ 7	0	0	-9M/ 7 +30/ 7	2M/ 7 -5/ 7	M	0
					Ýmin

 

Направляющий элемент a₇₃=9/ 7( в таблице выделен зеленым цветом).

 

Табл 3		0	2	3	-5	0	0
Csi	базис	A0	A1	A2	A3	A4	A5
2	A1	28/9	1	0	0	0	-4/9
-5	A3	4/9	0	0	1	2/9	-7/9
3	A2	11/9	0	1	0	-1/9	1/9
	D	23/3	0	0	0	23/9	30/9

Найдено оптимальное решение , так как все оценки неотрицательные и в базисе нет

искусственных переменных:

    x₁=28/9,   x₂=11/9, x₃=4/9,  x₄=0,  L=23/3.