Контрольная работа по «Методы оптимальных решений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ

рОССИЙСКОЙ ФЕДЕРАЦИИ

(МИНОБРНАУКИ РОССИИ)

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования

«Санкт-Петербургский  государственный политехнический  университет» (ФГБОУ ВПО «СПбГПУ»)

 

ИНСТИТУТ МЕНЕДЖМЕНТА  И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

(филиал) федерального  государственного бюджетного образовательного  учреждения высшего профессионального  образования «Санкт-Петербургский  государственный  политехнический  университет» в г.Череповце (ИМИТ «СПбГПУ»)

Кафедра финансов

 

 

 

 

Контрольная работа №1

 

 

 

Дисциплина: «Методы оптимальных решений»

 

Вариант №3

 

 

Выполнил  студент группы д.614в   Полумиева Ирина Александровна

              (Ф.И.О., полностью) 

№ зачетной книжки__________

Руководитель       ___________________________

                    (Ф.И.О., полностью)

«____» _____________ 20___ г.

___________    ______________

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

   

 

 

 

 

 

 

 

       

 

г. Череповец

2012 г.

 

Задание 1 (20 баллов)

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

	1 продукт	2 продукт	Запасы
1 ресурс	6	9	54
2 ресурс	10	5	50
3ресурс	7	8	84
Прибыль	2	3

 

Решение:

F = 2*x1+3*x2 -> max

6*x1+9*x2 ≤ 54

10*x1+5*x2 ≤ 50

7*x1+8*x2 ≤ 84

x1 ≥ 0, x2 ≥ 0

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

6*x1+9*x2 = 54

10*x1+5*x2 = 50

7*x1+8*x2 = 84

Ограничение x1 ≥ 0, x2 ≥ 0 говорит о том, что решение будет находиться только в I координатной четверти.

Областью  решений неравенств является пятиугольник OBGD (рис. 1).

Рис. 1.

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

 

 

Подставим координаты точки G в целевую функцию и найдем ее максимальное значение F = 2*3+3*4=18

 

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

Z = 54*z1+50*z2+84*z3 -> min

6*z1+10*z2+7*z3 ≥ 2

9*z1+5*z2+8*z3 ≥ 3

z1 ≥ 0, z2 ≥ 0, z3 ≥ 0

Входные данные:
	z1	z2	z3
				Всего	Ограничения
Целевая функция	54	50	84	18
Ограничение 1	6	10	7	2	>=	2
Ограничение 2	9	5	8	3	>=	3
	>=0	>=0	>=0
Выходные результаты:
	z1	z2	z3	G
Решение	0,33333333	0	0	18

Вывод: Целесообразно производить продукт 1 в количестве 3 усл. ед. и продукт 2 в количестве 4 усл. ед., при этом прибыль составит 18 ден. ед. Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное Z= 54*0.33333333+50*0+84*0 = 18 совпадает с максимальным значением целевой функции исходной задачи.

 

 

Задание 2 (20 баллов)

Для изготовления изделий А, В, С и D фабрика расходует в качестве сырья сталь и цветные металлы, имеющиеся в ограниченном количестве. Указанные изделия производят с помощью токарных и фрезерных станков. На основе математического моделирования средствами Excel определить, какую продукцию и в каких количествах целесообразно произвести с точки зрения получения наибольшей прибыли, решить двойственную задачу, проанализировать результаты.

Вид ресурса	Объем ресурса	Нормы расхода на одно изделие
		А	В	С	D
Сталь, кг	580	8	22	19	80
Цветные металлы, кг	430	20	20	32	40
Токарные станки, станко-час	5610	280	220	520	450
Фрезерные станки, станко-час	3410	210	200	100	110
Прибыль, ден. ед.		4	6	5	7

 

Решение:

Средствами  математического моделирования MS Excel

Входные данные:
	x1	x2	x3	x4
	A	B	C	D	Всего	Ограничения
Целевая функция	4	5	6	7	12,04545
Ограничение 1	20	20	32	40	48,18182	<=	480
Ограничение 2	280	220	520	450	530	<=	530
Ограничение 3	210	200	100	110	481,8182	<=	5610
Ограничение 4	8	22	19	80	53	<=	3410
	>=0	>=0	>=0	>=0
Выходные результаты:
	x1	x2	x3	x4	z
Решение	0	2,40909	0	0	12,04545

 

Вывод: Целесообразно производить изделия B, в количестве 2,40909 шт., при этом прибыль составит 12,04545 ден. ед.

 

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

G= 480*z1+530*z2+5610*z3+3410*z4 -> min

20*z1+280*z2+210*z3+8*z4 ≥ 4

20*z1+220*z2+200*z3+22*z4 ≥ 5

32*z1+520*z2+100*z3+19*z4 ≥ 6

40*z1+450*z2+110*z3+80*z4 ≥ 7

z1 ≥ 0, z2 ≥ 0, z3 ≥ 0, z4 ≥ 0

Решение двойственной задачи средствами MS Excel

Входные данные:
	z1	z2	z3	z4
					Всего	Ограничения
Целевая функция	480	530	5610	3410	12,04545
Ограничение 1	20	280	210	8	6,363636	>=	4
Ограничение 2	20	220	200	22	5	>=	5
Ограничение 3	32	520	100	19	11,81818	>=	6
Ограничение 4	40	450	110	80	10,22727	>=	7
	>=0	>=0	>=0	>=0
Выходные результаты:
	z1	z2	z3	z4	G
Решение	0	0,02273	0	0	12,04545

 

Вывод: Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное G= 480*0+530*0,02273+5610*0+3410*0 = 12,04545 совпадает с максимальным значением целевой функции исходной задачи.

 

Задание 3 (20 баллов)

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

	1 продукт	2 продукт	Запасы
1 ресурс	9	8	72
2 ресурс	4	9	36
Прибыль	1	2

 

Решение: Математическая модель данной задачи

f = x₁ + 2x₂ -> max

9x₁ + 8x₂ <= 72

4x₁ + 9x₂ <= 36

x₁ >= 0, x₂ >= 0

В математическую модель задачи введём свободные переменные y₁ и y₂ и запишем ограничения в виде уравнений:

-f = -x₁ - 2x₂ -> min

9x₁ + 8x₂ + y₁ = 72

4x₁ + 9x₂ + y₂ = 36

x₁ >= 0, x₂ >= 0, y₁ >= 0, y₂ >= 0

Записанная  в данном виде задача может быть представлена в виде следующей симплекс-таблицы:

Базисные переменные	Свободные члены	y1	y2	x1	x2
y1	72	1	0	9	8
y2	36	0	1	4	9
f	0	0	0	-1	-2

 

В индексной  строке имеются два отрицательных  числа: -1 и -2.Возьмем число -2 и рассмотрим столбец переменной x₂. В этом столбце имеется два положительных элемента 8 и 9, разделим на данные числа соответствующие свободные члены. Получим числа 9 и 4. Из полученных частных наименьшее 4, значит разрешающий элемент 9, стоящий на пересечении строки y₂ и столбца x₂. Далее переменную y₂ выведем из базисных, а переменную x₂ введём в базисные. Для этого умножим выбранную строку на 1/9 и полученную строку запишем в новую симплекс таблицу на место прежней. К каждой из остальных строк прибавляем вновь полученную строку умноженную на такое число, чтобы в клетках для столбца x₂ появились 0, и запишем вновь полученные строки на место прежних. В итоге получим следующую симплекс-таблицу: