Контрольная работа по "Методам математического моделирования"

 

 

№1. Решить задачу линейного программирования графическим методом. Мебельное предприятие выпускает линейку продукции двух видов: вида А и вида В. Стоимость одной единицы продукции А составляет 300 евро, продукции В – 400 евро. На производство одной единицы А необходимо 5 кв.м ДСП, 9 кв. м. ткани. На производство продукции В – 5 кв.м ДСП и 3 кв.м. ткани. Ресурсы производства ограниченны. ДСП можно потратить не больше 2500 кв.м, ткани – не больше 2700 кв.м. Найдите, какое количество продукции А и Б необходимо произвести и продать, чтобы получить максимальную прибыль.

Решение:

Необходимо найти максимальное значение целевой функции F = 2500x1+2700x2 → max, при системе ограничений:

5x1+5x2=300
9x1+3x2=400
x1≥0
x2≥0

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Построим уравнение 5x1+5x2=300 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 60. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 60. Соединяем точку (0;60) с (60;0) прямой линией. Построим уравнение 9x1+3x2=400 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 133.33. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 44.44. Соединяем точку (0;133.33) с (44.44;0) прямой линией.

или

Границы области допустимых решений

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

Рассмотрим целевую функцию задачи F = 2500x1+2700x2 → max.  
Построим прямую, отвечающую значению функции F = 0: F = 2500x1+2700x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (2500; 2700). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб

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

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

5x1+5x2=300

9x1+3x2=400

Решив систему уравнений, получим: x1 = 36.6, x2 = 23.3

Откуда найдем максимальное значение целевой функции: 
F(X) = 2500*36.6667 + 2700*23.3 = 154666.6

 

 

 

 

 

 

 

 

 

 

 

 

 

№2. Решить задачу линейного программирования симплекс- методом.

Функция цели задана уравнением . Система ограничений имеет вид:

 

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

Решение:

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. 
Определим максимальное значение целевой функции F(X) = 3x1 + 5x2 при следующих условиях-ограничений. 
8x1 + 8x2≤64 
2x1 + 4x2≤24 
x1≥0 
x2≥0 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
8x1 + 8x2 + 1x3 + 0x4 + 0x5 + 0x6 = 64 
2x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 24 
1x1 + 0x2 + 0x3 + 0x4-1x5 + 0x6 = 0 
0x1 + 1x2 + 0x3 + 0x4 + 0x5-1x6 = 0 
Для постановки задачи на максимум целевую функцию запишем так: 
F(X) = 3x1+5x2 - Mx7 - Mx8 → max 
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. 
Из уравнений выражаем искусственные переменные: 
x7 = 0-x1+x5 
x8 = 0-x2+x6 
которые подставим в целевую функцию: 
F(X) = 3x1 + 5x2 - M(0-x1+x5) - M(0-x2+x6) → max 
или 
F(X) = (3+M)x1+(5+M)x2+(-M)x5+(-M)x6 → max 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

8	8	1	0	0	0	0	0
2	4	0	1	0	0	0	0
1	0	0	0	-1	0	1	0
0	1	0	0	0	-1	0	1

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	64	8	8	1	0	0	0	0	0
x4	24	2	4	0	1	0	0	0	0
x7	0	1	0	0	0	-1	0	1	0
x8	0	0	1	0	0	0	-1	0	1
F(X0)	0	-3-M	-5-M	0	0	M	M	0	0

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x3	64	8	8	1	0	0	0	0	0	8
x4	24	2	4	0	1	0	0	0	0	6
x7	0	1	0	0	0	-1	0	1	0	-
x8	0	0	1	0	0	0	-1	0	1	0
F(X1)	0	-3-M	-5-M	0	0	M	M	0	0	0

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
64-(0 • 8):1	8-(0 • 8):1	8-(1 • 8):1	1-(0 • 8):1	0-(0 • 8):1	0-(0 • 8):1	0-(-1 • 8):1	0-(0 • 8):1	0-(1 • 8):1
24-(0 • 4):1	2-(0 • 4):1	4-(1 • 4):1	0-(0 • 4):1	1-(0 • 4):1	0-(0 • 4):1	0-(-1 • 4):1	0-(0 • 4):1	0-(1 • 4):1
0-(0 • 0):1	1-(0 • 0):1	0-(1 • 0):1	0-(0 • 0):1	0-(0 • 0):1	-1-(0 • 0):1	0-(-1 • 0):1	1-(0 • 0):1	0-(1 • 0):1
0 : 1	0 : 1	1 : 1	0 : 1	0 : 1	0 : 1	-1 : 1	0 : 1	1 : 1
(0)-(0 • (-5-M)):1	(-3-M)-(0 • (-5-M)):1	(-5-M)-(1 • (-5-M)):1	(0)-(0 • (-5-M)):1	(0)-(0 • (-5-M)):1	(M)-(0 • (-5-M)):1	(M)-(-1 • (-5-M)):1	(0)-(0 • (-5-M)):1	(0)-(1 • (-5-M)):1

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	64	8	0	1	0	0	8	0	-8
x4	24	2	0	0	1	0	4	0	-4
x7	0	1	0	0	0	-1	0	1	0
x2	0	0	1	0	0	0	-1	0	1
F(X1)	0	-3-M	0	0	0	M	-5	0	5+M

 

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
64-(0 • 8):1	8-(1 • 8):1	0-(0 • 8):1	1-(0 • 8):1	0-(0 • 8):1	0-(-1 • 8):1	8-(0 • 8):1	0-(1 • 8):1	-8-(0 • 8):1
24-(0 • 2):1	2-(1 • 2):1	0-(0 • 2):1	0-(0 • 2):1	1-(0 • 2):1	0-(-1 • 2):1	4-(0 • 2):1	0-(1 • 2):1	-4-(0 • 2):1
0 : 1	1 : 1	0 : 1	0 : 1	0 : 1	-1 : 1	0 : 1	1 : 1	0 : 1
0-(0 • 0):1	0-(1 • 0):1	1-(0 • 0):1	0-(0 • 0):1	0-(0 • 0):1	0-(-1 • 0):1	-1-(0 • 0):1	0-(1 • 0):1	1-(0 • 0):1
(5+M)-(0 • (-3-M)):1	(-3-M)-(1 • (-3-M)):1	(0)-(0 • (-3-M)):1	(0)-(0 • (-3-M)):1	(0)-(0 • (-3-M)):1	(M)-(-1 • (-3-M)):1	(-5)-(0 • (-3-M)):1	(0)-(1 • (-3-M)):1	(5+M)-(0 • (-3-M)):1

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	64	0	0	1	0	8	8	-8	-8
x4	24	0	0	0	1	2	4	-2	-4
x1	0	1	0	0	0	-1	0	1	0
x2	0	0	1	0	0	0	-1	0	1
F(X2)	0	0	0	0	0	-3	-5	3+M	5+M

 

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
64-(24 • 8):4	0-(0 • 8):4	0-(0 • 8):4	1-(0 • 8):4	0-(1 • 8):4	8-(2 • 8):4	8-(4 • 8):4	-8-(-2 • 8):4	-8-(-4 • 8):4
24 : 4	0 : 4	0 : 4	0 : 4	1 : 4	2 : 4	4 : 4	-2 : 4	-4 : 4
0-(24 • 0):4	1-(0 • 0):4	0-(0 • 0):4	0-(0 • 0):4	0-(1 • 0):4	-1-(2 • 0):4	0-(4 • 0):4	1-(-2 • 0):4	0-(-4 • 0):4
0-(24 • -1):4	0-(0 • -1):4	1-(0 • -1):4	0-(0 • -1):4	0-(1 • -1):4	0-(2 • -1):4	-1-(4 • -1):4	0-(-2 • -1):4	1-(-4 • -1):4
(5+M)-(24 • (-5)):4	(0)-(0 • (-5)):4	(0)-(0 • (-5)):4	(0)-(0 • (-5)):4	(0)-(1 • (-5)):4	(-3)-(2 • (-5)):4	(-5)-(4 • (-5)):4	(3+M)-(-2 • (-5)):4	(5+M)-(-4 • (-5)):4

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	16	0	0	1	-2	4	0	-4	0
x6	6	0	0	0	1/4	1/2	1	-1/2	-1
x1	0	1	0	0	0	-1	0	1	0
x2	6	0	1	0	1/4	1/2	0	-1/2	0
F(X3)	30	0	0	0	11/4	-1/2	0	1/2+M	M

 

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

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
16 : 4	0 : 4	0 : 4	1 : 4	-2 : 4	4 : 4	0 : 4	-4 : 4	0 : 4
6-(16 • 1/2):4	0-(0 • 1/2):4	0-(0 • 1/2):4	0-(1 • 1/2):4	1/4-(-2 • 1/2):4	1/2-(4 • 1/2):4	1-(0 • 1/2):4	-1/2-(-4 • 1/2):4	-1-(0 • 1/2):4
0-(16 • -1):4	1-(0 • -1):4	0-(0 • -1):4	0-(1 • -1):4	0-(-2 • -1):4	-1-(4 • -1):4	0-(0 • -1):4	1-(-4 • -1):4	0-(0 • -1):4
6-(16 • 1/2):4	0-(0 • 1/2):4	1-(0 • 1/2):4	0-(1 • 1/2):4	1/4-(-2 • 1/2):4	1/2-(4 • 1/2):4	0-(0 • 1/2):4	-1/2-(-4 • 1/2):4	0-(0 • 1/2):4
(M)-(16 • (-1/2)):4	(0)-(0 • (-1/2)):4	(0)-(0 • (-1/2)):4	(0)-(1 • (-1/2)):4	(11/4)-(-2 • (-1/2)):4	(-1/2)-(4 • (-1/2)):4	(0)-(0 • (-1/2)):4	(1/2+M)-(-4 • (-1/2)):4	(M)-(0 • (-1/2)):4

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x5	4	0	0	1/4	-1/2	1	0	-1	0
x6	4	0	0	-1/8	1/2	0	1	0	-1
x1	4	1	0	1/4	-1/2	0	0	0	0
x2	4	0	1	-1/8	1/2	0	0	0	0
F(X4)	32	0	0	1/8	1	0	0	M	M