Оптимальное планирование [optimal planning] комплекс методов, позволяющих выбрать из многих возможных (альтернативных) вариантов или программы один оптимальный вариант. О. п основано на решении задач

Вид материала

Содержание

Подобный материал:

1 ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ [optimal planning] — комплекс методов, позволяющих выбрать из многих возможных (альтернативных) вариантов плана или программы один оптимальный вариант.

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

На начальном этапе развития экономико-математических методов в бывш. СССР основное внимание было обращено именно на проблемы О. п.: казалось, что разработка оптимального плана — гарантия успешного роста экономики. Это вполне укладывалось в рамки господствовавшей тогда идеологии централизованное планирование экономики: отсюда применявшийся В. С. Немчиновым термин “планометрия”. Впоследствии исследования охватили также проблему оптимизации экономического механизма в целом. Это означало, что вместо теории О. п. была выдвинута идея разработки системы оптимального функционирования социалистической экономики (СОФЭ), в которую вопросы О. п. вошли как важная составная часть.

2 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [linear programming] — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.

В самом общем виде задачу Л. п. можно записать так. Даны ограничения типа

или в т. н. канонической форме, к которой можно привести все три указанных случая:

Требуется найти неотрицательные числа x_j (j = 1, 2, ..., n), которые минимизируют (или максимизируют) линейную форму

Неотрицательность искомых чисел записывается так: x_j ≥ 0.

Таким образом, здесь представлена общая задача математического программирования с оговорками: как ограничения, так и целевая функция линейные, а искомые переменные неотрицательные. Обозначения можно трактовать следующим образом: b_i — количество ресурса вида _i; m — количество видов этих ресурсов; a_ij — норма расхода ресурса вида i на единицу продукции вида j; x_j — количество продукции вида j, причем количество таких видов — n; c_j — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m₁, от m₁ + 1 до m₂ и от m₂ + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — “не больше”, во втором — “столько же”, в третьем — “не меньше”; Z — в случае максимизации, напр., объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т. п. Добавим еще одно обозначение, оно появится несколько ниже: v_i — оптимальная оценка i-го ресурса.

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

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

Рассмотрим две задачи Л. п. (на максимум и на минимум) на упрощенных примерах. Предположим, требуется разработать план производства двух видов продукции (объем первого — x₁; второго — x₂) с наиболее выгодным использованием трех видов ресурсов (наилучшим в смысле максимума общей прибыли от реализации плана). Условия задачи можно записать в виде таблицы (матрицы):

Вид продукции	Норма затрат (на единицу продукции)			Прибыль на единицу продукции
Вид продукции	1	2	3	Прибыль на единицу продукции
1	a₁₁	a₂₁	a₃₁	c₁
2	a₁₂	a₂₂	a₃₂	c₂
Наличие ресурса	b₁	b₂	b₃

Исходя из норм, зафиксированных в таблице, запишем неравенства (ограничения):

a₁₁x₁ + a₁₂x₂ ≤ b_i

a₂₁x₁ + a₂₂x₂ ≤ b₂

a₃₁x₁ + a₃₂x₂ ≤ b₃.

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

x1 ≥ 0, x2 ≥ 0.

Требуется найти такие значения x₁ и x₂, при которых общая сумма прибыли, т. е. величина c₁ x₁ + c₂ x₂, будет наибольшей или короче:

Удобно показать условия задачи на графике (рис. Л. 2).

Любая точка здесь, обозначаемая координатами x₁ и x₂, составляет вариант искомого плана. Очевидно, что все точки, находящиеся в области, ограниченной осями координат и прямой AA, удовлетворяют условию: не может быть израсходовано первого ресурса больше, чем его у нас имеется в наличии (в случае если точка находится на самой прямой, ресурс используется полностью). Если то же рассуждение отнести к остальным ограничениям, то станет ясно, что всем условиям задачи удовлетворяет любая точка, находящаяся в пределах области (края которой заштрихованы), — области допустимых решений (или области допустимых значений, допустимого множества).

Остается найти ту из них, которая даст наибольшую прибыль, т. е. максимум целевой функции. Выбрав произвольно прямую c₁x₁ + c₂x₂ = П с произвольной константой П и обозначив ее MM, находим на чертеже все точки (варианты планов), где прибыль одинакова при любом сочетании x₁ и x₂ (см. Линия уровня). Перемещая эту линию параллельно ее исходному положению, найдем точку, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений. (Перемещая линию уровня еще дальше, уже выходим из нее и, следовательно, нарушаем ограничения задачи.) Точка M₀ и будет искомым оптимальным планом. Она находится в одной из вершин многоугольника. Может быть и такой случай, когда линия уровня совпадает с одной из прямых, ограничивающих область допустимых значений, тогда оптимальным будет любой план, находящийся на соответствующем отрезке.

Координаты точки M₀ (т. е. оптимальный план) можно найти, решая совместно уравнения тех прямых, на пересечении которых она находится.

Противоположна изложенной другая задача Л. п.: поиск минимума функции при заданных ограничениях. Такая задача возникает, напр., когда требуется найти наиболее дешевую смесь некоторых продуктов, содержащих необходимые компоненты (см. Задача о диете). При этом известно содержание каждого компонента в единице исходного продукта — a_ij, ее себестоимость — c_j; задается потребность в искомых компонентах — b_i.

Эти данные можно записать в таблице (матрице), сходной с той, которая приведена выше, а затем построить уравнения как ограничений, так и целевой функции. Предыдущая задача решалась графически. Рассуждая аналогично, можно построить график (рис. Л. 3), каждая точка которого — вариант искомого плана (сочетания разных количеств продуктов x₁ и x₂).

Область допустимых решений здесь ничем сверху не ограничена: нужное количество заданных компонентов тем легче получить, чем больше исходных продуктов. Но требуется найти наиболее выгодное их сочетание. Пунктирные линии, как и в предыдущем примере, — линии уровня. Здесь они соединяют планы, при которых себестоимость смесей исходных продуктов одинакова. Линия, соответствующая наименьшему ее значению при заданных требованиях, — линия MM. Искомый оптимальный план — в точке M₀.

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

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

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

Один из видов решения имеет особое значение для экономической интерпретации задачи Л. п. Он связан с тем, что каждой прямой задаче Л. п. соответствует другая, симметричная ей двойственная задача (подробнее см. Двойственность в линейном программировании). Если в качестве прямой принять задачу максимизации выпуска продукции (или объема реализации, прибыли и т. д.), то двойственная задача заключается, наоборот, в нахождении таких оценок ресурсов, которые минимизируют затраты. В случае оптимального решения ее целевая функция — сумма произведений оценки (цены) v_i каждого ресурса на его количество b_i, т. е.

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

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

Первооткрыватель Л. п. — советский ученый, академик, лауреат Ленинской, Государственной и Нобелевской премий Л. В. Канторович. В 1939 г. он решил математически несколько задач: о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта и др., при этом разработав универсальный метод решения этих задач, а также различные алгоритмы, реализующие его. Л. В. Канторович впервые точно сформулировал такие важные и теперь широко принятые экономико-математические понятия, как оптимальность плана, оптимальное распределение ресурсов, объективно обусловленные (оптимальные) оценки, указав многочисленные области экономики, где могут быть применены экономико-математические методы принятия оптимальных решений. Позднее, в 40—50-х гг., многое сделали в этой области американские ученые — экономист Т. Купманс и математик Дж. Данциг. Последний ввел термин “Л. п.”.

3 НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [nonlinear programming] — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабов производства): напр., из-за деления издержек производства на предприятиях на переменные и условно-постоянные; из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую; из-за влияния экстерналий (см. Внешняя экономия, внешние издержки) и т. д.

В краткой форме задачу Н. п. можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0,

где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

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

Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейны; и целевая функция, и ограничения нелинейны.

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

Напр., задачу для двух переменных (выпуск продукта x и выпуск продукта y) и вогнутой целевой функции (прибыль Р) можно геометрически представить на чертеже (рис. H.4; заштрихована область допустимых решений).

Эта задача реалистично отражает распространенное в экономике явление: рост прибыли с ростом производства до определенного (оптимального) уровня в точке B′, а затем ее снижение (напр., вследствие затоваривания продукцией или исчерпания наиболее эффективных ресурсов).

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

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

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

4 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [dynamic programming] — раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.

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

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

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

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

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

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

5 ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ [discrete programming] — раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением: x₁, x₂, ..., x_n — целочисленны.

В экономике огромное количество задач носит дискретный характер. Прежде всего это связано с физической неделимостью многих факторов и объектов расчета: напр., нельзя построить 2,3 завода или купить 1,5 автомобиля. Все отраслевые задачи строятся в расчете на определенное количество предприятий или проектных вариантов. В планировании распространены типовые размеры предприятий, типовые мощности агрегатов — все это вносит дискретность в расчеты. Наконец, плановые показатели: годовые, месячные или суточные периоды — это дискретные, раздельные периоды, у каждого из которых есть свое начало и свой конец.

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

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

Часто в практических задачах искомые переменные принимают только два значения — “1” и “0”. (Их называют задачами булева линейного программирования.) Это означает, что данный вариант решения принимается или отвергается (строить или не строить шахту, приобретать или не приобретать машину и т. п.).

Иногда Д. п. называется целочисленным. Как видно из приведенных примеров, это не лишено основания, хотя некоторые математики считают такой термин неправильным (так как, строго говоря, дискретное — это не обязательно целочисленное; напр., ряд чисел 1,1; 1,2; 1,3... — дискретный, но не целочисленный). Поэтому правильнее, очевидно, считать целочисленное программирование частным случаем Д. п.

6 БЛОЧНОЕ ПРОГРАММИРОВАНИЕ [block programming] — метод решения сложных задач линейного программирования путем разложения модели на блоки. Крупноразмерная модель (включающая много показателей в исходной таблице) сводится к нескольким моделям меньшей размерности. Получившиеся задачи решаются вместе по специальным правилам согласования.

Необходимость такого подхода обосновывается тем, что с ростом размерности трудоемкость (сложность) решения задач растет невероятно быстро. “Проклятие размерности”, по меткому выражению американского математика Р. Беллмана, характерно для большинства реальных задач математического программирования.

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

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

Иначе говоря, схема Данцига—Вульфа построена по принципу “централизованное определение цен — децентрализованное определение наилучших возможностей”, а схема Корнаи—Липтака — по принципу “централизованное лимитирование возможностей — децентрализованное выявление эффекта от их использования”⁷. В обоих случаях важную роль играют двойственные оценки, причем их оптимальный уровень выявляется вместе с оптимальным распределением ресурсов, т. е. собственно планом (именно в этом состоит принцип оптимального планирования).

7 ПАРАМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [parametrical programming] — раздел математического программирования, изучающий задачи, отличие которых от других задач состоит в следующем. Коэффициенты их целевой функции, или числовые характеристики ограничений, или и те и другие, предполагаются не постоянными величинами (как, напр., в линейном программировании), а функциями, зависящими от некоторых параметров. Причем чаще всего эта зависимость носит линейный характер.

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

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

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

8 СЕПАРАБЕЛЬНОЕ ПРОГРАММИРОВАНИЕ [separable programming] — совокупность методов решения нелинейных экстремальных задач с сепарабельной целевой функцией (см. Сепарабельность функции) и с линейной системой ограничений. Такие задачи решаются в случаях, когда величина критерия оптимальности определяется рядом факторов, независимых друг от друга (или принимаемых за независимые). Напр., в задаче на минимум затрат последние могут быть связаны, с одной стороны, с объемом производства (x₁), с другой — c размером брака продукции (x₂) и т. д.

9 СТОХАСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [stochastic programming] — раздел математического программирования, совокупность методов решения оптимизационных задач вероятностного характера. Это означает, что либо параметры ограничений (условий) задачи, либо параметры целевой функции, либо и те и другие являются случайными величинами (содержат случайные компоненты). В ст. “Транспортная задача”, напр., приведена детерминированная модель. В стохастической постановке та же задача будет более близкой к реальности. Рассмотрим одно условие (заданный объем спроса) и допустим, что спрос b_j потребителя j — случайная величина b_j(w), где w — характеристика распределения этой величины. Тогда в одних случаях (при одних ее реализациях) возникает ущерб от неудовлетворенного спроса — “штраф за дефицит”, в других, наоборот, потребитель получает излишний груз и, следовательно, тратит дополнительные средства на хранение и перевозку. Все это усложняет решение задачи, т. е. нахождение оптимального варианта прикрепления поставщиков к потребителям.

Вероятностный характер задач планирования часто объясняется неполнотой информации об их условиях. Бывает, однако, и так, что сложную детерминированную задачу, для точного решения которой требуется слишком большой объем вычислений, целесообразно привести к вероятностному виду, хотя вся информация известна. Это называется “стохастическое расширение детерминированной задачи”. Объем вычислений при этом существенно сокращается. Образно говоря, модель как бы рассматривается издалека: детали исчезают, но зато общая структура задачи становится более ясной, обозримой.

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

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

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

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

10 ГЕОМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [geometric programming] — раздел математического программирования, изучает определенный класс оптимизационных задач, встречающихся главным образом в инженерно-экономических расчетах. Основное требование метода состоит в том, чтобы все технические характеристики проектируемых объектов были выражены количественно в виде зависимостей от регулируемых параметров. Геометрическим такой вид программирования назван потому, что в нем эффективно используется геометрическое среднее и ряд таких геометрических понятий, как векторные пространства, векторы, ортогональность и др.

Blog

Содержание