Учебная книга: Динамическое программирование СОДЕРЖАНИЕ ОБЩАЯ ХАРАКТЕРИСТИКА МОДЕЛИ ЦП; ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ МЕТОДОВ ЦП __________________________________________________________________________ 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 . Модель: Получили частичную ЦЗП, которая решается, например, методом Балаша. Модификациями транспортной задачи являются: ТЗ с ограниченными пропускными способностями коммуникаций, ТЗ с запретами. Многие специальные ТЗ сводятся к классической ТЗ: ТЗ с перевалочными пунктами или с промежуточной обработкой, ТЗ с резервированием, ТЗ с дополнительными ограничениями. К задачам транспортного типа относятся также задача о максимальном потоке и задача о кратчайшем пути. Они называются ТЗ в сетевой постановке. Задача о коммивояжере Рассмотрим задачу о коммивояжере (КВ). Есть ( n 1) городов, c ij - матрица расстояний. Из города номер 0 выезжает КВ. Надо найти путь минимальной длины, проходящий раз и только раз через каждый город и заканчивался бы в нулевом. 1, переходизiв jесть x ij 0, иначе Модель: 1) . Полученное условие не справедливо, следовательно, условие замкнутости не позволяет затратить часть звеньев на подцикл. Задача о назначении Если условие замкнутости отсутствует, то имеем модель о назначении – есть i 1, n кандидатов на 1, n рабочих должностей, если i -ый кандидат назначается на j , то c j - затраты. Надо так провести все назначения, чтобы суммарные затраты были минимальными: . Задачи теории расписаний (календарного планирования) Задача календарного планирования относится к задачам теории расписания. Имеется m , i 1, m станков и n , j 1, n деталей. Каждая деталь должна пройти обработку на m станках в определенной последовательности, причем операции неделимы. Задана матрица A a ij i j 1 1 , , m n , которая интерпретируется как время для обработки j -ой детали на i -ом станке. Надо найти такую последовательность обработки деталей, которая минимизировала бы продолжительность производственного цикла (общее время выполнения всех работ). Введем обозначение x ij - моменты начала обработки j -ой детали на i -ом станке. Тогда, календарный план есть совокупность элементов x ij , а продолжительность производственного цикла – общее время выполнения всех работ не складывается из x ij . Ограничения: 1) деталь проходит обработку в определенной последовательности. Пусть деталь j сначала обрабатывается на станке i в продолжительности времени a ij , а затем идет на станок k . Тогда моменты начала обработки - x kj x ij a ij (1) Здесь возможны варианты: - деталь ждет обработки на k -ом станке, тогда - деталь не ждет обработки - при a ij 0 деталь j на i -ом станке не обрабатывается по технологии. 2) На одном станке нельзя одновременно обрабатывать две детали j и s . Моменты начала обработки двух деталей должны отстоять как минимум на длину обрабатывания детали, которая идет первой. x isij ( сначалаобрабатывается j ) Но мы не знаем, какая деталь идет первой, поэтому условия x ijis ( сначалаобрабатывается s ) альтернативные, т.е. работает одно или другое. Чтобы реализовать эту ситуацию введем дополнительную целочисленную переменную y ijk . Обозначим верхнюю границу продолжительности производственного цикла через T . Тогда можно записать: T a ij 1 y ijs x is x ij a ij (*) T a is y ijs x ij x is a is (**) x is x ij T Исследуем данную конструкцию: А) x ij x is 0 . Ситуация невозможна, т.к. это означает одновременную обработку двух деталей на станке. В (*) y ijs 0 , (**) y ijs 1 . Б) x ij x is 0 , то (*) y ijs 0 ; (**) y ijs {0,1} . Значит y ijs 0 (единственное возможное значение). В) x ij x is 0 , то (*) y ijs {0,1} ; (**) y ijs 1 . Значит y ijs 1 (единственное возможное значение). Таким образом, формальная конструкция (*) и (**) реализует альтернативные условия. 3) Момент окончания обработки на j ой детали на i -ом станке не превышает искомую длину производственного цикла t : x ij a ij t . Целевая функция задачи f t min . Таким образом имеем модель: f min x kj a ij Вследствие большого разнообразия производственных условий возможностей производства универсальная постановка задачи календарного планирования невозможна. Приведенная постановка является наиболее простой. Ограничения задачи могут быть дополнены следующими: - условиями на сроки окончания отдельных работ; - требование учета различных проиводственных факторов (труд, материалы, оборудование); - требование учета дополнительных производственных факторов, сопровождающих процесс производства – особенностей технологии. В качестве критериев оптимальности в этой задаче может быть использованы и другие критерии, которые делятся на 2 группы: 1) критерии, зависящие от общей продолжительности обработки изделий. К ним относятся: минимум простоев оборудования; максимум показателя использования оборудования; минимум издержек на незавершенное производство 2) критерии, которые являются функцией заданных сроков готовности: минимум суммарного отставания от сроков; минимум издержек, связанных с невыполением работ в срок; минимум числа отстающих работ. 4) Модель задачи о покрытии. Задача о покрытии Общий вид: n c j x j min j 1 n a ij x j b i , i 1, m j 1 x j {0,1}, a ij {0,1} Если c j 1, j , то простая задача о покрытии; если c j R , то взвешенная задача о покрытии. Описание конкретных постановок задач о покрытии проводится на логическом языке в терминах синтеза схем с использованием булевых функций, связывающих входы и выходы устройства. Тогда задачей синтеза является построение схемы, реализующей дополнительную булеву функцию, затем среди полученной совокупности схем выбираются в соответствии с заданным критерием. 5) Особые задачи. Неоднородная ТЗ с фиксированными доплатами В качестве задачи с разрывной функцией цели рассмотрим ТЗ с фиксированными доплатами или неоднородную ТЗ. Постановка: i 1, m - пункты производства, a i - объемы производства; j 1, n - пункты назначения, b i - потребности. Кроме того, по условиям перевозки требуется дополнительно платить d ij ден.ед. независимо от величины груза в случае, если груз перевозится из i в j . Интерпретация доплаты d ij может быть: плата за аренду авто, дорожный сбор на крупных дорожных сооружениях, таможенная политика и т.д. Модель. В связи с новыми условиями целевая функция ТЗ становится принципиально другой. Это функция, в которой прежнее c ij становится зависимой от того, перевозится груз или нет. Здесь переменных целочисленных нет. Чтобы численно реализовать такую модель сведем ее к ЧЦЗ. - определим величины M ij min{ a i , b j } i , j - введем переменные y ij {0,1} и условия x ij M ij y ij . m n Тогда F ( c ij x ij d ij y ij ) . i 1 j 1 Рассмотрим, как работает в оптимальном плане: - если y ij 0 , то x ij 0 ; - если y ij 1 , то x ij M ij неравенство излишнее (по построению); - если x ij 0 , то y ij должен быть нулем, иначе план не оптимальный и его можно улучшить; - Если x ij 0 , то y ij 1 . Таким образом, переменные y ij {0,1} «согласуют» плату за аренду и действие – осуществление перевозки. В схему ТЗ с фиксированными доплатами укладывается также задача о смесях, имеющие фиксированные доплаты (фиксированная стоимость заказа, компоненты смеси, не зависящие от заказываемого количества). Распределительная задача (обобщенная ТЗ) Рассматривается транспортное предприятие с j 1, n транспортными линиями (маршрутами). В соответствии с планом графика по j -ой линии надо выполнить b j рейсов. Фонд наличных транспортных средств (транспортный парк) представлен i 1, m типами транспортных единиц с полными резервами времени a i . Заданы затраты времени на выполнение i -ой транспортной единицей рейса j - t ij и затраты денежных средств c ij . Надо оптимизировать расстановку транспортных единиц по рейсам так, чтобы суммарные затраты были минимальными. Введем обозначение: x ij - количество i -го транспорта на j -ом маршруте. Модель: (2) (3) (4) Распределительная задача с фиксированными доплатами Пусть дополнительно в постановке обобщенной ТЗ нужно учесть следующее: выпуск транспортных средств i на маршрут j связан с дополнительными затратами времени , не зависящие от числа рейсов, и денежных средств d ij . Тогда затраты средств c ij будут зависеть от того, будет ли транспортное средство i содержать хотя бы один рейс по маршруту j или нет. Таким образом: c ij (5) d ij , x ij Аналогично, для затрат времени: t ij ( x ij ) (6) Получили модель: Отличие данной задачи с задачей с фиксированными доплатами в том, что фиксированные доплаты входят не только в целевую функцию, но и в ограничения. Сведение (7)-(10) к ЗЦП основано на использовании верхних границ для переменных x ij - M ij . Найдем эти границы: А) из (9) имеем x ij b j времени и определять был или не был совершен рейс. Получили модель: (15) (16) Модель задачи выпуска продукции с разрывной целевой функцией Одним из источников возникновения дискретности является разрывная целевая функция. Пусть x j - объем выпускаемой продукции типа j , c j - прибыль за комплект продукции j . Предполагается, что прибыль получается только за готовые комплекты, отвечающие целочисленным значениям x j . a ij - удельные затраты ресурса на 1 ед. продукции. Максимизировать прибыль для описанного производства. Сведем задачу к частично целочисленной. Введем дополнительные целочисленные z j Z , которые ин- Модель многоэкстремальной задачи оптимизации Многоэкстремальную задачу можно рассматривать как задачу оптимизации с линейным целевым функционалом и с невыпуклой или несвязной областью определения. Такую область можно точно или приближенно представить в виде объединения конечного числа выпуклых областей (при линейных ограничениях – выпуклых многогранниках). Затем вводя целочисленные переменные свести задачу к частично целочисленной. Пусть невыпуклая область M представляет собой объединение многогранников M M 1 M 2 . Каждый из многогранников описывается системой ограничений: Обозначим левые части через g 1 x , g 2 x . Пусть известно число b , для которого справедливо: X , т.е. найдены верхние границы. X Сведем задачу к ЧЗЦП, вводя y {0,1} . 0 , то работаем во второй области, y 1 в первой. Т.о., через y «связали» невыпуклую область. Задачи логического проектирования: задача о расположении производственных единиц Задачи логического проектирования – самое молодое направление ЛП. Его применение связано с вопросами проектирования логических устройств, связанных с теорией кибернетики дискретного анализа. Задача о расположении произодственных единиц: имеется i 1, m производственных единиц, или центров. Карта возможного расположения центров имеет j 1, n мест. Заданы затраты, связанные с помещением центра i на место j - затраты на установку c ij . Известны также затраты, связанные с перемещиеним i на место j , называюся «расстоянием» - d ij . Кроме этого заданы производственные потоки по пути ( i , j ) - f ij . Целью задачи является закрепление центров по местам, минимизирующие суммарные затраты. Пусть mn . Модель: каждое назначение центров по местам представляет собой перестановки чисел 1,..., n . Для каждого назначения заданы: 1) затраты, зависящие от назначения i на место p i ,( p 1 , p 2 ,..., p n ) c ip i (непосредственные затраты) 2) затраты, зависящие от пар назначений (затраты на взаимосвязь центров) d p i p j . Причем затраты при перемещении центра i в место p i и центра j в место p j равны произведению f ij на d p i p j . Таким образом, в соответствие с постановкой, чтобы реализовать функцию цели нужно найти перестановку p 1 , p 2 ,..., p n чисел от 1 до n , минимизирующие суммарные затраты на назначение и взаимосвязь центров. f d p i p j min Примечание. В случае, когда производственная единица может быть помещена не в любое место, а лишь в одно из мест заданного списка S i , появляются ограничения p i S i , i 1, m . Задача является экстремально-комбинаторной. Сведем ее к ЗЦП введя допущения: 1) производственные центры не зависят друг от друга, т.е. f 0 . Введем переменные x ij - центр i помещен на место j : x ij Таким образом, получили задачу о назначении. Пусть в некоторой задаче МП помимо обычных условий есть условия вида h 1 ( x 1 ,..., x n )0, h 2 ( x 1 ,..., x n )0 (**) h 1 , h 2 -заданные линейные функции; известны верхняя и нижняя границы h 1 ( h 1 , h 1 ) и нижняя граница h 2 h 2 . Действуют так: Условия (**) перепишем в виде: либо h 1 ( x ) 0, h 2 ( x )0, либо h 1 ( x )0 Вводим переменную y {0,1} . Запишем условия в виде: h 1 ( x ) h 1 ( x ) y h 1 ( x ) h 1 ( x )(1 y ) . h 2 ( x ) h 2 ( x ) y Записанная система неравенств не содержит логических условий и реализует условия «либо-либо». Кроме рассмотренных, к особым относятся задачи многоэкстремальные на незамкнутых ОДР с разрывными функциями цели другого рода и другие. 1.2 КЛАССИФИКАЦИЯ ЧИСЛЕННЫХ МЕТОДОВ; ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ МЕТО- ДОВ РЕШЕНИЯ ЗЦП Все методы делятся на точные и приближенные. Точные методы делятся на 2 основные группы: 1) методы, основанные на идеях направленного перебора вариантов – методы ветвей и границ (Лэнд и Дойг, Литтл); 2) методы, суть которых состоит в численной реализации ЗЦП с дополнительным условием – правильного отсечения. Это методы отсечения (алгоритм Гомори). Методы ветвей и границ Общая схема метода состоит в двухэтапном решении задачи. На первом этапе производится поиск экстремума функции цели на расширенной ОДР. На втором этапе последовательное пошаговое уточнение решения первого этапа. Идея метода состоит в усовершенствовании процесса перебора вариантов. Сокращение числа вариантов достигается за счет того, что удается оценить сверху значение функции цели на разбиениях расширенного множества допустимых решений и затем исключить из рассмотрения те разбиения, для которых оценка оказалась слишком малой. Оценки называются границами, а поиск решения проводится по ветвям дерева вариантов. Методы отсечений Методы отсечений используют 2 идеи: пошаговую линейную аппроксимацию ЗЦП, переход от шага к шагу с помощью правильного отсечения. Общая схема метода такова: Рассматривается ЗЛП, соответствующая исходной ЗЦП. ОДР для нее - выпуклый многогранник. Совокупность целочисленных точек в нем является множеством допустимых решений задачи и не является выпуклым. К ограничениям ЗЦП последовательно добавляются новые – они связывают внешние целочисленные точки последовательных решений. В результате на каждом шаге получается новый выпуклый многоугольник, представляющий собой ОДР для новой ЗЦП. При это, вершина, соответствующая нецелочисленному решению отсекается. За конечное число шагов мы придем к вершине, координаты которого целочисленные. 1.3 МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ 1.3.1 Схема метода ветвей и границ 1) Итераций K 0 . Для расширенной ОДР X (0) полученной из исходной X исключением части ограничений определяется максимальное значение целевой функции задачи: f ( x ) max, x X (1). Обозначим максимальное значение f ( x ) f ( x 0 ) . Это значение одновременно является верхней границей функции цели на исходном множестве допустимых планов: M ( X ) f ( x 0 ), x 0 X (0) (2). Если при этом план x (0) удовлетворяет исходному множеству допустимых планов x (0) X , то процесс решения задачи (1) закончен и x (0) - искомое решение. 2) K 1,2,... В соответствии с выбранным способом, отвечающим специфике задачи (1) производится разбиение перспективного подмножества допустимых планов (для K 1 такое подмножество одно, это X (0) ) на непересекающиеся подмножества: X r ( k ) , r 0,..., r k : X t ( k ) X sr ( k ) (3) r -индекс подмножества, s - идентификатор множества предыдущего шага. Причем известно, что в X s 0 оптимальных решений нет. Помня, что в формуле (3) должен быть двойной индекс для дальнейшего упрощения изложения опустим его. Тогда оценки M ( x r ( k ) ), r 1, k ищутся как максимумы целевой функции на подмножествах X r ( k ) , r 1, r k . Если план x l ( k ) , приносящий максимум f ( x ) на некотором подмножестве X l ( k ) одновременно удовлетворяет исходной системе ограничений x l ( k ) X и является решением на итерации K , то этот план является претендентом на решение исходной задачи. 3) В процессе решения задачи подмножество X 0 увеличивается за счет включения в него X t ( k ) в следующих случаях: а) если в результате сравнения оценок на разбиениях внутри итерации K хотя бы для одного подмноже- ства X r ( k ) максимум f ( x ) на подмножестве X t ( k ) меньше максимума f ( x ) на подмножестве X r ( k ) : X t ( k ) X 0 : M ( X t ( k ) ) M ( X r ( k ) ), t , r R ( k ) , где R ( k ) - подмножество индексов разбиений на итерации K . б) если в результате сравнения оценок между итерациями K , P , KP хотя бы для одной итерации P найдется такое подмножество X l ( p ) , что максимум f ( x ) на подмножестве X t ( k ) меньше максимума f ( x ) на подмножестве X l ( p ) , т.е. X tk X 0 : M ( X l ( p ) ) M ( X tk ), t R ( k ) , l R ( p ) , p k 1,...,1 Ветви, включенные в X 0 являются тупиковыми. 4) Решением задачи (1) является лучшее из решений-претендентов; если в результате разбиения последнее подмножества процесса решения оказалось пустым и решений-претендентов нет, то исходная задача (1) целочисленных решений не имеет. Процесс решения задачи (1) с использованием методов ветвей и границ иллюстрируется так называемым деревом ветвлений. Для реализации описанной выше схемы в виде конкретного алгоритма необходимо указать: - способ расширения ОДР; - правило ветвления (разбиения на подмножества); - правило вычисления границ (оценок). 1.3.2. Алгоритм Лэнда и Дойга Алгоритм применяется для решения частично целочисленных задач. Конкретизация алгоритма в соответствии с схемой метода ветвей и границ следующая: 1) способ расширения ОДР. В качестве расширения X (0) исходной области ограничений X используют область ограничений ЗЛП, соответствующая исходной ЗЦП. 2) правило ветвления. Пусть X s ( k 1) - перспективное подмножества шага k 1 . Разбиение его на подмножества X sr ( k ) , r 1, r k производится по правилам: - из плана x s ( k 1) выбирается нецелочисленная компонента x * j ; - из ОДР, соответствующей этому плану x s ( k 1) исключается значения x * j , лежащие в промежутке: ([ x * j ];[ x * j ] 1) . Таким образом, при разбиении X s ( k 1) получаем два подмножества X 1( k ) , X 2( k ) , где: X 1 ( k ) { x 1 ( k ) : x 1 ( k ) X s ( k 1) , x j [ x * j ]}, . (4) X 2 ( k ) { x 2 ( k ) : x 2 ( k ) X s ( k 1) , x j [ x * j ] 1} Если оценки на некоторых подмножествах предыдущего шага одинаковы, то просматриваются все эти ветви с целью получения альтернативного решения. 3) Правило вычисления границ (оценок). Способ разбиения множеств на подмножество на каждом шаге K 0 генерирует две ЗЛП с целевыми функциями исходной задачи (1) и ОДР X 1 ( k ) , X 2 ( k ) . Границами M ( X 1 ( k ) ), M ( X 2 ( k ) ) являются максимальные значения исходной целевой функции на соответствующих ОДР f ( x r ( k ) ), r 1, r k . Примечание 1 . Если коэффициенты функции цели при переменных, на которые накладываются условия целочисленности целые, а при остальных равны нулю, то оценку можно усилить: Z r ( k ) ] f ( x r ( k ) )[, r 1, r k . Здесь ] [ - наименьшее целое, не меньшее . Примечание 2. При построении дерева ветвлений можно следовать по ветвям, приводящим к скорейшему получению 1-го претендента по решению исходной задачи – схема одностороннего обхода дерева. Ветви, не включенные в обход называются оборванными; их оценка вычисляется после первого рекорда. По другой схеме просматриваются и производятся ветвления одновременно по всем подмножествам итерации K . Первый способ ветвления предпочтительнее, т.к. он нагляднее в интерпретации и экономичнее при программировании метода. В вычислительном аспекте алгоритм Л. и Д. сводится к решению серий ЗЛП. Конечность алгоритма обеспечивается тем, что исходное множество дополнительных планов ограничено. Альтернативные решения ищутся в том случае, если в условии задачи его требовалось найти. 1.3.3 Алгоритм Литтла Алгоритм Литтла укладывается в схему методов ветвей и границ и предназначен для решения прикладных задач ЦП специальной структуры. Классической постановкой такой задачи является задача о коммивояжере, алгоритм решения которой в терминах теории графов можно сформулировать так: Среди множества допустимых гамильтоновых контуров (ГК) выбрать контур минимальной длины. Алгоритм Литтла реализует схему направленного частичного перебора вариантов ГК. Конечность алгоритма следует из конечного числа ГК в допустимой области рассматриваемой задачи. Определим основные положения алгоритма Литтла (АЛ) построения его как метода ветвей и границ. 1) Способ расширения ОДР. Для расширения исходной области ограничений X опускается ограничение замкнутости маршрута. В результате получим область ограничения в задаче о назначении. В качестве матрицы затрат применяется матрица рассмотренной задачи о КВ, приведенная по строкам и столбцам C (0) C '' . 2) Правила ветвления. Принцип деления для каждого из подмножеств X r ( k ) , r 0, r k следующий: фиксируется дуга ( i 0 , j 0 ) наименьшей длины. По этой дуге исходное множество ГК разбивается на 2 подмножества: 1) X i ( 0 k j 0 ) , составленное из ГК, содержащих дугу ( i 0 , j 0 ) ; 2) X i ( 0 k j 0 ) , составленное из ГК, не содержащих дугу ( i 0 , j 0 ) . Требование включения или не включения i 0 , j 0 в подмножество ГК реализуется путем соответствующих преобразований матрица, рассмотренной для подмножеств X r ( k ) , r 0, r k . 3) Правила вычисления границ (оценок) Оценкой снизу на X (0) является константа приведения исходной матрицы расширений C . Действительно, не сложно показать, что длина пути на C равна длине пути на C " (матрица, приведенная по строкам и столбцам) с константой приведения. Поэтому, отбрасывая длину пути на C " получаем нижнюю границу длин ГК на X (0) m ( X 0 ) . В качестве оценки снизу подмножества X r берется сумма оценки исходной для X r k множества – пусть это X r k 1 и константа приведения матрицы расширений, соответствующей подмножеству X r k m X r k и трансформированной с учетом требования замкнутости мар шрута: m X r k m X r k 1 m r k , r 1, r k . Для контроля некоторого состояния маршрута дополнительно вводятся множества P r k , P r k , r 1, r k соответственно множество дуг входящих и не входящих в маршрут по ветви r шага k . Учитывая факт, что АЛ использует специальный математический аппарат, приведем для него детальное описание схемы ветвей и границ с интерпретацией действий в терминах теории графов. 1.3.4 Схема алгоритма Литтла 1) Итерация K 0 А: на X 0 по исходной матрице расстояний ищется нижняя граница всех ГК как константа приведения n n матрицы C : m 0 min C ij min C ' ij или m v , где C ' -матрица, приведенная i 1 j j 1 i по строкам. Б: Прежде чем перейти к шагу K 1 по C " определяется дуга разбиения 1-го наша i 0 , j 0 1 . При выборе i 0 , j 0 1 логика размышлений такова: нужно стремиться к тому, чтобы множество ГК, включающее дугу X i 0 1 j 0 содержало оптимальный контур, а X i 0 1 j 0 не содержало. Поэтому в X i 0 j 0 нужно включать дуги матрицы C " с нулевым расстоянием. Одновременно в X i 0 1 j 0 должны оставаться дуги с наибольшим расстоянием. Последнее требование формализуется следующим образом: по определению, X i 0 1 j 0 не содержит дугу i 0 , j 0 , т.е. для любого ГК путь из i 0 приводит в любую j j 0 , а в j 0 приводит из i i 0 . При этом длина дуги пути будет не меньше, чем так называемая степень нулевого элемента: ij i o j i i 0 ij 0 . Здесь R 0 - множество дуг матрицы C , имеющих нулевое рас min C min C , i , j j j 0 стояние. Затем, среди ij , i , j R 0 выбирается дуга i 0 , j 0 1 так, чтобы расстояние i 0 j 0 было наибольшим, т.е. i 0 , j 0 1 argmax ij , i , j R 0 . i , j Получив дугу разбиения формируем подмножество дуг, составляющих промежуточные маршруты по ветвям r 1, r 2 шага k 1 : i 0 , j 0 P 11 , P 21 , r 2 P 11 i 0 , j 0 1 , P 11 , P 21 , P 21 i 0 , j 0 1 2) Итерация K 1 А: разбиваем X 0 по i 0 , j 0 1 на 2 подмножества X i 0 1 j 0 , X i 0 1 j 0 . Подмножество X i 0 1 j 0 получается из X 0 сужением области за счет введения дополнительных условий: - запрещается повтор перехода из i 0 в j 0 , переходы из i 0 в j j 0 , переходы из j 0 в i i 0 , - запрещается обратный переход из j 0 в i 0 . Чтобы это формализовать матрица C C " преобразуется в матрицу первого шага C i 0 j 0 следующим образом: - в C строки i 0 и столбец j 0 опускаются, тем самым реализуется первая группа условий; - элемент C (вторая группа). Подмножество X i