Решение задач по методам оптимизации
Подождите немного. Документ загружается.
- 1 -
Задание№1(9)
Металлургическому заводу требуется уголь с содержанием фосфора не более 0, 3% и с долей зольных
примесей не более 3,25%. Завод закупает 3 сорта угля А, В, С с известным содержанием примесей. В какой
пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на
содержание примесей и имела минимальную цену?
Сорт угля
Содержание(%)
Цена 1т (руб.)
Фосфора Золы
А 0,06 2,0 30
В 0,04 4,0 30
С 0,02 3,0 45
Решение:
Введем следующие обозначения:
Х
1
– содержание угля А в смеси;
Х
2
– содержание угля В в смеси;
Х
3
– содержание угля С в смеси;
Ограничения имеют вид:
25,30,30,40,2
3,002,004,006,0
321
321
ХХХ
ХХХ
Окончательный вид:
321
453030)(min XXXXf
Приведем к каноническому виду:
21321
2321
1321
00453030)(min
25,30,30,40,2
3,002,004,006,0
SSXXXXf
SXXX
SXXX
Решим симплекс-методом:
S i
N
nС
bnX
30 30 45 0 0
A
1
A
2
A
3
A
4
A
5
0
1 4 0 0,3 0,06 0,04 0,02 1 0 15
2 5 0 3,25 2,0 4,0 3,0 0 1 1
0)( Xf
-30 -30 -45 0 0 K=3, l=2
1
1 4 0 21/200 7/150 1/75 0 1 -1/150
2 3 45 39/4 2/3 4/3 1 0 1/3
75,438f
0 30 0 0 45/3
75,43800
200
21
045
4
39
300300)(min
)0;200/21;4/39;0;0(
)3;4(
)4/39;200/21(
*
*
)1(
)1(
Xf
X
N
X
n
Задание№2(9)
- 2 -
Предприятие производит три вида продукции А
1
, А
2
, А
3
, используя сырье двух видов: В
1
и В
2
.
Известны затраты сырья i-го вида на единицу изделия j-го вида a
ij
, количество сырья каждого вида b
i
(i=1,2),
а так же прибыль полученная от единицы изделия j-го вида с
j
(j=1,2,3).
(1) Сколько изделий каждого вида необходимо произвести, что бы получить:
1) max прибыли;
2) max товарной продукции.
233
900
1300
223
122
А
1
А
2
А
3
Сырье
В
1
2 2 1 1300
В
2
3 2 2 900
Прибыль 3 3 2
1) Найти максимум прибыли?
321
321
321
233)(max
900223
130022
XXXXf
ХХХ
ХХХ
Приводим к каноническому виду:
21321
2321
1321
00233)(max
900223
130022
SSXXXXf
SXXX
SХХХ
90010223
130001122
)0(
K
)0;0(
)5;4(
)900;1300(
)0(
)0(
)0(
nC
N
nX
S i
N
nС
bnX
3 3 2 0 0
A
1
A
2
A
3
A
4
A
5
0
1 4 0 1300 2 2 1 1 0 650
2 5 0 900 3 2 2 0 1 300
0)( xf
-3 -3 -2 0 0 K=1, l=2
1
1 4 0 700 0 2/3 -1/3 1 2/3 1050
2 1 3 300 1 2/3 2/3 0 1/3 900
900)( xf
0 -1 0 0 1 K=2, l=2
2
1 4 0 400 -1 0 -1 1 1/3
2 2 3 450 3/2 1 1 0 1/2
1350)( xf
3/2 0 1 0 3/2
135000040020345030)(
)0;400;0;450;0(
)3;0(
)2;4(
)450;400(
*
)2(
)2(
)2(
Xf
X
nC
N
nX
2) Найти максимум товарной продукции:
- 3 -
321
321
321
)(max
900223
130022
XXXXf
XXX
XXX
Приведем к каноническому виду:
21321
2321
1321
00)(max
900223
130022
SSXXXXf
SXXX
SXXX
S i
N
nС
bnX
1 1 1 0 0
A
1
A
2
A
3
A
4
A
5
0
1 4 0 1300 2 2 1 1 0 650
2 5 0 900 3 2 2 0 1 300
0)( xf
-1 -1 -1 0 0 K=1, l=2
1
1 4 0 700 0 2/3 -1/3 1 2/3 1050
2 1 1 300 1 2/3 2/3 0 1/3 450
900)( xf
0 -1/3 -1/3 0 1/3 K=2, l=2
2
1 4 0 400 -1 0 -1 1 1/3
2 2 1 450 3/2 1 1 0 1/2
1350)( xf
1/2 0 0 0 ½
45000040010145010)(max
)0;400;0;450;0(
)2;4(
)450;400(
*
*
)2(
)2(
Xf
X
N
nX
(2) Решить задачу при дополнительных условиях: предприятия платят за хранение единицы сырья В
1
и В
2
соответственно 0,1 и 0,3 денежных единицы.
1) Найти max прибыли?
321
321
321
233)(max
3,0900223
1,0130022
XXXXf
XXX
XXX
Приведем к каноническому виду:
21321
1321
1321
00233)(max
2703,0900223
1301,013002
SSXXXXf
SXXX
SXXX
2
S i
N
nС
bnX
3 3 2 0 0
A
1
A
2
A
3
A
4
A
5
0
1 4 0 130 2 2 1 1 0 65
2 5 0 270 3 2 2 0 1 90
0)( xf
-3 -3 -2 0 0 K=1, l=1
1
1 1 3 65 1 1 ½ 1/2 0 130
2 5 0 75 0 -1 ½ -3/2 1 150
195)( xf
0 0 -1/2 3/2 0 K=3, l=1
2
1 3 2 130 2 2 1 1 0
2 5 0 10 -1 -2 0 -2 1
- 4 -
260)( xf
1 1 0 2 0
2601000013020000)(max
)10;0;130;0;0(
)5;3(
)0;2(
)10;130(
)2(
)2(
)2(
Xf
X
N
nC
nX
2) Найти MAX продукции:
321
321
321
)(max
3,0900223
1,0130022
XXXXf
XXX
XXX
Приведем к каноническому виду:
21321
2321
1321
00)(max
270223
13022
SSXXXXf
SXXX
SXXX
S i
N
nС
bnX
1 1 1 0 0
A
1
A
2
A
3
A
4
A
5
0
1 4 0 130 2 2 1 1 0 65
2 5 0 270 3 2 2 0 1 90
0)( xf
-1 -1 -1 0 0 K=1, l=1
1
1 1 1 65 1 1 ½ 1/2 0 130
2 5 0 75 0 -1 ½ -3/2 1 150
65)( xf
0 0 -1/2 1/2 0 K=3, l=1
2
1 3 1 130 2 2 1 1 0
2 5 0 10 -1 -2 0 -2 1
130)( xf
1 1 0 1 0
)0;1(
)10;130(
)5;3(
)2(
)2(
)2(
nC
nX
N
1301000013010000)(max
)10;0;130;0;0(
*
*
Xf
X
(3) Решить задачу при условии, что задан план выпуска изделий. При решении учитывать
возможность перевыполнения плана.
200100100
1) Найти max прибыли:
321
321
321
3
2
1
233)(max
900223
130022
200
100
100
XXXXf
XXX
XXX
X
X
X
Приведем к каноническому виду:
- 5 -
54321321
2321
1321
53
42
31
00000233)(max
900223
130022
200
100
100
SSSSSXXXXf
SXXX
SXXX
SX
SX
SX
S I
N
nС
bnX
3 3 2 0 0 0 0 0
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
0
1 4 0 1300 2 2 1 1 0 0 0 0 650
2 5 0 900 3 2 2 0 1 0 0 0 300
3 6 0 -100 -1 0 0 0 0 1 0 0 100
4 7 0 -100 0 -1 0 0 0 0 1 0 ---
5 8 0 -200 0 0 -1 0 0 0 0 1 ---
0)( xf
-3 -3 -2 0 0 0 0 0 K=1, l=3
1
1 4 0 1100 0 2 1 1 0 2 0 0 550
2 5 0 600 0 2 2 0 1 3 0 0 300
3 1 3 -100 1 0 0 0 0 -1 0 0 ---
4 7 0 -100 0 -1 0 0 0 0 1 0 100
5 8 0 -200 0 0 -1 0 0 0 0 1 ---
300)( xf
0 -3 -2 0 0 3 0 0 K=2, l=4
2
1 4 0 900 0 0 1 1 0 2 2 0 900
2 5 0 400 0 0 2 0 1 3 2 0 200
3 1 3 100 1 0 0 0 0 -1 0 0 ---
4 2 3 100 0 1 0 0 0 0 -1 0 ---
5 8 0 200 0 0 -1 0 0 0 0 1 200
600)( xf
0 0 -2 0 0 0 0 0 K=3, l=5
3
1 4 0 700 0 0 0 1 0 2 2 1
2 5 0 0 0 0 0 0 1 3 2 2
3 1 3 100 1 0 0 0 0 -1 0 0
4 2 3 100 0 1 0 0 0 0 -1 0
5 3 2 200 0 0 1 0 0 0 0 -1
1000)( xf
0 0 0 0 0 3 2 2
1000000000007000200210031003)(max
)0;0;0;0;700;200;100;100(
)200;100;100;0;700(
)3;2;1;5;4(
*
*
)3(
)3(
Xf
X
X
N
N
2) Найти max продукции:
200
100
100
900223
130022
)(max
3
2
1
321
321
321
X
X
X
XXX
XXX
XXXXf
Приведем к каноническому виду:
- 6 -
200
100
100
900223
130022
00000233)(max
53
42
31
2321
1321
54321321
SX
SX
SX
SXXX
SXXX
SSSSSXXXXf
S I
N
nС
bnX
1 1 1 0 0 0 0 0
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
0
1 4 0 1300 2 2 1 1 0 0 0 0 650
2 5 0 900 3 2 2 0 1 0 0 0 300
3 6 0 -100 -1 0 0 0 0 1 0 0 100
4 7 0 -100 0 -1 0 0 0 0 1 0 ---
5 8 0 -200 0 0 -1 0 0 0 0 1 ---
0)( xf
-1 -1 -1 0 0 0 0 0 K=1, l=3
1
1 4 0 1100 0 2 1 1 0 2 0 0 550
2 5 0 600 0 2 2 0 1 3 0 0 300
3 1 1 100 1 0 0 0 0 -1 0 0 ---
4 7 0 -100 0 -1 0 0 0 0 1 0 100
5 8 0 -200 0 0 -1 0 0 0 0 1 ---
100)( xf
0 -1 -1 0 0 1 0 0 K=2, l=4
2
1 4 0 900 0 0 1 1 0 2 2 0 900
2 5 0 400 0 0 2 0 1 3 2 0 200
3 1 1 100 1 0 0 0 0 -1 0 0 ---
4 2 1 100 0 1 0 0 0 0 -1 0 ---
5 8 0 200 0 0 -1 0 0 0 0 1 200
200)( xf
0 0 -2 0 0 1 1 0 K=3, l=5
3
1 4 0 700 0 0 0 1 0 2 2 1
2 5 0 0 0 0 0 0 1 3 2 2
3 1 1 100 1 0 0 0 0 -1 0 0
4 2 1 100 0 1 0 0 0 0 -1 0
5 3 1 200 0 0 1 0 0 0 0 -1
400)( xf
0 0 0 0 0 1 1 1
400000000007000200110011001)(max
)0;0;0;0;700;200;100;100(
)200;100;100;0;700(
)3;2;1;5;4(
*
*
*
)3(
Xf
X
X
N
N
Задание№3
Предприятию необходимо выпустить по плану продуции А
1
– 500 единиц, А
2
– 300, А
3
– 450. Каждый
вид изделия может производиться на двух машинах. Полезное затрачиваемое время каждой машины 5000
мин. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были
минимальными, если задана матрица затрат. Учитывать возможность перевыполнение плана.
223
442
Решение:
- 7 -
0
450
300
500
5000223
5000442
665)(min
450
300
500
3,2,1
3
2
1
321
321
321
3
2
1
X
X
X
X
XXX
XXX
XXXXf
А
А
А
450
300
500
5000223
5000442
)665max(
53
42
31
2321
1321
321
SX
SX
SX
SXXX
SXXX
XXX
или
450
300
500
5000223
5000442
)665max(
53
42
31
2321
1321
321
SX
SX
SX
SXXX
SXXX
XXX
45010000100
30001000010
50000100001
500000010223
500000001442
~
A
S I
)(S
N
)(S
nC
)(S
nX
-5 -6 -6 0 0 0 0 0
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
0
1 4 0 5000 2 4 4 1 0 0 0 0
2 5 0 5000 3 2 2 0 1 0 0 0
3 6 0 -500 -1 0 0 0 0 1 0 0
4 7 0 -300 0 -1 0 0 0 0 1 0
5 8 0 -450 0 0 -1 0 0 0 0 1
6
0)( Xf
5 6 6 0 0 0 0 0
7
5 --- --- --- --- --- --- ---
1 1 4 0 4000 0 4 4 1 0 0 0 0
- 8 -
2 5 0 3500 0 2 2 0 -1 3 0 0
3 1 -5 500 1 0 0 0 0 -1 0 0
4 7 0 -300 0 -1 0 0 0 0 1 0
5 8 0 -450 0 0 -1 0 0 0 0 1
6
2500)( Xf
0 6 6 0 0 5 0 0
7
--- --- 6 --- --- --- --- ---
2
1 4 0 2200 0 4 0 1 0 0 0 4
2 5 0 2600 0 2 0 0 1 3 0 2
3 1 -5 500 1 0 0 0 0 -1 0 0
4 7 0 -300 0 -1 0 0 0 0 1 0
5 3 -6 450 0 0 1 0 0 0 0 -1
6
5200)( Xf
0 6 0 0 0 5 0 6
7
--- 6 --- --- --- --- --- ---
3
1 4 0 1000 0 0 0 1 0 0 4 4
2 5 0 2000 0 0 0 0 1 3 2 2
3 1 -5 500 1 0 0 0 0 -1 0 0
4 2 -6 300 0 1 0 0 0 0 -1 0
5 3 -6 450 0 0 1 0 0 0 0 -1
6
7000)( Xf
0 0 0 0 0 5 6 6
Т.к. компаненты псевдоплана
)450;300;500;2000;1000(
)3(
nX
являются
неотрицательными, то
)3(
nX
является оптимальным опорным планом ЗЛП.
7000)(min
)0;0;0;2000;1000;450;300;500(
*
*
Xf
X
Задание№4(9)
Из четырех видов кормов необходимо составить рацион, в состав которого должно входить не менее
В
1
единиц вещества А, В
2
единиц вещества В и В
3
единиц вещества С. Количество единиц вещества,
содержащегося в одном килограмме каждого вида, указано в таблице. В ней же приведена цена одного кг.
корма каждого вида.
1) Составить рацион, содержащий не менее нужного количества указанных питательных веществ и
имеющих минимальную стоимость.
Вещество Количество единиц вещества, содержащегося в 1 кг корма каждого вида.
1 2 3 4
А 10,5 5 7 4
В - 10 13 -
С 20 - 12 5
Цена 1 кг корма (руб.) 16 15 12 17
6);200,180,400( ZB
1) Составить рацион, содержащий не менее нужного количества указанных питательных веществ и
имеющих минимальную стоимость.
1 2 3 4
B
А 10,5 5 7 4 400
В - 10 13 - 180
С 20 - 12 5 200
16 15 12 17
Прямая задача
- 9 -
0;0
20051220
1801310
4004755,10
)00017121516min(
3,2,13,2,1
3431
232
14321
3214321
SX
SXXX
SXX
SXXXX
SSSXXXX
Двойственная задача
16205,1016205,10
)200180400max()200180400max(
43131
7654321321
YYYYY
YYYYYYYYYY
12541254
17121371712137
1510515105
73131
6321321
52121
YYYYY
YYYYYYY
YYYYY
S I
N
nС
bnX
16 15 17 12 0 0 0
А
1
А
2
А
3
А
4
А
5
А
6
А
7
0
1 5 0 400 10,5 5 7 4 1 0 0 57
2 6 0 180 0 10 13 0 0 1 0 13
3 7 0 200 20 0 12 5 0 0 1 16
0f
-16 -15 -17 -12 0 0 0
1
1 5 0 3940/13 21/2 -5/13 0 4 1 -7/13 0 28
2 3 17 180/13 0 10/13 1 0 0 1/13 0 -
3 8 0 440/13 20 -120/13 0 5 0 -12/13 1 1
13/3060f
-16 -25/13 0 -12 0 17/13 0
2
1 5 0 3709/13 0 58/13 0 11/8 1 -7/130 -21/400 63
2 3 17 180/13 0 10/13 1 0 0 1/13 0 18
3 1 16 22/13 1 -6/13 0 1/4 0 -3/65 1/20 -
13/3412f
0 -121/13 0 -8 0 7/65 4/5
3
1 5 0 205 0 0 -58/10 11/8 1 -1/2 -21/400 149
2 2 15 18 0 1 13/10 0 0 1/10 0 -
3 1 16 10 1 0 6/10 1/4 0 0 1/20 1
430f
0 0 121/10 -8 0 1537/65 4/5
4
1 5 0 721/4 0 0 -91 0 1 -1/2 -131/400
2 2 15 18 0 1 13 0 0 1/10 0
3 4 12 40 4 0 24 1 0 0 1/5
750f
32 0 466 0 0 3/2 12/5
75048027000000
4
721
12400171815016)(min
)0;0;4/721;40;0;18;0();4;2;5();40;18;4/721(
*
*)4()4(
Xf
XNnX
- 10 -
)(max)(min
0
466
0
32
512
23
0
0
0
4721
40
0
18
0
750480270512200231800400)(
5
12
;
2
3
;0)05/12;010/15;00();;(
5
12
;
2
3
;0
5/100
010/10
400/1312/11
)12;15;0(
**
*
7
)4(
76
)4(
65
)4(
5
*
1
4
)4(
YgXf
YX
Yg
CCCY
BnCY
2) Определите, все ли виды кормов входят в рацион, ценность дополнительной единицы каждого
питательного вещества и его приоритете при решение задач уменьшения стоимости рациона.
В рацион входят только два вида вещества В и С. При увеличение вещества В на единицу вещества,
то ценность увеличивается на 3/2. При увеличение вещества С на единицу вещества, то ценность увеличится
на 2,4 единицы. Вещества В и С приоритетные, а вещество С не приоритетные.
3) Определите суммарную стоимостную оценку питательных веществ в единицы каждого корма,
использование какого вида корма нерентабельно.
Т.к. основные переменные Х
1
, Х
3
равны 0, то использование этих кормов нерентабельно.
4) Содержание, какого из питательных веществ превышает заданный минимальный уровень и насколько?
Вещество А превышает заданный минимальный уровень на 721/4 единицы.
5) Определите возможное максимальное уменьшение содержание каждого из питательных веществ в
рационе, при котором структура рациона остается без изменений.
Пусть содержание 721/4+
А
5,360180
0040
010/118
02/14/721
040
10/118
2/14/721
0
10/1
2/1
40
18
4/721
4
A
A
A
A
A
A
A
Ab
Перейдем к пределам изменения А, получим
75,5404/1 А
6) На сколько уменьшится стоимость рациона и используемое количество кормов при снижение
минимального уровня потребления питательных веществ В до Z единиц.
7) Определите интервал изменения цен на каждый вид корма, при котором сохраняется структура рациона.
.5/12
5/1
0
400/131
,
12
15
0
;10/12/3
0
10/1
2/1
,
12
15
0
;0;0
;13466
24
13
91
,
12
15
0
;0;32
4
0
0
,
12
15
0
1
4
711
4
6
4
5
4
4
11
4
3
4
21
4
1
ССС
ССС
Полученное решение
X
останется оптимальным при условие
7,1;0
4
j
J
, то есть
010/12/3
013466
1
1
С
С
решая эту систему получим
15
1
С