Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 48
Текст из файла (страница 48)
Е.Вгузоп, %. Г. Т<епйаш, Р. ЛСагго!1 апдК.М1- 1< а ш 1, Ьсгегш!па<!оп о1 !Ье Ь111 ог Ггга8 Ргоягаш Гйаг М<пцп1- тез Кссп1гу Неайпб и <РЬ Ассе1сгаиоп ог Капяе Сопзггаш!з Сз<пц а 5<серезг Псзссп! Сошрц!а!юп Ргосебпге (готовится к печати). По поводу использования леммы Неймана — Пирсона и распро- странения ее для решения вариационных задач с ограничениями см. К. Ве!1шап, 1. О<1!с!<вЬегя апб О. Огозз, Ботс Азрсс1в о1 гйе Магйешаг<са! ТЬсогу о1 Соп1<о1 Ргосеззеа, ТЬе КАХ)т Со<рога!!оп, Керог! К-318, 1958 )русский перевод: Р.
Беллман, И. Гликсберг, О. Гросс, Некоторые вопросы мател<атической теории у'правления, ИЛ, 1961]. О, О осг1ге1, М<пгпшгп слйсаг шазз ап<1 1!а! !1цх, Ю, Хпс1еаг Епег8у, то!. 2, 1956, рр. 193 — 201. ОПТИМДЛЫ!ЫН ТПЛГгГТОРИГ! Ггл. и! 96 20 — 22. Эти резулыаты получены Тсн-Дайком. См. К. Р. Т е п - П у 1г е, Сошрп1айоп о1 гос1ге1 шер тче!81т!в !о пил!пизе 1п111а! еговв же!ВЫв, зе! Ргорп1в1оп, чо!. 28, 1958, рр. 338 — 340. 6 24.
Изложение основывается на работе: К. В е11гп а п, А гоойпй ргоЫеш, О. АРР1. Май., чо!. 16, 1958, рр. 87 — 90. См. также К. Е. 0 ге си к о об, 11пеаг йгарЫ апб ша1псев, Техав 3. Бе!енсе, чо!. 12, 1960, рр. 105 — 108. Возможны и многие другие подходы к решению этой фунда- ментальной проблемы. Дальнейшие ссылки и обобщения, а также иные методы даны в К. К ага Ь а, Оп восле сопппкпка11оп псгжогй ргоЫешв, сошЬ1пагог!а! апа1увгв, Ргос. Бггпромпгп 1п Аррйегг Майсшайсв, Агпепсап Май.
Бос., ъо!. 1О, 1960, М. Ро11ас1г, ТЛс шах|пшпт сарае|!у гонге !Ьгопий а пс!жогй, Орегапопэ Ксвсагсй, чо1. 8, 1960, рр. 733 — 736. м. Р о!1 а с к апг! х. !э!ге ь си вон, Бо1птгопв о!тле влог1ев1 гоше ргоЫешв — а геч!еж, Орегайопв Кевеагсй, чо1. 8, 1960, рр. 224 — 230. Рассмотрение близких задач с помощью линейного програмиирования см.
в !.. К. Г о г б, уг. апб Еь К. Г п!й е г в о п, Махппа1 !1огч гЛговйЛ а пс!чгогй, Сапаб!ап Л Магп., чо1. 8, 19об, рр. 399 — 404. 9 26. Бояее детальное рассмотрение можно найти в работе: К. В е11ш а п апг1 К. К а!а Ь а, Оп й-й Ьегй ро!!с!ев, Л Бес. 1пбпвг. АРР1.
Май., чо1. 8, 1960, рр. 582 — 588, и в работе Р. Калаба, чказанной в ссылке н 9 24. Некоторые совершенно иные идеи развивакттся в у. Всагджооб, Л Н.На1!оп апбЛМ. Нашшегэ!еу,ТЬе вйоггсш ра1Л !Лгонйй шалу рогпш, Ргос. Сашйг1бйе РЫ1. Бес., чог. о5, 1959, рр. 299 — 327. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Проблеме построении оптимальных траекторий посвящена огромная литература. Одна из первых важных работ в этом направлении отражена в статье: Д.
Е. О х о и и м с к и й, К теории движения ракет, Ггрикладная математика и механика, т. Х, в. 2, 1946, 251 †2. кпммнптхнии и вигпиогнхеия зо! Ряд задач рассмогреп я книге: Л, С. Понтрягин, В,Г.Болтянский,Р,В.Гамкрелидзе, Бь Ф. М ища н к о, Математическая теория оптииальных процессов, Физматгиз, 1961. Можно также указать несколько работ последнего времени, где можно найти и дальнейшие ссылки: В К.
И с а е в, Принцип максимума Л. С. Понтрягина и оптимальное управление тяги ракет, Автоматика и телемеханика, № 8, 1961, Г. Л е й т м а н н, О мансимальной длине полета ракеты в горизонтальной плоскости, Прикладная математика и механика, в. з, 1963. О, !.е!1ва пи, Оп а с1агж о! тапапоча1 РгоЫева !п Косйе! ВИДИ!, Яошп. о1 Асго-красе ась, № 9, 1959. А. М ! е1е, Оепега1 Наг1айопа! Тпеогу о! 1пс ГИДЫ Ра1И о! Косйет Ровегеб А!гсга!1, м!вм!еа апб Баге!Сне Сам!сга, Асгопалг.
Ас1а, № 4, 1958. глдвд чл МНОГОШАГОВЫЕ ПРОИЗВОДСТВЕННЫЕ ПРОЦЕССЫ, ИСПОЛЬЗУЮЩИЕ ПРОМЫШЛЕННЫЕ НОМПЛЕКСЫ а. вввдвнив Эффективное использование комплекса взаимоззвисимых отраслей предстзвляет собой исключительно важную задачу в области экономики и промышленности. Очевидно, что при любом реалистическом ее рзссмотрении мы столкнемся с трудно преодолимыми препятствиями. Прежде чем думать об оптимизации, нзм придется столкнуться с точным количественным опнсзнием возникающих процессов, с определением критериев, с необходимостью учета стохастических явлений н приспособления и с нахождением допустимых, а не оптимальных политик.
Здесь мы ставим весьма скромную задачу — изучить упроцгенные модели многошзговых производственных процессов. Цель наша состоит в том, чтобы показать, как методика функциональных уравнений позволяет получить вычислительную основу для решения ряда задач, которые сохраняют некоторые особенности реальных экономических проблем. Наша, по видимости специализированная, матемазическая модель достойна внимания, так как тождественные аналитические вопросы возникают во многих областях, например в лесоводстве, при исследовании производства и хранения марганца, на многих стадиях химической технологии.
В качестве примеров последней группы рассмотрим 2~ двгхотглслввоИ экономичвскиИ комплвкс 303 задачи разделения изотопов, замены катализатора, а также другие задачи химического производства. )Угы очень кратко укажем некоторые связи между представленными здесь результатами и макроэкономической теорией фон Неймана, примыкающей к теории игр и линейному программированию. Дальнейшие результаты можно нзИти в работах, ссылки нз которые даны в конце главы. Часто процессы рассматриваемого здесь типа носят название задач на узкие места, так как свойства всего процесса определяются ресурсами или производственными мощностями, имеюшимнся в наименьшем количестве. 2, ДВУХОТРАСЛЕВОЙ ЭКОНОМИЧЕСКИЙ КОМПЛЕКС Допустим, что мы исследуем работу двухотраслевого комплекса, состоящего из автомобильной и сталелитейной промышленности.
Хотя этн названия не должны приниматься всерьез, но, используя привычные понятия и опираясь на определенные интуитивные представления, мы можем надеяться получить ключ к численному и знзлитическому решениям. С другоИ стороны, получаемые нами решения можно использовать для обеспечения некоторой интуитивной основы при решении еще более сложных моделей. Одной из причин того, чго стоит тратить время на рассмотрение этих сверхупрощенных моделеИ в некоторых подробностях, является надежда на известное прояснение структуры решения более общих задач агой природы. Мы будем предползгзть, используя идею сосредоточенных параметров, которая играет такую существенную роль в математической физике, что состояние каждой отрасли в любой отдельный момент времени может быть определено двумя величинами: (а) запасы сырья, необходимого дав производства, (Ь) производственная мощность отрасли по изготовае- (7.
!) нию своего продукта. Чтобы упростить формулировку и вычисления в этом частном случае, мы будем предполагать, что мощности автомобильной промышленности неограниченно велики. Короче, производство автомобилей будет зависеть только от количества отведенной на это стали. миогошлговыв пеоизводствянныа пгоцвссы [гл, чн Мы хотим определить политику распределения ресурсов, которая максимичируег общее количество автомобилей, произведенных за данный период времени. 3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ В данной задаче процесс будет предполагаться дискретным; распределение ресурсов производится только в моменты времени 1=0, 1, ..., Т вЂ” 1.
В любой отдельный момент времени 1=п состояние системы определяется величинами: (а) х (л) — количество стали на складах, (Ь) лм (л) — люгцнасть сталелитейных заводов. При определении распределения стали, имеющейся в рас- поряжении на шаге л, мы вводим величины: (а) г, (л) — количество стали, используемой 1 для производства дополнительной стали, (Ь) л,я (л) — количество стали, используемой для увеличения мощности сталелитейной 1(7,4) проиышленногти, (с) л (л) — количество стали, используемой ! длн производства автомобилей, Мы имеем соотношение Х, (и) = л, (л) + г (л) + ля (и). (7.5) Чтобь( отразить некоторые черты реальных процессов, мы налагаем два ограничения на величины гп (а) г (п)~а,хл(тт), 0(а,(1, ~ (Ь) г,(п) ( х (и).
(7.6) В любой отдельный момент времени сталь из общих за- пасов стали может быть использовзна с любой из трех целей:. (а) произвести дополнительную сталь, использтя существующую мощность сталелитейной промышленности, (Ь) увеличить существующую мощность сталелитейной (7. 2) промышленности, (с) произвести автомобили, используя существующую мощность автомобильной промышленности.
305 Овсгжденив Г1ервое ограничение утверждзег, что для ироизввдетва автомобилей можно использовзть не более определенного количества процентов имеющейся в рзспоряженни стали на любом шаге оа и до п -1- 1, в го время как второе утверждае~., что нельзя разместить на сталелитейных заводах больше стали, чем максимальная могцность заводов. Мы выберем единицы измерения гак, чтобы количество ав~омобилей, произведенных на шаге (л, и + 1), было равно г,(п).
Далее, количество стали, произведенной на шаге (л, и — ,' — 1), пропорционально г,(п), н рост мощности сталелитейной промышленносги пропорционален г,„(п). Пусть соответствующие коэффициен гы пропорциональности равны аэ и аа. Таким образом, мы предполагаем, что имеем линейную модель производствз. Аналитически это вырзжается в виде х,(п+ 1) =ляг,(п), ая) 1, х (0) = с,, х (и †' 1) = х„ (и) + ааг,„ (и), а, ) О, х (0) = са. ( Требуется выбрать величины г,(п), г,(п) и г (и), и= =О, 1,..., 7' — 1, так, чтобы максимизирова.гь общее количесгво автомобилей, произведенных за время Т-шагового процесса. 4. ОБСУЖДЕНИŠ— = Ах+ Ву, х (О) = С гГх лг (7.8) и ограничением вида Су «7)х.
(7.9) Эти задачи не могут решаться классическими методами вариационного исчисления. Работы, содержащие аналитическое Аналигическое решение подобных задзч усложняется двумя факгорамн; линейносгью и наличием ограничений. Тем не менее обширное множесгво вариационных задач может быть решено в явном виде. Непрерывный вариант этой вариационной задачи состоит в нахождении векгора у, максимизируюшего скалярное произведение (х (Т), а), причем х и у связаны дифференциальным уравнением ЗО6 многошаговыв пгоизводстввнныв пгоцвссы 1гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
