Решение задач по методам оптимизации
Подождите немного. Документ загружается.
- 11 -
Это условие определяет пределы изменения,
1
С
, при которых сохраняется структура оптимального
плана. Если от пределов изменения приращения
1
С
перейдем к изменениям самой величины С
1
, то
получим:
01515min15min
11
CC
, таким образом, при изменение С
1
в пределах
0
1
С
при этом
11
*
1875040121518
4
721
0 CCXf
2
С
изменяется в пределах
8
2
С
. Если от пределов
2
С
перейдем к изменениям самой величины
С
2
, то получим:
4812min12min
22
CC
, таким образом, при изменение С
2
в пределах
4
2
С
при этом
22
*
4075012401518
4
721
0 CCXf
8) Возможно ли сделать выгодным использования корма, не вошедшего в рацион.
9) На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг
нерентабельного вида корма.
При принудительном включение в рацион одного килограмма корма I, то стоимость рациона увеличится на
32 рубля.
При принудительном включение в рацион одного килограмма корма III, то стоимость рациона увеличится
на 466 рубля.
При принудительном включение в рацион по одному килограмму корма I и III, то стоимость рациона
увеличится на 498 рубля.
10) На сколько нужно снизить минимальный уровень потребления каждого из питательных веществ, чтобы
уменьшить стоимость рациона на 10%?
Задача№5(9)
Решить задачи из домашнего задания 3 двухэтапным симплекс-методом без учета возможности
перевыполнения плана.
Задание№3
Предприятию необходимо выпустить по плану продуции А
1
– 500 единиц, А
2
– 300, А
3
– 450. Каждый
вид изделия может производиться на двух машинах. Полезное затрачиваемое время каждой машины 5000
мин. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были
минимальными, если задана матрица затрат. Учитывать возможность перевыполнение плана.”
223
442
А
1
=500 А
2
=300 А
3
=450
500
5000223
5000442
665)(min
1
321
321
321
X
XXX
XXX
XXXXf
0;450;300
3,2,132
XXX
Канонический вид:
45000100
30000010
50000001
500010223
500001442
~
450;300
500
5000223
5000442
)665max(
32
1
2321
1321
321
A
XX
X
SXXX
SXXX
XXX
- 12 -
Т.к.
A
~
не является К матрицей, то вводим 3 искусственные переменные U
1
, U
2
, U
3
в 3-е, 4-е и 5-е
уравнения.
ВЗ имеет вид:
450
300
500
5000223
5000442
max)()(
53
42
31
2321
1321
543
UX
UX
UX
SXXX
SXXX
UUUmX
S I
)(S
N
)(S
nC
)(S
nX
0 0 0 0 0 -1 -1 -1
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 2500
2 5 0 5000 3 2 2 0 1 0 0 0 1666
3 6 -1 500 1 0 0 0 0 1 0 0 500
4 7 -1 300 0 1 0 0 0 0 1 0 ---
5 8 -1 450 0 0 1 0 0 0 0 1 ---
6
-1250 -1 -1 -1 0 0 0 0 0
1
1 4 0 4000 0 4 4 1 0 -2 0 0 1000
2 5 0 3500 0 2 2 0 1 -3 0 0 1750
3 1 0 500 1 0 0 0 0 1 0 0 ---
4 7 -1 300 0 1 0 0 0 0 1 0 300
5 8 -1 450 0 0 1 0 0 0 0 1 ---
6
-750 0 -1 -1 0 0 1 0 0
2
1 4 0 2800 0 0 4 1 0 -2 -4 0 700
2 5 0 2900 0 0 2 0 1 -3 -2 0 1450
3 1 0 500 1 0 0 0 0 1 0 0 ---
4 2 0 300 0 1 0 0 0 0 1 0 ---
5 8 -1 450 0 0 1 0 0 0 0 1 450
6
-450 0 0 -1 0 0 1 1 0
3
1 4 0 1000 0 0 0 1 0 -2 -4 -4
2 5 0 2000 0 0 0 0 1 -3 -2 -2
3 1 0 500 1 0 0 0 0 1 0 0
4 2 0 300 0 1 0 0 0 0 1 0
5 3 0 450 0 0 1 0 0 0 0 1
6
0 0 0 0 0 0 1 1 1
0)(min
)0;0;0;2000;1000;450;300;500(
*
*
mXf
mX
Задание№6(9)
Решить задачу целочисленного программирования методом ветвей и границ, учитывая цело численность
переменных.
21
30
634
62
)23max(
2
1
21
21
21
X
X
XX
XX
XX
Решение:
В качестве
)1(
0
Z
возьмем
)( Xf
в точке
)0;0(X
, т.е.
0
)1(
0
Z
.
1)
- 13 -
21
30
634
62
)23max(
2
1
21
21
21
X
X
XX
XX
XX
2) Нижняя граница
0
)1(
0
Z
.
)6;6(
)1(
X
, т.к. эти значения выходят за рамки ограничения, то они не являются решением.
Находим корни решения методом подстановки удовлетворяющие ограничениям по Х
1
и Х
2
, при котором
функция принимает максимальное значение.
По условию цело численности берем целые значения по Х
1
и Х
2
соответствующие ограничениям.
Ограничиваем по Х
1
.
1) Решаем при Х
1
=0, тогда Х
2
6, что выходит за рамки ограничения и вектор
)6;0(1 X
не является
решением данной функции.
2) Решаем при Х
1
=1, тогда Х
2
4, что выходит за рамки ограничения и вектор
)4;1(2 X
не является
решением данной функции.
3) Решаем при Х
1
=2, тогда Х
2
2, что удовлетворяет ограничениям функции и вектор
)2;2(3 X
является решением данной функции.
102223)( Xf
4) Решаем при Х
1
=3, тогда Х
2
=0, что выходит за рамки ограничений и вектор
)0;3(4 X
не является
решением данной функции.
Ограничиваем по Х
2
.
5) Решаем при Х
2
=1, тогда Х
1
5,2
при ограничениях
30
1
Х
, то Х
1
может принимать значение
Х
1
=3, тогда вектор
)1;3(Х
. При этом функция принимает значения
111233)(max Xf
.
6) Решаем при Х
2
=2, тогда Х
1
2. То возникают сразу два вектора: а) вектор
)2;2(Х
, уже
существует; б)
)2;3(Х
, где
132233)(
*
Xf
Это значение функции является наиболее максимальным.
Решением исходной задачи является
)2;3(;13)(
**
XXf
Задание № 7(9)
Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных
условиях: из А
1
в В
2
и изА
2
в В
5
перевозки не могут быть осуществлены, а из А
2
в В
4
будет завезено 60
единиц груза.
Пункты
отправления
Пункты назначения
Запасы
В1 В
2
В3 В
4
В5
А
1
А
2
А
3
1
6
8
2
3
2
3
4
1
1
5
9
4
2
3
180
220
100
Потребности 120 80 160 90 50
510
500
Пункты назначения Запасы
- 14 -
Пункты
отправления
В1 В
2
В3 В
4
В5
А
1
1 2 3 1 4
180
120 0 15 45
А
2
6 3 4 5 2
230
80 105 45 0
А
3
8 2 1 9 3
100
40 50
Потребности 120 80 160 90 50
510
500
10 единиц останется у третьего поставщика.
Полученный план является оптимальным:
1285)(
50...40......
04510580...
...45150120
**
XfиX
1300150225454042045240120)(
*
Xf
Задание№8(10)
Завод строительных материалов по договору с мостостроительной организацией должен поставить
следующие партии строительных конструкций (ферм): в сентябре – 30, октябре – 20, ноябре – 20, декабре –
10. Производство каждой фермы обходится в 1000 руб.., а издержки ее хранения равны: в сентябре и
октябре – 100 руб., ноябре и декабре – 200 руб. Затраты на запуск производства ферм в сентябре и октябре –
1000 руб., в ноябре – 0 руб., в декабре – 2000 руб. Ограничения на производственные мощности и объем
складских помещений таковы:
20,40
КК
Х
, начальный и конечный объем запасов Х
0
=Х
4
=0.
Построить оптимальный план производства, если объем производства кратен 10.
Поставки:
Сентябрь d
1
=30; Октябрь d
2
=20; Ноябрь d
3
=20; Декабрь d
4
=10 N=4
Затраты на производство:
Сентябрь и Октябрь:
10001000)(
2,1
КК
Ноябрь:
01000)(
3
КК
Декабрь:
20001000)(
4
КК
Затраты на хранение:
Сентябрь и Октябрь:
КК
ХХ 100)(
2,1
Ноябрь и Декабрь:
КК
ХХ 200)(
2,1
К=1…4
)()(),(
1 KKKRR
XXg
)4...1(
1
KdХХ
RККК
Уравнение Беллмана:
),(min()(
;4..2
))),,((),(min()(
1011
*
1
1
*
11
XqXF
гдеK
XTFXqXF
RK
KKKKKKKK
Значения для среднего уровня запасов:
)
2
(200200)(
)
2
(100100)(
222
4,3
2,1
1
К
KKRK
К
KKRK
К
KK
К
RКК
К
КК
dXXX
dXXX
dXdХХХ
)4..1(40;0
0
100095010010010001000
2
100
100100
10001000)
2
(100),(
12,1
KdX
dX
dXdX
dXXq
КKKК
KКK
КKKК
К
KK
К
К
KKКK
1 этап условной оптимизации
- 15 -
11
1111
*
1
0
)1000950100100min()(
1
dX
dXXF
К
из уравнения состояния и условий задачи (Х
0
=0; d
1
=30)
11101
300
dХХ
, откуда
30)(
11
*
1
ХХ
10002850095030001001000)30(95030100100)(
11111
*
1
XXXXXF
200
}565001001150min{
)}32500210001050105095010002000100min{(
}32500)20(1050950100020100100min{
)},((1000950100100min{()(
0
2
325001050
22
22
2222
2222
21
*
12222
*
2
222
1
X
X
XX
XX
XTFdXXF
dX
K
X
Т.к. функция убывает с ростом
2
, она достигает
max
при
20)(
222
XX
и равна
545009505650020001001150)(
2222
*
2
XXXXF
76500110077500100050115077500)20(501150
20)(
}77500501150min{
}54500190009509509004000200min{
}54500)20(95090020200200min{
))};((900200200min{
))};((1000100200200min{)(
1000)
2
(200),(
3
33333
333
33
3333
3333
32
*
2333
32
*
3
*
3
13
2
XXXXX
XXпри
X
XX
XX
XTFdX
XTFdXXF
dXXq
K
KKKK
K
K
KKKK
100
}915002001300min{
}76500)10(11002000100010010200200min{
))},((20001000100200200min{)(
4
44
44
44444
43
*
344444
*
4
X
X
XX
XTFdXXF
K
По условию задачи
.0,40
44
X
40;1000
44
Откуда
10;100
44
Тогда:
895001300}915002001300min{)(
4444
*
4
XXXF
2 этап – безусловная оптимизация.
К=4 Состояние Х
4
=0 – единственное, поэтому
0
4
X
- элемент оптимальной траектории,
10
*
4
- последний элемент оптимальной стратегии и
89500)(
*
4
*
4
XF
К=3
10100
4
*
4
*
4
*
3
dXX
20
20200)(
*
3
*
3
*
3
*
3
X
К=2
020200
3
*
3
*
3
*
2
dXX
2020020)(
*
2
*
2
*
2
*
2
XX
К=1
020200
2
*
2
*
2
*
1
dXX
3030030)(
*
1
*
1
*
1
*
1
XX
030300
2
*
2
*
1
*
0
dXX
Т.е., Оптимальная стратегия пополнения запасов
)10;20;20;30(
,
min
расходы на хранение
и пополнение запасов 89500