4 МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ
Многие задачи исследования операций, такие как распределения ресурсов, сетевого планирования и управления, календарного планирования, описываются математическими моделями дискретного программирования.
Рассмотрим общую задачу максимизации
максимизировать 
(4.1.1)
при условиях
. . . . . . . . . . (4.1.2)
(4.1.3)
где D - некоторое множество.
Если множество D конечным или счетным, то условие (4.1.3) - это условие дискретности и задача (4.1.1) - (4.1.3) является задачей дискретного программирования.
Чаще всего условие дискретности разделено по отдельным переменным следующим образом:
.
Если вводится ограничение 
- целое число, 
, то приходят к задаче целочисленного программирования (ЦП), а если вводится ограничение 
, то к задаче булевого программирования.
В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со значительными трудностями. В частности, невозможно применение стандартного подхода, состоящего в замене дискретной задачи ее непрерывным аналогом, и дальнейшем округлении найденного решения до ближайшего целочисленного. Проиллюстрируем это на таком примере.
Пример 4.1. Максимизировать 
при условиях
где 
, - целые числа 
.
Игнорируя условие целочисленности, находим оптимальный план симплекс-методом:
Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Искомое оптимальное целочисленое решение задачи таково:
Как видим, его нельзя получить простым округлением компонент оптимального непрерывного решения.
Таким образом, для решения задач дискретного программирования необходимы специальные методы.
Методы решения задач дискретного программирования делятся на такие группы:
1) точные методы, которые включают метод отсекающих плоскостей (Гомори), метод ветвей и границ, метод последовательного анализа и отсева вариантов, аддитивний метод и др.;
2) приближенные методы: метод локальной оптимизации, модификации точных методов, методы случайного поиска и эвристические методы, максимально учитывающие специфику решаемых задач.
По структуре математической модели задачи дискретного программирования разделяют на следующие основные классы: 1) задачи с неделимостями; 2) экстремальные комбинаторные задачи; 3) задачи на невыпуклых и несвязных областях; 4) задачи с разрывными целевыми функциями.
Рассмотрим некоторые из них.
Задачи с неделимостями
Математические модели задач этого типа основаны на требовании целочисленности переменных 
, вытекающем из физических условий практических задач. К таким задачам относится, в частности, задача об определении оптимальной структуры производственной программы 
, где 
- объемы выпуска соответствующей продукции. Математическая модель этой задачи имеет следующий вид:
максимизировать 
(4.1.1)
при условиях
(4.1.2)
- цілі, при 
. (4.1.3)
Если 
, то задача называется полностью целочисленной, в противном случае, если 
- частично целочисленной.
Задача о рюкзаке. Одной из наиболее распространенных задач целочисленного программирования является задача о рюкзаке (или о ранце).
Постановка задачи. Турист готовится к длительному переходу в горах. Он складывает вещи в рюкзак, который может включать n видов нужных предметов, причем предмет типа j имеет массу wj , . Для каждого вида предмета турист определяет його ценность Еj во время перехода. Максимальный вес груза в рюкзаке не может превышать W кг. Сколько предметов каждого типа он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной при ограничении на массу рюкзака?
Обозначим через xj - количество предметов j-го типа в рюкзаке. Тогда математическая модель задачи такова:
максимизировать 
(4.1.4)
при ограничениях
, (4.1.5)
,
- целое, .
Экстремальные комбинаторные задачи
В данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из n символов.
Одной из наиболее простых задач этого класса является известная задача о назначениях (см. гл. 3).
Найти такую перестановку 
из чисел 1, 2, ., n, при которой достигается минимум 
по всем перестановкам 
.
Каждая такая перестановка может быть представлена точкой в n2-мерном пространстве или в виде матрицы 
.
Введем переменные
Очевидно,
(4.1.6)
Задача о назначениях заключается в нахождении таких чисел {xij}, при которых достигается 
при ограничениях (4.1.6).
Хотя условия целочисленности в (4.1.6) в явном виде нет, оно выполняется, поскольку задача о назначениях является частным случаем Т-задачи.
Задача о коммивояжере. Рассмотрим известную задачу о коммивояжере. Пусть имеется n городов: A1, A2, ., An... Задана матрица 
расстояний между всеми городами. Выезжая из исходного города A1 коммивояжер должен во всех остальных городах побывать по одному разу и вернуться в исходный город A1. Требуется определить такой маршрут его движения, чтобы суммарное пройденное расстояние было минимально.
Математическая модель этой задачи имеет следующий вид:
минимизировать 
(4.1.7)
при условиях
(4.1.8)
(4.1.9)
(4.1.10)
где 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-м этапе. Отсюда следует, что 
для всех i и j, и, таким образом, условие (4.1.10) выполняется, если xij = 0. При xij = 1 условие (4.1.10) выполняется как строгое равенство:
ui - uj + n xij = p - (p+1) + n = n -1.
Задача о покрытии. Эта задача относится к классу экстремальных комбинаторных задач на графах.
Рассмотрим типичную задачу о покрытии. Дан граф G. Требуется найти его минимальное покрытие, т.е. такую минимальную совокупность ребер, чтобы любая вершина графа была инцидентна некоторому ребру, входящему в покрытие.
Обозначим вершины графа i, i =1, 2, ., m, а ребра - j, j =1, 2, ., n... Граф характеризуется своей матрицей инциденций вершин и ребер 
, где
Введем множество переменных {xj}, таких, что
Тогда нахождение минимального покрытия эквивалентно следующей задаче:
минимизировать 
(4.1.11)
при ограничениях
(4.1.12)
Задачи на несвязных и невыпуклых областях
Данные задачи представляют собой модели линейного программирования, в которых к обычным условиям присоединены некоторые дополнительные условия, превращающие область допустимых решений в невыпуклую или несвязную.
В частном случае при дополнительных условиях 
получаем несвязную область, приведенную на рис. 4.1.
Рис. 4.1 Рис. 4.2
Задачи на несвязных областях. Пусть переменная 
задачи ЛП имеет ограничение сверху и, кроме того, ограничение вида
либо 
, либо 
, (4.1.13)
где 
.
Задачи такого типа с дополнительными логическими условиями вида ИЛИ-ИЛИ будем называть дихотомическими.
Введем целочисленную переменную 
, принимающую значения 0 и 1. Дополнительная переменная в целевую функцию не включается. Тогда
(4.1.14)
Система (4.1.14) эквивалентна ограничениям (4.1.13). Если 
, то 
. Если 
, то 
.
Рассмотрим более общий случай. Пусть в задачах математического программирования с допустимой областью решений G(X) имеется альтернативное ограничение:
(4.1.15)
где 
, 
- заданные функции. Предположим, что нам известны нижние границы функций h(x), k(x) на области G, обозначаемые соответственно hmin , kmin . Введем вспомогательную переменную 
и рассмотрим систему неравенств
(4.1.16)
Эта система эквивалентная альтернативному ограничению (4.1.15).
Итак, данная задача при введении вспомогательной переменной становится задачей дискретного программирования.
Задачи на невыпуклых областях. Введение дополнительных дискретных переменных позволяет осуществить переход от задачи оптимизаци на невыпуклой области к задаче, представляющей собой сумму (объединение) выпуклых множеств.
Пусть имеется задача ЛП с дополнительным ограничением (рис. 4.2):
(4.1.17)
причем
либо 
, либо 
. (4.1.18)
Введем переменную y, охарактеризовав эту область системой неравенств
(4.1.19)
В более общем случае при решении задачи может быть задана система множеств 
, причем решение принадлежит либо 
, либо 
. Пусть для каждой пары множеств 
области 
и 
описываются соответственно системами неравенств:
(4.1.20)
(4.1.21)
Кроме того, пусть известны числа {
}, {
} - нижние границы для функций 
, 
соответственно.
Введем дополнительную целочисленную переменную y = {0, 1}. Тогда альтернативные ограничения
(4.1.22)
Рассмотрим случай условных или логических ограничений. Пусть имеется логическое ограничение:
если 
, то 
(4.1.23)
Запишем его в эквивалентном виде:
либо , ,
либо 
(4.1.24)
Введя переменную y = {0, 1}, приходим к следующей системе:
(4.1.25)
где 
G -область определения и .
Рассмотрим иной случай логических ограничений.
Если 
, то ;
если 
, то 
. (4.1.26)
Введем переменные y1, y2, и получим
(4.1.27)
где 
.
Таким образом, при использовании логических переменных задачи с логическими (условными) ограничениями сводятся к задачам дискретного программирования.
Задачи с разрывными целевыми функциями
Наиболее изучена из этого класса задач Т-задача с фиксированными доплатами [18]:
минимизировать 
(4.1.28)
при условиях
(4.1.29)
Введем вспомогательные переменные yij следующим образом:
(4.1.30)
где 
= 
. Тогда целевая функция имеет вид
(4.1.31)
Задача (4.1.31) эквивалентна исходной задаче (4.1.28). Действительно, при 
= 0, переменные xi = 0, а при = 1 неравенства (4.1.30) становятся несущественными, так как они выполняются в любом опорном плане. Таким образом, эта задача является частично-целочисленной.
Теперь рассмотрим более общую математическую модель с разрывной целевой функцией на примере задачи о смесях.
Примем следующие обозначения:
- содержание элемента i в единице компонента j;
- ограничение снизу на количество каждого элемента в смеси; 
- стоимость единицы компонента j;
- фиксированная стоимость заказа j-го компонента; - количество j-го компонента смеси.
Требуется составить наиболее дешевую смесь, удовлетворяющую требованиям по содержанию каждого элемента в смеси.
Формально модель задачи следующая:
минимизировать 
(4.1.32)
при условиях
(4.1.33)
где
(4.1.34)
Предположим, что в дополнение к условиям (4.1.33) задана для верхняя граница
(4.1.35)
Тогда запишем задачу минимизаци в следующем виде:
минимизировать 
(4.1.36)
при условии (4.1.33) и дополнительных условиях
(4.1.37)
Эквивалентность частично-целочисленной задачи (4.1.36) и исходной задачи может быть проверена аналогично Т-задаче с фиксированными доплатами.
Задачи, сводящиеся к целочисленным
Некоторые задачи, формально не являющиеся целочисленными, имеют целочисленные решения при любых целочисленных исходных данных. К таким задачам относится Т-задача, которая формально не является целочисленной, так как отсутствует соответствующее условие целочисленности:
- целое.
При анализе Т-задачи Г. Данцигом установлена следующая теорема.
Теорема 4.1. При любых целых значениях
, 
и 
, Т-задача всегда имеет целочисленный оптимальный план, независимо от значений 
.
Доказательство этой теоремы основано на двух положениях: существует исходный опорный целочисленный план; при переходе от одного опорного плана к другому целочисленность сохраняется.
Действительно, из этих положений сразу следует целочисленность всех опорных планов и, в частности, оптимального.
Целочисленность планов Т-задачи связана со структурой ее матрицы ограничений и имеет место для всех ее частных случаев, важнейшими из которых являются задача о назначениях и задача о потоке на транспортной сети.
