Обзор задач дискретного программирования

2. L(X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 1 Общий вид транспортной матрицы задачи о назначениях
Ресурсы, Ai	Работы, B1				Количество  ресурсов
	B1	B2	…	Bm
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Количество  работ	1	1	…	1

 

Модель  задачи о назначениях

 

(9)

В некоторых случаях, например, когда cij – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ. В этом случае ЦФ L(X) заменяют на L1(X) = – L(X) и решают задачу с ЦФ L1(X) → min, что равносильно решению задачи с ЦФ L(X) → max.

Задача  о покрытии. 

Эта задача относится к классу экстремальных  комбинаторных задач на графах. Рассмотрим типичную задачу о покрытии. Дан граф G. Требуется найти его минимальное покрытие, т.е. такую минимальную совокупность ребер, чтобы любая вершина графа была инцидентна некоторому ребру, входящему в покрытие.

Обозначим вершины графа i, i =1, 2, …, m, а ребра — j, j =1, 2, …, n... Граф характеризуется своей матрицей инциденций вершин и ребер  , где

Введем множество переменных {x_j}, таких, что

 

Тогда нахождение минимального покрытия эквивалентно следующей задаче:

минимизировать                            (10)

при ограничениях

                                      (11)

 

Задача  о коммивояжере

Имеется N городов, которые  должен обойти коммивояжер с минимальными затратами. При этом на его маршрут  накладывается два ограничения:  
маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.  
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат. 

Математическая  модель задачи

N - число городов.

Ci j ,  i, j=1..N - матрица затрат, где Ci j  - затраты на переход из i- го города в j-й.

Xi j - матрица переходов с компонентами:

Xi j  = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j  = 0, если не совершает перехода,

где i, j = 1..N  и i j.

Критерий:

                                                                                  (12)

Ограничения:

, i = 1..N                                                                                  (13)

, j = 1..N                                                                                  (14)

Ui - Uj + N × Xij ≤ N-1,   i, j = 1..N, i j.                                         (15)

 

1.2.3.Задачи с разрывными целевыми функциями.

Многие экономические  системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены  независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке,  тем, что в ней затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как

                                      (16)

где с_i,j —издержки на перевозку единицы груза;

d_i,j — фиксированная доплата за аренду транспортных средств. ai — объем производства в пункте производства i ; bj — объем потребления в пункте потребления j. Обозначим через xij объемы перевозок из пункта i в пункт j.

При таких предпосылках целевая функция суммарных затрат на перевозку

                                                                                 (17)                                

содержит «скачкообразные» разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный  метод решения основан на следующем преобразовании. Если ввести вспомогательные переменные у_i,j, такие, что

М ij = min (ai ,bj),  i = 1,2,...,m;  j = 1,2,...n.

 

yij = sign (xij)  т.е .                                                     (18)        

то целевая функция примет вид

                                                      (19) 

при дополнительном условии   i = 1,2,...,m;  j = 1,2,...n.

Действительно, если у_i,j =0 , то переменные х_i,j =0, а при у_i,j =1 неравенства (18) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача (19) эквивалентна исходной задаче (17). Задача (19) является задачей частично-целочисленного программирования.

Перечисленные примеры далеко не исчерпывают всего многообразия задач дискретного программирования. Далее мы рассмотрим методы решения дискретных задач.

 

1.3. Методы решения задач дискретного программирования.

Методы решения  задач дискретного программирования можно разделить на следующие классы:

• Метод отсечения;
• комбинаторные методы;
• приближенные методы.

Рассмотрим  каждый класс в отдельности.

1.3.1. Метод отсечения.

    Алгоритмы методов отсечения разработаны для решения полностью или частично целочисленных и дискретных задач линейного программирования.

    Общая схема методов отсечения заключается в переходе от решения задачи целочисленного (дискретного) линейного программирования к решению последовательности задач линейного программирования . Первая задача последовательности получается из исходной снятием требования целочисленности (дискретности).

Каждая последующая k-ая задача получается из предыдущей (k-1)-ой

путем добавления к условиям, определяющим область  допустимых

решений (k-1)-ой задачи, еще одного ограничения, называемого

правильным  отсечением.

После решения  каждой k-ой задачи ЛП (k = 0,1,2, . . .) проверятся

удовлетворяет ли полученное оптимальное решение  условиям исходной

задачи. При  положительном ответе итерационный процесс решения

задач из последовательности прекращается - полученное оптимальное решение задачи ЛП является и решением исходной задачи.

Решение каждой k-ой задачи ЛП называется k-ой большой итерацией.

Доказывается, что при выполнении определенных условий решение

исходной задачи будет получено через конечное число  итераций. Если

задачи ЛП не имеют решения, не имеет решения и исходная задача.

Основным понятием метода является термин правильное отсечение:

Правильные отсечения – отсечение (дополнительное ограничение), которое удовлетворяют следующим требованиям:

1. линейно;
2. отсекает от области допустимых решений ту ее часть, которая содержит оптимальное решение задачи ЛП, не удовлетворяющее требованиям исходной задачи;
3. в отсекаемой области не должно содержаться ни одной точки, принадлежащей области допустимых решений исходной задачи. (является «правильным»).

     Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде:

,   z ≥ 0,

где xj - небазисные переменные оптимального решения k-ой задачи ЛП,   γ0 , γj - определяются по коэффициентам разложения базисной переменной, не удовлетворяющей требованиям целочисленности (дискретности) исходной задачи по небазисным переменным в последней симплекс-таблице k-ой задачи ЛП (строка симплекс-таблицы с найденным оптимальным значением задачи ЛП).

Известны три  алгоритма отсечения:

1). 1-ый алгоритм  Гомори решения целочисленной  задачи ЛП.

2). 2-ой алгоритм  Гомори решения частично целочисленной  задачи ЛП.

3). Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.

Скажем пару слов о каждом приведённом алгоритме.

 

 

 

1-ый  алгоритм Гомори решения целочисленной  задачи ЛП.

Что бы решать задачу методом Гомори № 1 необходимо, чтобы все компоненты плана были целочисленными. Другими словами, даже к искусственным переменным предъявляется требование целочисленности.

Алгоритм метода Гомори № 1

1.Решим исходную задачу (без условия целочисленности) Симплекс-методом. Если все базисные компоненты оптимального плана решаемой задачи  целые, то найденное решение есть оптимальное решение исходной задачи. Если некоторая компонента -

нецелая, то переходим  к п.2.

2.Строим правильное отсечение. Гомори предложено делать каждый раз дополнительное ограничение для нецелой переменной с наибольшей дробной частью. Итак, задача с отброшенным условием целочисленности решена. Рассмотрим i-ю строку оптимальной симплексной таблицы, которой соответствует нецелое решение β _i базисной переменной x_i .Пусть R – множество индексов j, которые соответствуют небазисным переменным. Тогда переменная x_i может быть выражена через небазисные переменные x_j:

,   β _i – нецелое.

Обозначим наибольшую целую часть числа a, его не превосходящую, через [a], ( a≥[a]), а дробную положительную часть – через {a} Очевидно a = [a] + {a}. Например, если  a=4,7 то [a] = 4, {a} = 0,7.

Выразим базисную переменную x_i  в виде суммы целой и дробной частей.  
Выражение в левых круглых скобках целое число, и чтобы x_j было целым, необходимо, чтобы выражение в правых круглых скобках тоже было целым. Когда выражение Li= будет целым? Так как   0≤{β_i}≤1, а   ≥0,  то L_i  будет целым числом, если   .  
- правильное отсечение Гомори.  
Задача не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что β_i дробное число, а d_ij –целые.

3.Добавляем полученное дополнительное условие к задаче из п.1.Так как оптимальное решение задачи, решенной в п.1, определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи.Решаем полученную задачу С-методом.

Теорема (о конечности первого алгоритма Гомори)

Пусть множество  оптимальных планов задачи, полученной из исходной отбрасыванием условий целочисленности, ограничено, и выполняются следующие условия:

1)  cj- целые коэффициенты целевой функции F, строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

2) справедливо  одно из двух утверждений: либо  целевая функция ограничена снизу,  либо исходная задача имеет хотя бы один план.

Тогда первый алгоритм Гомори требует конечного числа  больших итераций.

Пример применение первого алгоритма Гомори будет  рассмотрено в главе 2.

Алгоритм  Дальтона-Ллевилина решения дискретной задачи ЛП.

В задачах, решаемых алгоритмом Дальтона-Ллевилина, область допустимых значений задается следующим образом

xj ≥0, j =1, 2, …,n,

x Є Aj (A j1,Aj2 ,...,Ajmj ), j =1,2,…,n1, n1 ≤ n .

Полагаем, что  коэффициенты Aj проранжированы, т.е. Аj1 < Аj2 < …< Аjmj .

Если x не удовлетворяет требованиям исходной задачи и

Aiv < xi0< Aiv+1 тогда, используя i-ю строку симплекс-таблицы, запишем

правильное  ограничение в виде

zi= - γ 0 + ∑ γ j xj ,   z ≥ 0,

γ 0= xi0 – Aiv ,

γ ij= xij ,если xij≥ 0,

γ ij= (-xij)*( xi0 – Aiv)/( Aiv+1 –xi0) ,если xij≤ 0,

 

Стоит отметить, что