Об идеях оптимизации

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

Познакомим наших читателей с математической идеей еще одного весьма интересного метода, широко применяемого на практике для оптимального планирования и управления. Речь идет о последовательных (пошаговых) процедурах нахождения решения. Этот метод получил название «динамическое программирование».

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

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

— какую прибыль приносит к концу года вложение капитальных средств в данную отрасль?

— какую величину к концу года составят вложенные в отрасль средства?

Предположим, что для трех конкретных отраслей, рассматриваемых в данной задаче, эти показатели таковы.

Прибыль: -

p₁(t) = t, p₂(t) = 0,4t, p₃(t) = 0,6t.

«Сохранность» капитальных вложений:

q₁(t) = 0,2t, q₂(t) = 0,8t, q₃(t) = 0,6t.

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

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

Как нам нередко приходится делать на практике, начнем решать эту задачу с конца. И далее, двигаясь шаг за шагом по годам, придем к исходной ситуации. Предположим, что к концу второго года у нас сохранилось a₂ капитальных вложений и мы последний раз (в условиях задачи) распределяем их по трем рассматриваемым отраслям. В первую отдадим x₂ из этих средств, во вторую y₂, в третью — все остальное: (а₂ — x₂ —y₂). Цель — получить максимальную прибыль. Тогда на последнем этапе задачи эта величина находится из условия:

Естественно, что при рассматриваемых ограничениях x₂ ≥ 0, y₂ ≥ 0, x₂ + y₂ ≤ a₂ максимум здесь достигается, если x₂ = a₂, y₂ = 0. Это вполне очевидно. На последнем этапе (в соответствии со спецификой задачи) мы уже не думаем о сохранении средств на будущее, а лишь стремимся получить максимальную прибыль. Ее дает нам первая отрасль. Сюда и следует на третий год вложить все оставшиеся средства.

Итак, x₂ = a₂, y₂ = 0; φ₁(a₂) = a₂.

Теперь отступим на один шаг назад от конца задачи и рассмотрим распределение капитальных вложений на второй год совместно с уже рассмотренным последним годом. Пусть по итогам первого года деятельности отраслей у нас сохранилось a₁ средств. Если мы распределим их по отраслям следующим образом: x₁, y₁, (a₁ — x₁ — y₁),  то к концу второго года (т. е. к началу последнего третьего этапа задачи) у нас сохранитсяq₁(x₁) + q₂(y₁) + q₃(a₁ — x₁ — y₁) капитальных вложений. Следовательно, максимальная прибыль за последние два этапа задачи определяется так:

Неожиданный результат! Максимальная прибыль (в условиях данной задачи) за последние два года равна 1,2a₁ и не зависит от величин x₁ и y₁, т. е. от того, как мы распределим капитальные вложения, оставшиеся после первого года, между нашими тремя отраслями на второй год.

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

Учитывая ограничения x ≥ 0, y ≥ 0, x + y ≤ a, получаем, что φ₃(a) = 1,36a при x = 0, y = a.

Итак, задача решена. Максимальная прибыль за все три года равна 1,36a. Она достигается, если имеющиеся a капитальных вложений распределить среди трех рассматривавшихся отраслей по годам следующим образом. На первом этапе все средства надо направить во вторую отрасль (имеющую наибольший коэффициент сохранения их). На последнем третьем году все средства целесообразно направить в наиболее прибыльную — первую отрасль. Распределение средств на втором этапе, как оказалось, не влияет на решение задачи. Поэтому здесь можно либо задействовать неиспользовавшиеся мощности третьей отрасли, либо принять во внимание какие-либо другие обстоятельства.

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

Рассмотрим один простой, но занятный пример. Приехав из своего города на экскурсию или в служебную командировку в Москву, вы, как и большинство приезжих, активно пользуетесь замечательным столичным метрополитеном. Как известно, многие подземные станции здесь очень длинные и имеют по несколько выходов на разные улицы. Вы сели в подземный поезд и едете на определенную станцию. Но вы не знаете, будет ли выход на нужную вам улицу в конце станции по ходу движения или в противоположном конце. Как быть? Есть любители рискнуть и специально сесть в первый или последний вагон. А вдруг ошибка? Тогда придется на станции назначения идти до нужного выхода около 100 м. И как всегда, это будет именно в тот момент, когда вы очень торопитесь.

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

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

В заключение заметим, что мы не случайно целую главу книги об ОГАС посвятили вопросам математического моделирования и знакомству с математическими методами оптимизации. Это совершенно необходимый и надежный инструмент для решения многих актуальных задач современного планирования и управления, но всегда очень важно точно определить поставленную цель, четко разобраться в критериях, по которым мы оптимизируем. Необходимо быть внимательным к ограничениям, вводимым в задачу, уметь проанализировать, как малейшие изменения повлияют на решение задачи.

Для широкой автоматизации в области планирования и управления, для создания ОГАС совершенно необходимо разрабатывать оригинальные методы, в большом количестве накапливать эффективные алгоритмы и программы для машинного решения множества самых разнообразных задач экономики.