Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В результате смешивания этих четырех компонентов в разных пропорциях образуется три сорта авиационного бензина: бензин А (а1:а2:а3:а4), бензин В (b1:b2:b3:b4) и бензин С (с1:с2:с3:с4).

Стоимость 1 тыс. л. бензина каждого сорта равна y1 руб., y2 руб. и y3 руб.

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

№ вар.	x1	x2	x3	x4	y1	y2	y3	а1	а2	а3	а4	b1	b2
1	400	250	350	100	120	100	150	2	3	5	2	3	1

№ вар.	b1	b2	c1	c2	c3	c4
1	2	1	2	2	1	3

Решение:

Составим математическую модель задачи.

Обозначим через t1 количество бензина А;

через t2 количество бензина В;

через t3 количество бензина С.

Тогда, целевая функция будет

L=y1t1+ y2t2+ y3t3=120t1+100t2+150t3 →max

Система ограничений:

Приведем систему ограничений к виду основной задачи линейного программирования (введем новые переменные t4 , t5 ,t6 ,t7, которые входят в целевую функцию с нулевыми коэффициентами):

Выберем t1 , t2 ,t3 свободными переменными, а t4 , t5 ,t6 ,t7 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:

L=0-(-120t1-100t2-150t3)

Составим симплекс-таблицу.

Это решение опорное, т.к. все свободные члены положительны.

Т. к. все коэффициенты в целевой функции отрицательные, то можно взять любой столбец разрешающим (пусть t1). Выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это t7)

	b		t1		t2		t3
L	0		-120		-100		-150
L		6000		60		60		180
t4	400		2		3		2		400/2=200
t4		-100		-1		-1		-3
t5	250		3		1		2		250/3=83,3
t5		-150		-1,5		-1,5		-4,5
t6	350		5		2		1		350/5=70
t6		-250		-2,5		-2,5		-7,5
t7	100		2		1		3		100/2=50
t7		50		0,5		0,5		1,5

Далее меняем t2 и t1 .

	b		t7		t2		t3
L	6000		60		-40		30
L		4000		40		80		120
t4	300		-1		2		-1		300/2=150
t4		-200		-2		-4		-6
t5	100		-1,5		-0,5		-2,5
t5		50		0,5		1		-4,5
t6	50		-2,5		-0,5		-6,5
t6		50		0,5		1		-7,5
t1	50		0,5		0,5		1,5		50/0,5=100
t1		100		1		2		1,5

	b	t7	t1	t3
L	10000	100	80	150
L
t4	100	-3	-4	-7
t4
t5	150	-1	1	-1
t5
t6	100	-2	1	-5
t6
t2	100	1	2	3
t2

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

Таким образом, t1 = t3 =0; t2=100; L=10000.

Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.

ОТВЕТ: для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.

2. Задача 2

Условие:

С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ³ £B,

где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T ,

XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).

№ вар.	с1		с2		с3		с4		с5		с6		b1		b2		b3		Знаки ограничений							a11		a12		a13	a14
																			1		2		3
34	3		3		1		1		0		0		4		4		15		=		=		=			2		0		3	1
№ вар.		a15		a16		a21		a22		a23		a24		a25		a26		a31		a32		a33		a34	a35		a36		Тип экстрем.
		1		2		3		4		5		6		7		8		9		10		11		12	13		14		15
1. 34		0		0		1		0		–1		2		3		0		3		3		6		3	6		0		max

Решение:

Исходная система:

Целевая функция Q= x1+3x2+x3+3x5.

Пусть х3, х4 – свободные переменные, х1, х2, х5 – базисные.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

Q=9 - (9/2x3-1/2x4)

Составим симплекс-таблицу:

	b		x3		x4
Q	9		9/2		-1/2
Q		2/3		-5/6		1
x1	2		3/2		1/2		2/0,5=4
x1		-2/3		5/6		-1
x2	7/3		4/3		0
x2		0		0		0
x5	2/3		-5/6		1/2		2/3 : 1/2=4/3
x5		4/3		-5/3		2

Это опорное решение, т.к. свободные члены положительны.

Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это х5).

	b	x3	x5
Q	29/3	11/3	1
Q
x1	4/3	2/3	-1
x1
x2	7/3	4/3	0
x2
x4	4/3	-5/3	2
x4

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

Т. о. Q=29/3

x3=x5=0; x1=4/3; x2=7/3; x4=4/3.

ОТВЕТ: Q=29/3ж

x3=x5=0; x1=4/3; x2=7/3; x4=4/3.

3. Задача 3

Условие:

Решение транспортной задачи:

1. Записать условия задачи в матричной форме.

2. Определить опорный план задачи.

3. Определить оптимальный план задачи.

4. Проверить решение задачи методом потенциалов.

№вар.	а1	а2	а3	b1	b2	b3	b4	b5	с11	с12	с13
14	90	50	30	15	45	45	50	15	45	60	40
с14	с15	с21	с22	с23	с24	с25	с31	с32	с33	с34	с35
60	95	35	30	55	30	40	50	40	35	30	100

Решение:

Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:

	B1		B2		B3		B4		B5		a
A1		45		60		40		60		95	90
A1	15		45		30						90
A2		35		30		55		30		40	50
A2					15		35				50
A3		50		40		35		30		100	30
A3							15		15		30
b	15		45		45		50		15		170

Это будет опорный план.

Количество заполненных ячеек r=m+n-1=6.

1) Рассмотрим цикл (1,2)-(1,3)-(2,3)-(3,2):

с1,2+с2,3>c1.3+c3.2 (60+55>30+40)

Количество единиц товара, перемещаемых по циклу: min (с1,2 ; с2,3)=15

2) Рассмотрим цикл (2,4)-(2,5)-(3,5)-(3,4):

c2,4+с3,5>c2.5+c3.4 (30+40>30+100)

Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15

В результате получится следующий план:

	B1		B2		B3		B4		B5		a
A1		45		60		40		60		95	90
A1	15		30		45						90
A2		35		30		55		30		40	50
A2			15				20		15		50
A3		50		40		35		30		100	30
A3							30				30
b	15		45		45		50		15		170

Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение.

Проверим методом потенциалов:

Примем α1=0, тогда βj = cij – αi (для заполненных клеток).

Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0

Очевидно, что Δij =0 для заполненных клеток.

В результате получим следующую таблицу:

	β1=45		β2=60		β3=40		β4=60		β5=70
α1=0		45		60		40		60		95	90
α1=0	15		30		45		0		+		90
α2= -30		35		30		55		30		40	50
α2= -30	+		15		+		20		15		50
α3= -30		50		40		35		30		100	30
α3= -30	+		+		+		30		+		30
	15		45		45		50		15		170

Δ1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки.

Страницы: 1, 2