Моделирование расчетов по алгоритму симплекс-метода

-0,18y1 - 0,21y2 - 3y3 - 0,2y4 - 0,11y5 - 0,2y6 + 0y7 + 1y8 + 0y9 ≤- 1832

-0,2y1 - 0,08y2 - y3 - 0,1y4 - 0,15y5 - 0,3y6 + 0y7 + 0y8 + 1y9 ≤ -952

 

Матрица коэффициентов A = a(ij) этой системы уравнений имеет  вид:

 

-0,3  -0,15  -4  -0,8  -0,25  -0,2   1  0 0

A=       -0,18 -0,21  -3  -0,2  -0,11  -0,2  0  1 0

-0,2 -0,08 -1  -0,1  -0,15 -0,3   0  0 1

 

 

 

Решим систему уравнений относительно базисных переменных:

y₇, y₈, y₉

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

Y1 = (0,0,0,-1752,-1832,-952)

Итерация  №1

1. Проверка критерия оптимальности. 
План F(x₁) в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.  
2. Определение новой свободной переменной. 
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. 
Ведущей будет вторая строка, а переменную x₈ следует вывести из базиса.  
3. Определение новой базисной переменной. Минимальное значение D_i соответствует 3-му столбцу, т.е. переменную x₃ необходимо ввести в базис. 
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3).

 

 

 

 

4. Пересчет симплекс-таблицы.

 

Итерация  №2

 

1. Проверка критерия  оптимальности. 
План F(x₂) в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 
2. Определение новой свободной переменной. 
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. 
Ведущей будет третья строка, а переменную x₉ следует вывести из базиса. 
3. Определение новой базисной переменной. Минимальное значение D_i соответствует шестому столбцу, т.е. переменную x₆ необходимо ввести в базис. 
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-0,23).

 

 

4. Пересчет симплекс-таблицы. Выполняем преобразования:

 

 

 

Итерация  №3

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

 

Анализ  оптимального плана

 

Оптимальный план можно записать так:

y₁ = 0

y₂ = 0

y₃ = 513,14

y₄ = 0

y₅ = 0

y₆ = 1462,85

y₇ = 593,14

y₈ = 0

y₉ = 0

 

Z^*_min = 110*513,1429 + 20*1462,857 = 85702,86

 

Таким образом мы убедились в  равенстве Z_max = Z^*_min.

 

Обоснование эффективности  оптимального плана

 

При подстановке оптимальных двойственных оценок в систему ограничений  двойственной задачи получим:

 

4*513,14 -  0,2*1462,85 < -1752

- 3*513,14 - 0,2*1462,85 < - 1832

- 513,14 - 0,3*1462,85  < -952

 

 

 

 

-2345,14  < -1752

-1832 =  - 1832

-952 = -952

 

1-ое ограничение выполняется как строгое неравенство, т.е. изготовление Чизкейков «Дабл капучино» экономически не выгодно. И действительно в оптимальном плане прямой задачи x₁ = 0.

 

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что экономически выгодно реализовывать чизкейки «Нью-Йорк», а их использование предусмотрено оптимальным планом прямой задачи.

 

3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что экономически выгодно реализовывать пирожные «Картошка», а их использование предусмотрено оптимальным планом прямой задачи.

 

Вывод

 

Симплекс- метод является универсальным методом, которым можно решить практически любую задачу линейного программирования. Его преимущество заключается в том, что он применим в реальных ситуациях, когда в модели присутствует большее количество переменных. Например, для оптимизации производственной программы предприятий оптимального размещения и концентрации производства, составления оптимального плана перевозок, работы транспорта управления производственными запасами. Также симплекс-метод характеризуется своей простотой решения, т.к. представляет собой строгий алгоритм решения, четкую описанной процедуру последовательных эквивалентных преобразований исходной математической модели методом Жордана –Гаусса. В результате получают либо оптимальный план, либо приходят к выводу, что задача неразрешима. 

 

Список использованной литературы

1. Чернов В.П. Математические методы финансового анализа. – СПб.: 2005
2. Чернов В.П. Введение в линейное программирование. – СПб.: 2002
3. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: 1986 
   

Приложение

 

Таблица 1

	Нормы расхода продуктов							Запас
	Чизкейк Дабл капучино		Чизкейк «Нью-Йорк» классический		Пирожное «Картошка»
Сливки (л.)	0,3		0,18		0,2			30
Сахар (кг)	0,15		0,21		0,08			100
Яйца (шт.)	4		3		1			110
Шоколад (пл.)	0,8	0,2			0,1	40
Сливочное масло (кг)	0,25	0,11		0,15		30
Песочное печенье (кг)	0,2	0,2		0,3			20
Цена (рубли)*	1752	1832		952

*цена  указана за 8 порций