Этап условной оптимизации

Задание№1(9)

Металлургическому заводу требуется уголь с содержанием фосфора не более 0, 3% и с долей зольных примесей не более 3,25%. Завод закупает 3 сорта угля А, В, С с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену?

Сорт угля	Содержание(%)	Цена 1т (руб.)
Фосфора	Золы
А	0,06	2,0
В	0,04	4,0
С	0,02	3,0

Решение:

Введем следующие обозначения:

Х₁ – содержание угля А в смеси;

Х₂ – содержание угля Вв смеси;

Х₃ – содержание угля С в смеси;

Ограничения имеют вид:

Окончательный вид:

Приведем к каноническому виду:

Решим симплекс-методом:

S	i
A1	A2	A3	A4	A5
				0,3	0,06	0,04	0,02
			3,25	2,0	4,0	3,0			1
					-30	-30	-45			K=3, l=2
				21/200	7/150	1/75			-1/150
			39/4	2/3	4/3			1/3
									45/3

Задание№2(9)

Предприятие производит три вида продукции А₁, А₂, А₃, используя сырье двух видов: В₁ и В₂. Известны затраты сырья i-го вида на единицу изделия j-го вида a_ij, количество сырья каждого вида b_i (i=1,2), а так же прибыль полученная от единицы изделия j-го вида с_j (j=1,2,3).

(1)Сколько изделий каждого вида необходимо произвести, что бы получить:

1) max прибыли;

2) max товарной продукции.

	А1	А2	А3	Сырье
В1
В2
Прибыль

Найти максимум прибыли?

Приводим к каноническому виду:

S	i
A1	A2	A3	A4	A5
									300
					-3	-3	-2			K=1, l=2
						2/3	-1/3		2/3
					2/3	2/3		1/3	900
						-1				K=2, l=2
					-1		-1		1/3
				3/2				1/2
					3/2				3/2

2) Найти максимум товарной продукции:

Приведем к каноническому виду:

S	i
A1	A2	A3	A4	A5
									300
					-1	-1	-1			K=1, l=2
						2/3	-1/3		2/3
					2/3	2/3		1/3	450
						-1/3	-1/3		1/3	K=2, l=2
					-1		-1		1/3
				3/2				1/2
					1/2				½

(2)Решить задачу при дополнительных условиях: предприятия платят за хранение единицы сырья В₁ и В₂ соответственно 0,1 и 0,3 денежных единицы.

1) Найти maxприбыли?

Приведем к каноническому виду:

S	i
A1	A2	A3	A4	A5
										65
					-3	-3	-2			K=1, l=1
							½	1/2		130
					-1	½	-3/2
							-1/2	3/2		K=3, l=1
				-1	-2		-2

2) Найти MAXпродукции:

Приведем к каноническому виду:

S	i
A1	A2	A3	A4	A5
										65
					-1	-1	-1			K=1, l=1
							½	1/2		130
					-1	½	-3/2
							-1/2	1/2		K=3, l=1
				-1	-2		-2

(3) Решить задачу при условии, что задан план выпуска изделий. При решении учитывать возможность перевыполнения плана.

1) Найти max прибыли:

Приведем к каноническому виду:

S	I
A1	A2	A3	A4	A5	A6	A7	A8
			-100	-1								100
			-100		-1							---
			-200			-1						---
					-3	-3	-2						K=1, l=3
			-100						-1			---
			-100		-1							100
			-200			-1						---
						-3	-2						K=2, l=4
									-1			---
										-1		---
						-1						200
							-2						K=3, l=5
									-1
										-1
											-1

2) Найти maxпродукции:

Приведем к каноническому виду:

S	I
A1	A2	A3	A4	A5	A6	A7	A8
			-100	-1								100
			-100		-1							---
			-200			-1						---
					-1	-1	-1						K=1, l=3
									-1			---
			-100		-1							100
			-200			-1						---
						-1	-1						K=2, l=4
									-1			---
										-1		---
						-1						200
							-2						K=3, l=5
									-1
										-1
											-1

Задание№3

Предприятию необходимо выпустить по плану продуции А₁ – 500 единиц, А₂ – 300, А₃ – 450. Каждый вид изделия может производиться на двух машинах. Полезное затрачиваемое время каждой машины 5000 мин. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Учитывать возможность перевыполнение плана.

Решение:

Или

S	I				-5	-6	-6
A1	A2	A3	A4	A5	A6	A7	A8
			-500	-1
			-300		-1
			-450			-1
			---	---	---	---	---	---	---
								-1
		-5							-1
			-300		-1
			-450			-1
		---	---		---	---	---	---	---
		-5							-1
			-300		-1
		-6									-1
		---		---	---	---	---	---	---
		-5							-1
		-6								-1
		-6									-1

Т.к. компаненты псевдоплана являются неотрицательными, то является оптимальным опорным планом ЗЛП.

Задание№4(9)

Из четырех видов кормов необходимо составить рацион, в состав которого должно входить не менее В₁ единиц вещества А, В₂ единиц вещества В и В₃ единиц вещества С. Количество единиц вещества, содержащегося в одном килограмме каждого вида, указано в таблице. В ней же приведена цена одного кг. корма каждого вида.

1) Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющих минимальную стоимость.

Вещество	Количество единиц вещества, содержащегося в 1 кг корма каждого вида.
А	10,5
В	-			-
С		-
Цена 1 кг корма (руб.)

1)Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющих минимальную стоимость.

А	10,5
В	-			-
С		-

Прямая задача

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

S

I

А1

А2

А3

А4

А5

А6

А7

10,5

13

13

-16

-15

-17

-12

3940/13

21/2

-5/13

-7/13

180/13

10/13

1/13

-

440/13

20

-120/13

-12/13

1

-16

-25/13

-12

17/13

3709/13

58/13

11/8

-7/130

-21/400

180/13

10/13

1/13

18

22/13

-6/13

1/4

-3/65

1/20

-

-121/13

-8

7/65

4/5

-58/10

11/8

-1/2

-21/400

13/10

1/10

-

6/10

1/4

1/20

1

121/10

-8

1537/65

4/5

721/4

-91

-1/2

-131/400

1/10

1/5

3/2

12/5

2) Определите, все ли виды кормов входят в рацион, ценность дополнительной единицы каждого питательного вещества и его приоритете при решение задач уменьшения стоимости рациона.

В рацион входят только два вида вещества В и С. При увеличение вещества В на единицу вещества, то ценность увеличивается на 3/2. При увеличение вещества С на единицу вещества, то ценность увеличится на 2,4 единицы. Вещества В и С приоритетные, а вещество С не приоритетные.

3) Определите суммарную стоимостную оценку питательных веществ в единицы каждого корма, использование какого вида корма нерентабельно.

Т.к. основные переменные Х₁, Х₃ равны 0, то использование этих кормов нерентабельно.

4) Содержание, какого из питательных веществ превышает заданный минимальный уровень и насколько?

Вещество А превышает заданный минимальный уровень на 721/4 единицы.

5) Определите возможное максимальное уменьшение содержание каждого из питательных веществ в рационе, при котором структура рациона остается без изменений.

Пусть содержание 721/4+

Перейдем к пределам изменения А, получим

6) На сколько уменьшится стоимость рациона и используемое количество кормов при снижение минимального уровня потребления питательных веществ В до Z единиц.

7) Определите интервал изменения цен на каждый вид корма, при котором сохраняется структура рациона.

Полученное решение останется оптимальным при условие , то есть

решая эту систему получим

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

изменяется в пределах . Если от пределов перейдем к изменениям самой величины С₂, то получим: , таким образом, при изменение С₂ в пределах при этом

8) Возможно ли сделать выгодным использования корма, не вошедшего в рацион.

9) На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг нерентабельного вида корма.

При принудительном включение в рацион одного килограмма корма I, то стоимость рациона увеличится на 32 рубля.

При принудительном включение в рацион одного килограмма корма III, то стоимость рациона увеличится на 466 рубля.

При принудительном включение в рацион по одному килограмму корма I и III, то стоимость рациона увеличится на 498 рубля.

10) На сколько нужно снизить минимальный уровень потребления каждого из питательных веществ, чтобы уменьшить стоимость рациона на 10%?

Задача№5(9)

Решить задачи из домашнего задания 3 двухэтапным симплекс-методом без учета возможности перевыполнения плана.

Задание№3

Предприятию необходимо выпустить по плану продуции А₁ – 500 единиц, А₂ – 300, А₃ – 450. Каждый вид изделия может производиться на двух машинах. Полезное затрачиваемое время каждой машины 5000 мин. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Учитывать возможность перевыполнение плана.”

А₁=500 А₂=300 А₃=450

Канонический вид:

Т.к. не является К матрицей, то вводим 3 искусственные переменные U₁, U₂, U₃ в 3-е, 4-е и 5-е уравнения.

ВЗ имеет вид: