Краткий обзор моделей стохастического программирования и методов решения экономических задач
| Вид материала | Документы |
- Задачи нелинейной и дискретной оптимизации. Методы решения. Постановка и экономико-математическая, 25.18kb.
- Литература: [1,8-11,16,18], 419.3kb.
- Привлечение экономико-математических методов для решения экономических задач Сливицкий, 113.25kb.
- Рабочей программы дисциплины Математическое моделирование на ЭВМ по направлению подготовки, 18.67kb.
- План изучения дисциплины № п/п, 155.57kb.
- «Исследование и сопоставительный анализ численных методов решения задач не линейного, 321.81kb.
- Теория разностных схем, 25.48kb.
- Учебно-тематический план дисциплины программа дисциплины, 303.16kb.
- 1 Постановки экстремальных задач, 55.69kb.
- Учебно-методический комплекс имитационное моделирование Для студентов, обучающихся, 172.99kb.
Краткий обзор моделей стохастического программирования
и методов решения экономических задач
Журавель Л.М.
Предметом стохастического программирования является изучение задач математического программирования, в которых данные имеют случайный характер. Ограничимся рассмотрением задач линейного программирования со случайными данными, причем будем предполагать, что распределение случайных величин известно.
В опубликованных ранее работах можно выделить три пути решения задач стохастического программирования. Первое из направлений состоит в замене случайных параметров их средними значениями, что позволяет получить так называемые решения задач на уровне математических ожиданий. Другой путь — изучение двухэтапных задач линейного программирования со случайными данными. Под этими задачами понимается следующее: на первом этапе решается задача по фиксации случайного спроса, который задается математическим ожиданием; на втором этапе ищется оптимальный вектор управления производством при фиксированном спросе на эту продукцию. Третий путь решения рассматриваемых задач имеет авторское название «программирование с вероятностными ограничениями».
Для каждого из трех путей присуща своя модель. Вкратце остановимся на этих моделях.
Характерным представителем первого пути является работа [1]. Экономическая постановка задачи в этой работе заключается в том, чтобы распределить транспорт по маршрутам, если известно только вероятностное распределение месячного спроса по каждому маршруту. При этом требуется минимизировать сумму стоимости ожидаемых перевозок и ожидаемый объем убытка из-за невозможности обслужить все спрашиваемые маршруты перевозок. Решая данную задачу на уровне математических ожиданий, автор указывает, что в некоторых случаях, используя дополнительную информацию о виде распределения случайного спроса, а, не ограничиваясь лишь математическим ожиданием, можно улучшить оптимальный план распределения транспорта.
Доказательство этого факта приводится на условном примере. Действительное оптимальное назначение транспорта по маршрутам при условии случайного спроса на маршруты и оптимальное назначение, основанное на математическом ожидании спроса, почти никогда не совпадают. В данной работе не приводится алгоритма решения таких задач с большой размерностью. Разновидностью модели, используемой в [1], является модель из работы [2], имеющая отличие в экономической постановке. Если в [1] рассматривается транспортная задача с неопределенным спросом, то в [2] изучается производственно-транспортная задача с неопределенным спросом, что позволяет расширить класс решаемых задач.
Эти модели в неявной форме используются многими авторами при выборе производственного плана и расчете транспортных связей [3-6]. Основным недостатком, общим для моделей первого пути изучения производственно-транспортных задач, является то, что численное решения задач находится в тесной зависимости от величины штрафов за неудовлетворение спроса, а выбор штрафов экономически не обосновывается.
Второй путь изучения стохастических задач основывается на представлении задачи линейного программирования с ее случайными данными в виде двухэтапной задачи [5-14]. Экономическая постановка подобных задач состоит в том, что при выбранном способе организации производства порождается такой выход продукции, которой не соответствует случайному спросу. Все же способ организации разумно считать допустимым, если предприятие в состоянии устранить любую возможную невязку между спросом и предложением продукции за счет введения каких-то дополнительных технологических процессов. Предположим, что излишки продукции администрация предприятия может отправить на склад, а недостающую продукцию может докупить на стороне по средней рыночной цене, чтобы выполнить обязательства перед клиентами. И в том, и другом случае предприятие терпит убытки, но, так или иначе, несогласованность между предложением продукции и спросом на эту продукцию можно ликвидировать.
В более общей форме можно предположить, что для устранения невязок между спросом и предложением продукции предприятие может располагать некоторым фиксированным набором технологическим способов производства. Так что сбалансирование предложения продукции со спросом экономико-математически описывается как выбор вектора управления. Естественно считать, что устранение невязок связано с некоторыми дополнительными затратами. Предположим что величину затрат (штрафов) можно описать линейной функцией, а вектор управления производством может быть выбран не единственным способом. Задачу оптимального выбора вектора управления при фиксированной реализации спроса называют задачей второго этапа.
Таким образом, ясно, что второй путь изучения вероятностных (стохастических) линейных задач более перспективен, так как он позволяет решать более широкий круг задач. Но решение оказывается более сложным в математическом отношении. Даже для сравнительно простых задач планирования таких производственных звеньев, какими являются бригада, цех, предприятие, подготовка численного решения сложно из-за сходимости алгоритмов. Простых алгоритмов решения подобных задач пока создано мало, а имеющиеся являются либо приближенными, либо слабо сходящимися, либо дающими большую погрешность. В работе [1] рассмотрен один из путей решения двухэтапной задачи, состоящий в переходе к двойственной задаче с последующим применением алгоритма, основанного на принципе разложения Данцига-Вулфа [15]. Другой пример алгоритма приведен в работе [4].
Точное же решение задачи нахождения оптимального плана в двухэтапной задаче стохастического линейного программирования наталкивается на большую размерность задачи, что ведет к большим затратам на получение результата. При условии, что случайная величина спроса на изделие предприятия имеет конечное число реализаций, решение задач такого объема затруднительно обычными линейными методами. В этом случае используют метод решения, предложенный работе [2].
При случайной величине спроса, равномерно распределенной в заданных интервалах, целевая функция оказывается квадратичной. Для других непрерывных законов распределения спроса задача может быть сведена к квадратичному приближению посредством аппроксимации случайной величины суммой равномерно распределенных случайных величин. Если такая аппроксимация неудобна (она может привести к значительному увеличению числа условий и числа переменных), то для решения задач можно воспользоваться методом переменных коэффициентов, указанных Данцигом [1]. По-видимому, указанные выше трудности привели к тому, что двухэтапные задачи в настоящее время мало используются в экономике.
Третий путь изучения стохастических линейных задач состоит в том, что рассматривается задача со случайными данными при вероятностных ограничениях [5-7, 9-14]. Экономическая постановка задачи заключается в том, что требуется оптимизировать деятельность предприятия при фиксированной технологической матрице способов производства и случайном векторе спроса на изделия данного предприятия при условии, что удовлетворение спроса должно превышать заданную вероятность. Известные задачи с вероятностными ограничениями отличаются лишь целевыми функциями. В одних задачах ищется экстремум математического ожидания суммарных затрат, в других в качестве целевой функции принимается математическое ожидание квадрата отклонения линейной формы от заданного числа, в третьих требуется найти такой вектор, при котором достигается максимум вероятности превышения линейной формой заданного числа.
В работах [1, 5] рассмотренные задачи сводятся к детерминированным задачам выпуклого программирования, а сведение к задаче выпуклого программирования связано с плотностью распределения составляющих случайного вектора ограничений. В зависимости от конкретных условий, в которых планируется производство, рассмотренные раньше модели третьего вида могут быть взаимно заменяемыми. Класс данных задач еще плохо изучен, мало задач доведено до численного решения. Поэтому о достоинствах и недостатках третьего пути развития судить трудно.
Литература
1. Данциг Дж. Линейное программирование, его обобщение и применение. — М.: Прогресс, 1966.
2. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. — М.: Советское радио, 1966. — 428 с.
3. Хедли Дж. Нелинейное и динамическое программирование. — М.: Наука, 1967. — 508 с.
4. Гольштейн Е.Г. Выпуклое программирование. Элементы теории. — М.: Наука, 1970. — 68 с.
5. Юдин Д.Б. Математические методы управления в условиях неполной информации. — М.: Советское радио, 1974.
6. Юдин Д.Б. Задачи и методы стохастического программирования. — М.: Советское радио, 1979.
7. Ермольев Ю.М. Методы стохастического программирования. — М.: Наука, 1976. — 240 с.
8. Ермольев Ю.М., Ястремский А.И. Стохастические модели и методы в экономическом планировании. — М.: Наука, 1979. — 256 с.
9. Сартания Т.Ш. Анализ стохастических экономических процессов. — Тбилиси: Изд. Тбилисского Университета, 1982. — 215 с.
10. Валтер Я. Стохастические модели в экономике. — М.: Статистика, 1976. — 231 с.
11. Аоки М. Оптимизация стохастических систем. — М.: Наука, 1971.
12. Вазан М. Стохастическая аппроксимация. — М.: Мир, 1974.
13. Кардаш В.А., Раппорт Э.О. Моделирование экономических процессов в сельском хозяйстве. — Новосибирск: Наука, 1979.
14. Кардаш В.А. Введение в стохастическую оптимизацию. Кн. 1 и 2. — Новочеркасск: Изд. НГТУ, 1995, 1996.
15. Danzig G.B. and Wolfe P. Decomposition principle of linear programs// Operations Research, No. 8, 1960.