Файл: Говар В.М. Математическое программирование учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.06.2024
Просмотров: 129
Скачиваний: 0
Оптимальный переход от одной точки плоскости к другой, приводящий к атим наименьшим затратам, отмечается в кандом случае стрелкой, выходящей из квадратика. Стрелка указывает на направле ние, по которому мы должны Двигаться из даннсѵ. точки в другую, если на предыдущем шаге планируемая система оказалась в этой точке.
Перейдем к планированию предпоследнего (Двенадцатого) шага. Для атого необходимо рассмотреть *>се допустимые результаты преды дущего (одиннадцатого)шага. После атого шага мы можем оказаться только в одной из точек Ъ^, или Др отмеченных на рисунке (13.3). 7.3 каждой такой точки нужно найти опт'лкальныи переход в точку M к соответствующие «тому пути минимальные затраты.
3.' |
1 |
• «л |
/VI |
|
|
|
і2 |
|
]iù |
-^*.*-—I |
|2 I С, |
|
Рис. |
13.3 |
|
|
|
|
|
Если |
планируемая |
система придет в |
точку |
Др то |
вопрос о мини |
||
муме суммарных затрат |
на |
переход в конечное |
состояние M ( х т , |
х^) |
|||
решается однозначно, то есть система переходит по вертикали из |
|||||||
течки Д[ |
в точку Ст , а |
затем в точку M (Д|—* Cj —> |
M), при |
этом |
|||
суммарные |
затраты LI + |
12 |
= 23 ден.зн. |
л и затраты |
записываем в |
||
квдратике при точке Дт |
и стрелкой указываем на единственно юозмож- |
||||||
ный xi данном случае оптимальный путь. |
|
|
|
|
|||
Аналогично решается вопрос в случае прихода системы в точку
В^. В этом случае система переходит по |
горизонтали |
из точки В 2 |
||||
точку Ър а затем л точку M (В2 |
—> Bj |
—#-М), при |
атом суммарные |
|||
затраты IV + 15 = 32 ден.ед. |
|
|
|
|
||
Из точки С2 л конечное состояние можно перейти Двумя спосо |
||||||
бами: (С2 —» |
B j — * M) и ( ^ - ' ' ' І |
~'М) . В перлом случае |
затраты |
|||
14 + 15 = 29 |
ден . ед . , а |
ло лтором: 14 + |
12 = 2ь ден.ед. |
Выбираем |
||
(С2 —* Cj — * |
M), то есть |
переход, |
которому соответствуют |
наимень |
||
шие затраты. Записываем |
их л квадратики |
при точке С2 и стрелкой |
||||
отмечаем оптимальный переход на данном |
ьтапе. |
|
|
|||
Диалогичным образом осуществляем переход от каждой узловой точки к точке Сверху вниз и справа налево (ст конца процесса к началу). Поступая таким образом,для каждой узловой точки таблицы
(13.II) находим оптимальные переходы |
на |
следующих шагах, |
то есть |
|
переходы, ведущие планируемую систему |
в |
конечную точку |
M с |
наи |
меньшими затратами, а Квадратиках при |
соответствующих |
точках |
||
записываем ати наименьшие затраты. Чтобы найти из каждой узловой точки оптимальный следующий шаг, нужно сравнить два возможных пути из утой точки: вверх и лправО, и для каждого из них найти сумму затрат на данном шаге и наименьших затрат на оптимальном продолжении, уже построенном из той точки, в которую направлен конец стрелки. Из зтих Двух возможных переходов выбирается тот, для которого сумма затрат меньшая; в том случае, если сумма затрат равны, выбирается любой из путей.
Таким образом, из каждой узловой точки таблицы (13.12) |
про |
|
водится стрелка, указывающая огтшальный путь из этой точки |
в |
|
соседнюю, а в квадратике |
записываются затраты на переход, начиная |
|
с этой точки до конечного |
состояния системы в точке M ( х т , |
х ? ) . |
Таблица 13.12
Уют процесс нахождения оптимальных переходов из любой узло
вой точки в точку M заканчивается при переходе в |
точку |
0, |
соответ |
||
ствующую начальному |
состоянию системы. |
|
|
|
|
Из |
этой точки, |
как и из любой другой узловой |
точки, |
ведет |
|
стрелка, |
указывающая |
на оптимальное перемещение из точки 0 в точку |
|||
М. После зтого можно построить оптимальную стратегию, |
перемещаясь |
||||
по стрелкам, уже от |
йачала процесса к концу. |
|
|
|
|
В таблице (13.12) помещено решение исследуемо.і задачи и стрелками показан оптимальный путь перехода из начального состо яния (точки 0) в конечное состояние планируемой системы (течку М), при атом от каждой точки перехода имеется оптимальное продолже
ние, указанное стрелками. Наименьшие суммарные затраты при опти |
||
мальном переходе планируемой системы из начального состояния в |
||
конечное, равные |
І4ь ден ед . , записаны в квадратике у точки О, |
|
действительно, |
|
|
10 + 8 + 10 + 14 |
+ 12 t 9 + I I + I I + 10 * І2 + 13 + 14 + 12 |
=І4ь |
денежных единиц. |
|
|
Таким образом, поставленная задача решена и оптимальная |
стра |
|
тегия по выпуску изделий найдена: на первых Двух шагах предпр-.ктие
должно |
выпускать продукцию первого |
вида, на третьем шаге - |
продук |
||||||||||
цию второго |
вида, |
на четвертом, |
пятом, шестом и седьмом |
шагах |
- |
||||||||
продукцию первого вида, на восьмом, |
девятом и десятом шагах |
- |
про |
||||||||||
дукцию второго вида, на одиннадцатом и Двенадцатом шагах - |
продук |
||||||||||||
цию первого вида и на последнем |
шаге - продукцию |
второго вида. |
|
||||||||||
Оптимальный переход планируемой системы в координатной плос |
|||||||||||||
кости |
Xj0x2 |
, |
отмеченный в таблице |
(13.ІІ) будет следующим: |
|
|
|||||||
( І ; 0 ) , (2;0), ( 2 ; І ) , (3,-І), ( 4 ; І ) , |
(b;I), |
(o;I), |
(ь;2), |
(ь;3), |
|
||||||||
(ь;4), |
(7;4), |
(8;4), |
(8;5). |
|
|
|
|
|
|
|
|
||
В литературе, |
посвященной |
динамическому программированию, |
|
||||||||||
например, в (4), последняя из рассмотренных задач носит также |
|
||||||||||||
название задачи о наборе высоты и скорости |
летательным |
аппаратом |
|||||||||||
При атом значения Xj соответствуют |
изменению скорости V , значе |
||||||||||||
ния |
- изменению |
высоты. |
|
|
|
|
|
|
|
|
|||
Летательныі. аппарат, находящийся в начальном |
состоянии |
на |
|
||||||||||
высоте |
Н0 и имеющий |
скорость |
у о |
, |
должен |
быть поднят на задан- |
|||||||
го-зію |
|
|
|
|
|
|
|
|
|
|
|
|
|
нуіи »ыссту С |
- |
Икон |
) , |
(а |
скорость его |
доведена |
до |
заданного | |
||||
а начет; и |
(х^ = V кск]. известен |
расход |
горючего, |
потребный для] |
||||||||
подъема аппарата |
с ЛІООО.І |
ВЫСОТЫ Н, |
на любую другую |
ru > H, |
||||||||
при неизменнее |
скорости |
|
»/ |
; известен |
|
также |
расход |
горючего, |
||||
потребный |
дл:. |
увеличения |
скорости |
от любого значения |
У> до любоь |
|||||||
другого |
Vx |
> |
V |
i |
при |
неизменном |
высоте |
\-\ |
|
|
||
Требуется найти оптимальный реаим набора высоты и скорости, |
||||||||||||
при кгторсм оивді. расход |
горючего |
оудет |
минимальным. |
|
||||||||
D рассмотренных выше задачах нами находились оптимальные стратегии при распределении ресурса одного вида. На практике чаще приходится встречаться с одновременным распределением ресурсов нескольких видов. Такие задачи такие могут быть решены методами динамического программирования, основой которого является принцип оптимальности.
iij-И формулировке задач в терминах динамического программи рования часто возникают затруднения. Ь отличие от линейного программирования, для которого симплексный метод является универ сальным, в динамическом программировании общего алгоритма, пркгод ноге для решения всех задач, не существует; каждая задача имеет свои сооствіжные трудности, v. в каждом случае требуется уметь находить наиболее подходящую методику оптимизации. Динамическое п[ограммпровапис является одним из перспективных методов матема тического программирования, которое должно найти широкое приме нение при решении нлановс-акономических задач.
