- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
Дискретное программирование – это раздел математического программирования и изучающий экстримальные задачи, в которых на искомые переменные налагаются условия целочисленности, а область допустимых решений конечна.
Дискретное программирование также называется целочисленным.
Задача о контейнерных перевозках (о рюкзаке или о бомбардировщике).
Контейнер оборудован m отсеками, вместимостью (). Для перевозкиn видов продукции. Виды продукции характеризуются свойствами неделимости. Пусть – расходi-того отсека для перевозки j-той продукции. Обозначим через полезность единицыj-й продукции. Требуется найти план перевозки, при котором прибыль от перевозки максимизируется:
при
Задача о назначении (проблема выбора, о женихах и невестах).
Имеется n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнениемi-м исполнителем j-той работы (i,j=). Нужно так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплён только один исполнитель.
Для составления математической модели задачи обозначим через – факт назначения или не назначенияi-того исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения 1 или 0. Такие переменные называются булевыми.
Так как нужно найти план назначения , который максимизирует суммарную полезность назначения
при
а) каждый исполнитель назначается только на одну работу:
б) на каждую работу назначается только один исполнитель:
, - ограничение неотрицательности и целочисленности.
Мы рассмотрели только два примера, можно еще рассмотреть задачу коммивояжера, транспортную задачу с фиксированными доплатами.
3.9. Сущность методов дискретной оптимизации
В первом приближении методы целочисленной оптимизации можно разделить на две группы: точные и приближённые. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить за десятки и тысячи итераций. Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем: исходная задача решается сначала без учёта ограничения целочисленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена, в противном случае к ограничениям исходной задачи добавляются новые, обладающие следующими свойствами:
Полученный нецелочисленный план нарушает это ограничение.
Любой целочисленный допустимый план исходной задачи заведомо удовлетворяет и новому ограничению.
Затем задача решается с учётом нового ограничения. В случае необходимости добавляется ещё одно ограничение и т.д. Геометрически добавления каждого нового ограничения отвечает проведение поверхности, которая отсекает от области допустимых решений некоторую его часть с оптимальной точкой и нецелыми координатами, но не затрагивает ни одной из целочисленных точек этого многогранника.
Для решения задачи дискретного программирования получили широкое распространение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ. Для выявления сущности этого момента воспользуемся известной задачей об отыскании фальшивой монеты. Пусть в мешке с монетами одинакового достоинства имеется одна фальшивая, отличающаяся бόльшим весом, которую будем искать по средствам взвешивания на рычажных весах без гирь. Поступим так: Разделим содержимое мешка на 2 равные по количеству монет части. В случае, если число n монет – нечётное – разделим n-1 монет на 2 равные части. Положим на чашки весов равные по количеству монет части. Если чашки весов уравновесятся, то отложенная монета – фальшивая, в противном случае она находится в более тяжёлой части, с которой поступим аналогичным образом. Так до тех пор, пока не найдём фальшивую монету. Здесь деление мешка есть деление множества на подмножества, т.е. разбиение области допустимых решений на непересекающиеся подмножества. Взвешивание каждой части соответствует оценке целевой функции на подмножестве (оценке верхней или нижней границы). Если при этом удастся найти некоторый план, для которого верхняя (нижняя) оценка на множестве плана одного из подмножеств равна значению функции в этой точке и не меньше (не превосходит) оценок сверху (снизу) на всех подмножествах, то этот план оптимальный. Если такой план не обнаружен, то продолжается процесс разбиения, начиная его с подмножества, имеющего самую высокую (низкую) оценку и т.д. Поскольку множество всех планов задачи конечно, то в конце концов план будет оптимальный.