Динамическое программирование (стр. 4 из 10)
Отличие данной задачи с задачей с фиксированными доплатами в том, что фиксированные доплаты входят не только в целевую функцию, но и в ограничения.
Сведение (7)-(10) к ЗЦП основано на использовании верхних границ для переменных xij - Mij .
Найдем эти границы:
А) из (9) имеем xijbj 
времени и определять был или не был совершен рейс. Получили модель:
(15)(16)
Модель задачи выпуска продукции с разрывной целевой функцией
Одним из источников возникновения дискретности является разрывная целевая функция.
Пусть xj - объем выпускаемой продукции типа j , c j - прибыль за комплект продукции j .
Предполагается, что прибыль получается только за готовые комплекты, отвечающие целочисленным значениям xj .
aij - удельные затраты ресурса на 1 ед. продукции.
Максимизировать прибыль для описанного производства.
Сведем задачу к частично целочисленной. Введем дополнительные целочисленные z j Z , которые ин- 
Модель многоэкстремальной задачи оптимизации
Многоэкстремальную задачу можно рассматривать как задачу оптимизации с линейным целевым функционалом и с невыпуклой или несвязной областью определения.
Такую область можно точно или приближенно представить в виде объединения конечного числа выпуклых областей (при линейных ограничениях – выпуклых многогранниках).
Затем вводя целочисленные переменные свести задачу к частично целочисленной.
Пусть невыпуклая область M представляет собой объединение многогранников M M1 M 2 . Каждый из многогранников описывается системой ограничений: 
Обозначим левые части через g1 x , g2 x .Пусть известно число b, для которого справедливо:
X, т.е. найдены верхние границы.
X
Сведем задачу к ЧЗЦП, вводя y {0,1} . 
0 , то работаем во второй области, y 1 в первой. Т.о., через y «связали» невыпуклую область.Задачи логического проектирования: задача о расположении производственных единиц
Задачи логического проектирования – самое молодое направление ЛП. Его применение связано с вопросами проектирования логических устройств, связанных с теорией кибернетики дискретного анализа.
Задача о расположении произодственных единиц: имеется i 1, m производственных единиц, или центров. Карта возможного расположения центров имеет j 1, n мест. Заданы затраты, связанные с помещением центра i на место j - затраты на установку cij .Известны также затраты, связанные с перемещиеним i на место j , называюся «расстоянием» - dij . Кроме этого заданы производственные потоки по пути ( i, j) - fij . Целью задачи является закрепление центров по местам, минимизирующие суммарные затраты.
Пусть mn .Модель: каждое назначение центров по местам представляет собой перестановки чисел 1,..., n. Для каждого назначения заданы:
1) затраты, зависящие от назначения i на место pi ,( p1, p2,..., pn ) cipi (непосредственные затраты) 2) затраты, зависящие от пар назначений (затраты на взаимосвязь центров) d pi p j .
Причем затраты при перемещении центра i в место pi и центра j в место p j равны произведению fij
на d pi pj .
Таким образом, в соответствие с постановкой, чтобы реализовать функцию цели нужно найти перестановку p1, p2,..., pn чисел от 1 до n , минимизирующие суммарные затраты на назначение и взаимосвязь центров. 
f d pi p j min 
Примечание. В случае, когда производственная единица может быть помещена не в любое место, а лишь в одно из мест заданного списка Si , появляются ограничения pi Si, i 1, m.Задача является экстремально-комбинаторной. Сведем ее к ЗЦП введя допущения:
1) производственные центры не зависят друг от друга, т.е. f 0 .Введем переменные xij - центр i помещен на место j : xij
Таким образом, получили задачу о назначении.
Пусть в некоторой задаче МП помимо обычных условий есть условия вида h1( x1,..., x n)0, h2( x1,..., x n)0 (**) 
h1, h2 -заданные линейные функции; известны верхняя и нижняя границы h1 ( h1, h1) и нижняя граница h2h2 .Действуют так:
Условия (**) перепишем в виде: либо h1( x) 0, h2( x)0, либо h1( x)0 Вводим переменную y {0,1} . Запишем условия в виде: h1( x) h1( x) y h1( x) h1( x)(1 y) .h2 ( x) h2 ( x) y
Записанная система неравенств не содержит логических условий и реализует условия «либо-либо». Кроме рассмотренных, к особым относятся задачи многоэкстремальные на незамкнутых ОДР с разрывными функциями цели другого рода и другие.
1.2 КЛАССИФИКАЦИЯ ЧИСЛЕННЫХ МЕТОДОВ; ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ МЕТО-
ДОВ РЕШЕНИЯ ЗЦП
Все методы делятся на точные и приближенные. Точные методы делятся на 2 основные группы:
1) методы, основанные на идеях направленного перебора вариантов – методы ветвей и границ (Лэнд и Дойг, Литтл);
2) методы, суть которых состоит в численной реализации ЗЦП с дополнительным условием – правильного отсечения. Это методы отсечения (алгоритм Гомори). Методы ветвей и границ
Общая схема метода состоит в двухэтапном решении задачи. На первом этапе производится поиск экстремума функции цели на расширенной ОДР. На втором этапе последовательное пошаговое уточнение решения первого этапа.
Идея метода состоит в усовершенствовании процесса перебора вариантов. Сокращение числа вариантов достигается за счет того, что удается оценить сверху значение функции цели на разбиениях расширенного множества допустимых решений и затем исключить из рассмотрения те разбиения, для которых оценка оказалась слишком малой.
Оценки называются границами, а поиск решения проводится по ветвям дерева вариантов.
Методы отсечений
Методы отсечений используют 2 идеи: пошаговую линейную аппроксимацию ЗЦП, переход от шага к шагу с помощью правильного отсечения.
Общая схема метода такова:
Рассматривается ЗЛП, соответствующая исходной ЗЦП. ОДР для нее - выпуклый многогранник. Совокупность целочисленных точек в нем является множеством допустимых решений задачи и не является выпуклым. К ограничениям ЗЦП последовательно добавляются новые – они связывают внешние целочисленные точки последовательных решений.
В результате на каждом шаге получается новый выпуклый многоугольник, представляющий собой ОДР для новой ЗЦП. При это, вершина, соответствующая нецелочисленному решению отсекается. За конечное число шагов мы придем к вершине, координаты которого целочисленные.