![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Исследование операций
|
04.10.2008
|
![]() |
![]() |
|||
4 МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯМногие задачи исследования операций, такие как распределения ресурсов, сетевого планирования и управления, календарного планирования, описываются математическими моделями дискретного программирования. Рассмотрим общую задачу максимизации максимизировать при условиях . . . . . . . . . . (4.1.2)
где D - некоторое множество. Если множество D конечным или счетным, то условие (4.1.3) - это условие дискретности и задача (4.1.1) - (4.1.3) является задачей дискретного программирования. Чаще всего условие дискретности разделено по отдельным переменным следующим образом:
Если вводится ограничение В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со значительными трудностями. В частности, невозможно применение стандартного подхода, состоящего в замене дискретной задачи ее непрерывным аналогом, и дальнейшем округлении найденного решения до ближайшего целочисленного. Проиллюстрируем это на таком примере. Пример 4.1. Максимизировать где Игнорируя условие целочисленности, находим оптимальный план симплекс-методом: Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Искомое оптимальное целочисленое решение задачи таково: Как видим, его нельзя получить простым округлением компонент оптимального непрерывного решения. Таким образом, для решения задач дискретного программирования необходимы специальные методы. Методы решения задач дискретного программирования делятся на такие группы: 1) точные методы, которые включают метод отсекающих плоскостей (Гомори), метод ветвей и границ, метод последовательного анализа и отсева вариантов, аддитивний метод и др.; 2) приближенные методы: метод локальной оптимизации, модификации точных методов, методы случайного поиска и эвристические методы, максимально учитывающие специфику решаемых задач. По структуре математической модели задачи дискретного программирования разделяют на следующие основные классы: 1) задачи с неделимостями; 2) экстремальные комбинаторные задачи; 3) задачи на невыпуклых и несвязных областях; 4) задачи с разрывными целевыми функциями. Рассмотрим некоторые из них. Задачи с неделимостямиМатематические модели задач этого типа основаны на требовании целочисленности переменных максимизировать при условиях
Если Задача о рюкзаке. Одной из наиболее распространенных задач целочисленного программирования является задача о рюкзаке (или о ранце). Постановка задачи. Турист готовится к длительному переходу в горах. Он складывает вещи в рюкзак, который может включать n видов нужных предметов, причем предмет типа j имеет массу wj , Обозначим через xj - количество предметов j-го типа в рюкзаке. Тогда математическая модель задачи такова: максимизировать при ограничениях
Экстремальные комбинаторные задачиВ данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из n символов. Одной из наиболее простых задач этого класса является известная задача о назначениях (см. гл. 3). Найти такую перестановку Каждая такая перестановка может быть представлена точкой в n2-мерном пространстве или в виде матрицы Введем переменные Очевидно,
Задача о назначениях заключается в нахождении таких чисел {xij}, при которых достигается Хотя условия целочисленности в (4.1.6) в явном виде нет, оно выполняется, поскольку задача о назначениях является частным случаем Т-задачи. Задача о коммивояжере. Рассмотрим известную задачу о коммивояжере. Пусть имеется n городов: A1, A2, ., An... Задана матрица Математическая модель этой задачи имеет следующий вид: минимизировать при условиях
где ui, uj - произвольные целые и неотрицательные числа. Условие ( 4.1.8 ) означает, что коммивояжер выезжает из каждого города один раз, а условие ( 4.1.9 ) - что он въезжает один раз в каждый город. Если ограничить задачу только условиями ( 4.1.8 ) и ( 4.1.9 ), то она эквивалентна задаче о назначениях, план которой не обязан быть цикличным. Иначе говоря, маршрут коммивояжера можно представить как ряд связных переходов или циклов, в то время как его маршрут в действительности состоит из одного цикла. Чтобы обеспечить это требование и используется условие (4.1.10). Покажем, что действительно для любого цикла, начинающего в пункте A1 , можно найти ui , удовлетворяющие условию (4.1.10). Пусть ui = p, если коммивояжер посещает город Aі на p-м этапе. Отсюда следует, что ui - uj + n xij = p - (p+1) + n = n -1. Задача о покрытии. Эта задача относится к классу экстремальных комбинаторных задач на графах. Рассмотрим типичную задачу о покрытии. Дан граф G. Требуется найти его минимальное покрытие, т.е. такую минимальную совокупность ребер, чтобы любая вершина графа была инцидентна некоторому ребру, входящему в покрытие. Обозначим вершины графа i, i =1, 2, ., m, а ребра - j, j =1, 2, ., n... Граф характеризуется своей матрицей инциденций вершин и ребер Введем множество переменных {xj}, таких, что
Тогда нахождение минимального покрытия эквивалентно следующей задаче: минимизировать при ограничениях
Задачи на несвязных и невыпуклых областяхДанные задачи представляют собой модели линейного программирования, в которых к обычным условиям присоединены некоторые дополнительные условия, превращающие область допустимых решений в невыпуклую или несвязную. В частном случае при дополнительных условиях Рис. 4.1 Рис. 4.2 Задачи на несвязных областях. Пусть переменная либо где Задачи такого типа с дополнительными логическими условиями вида ИЛИ-ИЛИ будем называть дихотомическими. Введем целочисленную переменную
Система (4.1.14) эквивалентна ограничениям (4.1.13). Если Рассмотрим более общий случай. Пусть в задачах математического программирования с допустимой областью решений G(X) имеется альтернативное ограничение:
где
Эта система эквивалентная альтернативному ограничению (4.1.15). Итак, данная задача при введении вспомогательной переменной становится задачей дискретного программирования. Задачи на невыпуклых областях. Введение дополнительных дискретных переменных позволяет осуществить переход от задачи оптимизаци на невыпуклой области к задаче, представляющей собой сумму (объединение) выпуклых множеств. Пусть имеется задача ЛП с дополнительным ограничением (рис. 4.2):
причем либо Введем переменную y, охарактеризовав эту область системой неравенств
В более общем случае при решении задачи может быть задана система множеств
Кроме того, пусть известны числа { Введем дополнительную целочисленную переменную y = {0, 1}. Тогда альтернативные ограничения
Рассмотрим случай условных или логических ограничений. Пусть имеется логическое ограничение: если Запишем его в эквивалентном виде: либо либо Введя переменную y = {0, 1}, приходим к следующей системе:
где Рассмотрим иной случай логических ограничений. Если если Введем переменные y1, y2, и получим
где Таким образом, при использовании логических переменных задачи с логическими (условными) ограничениями сводятся к задачам дискретного программирования. Задачи с разрывными целевыми функциямиНаиболее изучена из этого класса задач Т-задача с фиксированными доплатами [18]: минимизировать при условиях
Введем вспомогательные переменные yij следующим образом:
где
Задача (4.1.31) эквивалентна исходной задаче (4.1.28). Действительно, при Теперь рассмотрим более общую математическую модель с разрывной целевой функцией на примере задачи о смесях. Примем следующие обозначения: Требуется составить наиболее дешевую смесь, удовлетворяющую требованиям по содержанию каждого элемента в смеси. Формально модель задачи следующая: минимизировать при условиях
где
Предположим, что в дополнение к условиям (4.1.33) задана для
Тогда запишем задачу минимизаци в следующем виде: минимизировать при условии (4.1.33) и дополнительных условиях
Эквивалентность частично-целочисленной задачи (4.1.36) и исходной задачи может быть проверена аналогично Т-задаче с фиксированными доплатами. Задачи, сводящиеся к целочисленнымНекоторые задачи, формально не являющиеся целочисленными, имеют целочисленные решения при любых целочисленных исходных данных. К таким задачам относится Т-задача, которая формально не является целочисленной, так как отсутствует соответствующее условие целочисленности: При анализе Т-задачи Г. Данцигом установлена следующая теорема. Теорема 4.1. При любых целых значениях Доказательство этой теоремы основано на двух положениях: существует исходный опорный целочисленный план; при переходе от одного опорного плана к другому целочисленность сохраняется. Действительно, из этих положений сразу следует целочисленность всех опорных планов и, в частности, оптимального. Целочисленность планов Т-задачи связана со структурой ее матрицы ограничений и имеет место для всех ее частных случаев, важнейшими из которых являются задача о назначениях и задача о потоке на транспортной сети. |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |