Динамическое программирование (стр. 1 из 10)
СОДЕРЖАНИЕ
ОБЩАЯ ХАРАКТЕРИСТИКА МОДЕЛИ ЦП; ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ МЕТОДОВ ЦП
__________________________________________________________________________ 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( x1,..., xn ) - нелинейная функция, то имеем нелинейную задачу ЦП (НЗЦП); если f ( X) - линейная, то ЛЗЦП.Прикладной аспект ДО рассматривает в основном ЛЗЦП вида:
Если последние ограничения накладываются на все j , то задача полностью целочисленная, если на часть
j , то частично целочисленная.
1.1.2 Классификация прикладных задач
Рассмотрим класс прикладных задач по источникам возникновения целочисленности.
Требования целочисленности компонент вектора X вытекает из постановки задачи. Выделяют следующие основные источники целочисленности: 1) Задачи с неделимостями.
В таких задачах физическая неделимость единицы xj есть требование постановки, т.е. физическая сущность xj такова, что xj могут принимать только целочисленные значения. Это требование возникает в случаях, когда:
А) используемыми переменными являются крупные объекты (количество самолетов, турбин, заводов и т.д.)
Б) интерпретация результатов решения задачи такова, что требования целочисленности подразумевается априори. К таким постановкам относятся задачи, использующие в качестве интенсивности производства или распределения некоторые стандартные единицы – модули, комплексы машин и т.д.
Применение:
- задачи оптимизации средств в доставке грузов;
- задачи минимизации числа транспортных единиц для осуществления заданного графика перевозок;
- задачи минимизации порожнего пробега автомобилей при реализации заданного графика; - задачи оптимизации и комплектования стандартными модулями некоторого производства;
- И т.д.
2) Задачи размещения.
Постановка задачи предполагает выбор вариантов плановых решений из набора возможных таким образом, чтобы совокупность вариантов оптимизировала суммарный показатель качества.
Тогда формализация множества вариантов плановых решений для некоторого производственного объекта возможно только во множестве Z .
Применение:
- задача планирования, развития и размещения производства;
- задача специализации; - задача кооперирования.
3) Комбинаторные задачи.
Данный тип прикладных задач делится на 2 класса:
- задачи, укладывающиеся в схему классической задачи о коммивояжере; - задачи теории расписаний.
Формальная схема постановки: найти путь минимальной длины проходящий раз и только раз через каждую вершину графа, непрерывный и заканчивающийся в исходной вершине.
Применение: задачи нахождения маршрутов развозки груза, минимизирующие пробег.
Формальная постановка задачи теории расписаний: упорядочить во времени использование системы машин для обработки некоторого множества изделий.
Применение: большинство задач организации производственного процесса.
4) Задачи о покрытии; задачи ДО сетей (другие комбинаторные задачи).
Формальная схема постановки задачи о покрытии: найти минимальное подмножество множества ребер данного графа, содержащего все вершины графа.
Применение:
- задача синтеза логических сетей;
- задачи синтеза оптимальных по стоимости, компактности, надежности и т.д. систем переработки информации (управляющих систем).
Формализация схемы постановки задачи ДО сетей: на сети определить разрез с минимальной пропускной способностью, т.е. максимизировать поток через данную сеть.
Применение:
- собственно задачи поиска максимального потока; - транспортная задача по критерию времени.
5) Особые задачи.
Задачи, в которых требование целочисленности в явном виде не входит, но имеются особые требования, относящиеся либо к функции цели, либо к ограничениям, которые выводят данный круг задач за рамки ЛП.
К таким задачам относятся:
- задачи с неоднородной функцией цели на выпуклом многограннике; - задачи, в которых ограничения содержат условия «либо-либо».
Тогда ОДР не является выпуклым многогранником и оказывается либо невыпуклой, либо не связанной областью (обычно объединение нескольких выпуклых многогранников). Такого рода задачи могут быть сведены к ЦЗП вида (2).
1.1.3 Классификация моделей ЦП
1) Модели задач с неделимостями.
Приведем примеры постановок и моделей задач с неделимостями:
Задача о загрузке бомбардировщика (1955, США).
Определить загрузку бомбардировщиков различных типов бомбовыми запасами, чтобы максимизировать суммарный эффект данной системы от боевых операций. Дано: i 1, m - типы бомб, bi - запасы бомб,j 1, n - типы самолетов, nj - суммарное число боевых вылетов,
k 1, p - типы боевых операций, aik - эффективность бомбы i на операции k , wk - «вес» операции, оп-
ределенный командованием. Найти:
xijk - количество бомб типа i , подлежащих загрузке в самолет типа j при его использовании в операции