вар5 симпл. Симплекс метод Вариант. 5. Исследование операций вэкономике тема 2 симплексный метод решения задачи оптимального использования ресурсов

• Название: Исследование операций вэкономике тема 2 симплексный метод решения задачи оптимального использования ресурсов
• Анкор: вар5 симпл
• Дата: 15.03.2023
• Размер: 44.68 Kb.
• Имя файла: Симплекс метод Вариант. 5.docx
• Тип: Исследование; #991819

Дисциплина «Исследование операций вэкономике»

ТЕМА №2 СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУРСОВ

Вариант 5

Для производства трех видов продукции П1, П2, П3 предприятие использует три вида сырья S1, S2, S3. Нормы расхода сырья на производство единицы продукции каждого вида приведены в таблице.

Вид сырья	Нормы расхода сырья (кг) на производство единицы продукции			Запасы сырья
	П1	П2	П3
S1	а11	а12	а13		B1
S2	а21	а22	а23		B2
S3	а31	а32	а33		B3
Прибыль	С1	С2	С3

Требуется привести задачу к каноническому виду и симплексным методом определить оптимальный план выпуска продукции, при котором прибыль будет максимальная, дать экономический анализ полученного оптимального решения. Проверить полученное решение в MathCad.

Вид сырья	Нормы расхода сырья (кг) на производство единицы продукции			Запасы сырья
	П1	П2	П3
S1	1	6	2		1200
S2	2	3	1		1000
S3	0	4	1		800
Прибыль	60	40	80

Решение

Определим максимальное значение целевой функции
F(X) = 60x₁+40x₂+80x₃
при следующих условиях-ограничений.


x₁+6x₂+2x₃≤1200
2x₁+3x₂+x₃≤1000
4x₂+x₃≤800


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

.
x₁+6x₂+2x₃+x₄ = 1200
2x₁+3x₂+x₃+x₅ = 1000
4x₂+x₃+x₆ = 800


Матрица коэффициентов этой системы уравнений имеет вид:

A =

1 6 2 1 0 0 2 3 1 0 1 0 0 4 1 0 0 1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆
Полагая, что свободные переменные равны 0, получим первый опорный план:


X0 = (0,0,0,1200,1000,800)


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

Базис	B	x1	x2	x3	x4	x5	x6
x4	1200	1	6	2	1	0	0
x5	1000	2	3	1	0	1	0
x6	800	0	4	1	0	0	1
F(X0)	0	-60	-40	-80	0	0	0

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

1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3
и из них выберем наименьшее:


min (1200 : 2 , 1000 : 1 , 800 : 1 ) = 600


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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	1200	1	6	2	1	0	0	600
x5	1000	2	3	1	0	1	0	1000
x6	800	0	4	1	0	0	1	800
F(X1)	0	-60	-40	-80	0	0	0

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

B	x1	x2	x3	x4	x5	x6
1200 : 2	1 : 2	6 : 2	2 : 2	1 : 2	0 : 2	0 : 2
1000-(1200 • 1):2	2-(1 • 1):2	3-(6 • 1):2	1-(2 • 1):2	0-(1 • 1):2	1-(0 • 1):2	0-(0 • 1):2
800-(1200 • 1):2	0-(1 • 1):2	4-(6 • 1):2	1-(2 • 1):2	0-(1 • 1):2	0-(0 • 1):2	1-(0 • 1):2
0-(1200 • -80):2	-60-(1 • -80):2	-40-(6 • -80):2	-80-(2 • -80):2	0-(1 • -80):2	0-(0 • -80):2	0-(0 • -80):2

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	600	1/2	3	1	1/2	0	0
x5	400	3/2	0	0	-1/2	1	0
x6	200	-1/2	1	0	-1/2	0	1
F(X1)	48000	-20	200	0	40	0	0

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления:

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


min (600 : ¹/₂ , 400 : 1¹/₂ , - ) = 266²/₃


Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1¹/₂) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	600	1/2	3	1	1/2	0	0	1200
x5	400	3/2	0	0	-1/2	1	0	800/3
x6	200	-1/2	1	0	-1/2	0	1	-
F(X2)	48000	-20	200	0	40	0	0

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

B	x1	x2	x3	x4	x5	x6
600-(400 • 1/2):11/2	1/2-(11/2 • 1/2):11/2	3-(0 • 1/2):11/2	1-(0 • 1/2):11/2	1/2-(-1/2 • 1/2):11/2	0-(1 • 1/2):11/2	0-(0 • 1/2):11/2
400 : 11/2	11/2 : 11/2	0 : 11/2	0 : 11/2	-1/2 : 11/2	1 : 11/2	0 : 11/2
200-(400 • -1/2):11/2	-1/2-(11/2 • -1/2):11/2	1-(0 • -1/2):11/2	0-(0 • -1/2):11/2	-1/2-(-1/2 • -1/2):11/2	0-(1 • -1/2):11/2	1-(0 • -1/2):11/2
48000-(400 • -20):11/2	-20-(11/2 • -20):11/2	200-(0 • -20):11/2	0-(0 • -20):11/2	40-(-1/2 • -20):11/2	0-(1 • -20):11/2	0-(0 • -20):11/2

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	1400/3	0	3	1	2/3	-1/3	0
x1	800/3	1	0	0	-1/3	2/3	0
x6	1000/3	0	1	0	-2/3	1/3	1
F(X2)	160000/3	0	200	0	100/3	40/3	0

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	1400/3	0	3	1	2/3	-1/3	0
x1	800/3	1	0	0	-1/3	2/3	0
x6	1000/3	0	1	0	-2/3	1/3	1
F(X3)	160000/3	0	200	0	100/3	40/3	0

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


x₁ = 266²/₃=266.667 , x₂ = 0, x₃ = 466²/₃=466.667
F(X) = 60*266²/₃ + 40*0 + 80*466²/₃ = 53333


Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x₆. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 333¹/₃.
Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.
Значение 200> 0 в столбце x₂ означает, что использование x₂ - не выгодно.
Значение 0 в столбце x₃ означает, что использование x₃ - выгодно.
Проверка в MathCad