4 Решение задач симплекс−методом

В отличии от геометрического симплекс – метод универсален. Этим методом можно решить любую задачу линейного программирования.

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

Решим симплекс – методом простейшую задачу оптимального плана выпуска продукции.

Задание:

Таблица 5- Исходные данные:

Номер варианта	Виды ресурсов	Виды продукции					Запасы ресурсов
		А1	А2	А3	А4
21	1	5	0	6	2	1500
	2	4	2	2	1	1900
	3	3	0	2	4	700
Прибыль		3	2	2	1

Цель задачи – определить оптимальный план выпуска продукции

( Х₁, Х₂, Х₃, Х₄ ), при котором прибыль максимальна.

Математическая модель задачи принимает вид:

5Х₁ + 6Х₃ + 2Х₄ ≤ 1500;

4Х₁ + 2Х₂ + 2Х₃+ Х₄ ≤ 1900;

3Х₁ + 2Х₃ + 4Х₄ ≤ 700;

Целевая функция: П = 3Х₁ + 2Х₂ + 2Х₃ + Х₄ max

Для решения задачи систему неравенств превратим в систему линейных уравнений, для чего введем новые переменные Х₅, Х₆, Х₇.

5Х₁ + 6Х₃ + 2Х₄ + Х₅ ≤ 1500;

4Х₁ + 2Х₂ + 2Х₃+ Х₄ + Х₆ ≤ 1900;

3Х₁ + 2Х₃ + 4Х₄ + Х₇ ≤ 700;

Так как система состоит из трех уравнений с семью неизвестными, то число основных переменных равно трем, а не основных – четырем.

Нулевой шаг: на этом этапе необходимо найти любое базисное решение. Принимаем за основные переменные Х₅, Х₆, Х₇, а не основные Х₁, Х_2, Х_3, Х₄ приравниваем к нулю.

Х₅ =1500-5Х₁ -6Х₃ - 2Х₄;

Х₆ =1900 - 4Х₁ - 2Х₂ -2 Х₃- Х₄;

Х₇ =700 - 3Х₁ - 2Х₃ - 4Х_4;

П = 3Х₁ + 2Х₂ + 2Х₃ + Х₄;

Получили базисное решение (Х₁ = 0, Х₂ = 0_, Х₃ =0 _, Х₄ = 0, Х₅ = 1500, Х₆ = 1900_, Х₇ = 700). Решение является допустимым, так как все переменные положительны поэтому проверяем его на оптимальность. Решение не оптимально, так как в выражении целевой функции есть коэффициенты с положительными знаками.: П = 0, предприятие ничего не выпускает, поэтому прибыль равна нулю.

При переходе к следующему базисному решению одну из не основных переменных, с наибольшим положительным коэффициентом, переводим в основные переменные, а одну из основных (ту которая первая обращается в нуль, при вводе новой основной переменной) в не основные.

Первый шаг:

Х₅ = 0 если Х₁ = 475;

Х₆ = 0 если Х₁ = 300;

Х₇ = 0 если Х₁ = 233,33;

Следовательно Х₁ переводим в основные переменные, а Х₇ в не основные.

Х₁ = 700/3 – 2·Х₃/3 - 4·Х₄/3 – Х₇/3

Х₅ = 1000/3 – 8·Х₃/3 + 14·Х₄/4 + 5·Х₇/3

Х₆ = 2900/3 – 2·Х₂ + 2·Х₃/3 + 13·Х₄/3 + 4·Х₇/3

П = 700 + 2·Х₂ - 3·Х₄ – Х₇

Получили базисное решение (Х₁ = 700/3; Х₂ = 0; Х₃ =0 ; Х₄ = 0; Х₅ = 1000/3; Х₆ = 2900/3; Х₇ = 0). Прибыль П = 700 Решение является допустимым, так как все переменные положительны поэтому проверяем его на оптимальность. Решение не оптимально, так как в выражении целевой функции есть коэффициенты с положительными знаками

Второй шаг: На этом шаге в основные переводим Х₂, так как эта переменная имеет наибольший положительный коэффициент.

Х₆ = 0 если Х₂ =483,33;

В не основные переводим Х₆.

Х₂ = 1450/3 + Х₃/3 + 13Х₄/6 – Х₆/2 + 2·Х₇/3

Х₅ = 1000/3 - 8Х₃/3 + 14·Х₄/3 + 5Х₇/3

Х₁ = 700/3 - 2·Х₃/3 - 4·Х₄/3 - Х₇/3

П = 5000/3 + 2Х₃/3 + 4Х₄/3 – Х₆+ Х₇/3

Получили базисное решение (Х₁ = 700/3; Х₂ = 1450/3; Х₃ =0 ; Х₄ = 0; Х₅ = 1000/3; Х₆ = 0; Х₇ = 0). Прибыль П = 5000.

Решение является допустимым, так как все переменные положительны поэтому проверяем его на оптимальность. Решение не оптимально, так как в выражении целевой функции есть коэффициенты с положительными знаками

Третий шаг: На этом шаге в основные переводим Х₄, так как эта переменная имеет наибольший положительный коэффициент.

Х₂ = 0 если Х₄ = -223,08;

Х₅ = 0 если Х₄ = -71,43;

Х₁ = 0 если Х₄ = 175;

Следовательно Х₄ переводим в основные переменные, а Х₁ в не основные.

Х₂ = 1725/2 - 13Х₁/8 - 3Х₃/4 – Х₆/2 + Х₇/8

Х₄ = 175 - 3Х₁/4 – Х₃/2 - Х₇/4

Х₅ = 1150 - 7·Х₁/2 - 5·Х₃ + Х₇/2

П = 1900 - Х₁ – Х₆

Получили базисное решение (Х₁ = 0; Х₂ = 1725/2; Х₃ =0 ; Х₄ = 175; Х₅ = 1150; Х₆ = 0; Х₇ = 0). Прибыль П = 1900. Полученное решение является оптимальным, так как все переменные в целевой функции – отрицательны.

Таким образом, в принятой системе ограничений для получения максимальной прибыли П = 1900 руб. необходимо изготовить 863 единиц продукции 2 типа. Продукцию 1 и 3 типа выпускать не выгодно. На складе остается 1500 единиц ресурсов первого вида и 700 единиц ресурсов третьего вида;