Глава 1. Предмет и задачи исследования операций.

Глава 1. Предмет и задачи исследования операций.

§ 1. Что такое исследование операций и чем оно занимается.

§ 2. Основные понятия и принципы исследования операции.

§ 3. Математические модели операций.

Глава 2. Разновидности задач исследования операций и подходов к их решению.

§ 4. Прямые и обратные задачи исследования операций. Детерминированные задачи.

§ 5. Проблема выбора решения в условиях неопределенности.

§ 6. Многокритериальные задачи исследования операций. «Системный подход».

Глава 3. Линейное программирование.

§ 7. Задачи линейного программирования.

§ 8. Основная задача линейного программирования.

§ 9. Существование решения 03ЛП и способы его нахождения.

§ 10. Транспортная задача линейного программирования.

§ 11. Задачи целочисленного программирования. Понятие о нелинейном программировании.

Глава 4. Динамическое программирование.

§ 12. Метод динамического программирования.

§ 13. Примеры решения задач динамического программирования.

§ 14. Задача динамического программирования в общем виде. Принцип оптимальности.

Глава 5.Марковские случайные процессы.

§ 15. Понятие о марковском процессе.

§ 16. Потоки событий.

§ 17. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний.

Глава 6. Теория массового обслуживания .

§ 18. Задачи теории массового обслуживания. Классификация систем массового обслуживания.

§ 19. Схема гибели и размножения. Формула Литтла.

§ 20. Простейшие системы массового обслуживания и их характеристики.

§ 21. Более сложные задачи теории массового обслуживания.

Глава 7. Статистическое моделирование случайных процессов (метод Монте-Карло).

§ 22. Идея, назначение и область применимости метода.

§ 23. Единичный жребий и формы его организации.

§ 24. Определение характеристик стационарного случайного процесса по одной реализации.

Глава 8. Игровые методы обоснования решении.

§ 25. Предмет и задачи теории игр.

§ 26. Антагонистические матричные игры.

§ 27. Методы решения конечных игр.

§ 28. Задачи теории статистических решении.

ГЛАВА 1

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

Основные понятия и принципы исследования операций

В этом параграфе мы познакомимся с терминологией, основными понятиями и принципами науки «исследование операций».

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели (все мероприятия, рассмотренные в пунктах 1 — 8 предыдущего параграфа, являются «операциями»).

Операция есть всегда управляемое мероприятие, т. е. от нас зависит, каким способом выбрать некоторые параметры, характеризующие её организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяемых в операции.

Всякий определенный выбор зависящих от нас параметров называется решением. Решения могут быть удачными и неудачными, разумными и неразумными. Оптимальными называются решения, по тем или другим признакам предпочтительные перед другими. Цель исследования операций — предварительное количественное обоснование оптимальных решений.

Иногда (относительно редко) в результате исследования удается указать одно-единственное строго оптимальное решение, гораздо чаще — выделить область практически равноценных оптимальных (разумных) решений, в пределах которой может быть сделан окончательный выбор.

Заметим, что само принятие решения выходит за рамки исследования операции и относится к компетенции ответственного лица, чаще — группы лиц, которым предоставлено право окончательного выбора и на которых возложена ответственность за этот выбор. Делая выбор, они могут учитывать, наряду с рекомендациями, вытекающими из математического расчета, еще ряд соображений (количественного и качественного характера), которые этим расчетом не были учтены.

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

Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А₁,А₂,…, А_m в пункты назначения В₁,В₂, ..., В_n, то элементами решения будут числа x_ij, показывающие, какое количество груза будет отправлено из 1-го пункта отправления А_i в j-й пункт назначения В_j. Совокупность чисел x₁₁, x_{12, …,} x_1n, …, x_m1, x_m2, …, x_mn образует решение.

В простейших задачах исследования операций количество элементов решения может быть сравнительно невелико. Но в большинстве задач, имеющих практическое значение, число элементов решения очень велико, в чем читатель может убедиться, попытавшись самостоятельно выделить и «назвать по имени» элементы решения в примерах 1 — 8 предыдущего параграфа. Для упрощения мы будем всю совокупность элементов решения обозначать одной буквой x и говорить «решение х».

Кроме элементов решения, которыми мы, в каких-то пределах, можем распоряжаться, в любой задаче исследования операций имеются еще и заданные, «дисциплинирующие» условия, которые фиксированы с самого начала и нарушены быть не могут (например, грузоподъемность машины; размер планового задания;

весовые характеристики оборудования и т. п.). В частности, к таким условиям относятся средства (материальные, технические, людские), которыми мы вправо распоряжаться, и иные ограничения, налагаемые на решение. В своей совокупности они формируют так называемое «множество возможных решений».

Обозначим это множество опять-таки одной буквой X, а тот факт, что решение х принадлежит этому множеству, будем записывать в виде формулы: х X (читается: элемент х входит в множество X).

Речь идет о том, чтобы в множестве возможных решений Х выделить те решения х (иногда — одно, а чаще — целую область решений), которые с той или другой точки зрения эффективнее (удачнее, предпочтительнее) других. Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют «целевой функцией»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать, «назвать по имени» показатель эффективности W, нужно, прежде всего, спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение, мы, естественно, предпочтем такое, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W => mах, а если минимизировать — W => min.

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

В некоторых случаях бывает, что операция, сопровождаемая случайными факторами, преследует какую-то вполне определенную цель А, которая может быть только достигнута полностью или совсем не достигнута (схема «да—нет»), и никакие промежуточные результаты нас не интересуют. Тогда в качестве показателя эффективности выбирается вероятность достижения этой цели Р(А). Например, если ведется стрельба по какому-то объекту с непременным условием уничтожить его, то показателем эффективности будет вероятность уничтожения объекта.

Неправильный выбор показателя эффективности очень опасен. Операции, организованные под углом зрения неудачно выбранного критерия, могут привести к неоправданным затратам и потерям (вспомним хотя бы пресловутый «вал» в качестве основного критерия оценки хозяйственной деятельности предприятий).

Для иллюстрации принципов выбора показателя эффективности вернемся опять к примерам 1 — 8 § 1, выберем для каждого из них естественный показатель эффективности и укажем, требуется его максимизировать или минимизировать. Разбирая примеры, нужно иметь в виду, что не во всех из них выбор показателя эффективности однозначно диктуется словесным описанием задачи, так что по этому вопросу возможны расхождения между читателем и автором.

1. План снабжения предприятий. Задача операции — обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R => min).

2. Постройка участка магистрали. Требуется так спланировать строительство, чтобы закончить его как можно скорее. Естественным показателем эффективности было бы время завершения стройки, если бы оно не было связано со случайными факторами (отказы техники, задержки в выполнении отдельных работ). Поэтому в качестве показателя эффективности можно выбрать среднее ожидаемое время Т окончания стройки (Т => min).

3. Продажа сезонных товаров. В качестве показателя эффективности можно взять среднюю ожидаемую прибыль П от реализации товаров за сезон (П => mах).

4. Снегозащита дорог. Речь идет о наиболее выгодном экономически плане снегозащиты, поэтому в качестве показателя эффективности можно выбрать средние за единицу времени (например, за год) расходы R на содержание и эксплуатацию дорог, включая расходы, связанные как с сооружением защитных устройств, так и с расчисткой дорог и задержками транспорта (R => min).

5. Противолодочный рейд. Так как рейд имеет вполне определенную цель А — уничтожение лодки, то в качестве показателя эффективности следует выбрать вероятность Р(A) того, что лодка будет уничтожена.

6. Выборочный контроль продукции. Естественный показатель эффективности, подсказанный формулировкой задачи, это средние ожидаемые расходы R на контроль за единицу времени, при условии, что система контроля обеспечивает заданный уровень качества, например, средний процент брака не выше заданного (R => min).

7. Медицинское обследование. В качестве показателя эффективности можно выбрать средний процент (долю) Q больных и носителей инфекции, которых удалось выявить (Q => шах).

8. Библиотечное обслуживание. В формулировке задачи сознательно допущена некоторая нечеткость:

неясно, что значит «наилучшее обслуживание абонентов» или «удовлетворение их запросов в максимальной мере». Если о качестве обслуживания судить по времени, которое запросивший книгу абонент ждет ее получения, то в качестве показателя эффективности можно взять среднее время Т ожидания книги читателем, подавшим на нее заявку (Т => min). Можно подойти к вопросу и с несколько иных позиций, выбрав в качестве показателя эффективности среднее число М книг, выданных за единицу времени (М => mах).

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

К сожалению, в большинстве задач, имеющих практическое значение, выбор показателя эффективности не прост и решается неоднозначно. Для сколько-нибудь сложной задачи типично положение, когда эффективность операции не может быть исчерпывающим образом охарактеризована одним единственным числом — на помощь ему приходится привлекать другие. С такими «многокритериальными» задачами мы познакомимся в § 6.

Математические модели операций

Для применения количественных методов исследования в любой области всегда требуется какая-то математическая модель. При построении модели реальное явление (в нашем случае — операция) неизбежно упрощается, схематизируется, и эта схема («макет» явления) описывается с помощью того или другого математического аппарата. Чем удачнее будет подобрана математическая модель, чем лучше она будет отражать характерные черты явления, тем успешнее будет исследование и полезнее — вытекающие из него рекомендации.

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

Математическая модель должна отражать важнейшие черты явления, все существенные факторы, от которых в основном зависит успех операции. Вместе с тем, модель должна быть по возможности простой, не «засоренной» массой мелких, второстепенных факторов: их учет усложняет математический анализ и делает труднообозримыми результаты исследования. Две опасности всегда подстерегают составителя модели: первая — увязнуть в подробностях («из-за деревьев не увидеть леса») и вторая—слишком огрубить явление («выплеснуть вместе с водой и ребенка»). Искусство строить математические модели есть именно искусство, и опыт в нем приобретается постепенно.

Поскольку математическая модель не вытекает с непреложностью из описания задачи, всегда полезно не верить слепо ни одной модели, а сличать результаты, полученные по разным моделям, устраивать как бы «спор моделей». При этом одну и ту же задачу решают не один раз, а несколько, пользуясь разной системой допущений, разным аппаратом, разными моделями. Если научные выводы от модели к модели меняются мало — это серьезный аргумент в пользу объективности исследования. Если они существенно расходятся, надо пересмотреть концепции, положенные в основу различных моделей, посмотреть, какая из них более адекватна действительности, в случае надобности — поставить контрольный эксперимент. Характерным для исследования операций является также повторное обращение к модели (после того, как первый тур расчетов уже проведен) для внесения в модель коррективов.

Создание математической модели — самая важная и ответственная часть исследования, требующая глубокого знания не столько математики, сколько существа моделируемых явлений. Как правило, «чистые» математики (без помощи специалистов в той области, к которой относится задача) с построением модели справляются плохо. В центре внимания у них оказывается математический аппарат с его тонкостями, а не реальная практическая задача.

Опыт показывает, что самые удачные модели создаются специалистами в данной области практики, получившими, в дополнение к основной, глубокую математическую подготовку, или же коллективами, объединяющими практиков-специалистов и математиков. Большую пользу приносят консультации, даваемые математиком, хорошо знающим исследование операций, практикам — инженерам, биологам, медикам и др., встречающимся в своей работе с необходимостью научного обоснования решений. От таких консультаций выигрывают не только практики, но и сам математик, знакомящийся с реальными задачами из самых разных областей. Для решения таких задач ему нередко приходится пополнять свое образование, а также развивать, обобщать и модифицировать известные ему методы.

Математическая подготовка специалиста, желающего самостоятельно (без посторонней помощи) заниматься исследованием операций в своей области практики, должна быть достаточно широка. Наряду с классическими разделами математического анализа (обычно проходимыми в вузе) в исследовании операций часто применяются современные, сравнительно новые разделы математики, такие, как линейное, нелинейное, динамическое программирование, теория игр и статистических решений, теория массового обслуживания и др. Некоторое понятие об этих разделах математики читатель может почерпнуть из нашей книги.

Специально надо подчеркнуть необходимость сведений по теории вероятностей — не столько обширных и глубоких, сколько неформальных, действенных, наличие привычки к оперированию со статистическими данными и вероятностными представлениями. Особые требования именно к этой области математических знаний объясняются тем, что большинство операций проводится в условиях неполной определенности, и их ход и исход зависят от случайных факторов. К сожалению, в широких кругах специалистов — инженеров, биологов, медиков, химиков — хорошее владение теорией вероятностей встречается редко. Ее положения и правила часто применяются формально, без подлинного понимания их смысла и духа. Нередко на теорию вероятностей смотрят как на некое подобие «волшебной палочки», позволяющее получить информацию «из ничего», из полного незнания. Это заблуждение: теория вероятностей позволяет только преобразовывать информацию, т. е. из сведений об одних явлениях, доступных наблюдению, делать выводы о других, недоступных. Наличие элементарных сведений по теории вероятностей предполагается у читателя этой книги.

Очень не хочется, чтобы перечисление разделов математики, применяемых в исследовании операций, запугало начинающего читателя и отбило у него охоту заниматься такими задачами. Во-первых, как говорится, не боги горшки обжигают, и любым аппаратом можно овладеть, если он действительно нужен. Во-вторых, не в каждой задаче применяются все перечисленные разделы; знакомиться можно не со всеми сразу, а с самыми необходимыми. Какие знания по математике для каких задач нужны — можно опять-таки узнать из этой книги.

При построении математической модели может быть (в зависимости от вида операции, задач исследования и точности исходных данных) использован математический аппарат различной сложности. В самых простых случаях явление описывается простыми, алгебраическими уравнениями. В более сложных, когда требуется рассмотреть явление в динамике, применяется аппарат дифференциальных уравнений (обыкновенных или с частными производными). В наиболее сложных случаях, когда развитие операции, и ее исход зависят от большого числа сложно переплетающихся между собой случайных факторов, аналитические методы вообще отказываются служить, и применяется метод статистического моделирования (Монте-Карло), о котором будет идти речь в гл. 7. В первом, грубом приближении идею этого метода можно описать так: процесс развития операции, со всеми сопровождающими его случайностями, как бы «копируется», воспроизводится на машине (ЭВМ). В результате получается один экземпляр («реализация») случайного процесса развития операции со случайным ходом и исходом. Сама по себе одна такая реализация не дает оснований к выбору решения, но, получив множество таких реализации, мы обрабатываем его как обычный статистический материал (отсюда и термин «статистическое моделирование»), находим средние характеристики процесса и получаем представление о том, как в среднем влияют на них условия задачи и элементы решения.

В исследовании операций широко применяются как аналитические, так и статистические модели. Каждый из этих типов имеет свои преимущества и недостатки. Аналитические модели более грубы, учитывают меньшее число факторов, всегда требуют каких-то допущений и упрощений. Зато результаты расчета по ним легче обозримы, отчетливее отражают присущие явлению основные закономерности. А, главное, аналитические модели больше приспособлены для поиска оптимальных решений.

Статистические модели, по сравнению с аналитическими, более точны и подробны, не требуют столь грубых допущений, позволяют учесть большое (в теории — неограниченно большое) число факторов. Но и у них — свои недостатки: громоздкость, плохая обозримость, большой расход машинного времени, а главное, крайняя трудность поиска оптимальных решений, которые приходится искать «на ощупь», путем догадок и проб.

Молодые специалисты, чей опыт в исследовании операций мал, имея в распоряжении вычислительные машины, часто без особой нужды начинают исследование с построения статистической модели, стараясь учесть в ней как можно больше факторов. Они забывают, что построить модель и произвести по ней расчеты — это полдела; важнее суметь проанализировать результаты и перевести их в ранг «рекомендаций».

Наилучшие работы в области исследования операций основаны на совместном применении аналитических и статистических моделей. Аналитическая модель дает возможность в общих чертах разобраться в явлении, наметить как бы «контур» основных закономерностей. Любые уточнения могут быть получены с помощью статистических моделей (подробнее см. главу 7).

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

ГЛАВА 2

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Примеры решения задач динамического программирования

В этом параграфе мы рассмотрим (и даже решим до конца) несколько простых (до крайности упрощенных) примеров задач динамического программирования

1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий

Рис. 13.1.

два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим,. что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 13.1). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны.

Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В на отдельные шаги (один шаг — один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным «слепым» перебором.

Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном — на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из т = 7 + 5 == 12 отрезков, направленных на восток или на север (рис. 13.2). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна.

Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной (х) и северной (у), обе — целочисленные (0 х 5 7, 0 у 5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 13.2) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление «с») или на восток (управление «в»). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по-прежнему будем называть «условным оптимальным выигрышем» (хотя в данном случае это не «выигрыш», а «проигрыш») для данного состояния системы S перед началом очередного шага.

Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 13.3). Где мы можем находиться после 11-го шага? Только

С₁ 11 10 В

13 14

С₂ 14

8

С₃

там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из точек В₁ или В₂. Если мы находимся в точке В₁, у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В₁, а оптимальное управление покажем короткой стрелкой, исходящей из В₁ и направленной на восток. Для точки В₂ управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В₂. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В₁, В₂ найден и записан в соответствующем кружке.

Теперь давайте оптимизировать предпоследний (11-й) шаг. После предпредпоследнего (10-го) шага мы могли оказаться в одной из точек С₁, С₂, С₃ (рис. 13.4). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С₁ управление вынужденное: идти на восток;

обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при В₁). Число 21 записываем в кружке при точке С₁. Для точки С₂ управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В₂ до конца — еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С₂ — идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С₂), Для точки С₃ управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С₃).

• Рис. 13.5.

Аналогично, «пятясь» от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление («с» или «в»), которое обозначим стрелкой, и условный оптимальный выигрыш (расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним — уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 13.5.

Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем, куда идти (стрелка) и во что нам обойдется путь до конца (число в кружке). В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В:

W* = 118.

Теперь остается построить безусловное оптимальное управление — траекторию, ведущую из А и В самым дешевым способом. Для этого нужно только «слушаться стрелок», т. е. прочитать, что они предписывают делать на каждом шаге. Такая оптимальная траектория отмечена на рис. 13.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:

х* = (с, с, с, с, в, в, с, в, в, в, в, в),

т. е. первые четыре шага мы должны делать на север, следующие два — на восток, затем опять один на север и остальные пять — на восток. Задача решена.

Заметим, что в ходе условной оптимизации мы можем столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, т. е. приводят к одинаковому расходу средств от этой точки до конца, Например, в точке с координатами (5; 1) оба управления «с» и «в» являются оптимальными и дают расход до конца равным 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали «с»; с тем же успехом мы могли бы выбрать «в»). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании; в дальнейшем мы специально отмечать их не будем, а попросту выберем произвольно любой из равноценных вариантов. От этого произвола, разумеется, может зависеть оптимальное управление всем процессом, но не оптимальный выигрыш. Вообще, в задачах динамического программирования (как и в задачах линейного) решение далеко не всегда единственное.

А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два, выбираем любое). Таким способом мы получим управление

х = (с, с, в, в, в, в, с, в, в, в, с, с).

Подсчитаем расходы для этой траектории. Они будут равны W =10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, что безусловно больше, чем W* = 118. В данном случае разница не очень велика, но в других она может быть существенной.

В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, но, разумеется, усложняет и удлиняет расчеты.

Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике: например, при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле расхода горючего) набора скорости и высоты летательным аппаратом.

Сделаем одно попутное замечание. Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные — в обратном направлении. Действительно, это так: в любой задаче динамического программирования «начало» и «конец» можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на «уже сложившиеся» условия к началу данного шага, чем на те, которые еще «предстоят» после этого шага. По существу же оба подхода совершенно равносильны.

2. Задача о распределении ресурсов. Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, [6, 10]). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между т предприятиями П₁, П₂, ..., П_m. Каждое из предприятий П_i при вложении в него каких-то средств х приносит доход, зависящий от x, т. е. представляющий собой какую-то функцию (x). Все функции (x) (i = 1, 2, ..., т) заданы (разумеется, эти функции — неубывающие). Спрашивается, как нужно распределить средства К. между предприятиями, чтобы в сумме они дали максимальный доход?

Эта задача легко решается методом динамического программирования.. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П₁, за второй — в П₂ и т. д.

Управляемая система S в данном случае — средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S — наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х₁, х₂, ..., х₃, выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совок<