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

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»

КАФЕДРА ЭКОНОМИЧЕСКОЙ  КИБЕРНЕТИКИ И ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ

КУРСОВАЯ РАБОТА

по дисциплине

«Математические методы и  модели исследования операций»

 

Тема:

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

 

Выполнил:

студент группы Р-341

Иванов Александр Владимирович

 

Руководитель:  профессор В.П. Чернов

 

 

Оценка:

_________________________________________________________

 

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2013 

Оглавление

Глава I. Постановка задачи 3

Глава II. Математическое моделирование конкретной ситуации 4

Глава III. Расчет математической модели и определение оптимального плана 5

Итерация №1 6

1. Проверка критерия оптимальности. 6

2. Определение новой базисной переменной. 6

3. Определение новой свободной переменной. 6

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

Итерация №2 8

1. Проверка критерия оптимальности. 8

2. Определение новой базисной переменной. 8

3. Определение новой свободной переменной. 8

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

Итерация №3 9

1. Проверка критерия оптимальности. 9

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

Двойственная задача 11

Определение двойственной математической модели и расчет ее оптимального плана 11

Итерация №1 12

Итерация №2 13

Итерация №3 14

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

Вывод 15

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

Приложение 17

 

 

Глава I. Постановка задачи

 

Цель работы: научиться применять на практике симплекс – метод в моделировании расчетов.

 

Так же задачами курсовой работы являются:

• построение математической модели;
• реализация модели программными средствами Excel;
• вариантные расчеты по модели;
• выводы по расчетам;
• анализ возможностей использования результатов;
• выводы по работе в целом.

 

Глава II. Математическое моделирование конкретной ситуации

 

Кондитерская сети «Кофе Хаус»  производит различные десерты и  сладости. Среди них пирожные «Картошка», а также  чизкейки Нью-Йорк и Дабл капучино. Цены на одну порцию без учета скидок и акций составляют 119,  229 и 219 рублей. Уровень запасов и нормы расхода необходимых продуктов приведены в таблице 1. Необходимо найти оптимальный объем производства ,который максимизирует выручку организации. Построим математическую модель данной задачи. Введем обозначение: x1-x3 – объемы продукции. Тогда прибыль , которая будет получена от их реализации, мы можем выразить в виде:

 

Z = 1752х₁ + 1832х₂+ 952х₃

Расход сырья на необходимые  изделия составляет: (а также введем ограничения на ресурсы) :

 

0,3x₁ + 0,18x₂ + 0,2x₃ ≤ 30

0,15x₁ + 0,21x₂ + 0,08x₃ ≤ 100

4x₁ + 3x₂ + x₃ ≤ 110

0,8x₁ + 0,2x₂ + 0,1x₃ ≤ 40

0,25x₁ + 0,11x₂ + 0,15x₃ ≤ 30

0,2x₁ + 0,2x₂ + 0,3x₃ ≤ 20

 

Полностью математическая модель выглядит так:

 

Max (1752х₁ + 1832х₂+ 952х₃)

 

0,3x₁ + 0,18x₂ + 0,2x₃ ≤ 30

0,15x₁ + 0,21x₂ + 0,08x₃ ≤ 100

4x₁ + 3x₂ + x₃ ≤ 110

0,8x₁ + 0,2x₂ + 0,1x₃ ≤ 40

0,25x₁ + 0,11x₂ + 0,15x₃ ≤ 30

0,2x₁ + 0,2x₂ + 0,3x₃ ≤ 20

x1≥0

x2≥0

x3≥0

 

 

Глава III. Расчет математической модели и определение оптимального плана

 

Для построения первого опорного плана  систему неравенств приведем к системе  уравнений путем введения дополнительных переменных (переход к канонической форме).

 

0,3x₁ + 0,18x₂ + 0,2x₃ + 1x₄ +0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ ≤ 30

0,15x₁ + 0,21x₂ + 0,08x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ ≤ 100

4x₁ + 3x₂ + x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ ≤ 110

0,8x₁ + 0,2x₂ + 0,1x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ ≤ 40

0,25x₁ + 0,11x₂ + 0,15x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 1x₈ + 0x₉ ≤ 30

0,2x₁ + 0,2x₂ + 0,3x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ ≤ 20

 

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

 

             

          0,3   0,18  0,2  1 0 0 0 0 0

          0,15 0,21 0,08 0 1 0 0 0  0

A =    4      3       1     0 0 1 0 0 0

          0,8   0,2    0,1   0 0 0 1 0 0

          0,25 0,11 0,15  0 0 0 0 1 0

          0,2   0,2    0,3   0 0 0 0 0 1

 

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

 

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

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

x₄, x₅, x₆, x₇,x₈,x₉

 

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

X1 = (0,0,0,30,100,110,40,30,20)

 

Базисное решение называется допустимым, если оно неотрицательно.

 

 

 

 

 

 

 

 

 

			1752	1832	952
	базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
	x4	30	0,3	0,18	0,2	1	0	0	0	0	0
	x5	100	0,15	0,21	0,08	0	1	0	0	0	0
	x6	110	4	3	1	0	0	1	0	0	0
	x7	40	0,8	0,2	0,1	0	0	0	1	0	0
	x8	30	0,25	0,11	0,15	0	0	0	0	1	0
	x9	20	0,2	0,2	0,3	0	0	0	0	0	1
m+1		0	-1752	-1832	-952	0	0	0	0	0	0

 

Переходим к основному алгоритму  симплекс-метода.

Итерация №1

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной  переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (30 : 0,18, 100 : 0,21, 110 : 3, 40 : 0,2, 30 : 0,11, 20 : 0,2 ) = 36,666

Следовательно, 4-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

			1752	1832	952							Di
	базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
	x4	30	0,3	0,18	0,2	1	0	0	0	0	0	166,7
	x5	100	0,15	0,21	0,08	0	1	0	0	0	0	476,2
	x6	110	4	3	1	0	0	1	0	0	0	36,67
	x7	40	0,8	0,2	0,1	0	0	0	1	0	0	200
	x8	30	0,25	0,11	0,15	0	0	0	0	1	0	272,7
	x9	20	0,2	0,2	0,3	0	0	0	0	0	1	100
m+1		0	-1752	-1832	-952	0	0	0	0	0	0

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

Формируем следующую часть симплексной  таблицы.

Вместо переменной x₇ в опорный план войдет переменная x₂.

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

 

			1752	1832	952
	базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
	x4	30-36,6*0,18	0,3-1,3*0,75	0,18-1*0,75	0,2-0,3*0,75	1-0*0,75	0-0*0,75	0-0*0,75	0-0,3*0,75	0-0*0,75	0-0*0,75
	x5	100-36,6*0,21	0,3-1,3*0,21	0,18-1*0,21	0,2-0,3*0,21	0-0*0,21	1-0*0,21	0-0*0,21	0-0*0,21	0-0*0,21	0-0*0,21
	x6	110/3=36,6	4/3=1,3	3/3=1	1/3=0,3	0/3=0	0/3=0	1/3=0,3	0/3=0	0/3=0	0/3=0
	x2	40-36,6*0,2	0,8-1,3*0,2	0,2-1*0,2	0,1-0,3*0,2	0-0*0,2	0-0*0,2	0-0,3*0,2	1-0*0,2	0-0*0,2	0-0*0,2
	x8	30-36,6*0,11	0,8-1,3*0,11	0,2-1*0,11	0,1-0,3*0,11	0-0*0,11	0-0*0,11	0-0*0,11	0-0*0,11	1-0*0,11	0-0*0,11
	x9	20-36,6*0,2	0,25-1,3*0,2	0,11-1*0,2	0,15-0,3*0,2	0-0*0,2	0-0*0,2	0-0*0,2	0-0*0,2	0-0*0,2	1-0*0,2
m+1		0-36,6*(-1832)	-1752-1,3*(-1832)	-1832-1*(-1832)	-952-0,3*(-1832)	0-0*(-1832)	0-0*(-1832)	0-0*(-1832)	0-0*(-1832)	0-0*(-1832)	0-0*(-1832)

 

 

 

 

 

 

 

Получаем новую симплекс-таблицу:

Итерация №2

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной  переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (23,4:0,14,  92,3:0,01,  36,6:0,3,  32,6:0,03,  25,96:0,11, 12,6:0,23) = 54,28

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (0,23) и находится на пересечении ведущего столбца и ведущей строки.

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

Формируем следующую часть симплексной  таблицы.

Вместо переменной x₂ в опорный план войдет переменная x₃.

Произведем расчет. Для этого преобразуем разрешающую строку и элементы базисного столбца: .

 

Получаем новую симплекс-таблицу:

Итерация  №3

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

 

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

x₁ = 0

x₂ = 18,57

x₃ = 54,28

x₄ = 15,8

x₅ = 91,75

x₆ = 0

x₇ = 30,85

x₈ = 19,81

x₉ = 0

 

Z = 18,57*1832 + 54,28*952= 85702,86

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

Данный план предписывает изготовление 18 чизкейков «Нью-Йорк классический»  и 54 пирожных «Картошка». Максимальная выручка при этом составит 85702,86 рублей. Переменные x4…x9 имеют смысл неиспользованных объемов ресурсов.

 

Двойственная  задача

Определение двойственной математической модели и  расчет ее оптимального плана

 

Каждой задаче линейного программирования можно определенным образом сопоставить  некоторую другую задачу (линейного  программирования), называемую двойственной или сопряженной по отношению  к исходной или прямой задаче. Существуют зависимости между решениями прямой и двойственной задачи, характеризуемые сформулированными леммами и теоремами. Например, по первой теореме двойственности: если одна из задач двойственной пары имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е. Z_max = Z^*_min . Убедимся в этом на практике. Целевое значение на максимизацию было получено в прямой задаче. А для расчета Z^*_min построим соответствующую математическую модель:

 

  Z^*_min = 30y₁ + 100y₂ + 110y₃ + 40y₄ + 30y₅ + 20y₆

 

0,3y1 + 0,15y2 + 4y3 + 0,8y4 + 0,25y5 + 0,2y6  ≥ 1752

0,18y1 + 0,21y2 + 3y3 + 0,2y4 + 0,11y5 + 0,2y6 ≥ 1832

0,2y1 + 0,08y2 + y3 + 0,1y4 + 0,15y5 + 0,3y6 ≥ 952

 

 

Приведем систему ограничений  к системе неравенств смысла ≤, умножив соответствующие строки на (-1):

 

-0,3y1 - 0,15y2 - 4y3 - 0,8y4 - 0,25y5 - 0,2y6  ≤ -1752

-0,18y1 - 0,21y2 - 3y3 - 0,2y4 - 0,11y5 - 0,2y6 ≤ - 1832

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

 

Для построения первого опорного плана  систему неравенств приведем к системе  уравнений путем введения дополнительных переменных.

В первом неравенстве вводим базисную переменную y₇. Во втором неравенстве вводим базисную переменную y₈.А в третьем y_9.

 

  -0,3y1 - 0,15y2 - 4y3 - 0,8y4 - 0,25y5 - 0,2y6 + 1y7+ 0y8 + 0y9 ≤ -1752

-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 порций