Применение оптимизационных методов к решению экономических задач

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

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

6. Стохастическое  программирование

 

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

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

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

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

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

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

     Оптимизационные стохастические задачи начали разрабатываться  только в последнее десятилетие.

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

     В задаче линейного программирования: 

         1.1

     заданные  величины с_j, а_ij, b_i, d_j, D_j. Часто на практике величины c_j, a_ij, b_j, могут быть случайными. Так, если b_i — ресурс, то он зависит от ряда факторов. Аналогично, с_j — цены — будут зависеть от спроса и предложения, a_ij — расходные коэффициенты — от уровня техники и технологии. Задачи, в которых с_j, а_ij, b_i — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.

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

     Стохастическая  постановка целевой функции может быть двух видов: М-постановка и Р-постановка.

     При М-постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции: 

           1.2 

      где с_j — математическое ожидание случайной величины сj.

     При Р-постановке целевая функция будет  иметь вид:

• при максимизации целевой функции:

 

          1.3 

     обозначает  максимизацию вероятности того, что  случайная величина ∑ c_j x_j будет не меньше некоторого значения r;

• при минимизации целевой функции:

          1.4 

     обозначает  максимизацию вероятности того, что  случайная величина ∑ c_j x_j будет не больше некоторого значения r.

     Наиболее  распространены СТП-постановки в вероятностных  ограничениях вида: 

          1.5 

     где а_{i j} , b_i — случайные величины; a_i — заданные уровни вероятности.

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

            1.6 

     Для случая, когда вероятностные ограничения  представлены в виде типа (а), задачу СТП можно записать при М-постановке:

              1.7 

     При Р-постановке:

• в случае максимизации целевой функции

 

               1.8 

     

• в случае минимизации целевой функции

 

                1.9 

     где c_j , a_{i j} , b_i — случайные величины.

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

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

 

3. Практические  вопросы: применение динамического программирования к решению экономических задач

     Задача  о выборе наиболее экономного маршрута доставки груза.

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

     

     рис. 1 

     Для решения задачи методом динамического  программирования разобьем все пункты сети на группы (табл. 1). 

     Таблица 1

 

     К группе I отнесем пункт 1, к группе II – пункты, в которые можно попасть из пункта 1 (таковыми будут 2; 3; 4), к группе III отнесем пункты, в которые можно попасть непосредственно из любого пункта группы II (таковыми будут 5; 6; 7), и т.д. в результате движение транспорта с грузом из пункта 1 в пункт 10 примет поэтапный характер: на первом этапе транспорт перемещается из пункта 1 в какой-то пункт группы II, на втором этапе – из пункта группы II в пункт группы III и т.д. Вместе с этим и процесс нахождения наиболее экономного маршрута из пункта 1 в пункт 10 распадается на шаги. На каждом шаге надо так выбрать маршрут следования груза в пункт соседней группы, чтобы доставка груза по всему маршруту была сопряжена с минимальными затратами. Избранный нами подход к решению задачи учитывает особенности сети, изображенной на рис. 1: после разбиения на группы пункты, оказавшиеся в одной и той же группе, дорогами не соединены.

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

     В данном случае процесс состоит из четырех шагов (рис. 2). Будем оптимизировать каждый шаг, начиная с последнего – четвертого. На этом шаге в пункт 10 можно попасть из пункта 8 или 9, причем из каждого пункта только одним способом. Если предпоследний, третий, шаг привел груз в пункт 8, то дальше следует двигаться по маршруту 8 – 10, и затраты на перевозку единицы груза будут равны единице; если же в пункт 9 – то следует двигаться по маршруту 9 – 10, на котором затраты составят 4 единицы. Условное оптимальное решение помечаем на сети стрелкой, выходящей из соответствующего кружка, а величину затрат записываем в нижней половинке кружка.