- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
4.3. Стохастическое программирование. Основные понятия
Определение: Оптимизационные задачи и их модели, в которых вся исходная информация задана строго однозначно, называются детерминированными.
В действительности детерминированные модели часто оказываются неадекватными реальным процессам экономики. Это объясняется неполнотой, неточностью данных, на основе которых формируется модель. В одних случаях некоторые параметры носят вероятностный характер. Тогда говорят о ситуациях, связанных с риском. В других случаях имеющаяся информация не позволяет составить представление о характере изменения параметров, описываемых случайный процесс. Такие ситуации называются неопределенными.
Определение: Оптимизационные задачи, при постановке которых нет исчерпывающих данных об их условиях, называются стохастическими.
Поскольку стохастические задачи приходится решать при недостаточной информации, это ведет к снижению экономической эффективности получаемых решений. Для исследования описываемых ситуаций разрабатываются специальные методы, объединенные в разделе математического программирования, называемом стохастическим программированием.
Стохастическое программирование изучает теорию и методы решения условных экстремальных задач при неполной информации об их условиях.
Различают пассивное и активное стохастическое программирование.
Определение: Пассивное стохастическое программирование – совокупность приемов, позволяющих находить наилучшее решение и экстремальное значение целевых функций в оптимизационных задачах со случайными исходными данными. При этом используются идеи параметрического программирования.
Определение: Активное стохастическое программирование – это совокупность приемов, позволяющих развивать методы выбора решений в условиях риска и неопределенности.
В стохастическом программировании исследуются одно-, двух-, многоэтапные задачи.
Определение: Одноэтапными называют задачи, в которых последовательность поступления исходной информации не имеет значения при выборе решения задачи. Оно принимается один раз и в дальнейшем не изменяется. Такие задачи могут порождаться детерминированными оптимизационными задачами, когда используемые данные теряют определенность и принимают случайный характер.
В одноэтапных задачах по-разному выбирается целевая функция и характер ограничений. В качестве целевых функций могут рассматриваться вероятность попадания решения в некоторую, случайную область или математическое ожидание некоторой функции от решения.
На практике чаще всего встречаются двухэтапные стохастические задачи. Подобные задачи возникают при планировании выпуска продукции в случае, когда отсутствуют данные о спросе, о ней. В такой ситуации сначала принимается предварительное решение об объеме выпуска на основе имеющейся информации (1 этап), затем после установления спроса принимается корректирующее решение (2 этап). При этом предварительное решение не должно исключать коррекции на втором этапе. Кроме того, предварительный и корректирующие планы согласовываются так, чтобы обеспечивались минимальные средние затраты за оба этапа.
Для ряда конкретных постановок двухэтапных стохастических задач Разработаны достаточно надежные методы решения.
В многоэтапных (динамических) задачах по мере получения информации о развивающемся процессе имеется возможность неоднократно корректировать решение, учитывая исходные ограничения и априорные статистические характеристики случайных параметров, описывающие процесс на каждом этапе. Многоэтапные задачи могут быть как с жесткими, так и с вероятностными ограничениями.