Задание № 4

Симплексный метод с искусственным базисом

Целевая функция: Х₁ + 10Х₂ – 3Х₃ + 2Х₄→ min

Система ограничений:

• 3Х₁ – 8Х₂ + 3Х₃ + 1Х₄ ≥ 11

• -6Х₁ + 2Х₂ + 1Х₃ – 3Х₄ = 4

• 4Х₁ + 2Х₂ – 1Х₃ + 5Х₄ ≥ 7

• 4Х₁ – 2Х₂ + 0Х₃ + 1Х₄ = 5

1. Приведение неравенств к канонической форме.

К канонической форме система неравенства приводится путем введения дополнительных переменных. Если знак в неравенстве ≥, дополнительная переменная вводится со знаком «–». Изначально дополнительная переменная вводится в правую часть уравнения. После того как все переменные переносятся в левую часть уравнения, а в правой остается свободный член , дополнительная переменная S₁ получается со знаком «–». То же происходит и с дополнительной переменной S₂.

• 3Х₁ – 8Х₂ + 3Х₃ + 1Х₄ – S₁ = 11

• -6Х₁ + 2Х₂ + 1Х₃ – 3Х₄ = 4

• 4Х₁ + 2Х₂ – 1Х₃ + 5Х₄ – S₂ = 7

• 4Х₁ – 2Х₂ + 0Х₃ + 1Х₄ = 5

• Х₁ + 10Х₂ – 3Х₃ + 2Х₄ – 0S₁ – 0S₂ → min

2. Нахождение первого опорного (базисного) плана

Составляем первую симплексную таблицу, она соответствует первому базисному плану, полученному непосредственно из канонической формы записи задачи. Однако, для данного примера, опорный базисный план обычным способом построить невозможно, так как в этом случае не соблюдается условие не отрицательности переменных.

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

В уравнения с отрицательными дополнительными переменными вводится искусственная переменная Y с коэффициентом = 1 и оценкой «+М» при решении задач на min. M – положительное число, сколь угодно большее самого великого коэффициента целевой функции.

• 3Х₁ – 8Х₂ + 3Х₃ + 1Х₄ – S₁ + Y₁ = 11

• -6Х₁ + 2Х₂ + 1Х₃ – 3Х₄ + Y₂ = 4

• 4Х₁ + 2Х₂ – 1Х₃ + 5Х₄ – S₂ + Y₃ = 7

• 4Х₁ – 2Х₂ + 0Х₃ + 1Х₄ + Y₄ = 5

• Х₁ + 10Х₂ – 3Х₃ + 2Х₄ – 0S₁ – 0S₂ + MY₁ + MY₂ + MY₃ + MY₄ → min

После включения в систему ограничений искусственных переменных можно составить первую симплексную таблицу (таблица 4). Каждая строка таблицы соответствует одному из уравнений системы. Основные переменные приравнивают к 0, остаются дополнительные, значения которых равны свободному члену (правой части уравнения). Количество базисных переменных будет соответствовать числу (n–m) или (10–4=6)

Отличием симплексного метода с искусственным базисом является то, что для функционала (Z – C_j) предусмотрены две строки с номерами (m+1) и (m+2). В первую строчку (m+1) заносят числа C_j (для первой симплексной таблицы коэффициенты функции цели записываются с обратным знаком, для последующих, коэффициенты рассчитываются по правилу прямоугольника). Во вторую строку (m+2) заносят коэффициенты рассчитанные как сумма произведений коэффициентов столбца на соответствующие М оценки базисных переменных. Обе эти строки называются индексными, так как суммарные коэффициенты в них указывают, на сколько единиц изменится функционал при увеличении соответствующей переменной на единицу. Окончательный результат индексной строки получается как сумма двух строк. При этом главный столбец – это столбец с положительным суммарным коэффициентом в индексных строках (так как задача на минимум). Для определения наибольшего коэффициента оценку М принимают за любое число большее, чем имеется в данной таблице. Например, для нашего примера возьмем М=10, тогда строка [(m+1) + (m+2)] рассчитывается как [(-10) + (-60)] = (-70)

Таблица 4 – первая симплексная таблица – опорный базисный план

правая часть (базис)			левая часть
оценка	базисный план	значение базисной переменной	не базисные переменные													симплексное отношение
			основные					Дополни-тельные			искусственные
			Х1	Х2	Х3	Х4	S1		S2	Y1		Y2	Y3	Y4
+ M	Y1	11	3	-8	3	1	-1		0	1		0	0	0	3,67
+ M	Y2	4	-6	2	1	-3	0		0	0		1	0	0	-
+ M	Y3	7	4	2	-1	5	0		-1	0		0	1	0	1,75
+ M	Y4	5	4	-2	0	1	0		0	0		0	0	1	1,25
(m+1)	Z-Cj	0	-1	-10	3	-2	0		0	+1M		+1M	+1M	+1M
(m+2)			+5M	-6M	+3M	+4M	-1M		-1M	+1M		+1M	+1M	+1M
[(m+1)+(m+2)]			49	-70	33	38	-10		-10	20		20	20	20

Формальный признак оптимальности – отсутствие в основной строке целевой функции положительных значений при условии решения задачи на min.

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

3. Последовательное улучшение плана до получения оптимального решения

Рассчитаем следующую симплексную таблицу (таблица 5). Вторая симплексная таблица, как и все последующие, заполняются по ранее обозначенному алгоритму:

1. находим главный столбец (по основной индексной строке)

2. находим главную строку (по симплексному отношению)

3. в новой таблице записываем базисные переменные и их оценки

4. новые коэффициенты главной строки рассчитываем делением старых значений на показатель главного элемента

5. главный столбец преобразуем в нулевой вектор-столбец

6. рассчитываются остальные коэффициенты внутри симплексной таблицы по правилу прямоугольника (коэффициенты индексной строки (m+1) так же рассчитываются по правилу прямоугольника)

7. коэффициенты индексной строки (m+2) рассчитываются как сумма произведений коэффициентов столбца (новых) и М-оценок базисных переменных

8. коэффициенты основной индексной строки рассчитываются как сумма двух строк [(m+1) + (m+2)]

9. значение целевой функции рассчитывают так же по правилу прямоугольника

10. полученный базисный план проверяется на оптимальность

11. если план по формальным признакам оптимален – делается проверка; если план не оптимален – делается следующий шаг по улучшению – рассчитывается следующая симплексная таблица и так до получения оптимального плана.

Таблица 5 – вторая симплексная таблица

правая часть (базис)			левая часть
оценка	базисный план	значение базисной перем-ой	не базисные переменные											симпл-е отнош-е
			основные				дополнительные			искусственные
			Х1	Х2	Х3	Х4		S1	S2	Y1	Y2	Y3	Y4
+ M	Y1	7,25	0,00	-6,50	3,00	0,25		-1,00	0,00	1,00	0,00	0,00	-			2,42
+ M	Y2	11,50	0,00	-1,00	1,00	-1,50		0,00	0,00	0,00	1,00	0,00	-			11,50
+ M	Y3	2,00	0,00	4,00	-1,00	4,00		0,00	-1,00	0,00	0,00	1,00	-			-
1	Х1	1,25	1,00	-0,50	0,00	0,25		0,00	0,00	0,00	0,00	0,00	-			-
(m+1)	Z-Cj	1,25	0,00	-10,50	3,00	-1,75		0,00	0,00	+1M	+1M	+1M	-
(m+2)			0	-4M	+3M	+3M		-1M	-1M	+1M	+1M	+1M	-
[(m+1)+(m+2)]			0	-50,5	33	28,3		-10	-10	20	20	20	-

Из анализа основной индексной строки видно, что решение не оптимально (Х₃ = 33). Улучшаем план, рассчитывая следующую симплексную таблицу.

Таблица 6 – третья симплексная таблица

правая часть (базис)			левая часть
оценка	базисный план	значение базисной перем-ой	не базисные переменные												симпл-е отн-е
			основные				дополнительные			искусственные
			Х1	Х2	Х3	Х4		S1	S2		Y1	Y2	Y3	Y4
-3	Х3	2,42	0,00	-2,17	1,00	0,08		-0,33	0,00		-	0,00	0,00	-		-
+ M	Y2	9,08	0,00	1,17	0,00	-1,58		0,33	0,00		-	1,00	0,00	-		7,79
+ M	Y3	4,42	0,00	1,83	0,00	4,08		-0,33	-1,00		-	0,00	1,00	-		2,41
1	Х1	1,25	1,00	-0,50	0,00	0,25		0,00	0,00		-	0,00	0,00	-		-
(m+1)	Z-Cj	-6	0,00	-4,00	0,00	-2,00		1,00	0,00		-	+1M	+1M	-
(m+2)			0	+3M	0	+2,5M		0	-1M		-	+1M	+1M	-
[(m+1)+(m+2)]			0	26	0	23		1	-10		-	20	20	-

Из анализа основной индексной строки видно, что решение не оптимально (Х₂ = 26). Улучшаем план, рассчитывая следующую симплексную таблицу.

Таблица 7 – четвертая симплексная таблица

правая часть (базис)			левая часть
оценка	базисный план	значение базисной перем-ой	не базисные переменные												Симпл-е отн-е
			основные				дополнительные			искусственные
			Х1	Х2	Х3	Х4		S1	S2		Y1	Y2	Y3	Y4
-3	Х3	7,64	0,00	0,00	1,00	4,91		-0,73	-1,18		-	0,00	-	-		-
+ M	Y2	6,27	0,00	0,00	0,00	-4,18		0,55	0,64		-	1,00	-	-		11,50
4	Х2	2,41	0,00	1,00	0,00	2,23		-0,18	-0,55		-	0,00	-	-		-
1	Х1	2,45	1,00	0,00	0,00	1,36		-0,09	-0,27		-	0,00	-	-		-
(m+1)	Z-Cj	3,64	0,00	0,00	0,00	6,91		0,27	-2,18		-	+1M	-	-
(m+2)			0	0	0	-4,18M		+0,55M	+0,64M		-	+1M	-	-
[(m+1)+(m+2)]			0	0	0	-35		5,77	4,22		-	20	-	-

Если искусственные переменные выходят из базисного плана, расчет их коэффициентов можно не производить , а индексную строку записать одной строкой (m+1). Далее по данной строке базисный план проверяется на оптимальность. В нашем примере оптимальное решение не найдено. Рассчитываем следующую симплексную таблицу.

Таблица 8 – пятая симплексная таблица

правая часть (базис)			левая часть
оценка	базисный план	значение базисной перем-ой	не базисные переменные						Симпл-е отн-е
			основные				дополнительные
			Х1	Х2	Х3	Х4	S1	S2
-3	Х3	16,00	0,00	0,00	1,00	-0,67	0,00	-0,33	-
-0,27	S1	11,50	0,00	0,00	0,00	-7,67	1,00	1,17	-
4	Х2	4,50	0,00	1,00	0,00	0,83	0,00	-0,33	5,4
1	Х1	3,50	1,00	0,00	0,00	0,67	0,00	-0,17	5,25
	Z-Cj	0,50	0,00	0,00	0,00	9,00	0,00	-2,50

Из анализа основной индексной строки видно, что решение не оптимально (Х₄ = 9). Улучшаем план, рассчитывая следующую симплексную таблицу.

Таблица 9 – шестая симплексная таблица

правая часть (базис)			левая часть
оценка	базисный план	значение базисной перем-й	не базисные переменные							Симпл-е отн-е
			основные				дополнительные
			Х1	Х2	Х3	Х4		S1	S2
-3	Х3	19,50	1,00	0,00	1,00	0,00		0,00	-0,50
-0,27	S1	51,75	11,50	0,00	0,00	0,00		1,00	-0,75
4	Х2	0,12	-1,25	1,00	0,00	0,00		0,00	-0,13
-9	Х4	5,25	1,50	0,00	0,00	1,00		0,00	-0,25
	Z-Cj	-46,75	-13,50	0,00	0,00	0,00		0,00	-0,25

В шестой симплексной таблице в индексной строке отсутствуют положительные коэффициенты, следовательно, найдено оптимальное решение.

В базисный план вошли следующие переменные с соответствующими значениями:

Х₂ = 0,12

Х₃ = 19,50

Х₄ = 5,25

S₁ = 51,75

Z = –46,75

4. Проверка решения

Проверим решение, подставив в уравнения значения переменных вошедших в базисный план:

• 3Х₁ – 8Х₂ + 3Х₃ + 1Х₄ – S₁ = 11

• -6Х₁ + 2Х₂ + 1Х₃ – 3Х₄ = 4

• 4Х₁ + 2Х₂ – 1Х₃ + 5Х₄ – S₂ = 7

• 4Х₁ – 2Х₂ + 0Х₃ + 1Х₄ = 5

• Х₁ + 10Х₂ – 3Х₃ + 2Х₄ – 0S₁ – 0S₂ → min

Подставив в уравнения значения Х₂ = 0,12; Х₃ = 19,50; Х₄ = 5,25; S₁ = 51,75, получим следующие равенства:

• 3·0 – 8·0,12 + 3·19,5 + 1·5,25 – 51,75 = 11 11=11

• -6·0 + 2·0,12 + 1·19,5 – 3·5,25 = 4 4=4

• 4·0 + 2·0,12 – 1·19,5 + 5·5,25 – 0 = 7 7=7

• 4·0 – 2·0,12 + 0·19,5 + 1·5,25 = 5 5=5

• 0 + 10·0,12 – 3·19,5 + 2·5,25 – 0·51,75 – 0·0 = –46,75 – 46,75 = – 46,75

Оптимальность плана доказана.