Динамическое программирование

СОДЕРЖАНИЕ
ОБЩАЯ ХАРАКТЕРИСТИКА МОДЕЛИ ЦП; ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ МЕТОДОВ ЦП
__________________________________________________________________________ 1
1.1 ПРЕДМЕТ ДО (ЦП) ___________________ Ошибка! Закладка не определена.
1.1.1 Предмет ДО ___________________________________________________________ 2
1.1.2 Классификация прикладных задач ________________________________________ 2
1.1.3 Классификация моделей ЦП _____________________________________________ 4
Задача о загрузке бомбардировщика (1955, США). _______________________________ 4
Задача о ранце (о контейнерах, о перевозках). ___________________________________ 4
Простейшая модель реконструкции. ___________________________________________ 5
Задача о развитии экономической зоны ________________________________________ 6
Задача о коммивояжере ______________________________________________________ 7
Задача о назначении_________________________________________________________ 8
Задачи теории расписаний (календарного планирования) _________________________ 8
Задача о покрытии _________________________________________________________ 10
Неоднородная ТЗ с фиксированными доплатами ________________________________ 10
Распределительная задача (обобщенная ТЗ) ____________________________________ 11
Распределительная задача с фиксированными доплатами ________________________ 12
Модель задачи выпуска продукции с разрывной целевой функцией ________________ 13
Модель многоэкстремальной задачи оптимизации ______________________________ 14
Задачи логического проектирования: задача о расположении производственных единиц14
1.2 КЛАССИФИКАЦИЯ ЧИСЛЕННЫХ МЕТОДОВ; ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ
МЕТОДОВ РЕШЕНИЯ ЗЦП_________________________________________________ 16
1.3 МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ __________________________________________ 16
1.3.1 Схема метода ветвей и границ ___________________________________________ 16
1.3.2. Алгоритм Лэнда и Дойга _______________________________________________ 17
1.3.3 Алгоритм Литтла _____________________________________________________ 18 1.3.4 Схема алгоритма Литтла _______________________________________________ 19
1.4 МЕТОДЫ ОТСЕЧЕНИЯ. ПЕРВЫЙ АЛГОРИТМ ГОМОРИ ___________________ 21
1.4.1 Первый алгоритм Гомори ______________________________________________ 21
1.4.2 Алгоритм двойственного симплекс-метода ________________________________ 22 1.4.3 Геометрическая интерпретация первого алгоритма Гомори __________________ 22
1.5 ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗЦП _____________________________ 23 1.5.1 Метод ближайшего соседа ______________________________________________ 23 1.5.2 Задача о контейнерных перевозках _______________________________________ 23
1.5.3 Метод Фогеля для решения задачи о назначении ___________________________ 24
1.6 ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ.
АДДИТИВНЫЙ МЕТОД БАЛАША __________________________________________ 25 1.6.1 Описание идеи аддитивного алгоритма ___________________________________ 26
1.6.2 Общая схема алгоритма Балаша _________________________________________ 26 1.6.3 Правила построения частичного решения _________________________________ 27
1.6.4 Алгоритм метода Балаша _______________________________________________ 28
1.6.5 Сведение ЗЦП в общей постановке к задаче с булевыми переменными ________ 29
1.7 ПРИБЛИЖЕННОЕ РЕШЕНИЕ. ИСПОЛЬЗОВАНИЕ ТОЧНЫХ МЕТОДОВ И ТОЧНОРЕШАЕМЫХ
ЗАДАЧ __________________________________________________________________ 29
1.7.1 Оценка качества приближенного решения291.7.2 Использование точно решаемых задач для получения приближенного решения31ОБЩАЯ ХАРАКТЕРИСТИКА МОДЕЛИ ЦП; ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ МЕТОДОВ ЦП
1.1.1 Предмет ДО
ЦП–часть математического программирования, изучающие экстремальные задачи на конечных множествах или нецелочисленных решетках. В терминах ЦП формулируется широкий круг прикладных задач оптимизации, связанных с неделимостью, фиксированными доплатами, условиями логического типа, с наличием стандартов при проектировании, комбинаторные задачи.
ДП является одним из наиболее важных и сложных разделов МП. Интерес к дискретным экстремальным задачам определяется не только широким кругом приложений, но и органической связью инструментария реализации дискретных задач с другими разделами МП и математики.
Проблематика ДП связана с дискретной и целочисленной математикой (теория чисел, математическая логика, теория графов, теория конечных групп и др.), а также использует теорию ЛП, теорию двойственности, теорию численных методов, методов случайного поиска, методов имитационного моделирования. Прикладным аспектом ДП являются многие задачи экономики, планирования, управления, проектирования; в рамках ДП также формализуются задачи с логическими условиями, многоэкстремальные задачи. В качестве поля проблем при постановке задач ДП используются различные проблемы и процессы экономического оптимизационного характера.
Задачи ДО характеризуются в виде модели ЦП вида:
Если f ( X ) , где X ( x 1 ,..., x n ) - нелинейная функция, то имеем нелинейную задачу ЦП (НЗЦП); если f ( X ) - линейная, то ЛЗЦП.
Прикладной аспект ДО рассматривает в основном ЛЗЦП вида:
Если последние ограничения накладываются на все j , то задача полностью целочисленная, если на часть
j , то частично целочисленная.
1.1.2 Классификация прикладных задач
Рассмотрим класс прикладных задач по источникам возникновения целочисленности.
Требования целочисленности компонент вектора X вытекает из постановки задачи. Выделяют следующие основные источники целочисленности: 1) Задачи с неделимостями.
В таких задачах физическая неделимость единицы x j есть требование постановки, т.е. физическая сущность x j такова, что x j могут принимать только целочисленные значения. Это требование возникает в случаях, когда:
А) используемыми переменными являются крупные объекты (количество самолетов, турбин, заводов и т.д.)
Б) интерпретация результатов решения задачи такова, что требования целочисленности подразумевается априори. К таким постановкам относятся задачи, использующие в качестве интенсивности производства или распределения некоторые стандартные единицы – модули, комплексы машин и т.д.
Применение:
- задачи оптимизации средств в доставке грузов;
- задачи минимизации числа транспортных единиц для осуществления заданного графика перевозок;
- задачи минимизации порожнего пробега автомобилей при реализации заданного графика; - задачи оптимизации и комплектования стандартными модулями некоторого производства;
- И т.д.
2) Задачи размещения.
Постановка задачи предполагает выбор вариантов плановых решений из набора возможных таким образом, чтобы совокупность вариантов оптимизировала суммарный показатель качества.
Тогда формализация множества вариантов плановых решений для некоторого производственного объекта возможно только во множестве Z .
Применение:
- задача планирования, развития и размещения производства;
- задача специализации; - задача кооперирования.
3) Комбинаторные задачи.
Данный тип прикладных задач делится на 2 класса:
- задачи, укладывающиеся в схему классической задачи о коммивояжере; - задачи теории расписаний.
Формальная схема постановки: найти путь минимальной длины проходящий раз и только раз через каждую вершину графа, непрерывный и заканчивающийся в исходной вершине.
Применение: задачи нахождения маршрутов развозки груза, минимизирующие пробег.
Формальная постановка задачи теории расписаний: упорядочить во времени использование системы машин для обработки некоторого множества изделий.
Применение: большинство задач организации производственного процесса.
4) Задачи о покрытии; задачи ДО сетей (другие комбинаторные задачи).
Формальная схема постановки задачи о покрытии: найти минимальное подмножество множества ребер данного графа, содержащего все вершины графа.
Применение:
- задача синтеза логических сетей;
- задачи синтеза оптимальных по стоимости, компактности, надежности и т.д. систем переработки информации (управляющих систем).
Формализация схемы постановки задачи ДО сетей: на сети определить разрез с минимальной пропускной способностью, т.е. максимизировать поток через данную сеть.
Применение:
- собственно задачи поиска максимального потока; - транспортная задача по критерию времени.
5) Особые задачи.
Задачи, в которых требование целочисленности в явном виде не входит, но имеются особые требования, относящиеся либо к функции цели, либо к ограничениям, которые выводят данный круг задач за рамки ЛП.
К таким задачам относятся:
- задачи с неоднородной функцией цели на выпуклом многограннике; - задачи, в которых ограничения содержат условия «либо-либо».
Тогда ОДР не является выпуклым многогранником и оказывается либо невыпуклой, либо не связанной областью (обычно объединение нескольких выпуклых многогранников). Такого рода задачи могут быть сведены к ЦЗП вида (2).
1.1.3 Классификация моделей ЦП
1) Модели задач с неделимостями.
Приведем примеры постановок и моделей задач с неделимостями:
Задача о загрузке бомбардировщика (1955, США).
Определить загрузку бомбардировщиков различных типов бомбовыми запасами, чтобы максимизировать суммарный эффект данной системы от боевых операций. Дано: i 1, m - типы бомб, b i - запасы бомб,
j 1, n - типы самолетов, n j - суммарное число боевых вылетов,
k 1, p - типы боевых операций, a ik - эффективность бомбы i на операции k , w k - «вес» операции, оп-
ределенный командованием. Найти:
x ijk - количество бомб типа i , подлежащих загрузке в самолет типа j при его использовании в операции
k ( в боковой бомбодержатель), y ijk - в центральный бомбодержатель.
Задача о ранце (о контейнерах, о перевозках).
Имеется j 1, n предметов веса a j ценностью c j . Задана грузоподъемность контейнера A .
Надо так загрузить контейнер предметами, чтобы суммарная стоимость их была максимальной при условии, что предмет может загружаться в количестве 1 штуки или не загружаться.
Обозначим переменные:
1, еслиберем jыйпредмет , x j
0, иначе .
Модель:
max
Примечания:
- Если ограничений несколько, то будет многомерная задача;
- Если предмет может загружаться в нескольких экземплярах, но не больше d j , тогда вместо требования бивалентности будем иметь:
j .
x j
2) Модели задач размещения.
Простейшая модель реконструкции.
ûé âàðèàíò ïðèíÿò
Данная модель реализует следующую постановку: предлагается j 1, n - способов вариантов реконструкции каждого из k 1, p предприятий, производящих i 1, n видов продукции.
Заданы удельные в единицу времени (имеется ввиду отрезок планирования) выпуски продукции по способам a ij и приведены затраты на осуществление реконструкции по вариантам j c j , N k - множество номеров вариантов реконструкции предприятия k . N k не пересекаются, т.е. N S S .
Примечание. Если варианты в N k пересекаются, то вводится двойная нумерация:
1, если реконструируетсяk приварианте j x kj
0, иначе
Выбрать такой набор вариантов реконструкции для совокупности предприятий числом p , чтобы затраты на осуществление реконструкции были минимальными и при условии, что требуемый объем продукции i будет произведен.
В случае, когда:
- речь идет не о реконструкции, а о основном строительстве, тогда в подмножестве номеров вариантов N k будет только один- вариант строительства;
- задача размещения в этом случае осуществляется или не осуществляется строительство по вариан n n
ту k . Тогда условие выбора единственного варианта 1, p заменяется на 1 .
Приведенная задача не учитывает интересы потребителей (потребности предприятий и оптимизации транспортных потоков). Задачи, которые это учитывают называются производственно-транспортными.
3) Модели комбинаторных задач
Задача о развитии экономической зоны
Задача о развитии экономической зоны – это расширенная задача выбора проектных вариантов.
Пусть имеется m , i 1, m предприятий вновь проектируемых или реконструируемых. Предприятия должны выпускать n видов продукции j 1, n в количествах не менее b j .
Каждое из предприятий i можно реконструировать по одному из заранее разработанных r проектных вариантов k 1, r (если количество вариантов для предприятий разное, то r
Каждый k -ый вариант для предприятия i характеризуется показателями величины выпуска продукции a ij k по вариантам проектов и заданы приведенные затраты на осуществление проекта R i k .
Требуется с минимальными затратами на строительство или реконструкцию предприятий удовлетворить потребности региона по всем видам продукции j в объемах b j .
Задача о развитии экономической зоны – это задача выбора проектных вариантов, в которой планирование развития экономической зоны необходимо выполнить с учетом размещения пунктов потребления продукции и осуществления возможных объемов перевозок. Чтобы это реализовать, дополним постановку так:
Пусть в регионе, представляющий собой совокупность n городов ( i 1, m ) (предприятий), каждое предприятие может перевезти в другой город количество продукции. В регионе существуют j 1, n предприятий, потребляющих однородную продукцию в количествах j .
Заданы затраты на перевозку c ij . Требуется так оптимизировать строительство и реконструкцию предприятий в зоне, чтобы суммарные затраты на строительство предприятий и транспортировку продукции были минимальны.
Введем переменную y ij -объемы перевозок предприятия i к потребителю j . Модель:
Получили частичную ЦЗП, которая решается, например, методом Балаша.
Модификациями транспортной задачи являются: ТЗ с ограниченными пропускными способностями коммуникаций, ТЗ с запретами.
Многие специальные ТЗ сводятся к классической ТЗ: ТЗ с перевалочными пунктами или с промежуточной обработкой, ТЗ с резервированием, ТЗ с дополнительными ограничениями.
К задачам транспортного типа относятся также задача о максимальном потоке и задача о кратчайшем пути. Они называются ТЗ в сетевой постановке.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию