• Название:

    Вагнер Основы ИСО т 2

  • Размер: 9.99 Мб
  • Формат: PDF
  • или
  • Сообщить о нарушении / Abuse

    Предпросмотр документа

    Г. ВАГНЕР

    ОСНОВЫ
    ИССЛЕДОВАНИЯ
    ОПЕРАЦИЙ

    Harvey M. Wagner
    Department of Administrative Science Yale University;
    Consultant to McKinsey and Company, Inc.

    Principles
    of
    Operations
    Research
    With Applications to Managerial Decisions

    Prentice-Hall, Inc., Englewood Cliffs,
    New Jersey 1969

    Г. ВАГНЕР
    ОСНОВЫ
    ИССЛЕДОВАНИЯ
    ОПЕРАЦИИ

    Том 2

    Перевод
    с английского
    В. Я. Алтаева

    Издательство «Мир»
    Москва 1973

    У Д К . 35.073.5

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

    Редакция литературы по вопросам новой техники

    D

    3314-335
    041(01)-73

    £5 7Г77"

    Г. ВАГНЕР

    Основы исследования операций
    Том 2
    Редактор М. ВЕЛИКОВСПИН
    Художник А. Шипов.
    Художественный редактор Ю. Урманчеее
    Технический редактор Н. Иовлева
    Сдано в набор 26/Х 1972 г. Подписано к печати
    /II 1973 г.
    Бумага № 1 60x901/16=15,25 бум. л. 30,50 печ. л. Уч.-изд. л. 32,39 Изд. •№ 2 0 / 6 4 7 9
    Цела' 2 р. 54 к. Зак. 0734^} 3L<^tO
    ИЗДАТЕЛЬСТВО «МИР» Москва,

    1-й

    Рижский пер., 2

    Ордена Трудового Красного Знамени Московская типография № 7 «Искра революции»
    Союзполиграфпрома при Государственном комитете Совета Министров СССР по делам
    издательств, полиграфии и книншой торговли. Москва, К-1, Трехпрудный пер., 9.

    ГЛАВА 8

    Введение в теорию динамических
    оптимизационных моделей
    8.1. АНАЛИЗ ДИНАМИЧЕСКИХ ПРОЦЕССОВ

    Элементы динамики и учет времени играли важнейшую роль
    в нескольких прикладных задачах исследования операций, рассмотренных в предыдущих главах,— как, скажем, в общей задаче планирования производственной программы (разд. 2.6). Однако ранее
    основное внимание уделялось рассмотрению алгоритмов, которые
    позволяют находить решения системы, включающей большее число
    ограничений. Мы, например, выяснили, каким образом симплексный метод позволяет на каждой итерации получать допустимый
    план, удовлетворяющий всем ограничениям системы. В том же
    контексте анализировалась устойчивость решения задачи линейного программирования. В гл. 6 и 7 рассмотрены особенности структуры сетевых моделей; основное внимание здесь было уделено
    эффективным методам отыскания численных решений задач большой
    размерности. Единственным важным отступлением от подобного
    подхода является алгоритм решения задачи отыскания кратчайшего
    пути на ориентированной ациклической сети (разд. 7.7). В этом
    алгоритме используется «односторонняя ориентация» сети, и читателю рекомендуется снова внимательно его рассмотреть, прежде
    чем приступить к изучению разд. 8.2.
    В гл. 8—12 решающее значение по-прежнему имеет одновременный учет всех ограничений системы, однако излагаемый здесь материал в основном посвящен динамическим структурным зависимостям оптимизационных моделей. В этих главах рассматриваются
    только детерминированные задачи, так что в каждой из них процесс решения приводит к однозначному результату. Вероятностные модели исследуются в гл. 17—18. Однако читатель увидит,
    что аналитические методы решения большинства вероятностных
    задач являются непосредственным обобщением тех подходов,
    которые излагаются в гл. 8—12. Соответственно изучение методов
    решения детерминированных задач оказывается весьма полезным
    и в качестве подготовки к рассмотрению вероятностных моделей.
    В гл. 8—12 основное внимание будет уделено форме и свойствам
    оптимальных планов. Будут изучены условия, которым должен
    удовлетворять оптимальный многошаговый процесс принятия решений, и исследовано, каким образом использовать эти условия для
    нахождения лучшего варианта. Подобный анализ часто называют
    динамическим программированием.
    Основным предметом рассмотрения в гл. 8 является анализ
    устойчивости решений во времени. Например, читатель увидит, что

    ГЛАВА 8

    увеличение длительности планового периода может существенно
    повлиять на правильность текущего выбора. Наряду с этим вопросом будет также изучено влияние начальных условий (начальный
    уровень запасов) и ограничений (ограниченность производственных
    мощностей).
    Во всех моделях, рассматриваемых в гл. 8 — 10, плановый период является конечным — например, он может быть равен году или
    десятилетию. В гл. И — 12 будут обсуждены особенности оптимизации в условиях бесконечного планового периода. (Вопросы дисконтирования во времени и приведения экономических показателей
    к исходному моменту времени будут излагаться лишь в гл. 11.)
    За увеличение глубины анализа динамических процессов приходится платить. Так, в этом случае необходимо радикально сокращать размерность (число ограничений) динамических оптимизационных моделей по сравнению с типичными задачами линейного программирования. Однако предлагаемый подход дает не только ценные
    дополнительные результаты, но и ряд практических преимуществ.
    Одно из них уже упоминалось выше: это возможность использования
    динамического программирования при бесконечном .плановом
    периоде. Другое его преимущество состоит в том, что такой подход
    позволяет решать ряд задач небольшой размерности, являющихся
    тем не менее важными частными случаями задач нелинейного программирования. К ним относятся задачи с нелинейной целевой
    функцией и небольшим числом нелинейных ограничений, а также
    задачи с целочисленными переменными. В гл. 10 будут приведены
    конкретные примеры, показывающие, что подобные задачи, даже
    внешне простые, могут быть сложными и запутанными. Наконец,
    приведенные численные методы применимы и к ряду проблем принятия решений, по существу не являющихся динамическими, которые, однако, для удобства алгоритмизации можно рассматривать
    как динамические или преобразовывать в многошаговые.
    Для того чтобы читатель видел все излагаемые вопросы в должной перспективе, подчеркивается, что численные решения всех
    моделей в гл. 8—10 можно получить с помощью ранее изученных
    алгоритмов (в частности, алгоритма нахождения кратчайшего пути
    на ориентированной ациклической сети). Важнейшая наша цель —
    научиться представлять модели в таком виде, в котором выявляются их динамические свойства. Эта цель достигается отчасти благодаря тому, что наш словарь в области исследования операций пополняется новыми терминами, а отчасти благодаря введению удобной системы математических обозначений. Однако читатель поймет,
    что не существует простых правил, механическое применение которых в любой задаче позволяет выявить ее динамические свойства.
    Лучшим учителем является опыт, поэтому в тексте приводятся многообразные примеры. Многие конкретные оптимизационные задачи
    удается сформулировать несколькими внешне различными способами, причем, как будет видно из дальнейшего, в каждой из форму-

    ТЕОРИЯ ДИНАМИЧЕСКИХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

    7

    лировок в центре внимания находится та или иная из структурных
    зависимостей.
    Значение динамического программирования. Сделанные выше
    вводные замечания должны облегчить читателю переход к новой
    точке зрения, отличной от той, которая развивалась в предыдущих
    главах. Однако до сих пор ничего не говорилось о практической важности изучаемых далее моделей. Велико ли их экономическое значение?
    Как было показано в предыдущих главах, модели линейного
    программирования в большинстве случаев используются в промышленности для принятия крупномасштабных плановых решений
    в сложных ситуациях. В то же время модели динамического программирования обычно применяются при решении задач значительно меньшего масштаба. Вот некоторые типичные области применения моделей динамического программирования при принятии
    решений:
    Разработка правил управления запасами, устанавливающих
    момент пополнения запасов и размер пополняющего заказа.
    Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося
    спроса на продукцию.
    Определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования.
    Распределение дефицитных капитальных вложений между
    возможными новыми направлениями их использования.
    Выбор методов проведения рекламной кампании, знакомящей
    покупателя с продукцией фирмы.
    Систематизация методов поиска ценного вида ресурсов.
    Составление календарных планов текущего и капитального
    ремонта сложного оборудования.
    Разработка долгосрочных правил замены выбывающих из
    эксплуатации основных фондов.
    Большинство этих применений детально рассматривается в настоящей и последующих главах, так что здесь не требуется дополнительных пояснений.
    Процессы принятия решений, к которым относится ряд упр.мянутых выше моделей, часто относятся к числу микроэкономических.] Однако во многих реально функционирующих системах еженедельно требуется принимать тысячи таких решений. В связи с этим модели динамического программирования ценны именно тем, что они позволяют
    принимать миллионы решений на основе стандартного подхода (часто
    с использованием ЭВМ) при минимальном вмешательстве человека.
    Без слов понятно, что даже если каждое из таких решений, взятое
    в отдельности, не является существенным, то в совокупности они
    могут оказывать большое влияние на прибыли фирм. Многие фирмы,
    воспользовавшиеся моделями динамического программирования,

    ГЛАВА 8

    были неплохо вознаграждены — им удалось добиться сокращения
    затрат на обслуживание и ремонт или же уровня запасов на 25% и
    более, причем без какого-либо ухудшения качества обслуживания.
    Небольшое наставление. Общей особенностью всех моделей динамического программирования является сведение задачи принятия
    решений к получению рекуррентных соотношений. Если читатель
    никогда не пользовался подобными формализованными методами для
    решения задач, то связанная с этим система математических обозначений может показаться ему странной и даже вызывающей недоумение. Приводимые ниже советы помогут читателю преодолеть подобные трудности.
    Текст рекомендуется прочесть не менее двух раз. При первом
    чтении следует постараться понять смысл поставленной задачи
    и хорошо ознакомиться с условными обозначениями; при втором чтении больше внимания целесообразно уделять деталям постановки,
    в том числе и характеру математических выражений. Необходимо
    внимательно ознакомиться с численными примерами и проверить
    правильность расчетов во всех тех случаях, когда это рекомендуется 1
    в тексте. Наконец, необходимо проявить терпение и не жалеть времени на изучение материала. Быстро усвоить методы динамического
    программирования удается далеко не всем, причем дело может медленно продвигаться даже у тех, кто сталкивался с рекуррентными
    соотношениями прежде. Однако если следовать приведенным советам,
    то после рассмотрения нескольких примеров в какой-то момент внезапно наступает «озарение», после чего читатель перестает испытывать трудности в понимании смысла рекуррентных соотношений.
    8.2. ЗАДАЧА

    О ДИЛИЖАНСАХ:

    АЛЛЕГОРИЯ

    На аллегорическом примере объясним некоторые важные идеи
    динамического программирования, а также построим систему условных обозначений динамических моделей^ Сама задача не содержит
    ничего нового — в ней попросту требуется найти кратчайший путь
    на ориентированной ациклической сети. Однако рассматриваемый
    в настоящем разделе конкретный пример содержит больше пояснений, чем пример в разд. 7.7, где излагался алгоритм нахождения
    кратчайшего пути.
    >
    Пример. Жил некогда мистер М., который решил отправиться
    искать счастья в Сан-Франциско. В те дни дилижансы были единственным видом общественного транспорта для поездки из восточных
    штатов, где проживал мистер М., на Запад. В бюро путешествий ему
    показали карту Соединенных Штатов (рис. 8.1) с нанесенными на ней
    дилижансовыми маршрутами, которые обслуживались в то время.
    Каждый квадрат на карте изображает один из штатов (состояний);
    для удобства штаты пронумерованы. Заметим, что, какой бы из
    вариантов пути от штата 1 (Восток) до штата 10 (Запад) мы ни выбрали, он включает 4 дилижансовых маршрута — или 4 «шага».

    ТЕОРИЯ ДИНАМИЧЕСКИХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

    9

    Поскольку мистеру М. было известно, что путешествие связано
    с серьезными опасностями для здоровья и жизни, перед отъездом он
    решил застраховаться. Ставка страхового платежа (иными словами,
    стоимость, отвечающая принятой стратегии выбора пути) зависела
    от избираемых дилижансовых маршрутов, и она была тем выше,
    чем опаснее маршрут. Обозначим через Сц стоимость страхового
    полиса для переезда из штата i в штат /. Условные численные значения сц проставлены на рис. 8.1. Цель мистера М.— выбрать
    ю

    Запад

    Р и с . 8.1. Задача о дилижансах.
    такой путь от штата 1 до штата 10, для которого общая стоимость
    страхования является минимальной (читателю рекомендуется отыскать оптимальный путь самостоятельно).
    Мистер М. начал анализ проблемы с того, что признал существенным сформулированный ниже принцип.
    П р и н ц и п о п т и м а ль н о е т и., Оптимальная стратегия
    обладает тем свойством, что, каков бы ни был путь достижения некоторого штата (или состояния), последующие решения должны принадлежать оптимальной стратегии для части пути, начинающейся
    с этого состояния.
    Таким образом, мистер М. понял, что, например, оптимальный
    путь из штата 6 не зависит от того, каким маршрутом он прибудет
    в него. (Вопрос читателю: как найти оптимальный маршрут из штата
    6?) Развивая эту логическую идею далее, мистер М. пришел к выво-

    10

    .

    ГЛАВА 8

    ду, что если бы он знал оптимальные пути из штатов 5, 6 ж 7, то смог
    бы достаточно легко определить и оптимальный путь из штата 3 —
    конечно, если бы он решил ехать через этот штат. В самом деле,
    потребовалось бы лишь суммировать стоимость переезда из штата 3
    (буть то с35, с3б или сг7) с ранее вычисленной стоимостью оптимального
    пути (соответственно из штатов 5, 6 или 7), а затем сравнить полученные суммы и выбрать тот штат, для которого эта сумма минимальна.
    Аналогичным образом, найдя оптимальные пути из штатов 2, 3 и 4,
    можно определить оптимальный путь из штата 1. (Вопрос читателю:
    как это сделать?)
    Для того чтобы учесть сформулированный принцип оптимальности
    и его вычислительный смысл, удобно использовать следующие обозначения:
    /л (s) — стоимость, отвечающая стратегии минимальных затрат
    для пути от штата (состояния) s, если до конечного штата остается
    п шагов;
    jn (s) — решение, позволяющее достичь /„ (s).
    Многих начинающих чрезвычайно затрудняет подобная система
    обозначений, которую всегда используют в моделях динамического
    программирования, и это объясняется тем, что она выглядит весьма
    сложной. Однако все эти б^квы и индексы необходимы и несут важную смысловую нагрузку:!/ означает, что данное число есть значение
    целевой функции, s — что это значение зависит от состояния системы,
    подстрочный индекс п несет динамическую информацию о том, что
    из состояния s необходимо сделать еще п шагов; наконец, символ j
    зависит как от шага п, так и от состояния s и соответствует некоторому фиксированному пути.
    Читая описание приводимых здесь и далее задач динамического
    программирования, иногда полезно просто выучить смысл обозначений, как заучивают значения слов при овладении иностранным языком. В моделях линейного программирования нет необходимости
    в столь сложной системе обозначений, поскольку эти модели решаются «за один шаг». Иное положение в динамическом программировании, где мы приходим к решению за ряд шагов. Будем надеяться,
    что эти соображения послужат некоторым утешением для читателя.
    Возвратимся к задаче, стоящей перед мистером М. Он знает
    /о (Ю):
    /о (10) = 0 для у о (10) = Остановка,
    (1)
    поскольку для штата 10 число оставшихся шагов равно нулю, т. е.
    в этом штате путешествие заканчивается. Затем он видит, что очень
    легко вычисляются /i (8) и /i (9): к / 0 (10) попросту надо прибавить
    соответственно с 8]10 или с 9]10. Ободренный достигнутыми успехами,
    мистер М. решил вычислить /2 (6) — стоимость стратегии минимальных затрат, отвечающей его нахождению в штате 6, т. е. за два шага
    до конечного пункта. Он заметил, что если он попадет в штат б, то
    далее можно следовать только по двум путям. Первый из них —

    ТЕОРИЯ ДИНАМИЧЕСКИХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

    Ц

    через штат 8', стоимость соответствующей стратегии определится,
    если прибавить с в>8 к вычисленному ранее значению /i (8). Второй
    путь — через штат 9; для вычисления его стоимости прибавим c 6i9
    к значению /i (9), которое также уже вычислено. Мистер М. понял,
    что значение /2 (6) должно равняться меньшей из этих двух сумм.
    (Вопрос читателю: таким ли способом он определял оптимальный
    маршрут из штата б?)
    Здесь мистер-М. начал подозревать, что в его подходе можно обнаружить известную методичность, и, разумеется, он был прав. Кратко
    описываемый метод можно представить в виде так называемого дина,ми_ческо.го рекуррентного соотношения:
    /»(s)=

    min

    по всем s
    и з на сети

    [ct] + /„-!(/)],

    в = 1, 2, 3, 4.

    (2)

    Выражение (2) означает, что мистер М. должен вычислить все
    возможные значения стоимости, отвечающие различным стратегиям,
    суммируя соответствующую стоимость для очередного шага пути
    (переезда из штата s в штат j), и стоимость, отвечающую оптимальной стратегии выбора пути, от штата /, из которого до конца пути
    остается только (п — 1) шагов. Вычисленные суммы следует сравнить между собой и выбрать такое у, для которого значение этой
    суммы минимально. Мистер М. пришел к выводу, что он должен применять выражение (2) следующим образом: вначале вычислить все
    /i (s), т. е. /! (8) и /i (9); затем в свою очередь для п = 2 вычислить
    /2 (5), /2 (6) и /2 (7); затем определить /3 (2), / 3 (3) и / 3 (4). Задача будет
    решена после вычисления /4 (1), так как шта