Методы решения задач целочисленного программирования

Дискретное программирование

Задачи целочисленного линейного программирования

3.1.1 Задача о размещениях

Пусть имеются "m" пунктов, в которых могут  размещаться предприятия, производящие некоторую единичную продукцию (станки, линии и т.д.). Кроме того заданы "n" пунктов потребления этой продукции с объемами потребления, равными соответственно b₁, b₂, ..., b_n, а также матрицы транспортных затрат с = {с_ij}_mхn. Здесь с_ij− затраты на транспортировку единицы продукции из производящего пункта "i" в потребляющий пункт "j". Задача состоит в таком размещении предприятий, определении их производственных мощностей и организации перевозок, чтобы суммарные затраты по производству и транспортировке были минимальны. Обозначим через х_i − объем продукции в единицах, который необходимо производить в пункте "i", а через х_ij− количество единиц продукции, поставляемой из пункта "i" в пункт "j". Тогда затраты на производство продукции, если стоимость производства единицы продукции в пункте "i"−с_i, будут равны

                  .

Затраты на транспортировку произведенной продукции к потребителям   

                                .

Вся задача формулируется так:

Найти такие х_i и х_ij, при которых

 (суммарные затраты по производству и транспортировке минимальны), при условиях:

1) x_i 0, x_ij 0 ;

2)  (производимая продукция полностью потребляется);

3)  (каждый потребитель получает продукции в объеме, не менее заданного значения);

4) х_i, x_ij − принимают целочисленные значения.

3.1.2 Задача о назначениях

Пусть имеется "n" единиц оборудования различных типов, которое требуется распределить между "n" предприятиями, имеющими различный уровень технической оснащенности. Обозначим с_ij - производительность "i"-го типа оборудования на "j''-м предприятии. Задача состоит в таком распределении оборудования (по одному на предприятие), которое обеспечит максимальную производительность.

 Определим неизвестные х_ij следующим образом:

   Теперь задача может быть сформулирована следующим образом. Найти такие значения х_ij, чтобы производительность распределяемого оборудования была максимальной

при условиях:

1) = 1, j=1,2,…,n (На каждое предприятие по одному виду оборудования),

2)  = 1, i = 1,2,…,n (Каждая единица оборудования распределяется на 1 предприятие).

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

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

Имеется "n" городов. Выезжая из одного, коммивояжер должен объехать все и вернуться в исходный город. В каждый город можно заезжать только один раз. Требуется найти минимальный замкнутый маршрут.

Обозначим s= {s_ij }_nxn - матрицу расстояний, х_ij - переменные, определим следующим образом:

          Требуется минимизировать

при условиях

(из каждого города коммивояжер выезжает только 1раз);

(в каждый город коммивояжер въезжает 1 раз).

            U_i – U_j + nx_ij  n – 1, , , i≠j,

где U_i ,U_j − произвольные действительные числа.

Последнее условие обеспечивает замкнутость маршрута и отсутствие петель.

Методы решения задач целочисленного программирования

3.2.1 Метод отсечения Гомори

Запишем общую задачу целочисленного программирования в виде: найти максимум

                                                                                  (3.1)

в области, определенной условиями

                                               (3.2)

                                х_j >0 ,                           (3.3)

                                х_j− целые,                      (3.4)

Метод отсечения Гомори состоит в следующем:

а) решаем задачу линейного программирования (3.1) − (3.3);

б) полученное оптимальное решение задачи (3.1) − (3.3), если оно существует, проверяем на целочисленность:

− если все x_j, j =  допустимые целые, то полученное оптимальное решение задачи линейного программирования является оптимальным решением задачи целочисленного программирования;

− если задача линейного программирования решения не имеет, то не имеет решения и задача целочисленного программирования;

− наконец, если хотя бы одна координата не удовлетворяет условию (3.4), то:

в) строим дополнительное линейное ограничение, с помощью которого отсекается та часть допустимой области, определяемой условиями (3.2) − (3.3), в которой содержится оптимальное решение задачи линейного программирования (3.1) − (3.3), но нет ни одного допустимого решения, удовлетворяющего условию (3.4) и вновь выполняем пункт а) для задачи линейного программирования с дополнительным ограничением и т.д.

 Гомори показал, что при "k-ом" возвращении к решению задачи линейного программирования, "k-ое" дополнительное ограничение имеет вид:

,

где  [x_i0], [x_ij] − целая часть соответствующей величины;

    x_i0 − нецелая координата оптимального плана задачи (3.1) − (3.3) с наименьшим индексом;

   x_ij − координаты разложения векторов А_j, не попавших в базис;

    N_k − множество векторов, не попавших в базис.

Ниже приводится схема алгоритма метода Гомори (рисунок 3.1).

3.2.2 Метод ветвей и границ

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

Рассмотрим второй из них. Пусть G₀ − множество допустимых решений задачи, в которой среди совокупности х  G₀ требуется найти то х, при котором целевая функция f имеет минимум. По некоторому закону (правилу) поставим в соответствие множеству G₀ число Z₀, которое является оценкой нижней границы целевой функции на множестве G₀. Разобьем множество G₀ на конечное число непересекающихся подмножеств (для наглядности на два) G₁ и G₂: G₀=G₁ G₂, G₁ G₂=Ø. Определим по выбранному закону (правилу) оценки нижней границы целевой функции на этих подмножествах Z₁ и Z₂.

Возьмем подмножество с меньшей оценкой, допустим G₂, и разобьем G₂=G₃ G₄, G₃ G₄=Ø и найдем оценки подмножеств G₃ и G₄.

Подмножество с меньшей оценкой выбираем для ветвления и т.д. (рисунок 3.2).

Рисунок 3.2

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

3.2.3 Метод ветвей и границ решения задачи о коммивояжере

Рассмотрим задачу о коммивояжере. Пусть  матрица, элемент которой S_ij определяет расстояние при переходе из пункта «i» в пункт «j». Полагаем S_ii= , i= , рассматриваем это как запрет на переезд из "i" в "i".

ОПРЕДЕЛЕНИЕ 3.1. Циклом t назовем набор из "n" упорядоченных пар городов, образующих маршрут, который проходит через каждый город только один раз:

t = {(i₁, i₂ ), (i₂, i₃),…, (i_{n-1, in}), (i_n, i₁)}.

ОПРЕДЕЛЕНИЕ 3.2.  Издержками Z(t) для цикла t назовем величину:

.

В нашей интерпретации Z(t) − это длина замкнутого маршрута, образованного циклом t.

ОПРЕДЕЛЕНИЕ 3.3. Матрица, которая получается из данной вычитанием из элементов каждой строки минимального элемента этой строки, а затемвычитанием из элементов каждого столбца минимального элемента этого столбца, называется приведенной матрицей. Сумма вычитаемых в процессе приведения элементов называется приводящей константой.

Если обозначить S_i,_j(i)=  S_i,j, i= −минимальный элемент S в строке "i", тогда после вычитания этих элементов получится матрица S' с неотрицательными элементами

S'_ij=S_ij−S_i,j(i), i= , .

Обозначим                      

минимальный элемент S′ в столбце j. Тогда после вычитания этих элементов по­лучится приведенная матрица S" с неотрицательными элементами

S"_ij = S'_ij − S'_i(j),j, .   

По определению приводящая константа

                         .                                                                  

Если Z(t) − издержки цикла t для исходной матрицы, a Z'(t)−издержки цикла t после приведения, то Z(t)=Z'(t)+h и, очевидно, что h является нижней границей издержек для всех циклов t исходной матрицы расстояний, поскольку h − сумма минимальных элементов строк и столбцов. Из этого следует, что применяя метод ветвей и границ, мы можем использовать h в качестве оценки разветвляемых подмножеств.

Определимся теперь с принципом разбиения на подмножества и нахождения оценок этих подмножеств. Пусть G₀ − множество всех маршрутов. Разобьем G₀ на два подмножества: первое подмножество состоит из всех маршрутов, включающих переезд из города "i" в город "j", говорят содержащих пару (i, j), а второе подмножество состоит из множества маршрутов не содержащих пару (i, j).

Пару городов (i, j) для ветвления будем выбирать среди тех пар, которым в приведенной матрице соответствуют нулевые элементы, причем выбирается такая пара (i, j), чтобы подмножество, не содержащее пару (i, j) имело максимальную оценку. Разветвляя последовательно, мы построим дерево ветвей, на вершине которого будет подмножество, содержащее две пары городов, завершающих маршрут. Спускаясь по дереву ветвей, мы по парам городов, определяющих ветвление, определим все пары городов, составляющих маршрут (рисунок 3.3).

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

1. Осуществим приведение матрицы S по строкам и столбцам, получим приведенную матрицу S′.

2. Вычислим сумму приводящих констант h^(k) - это оценка для исходного множества маршрутов G₀. Обозначим оценку ω(G₀) = h .

3. Выберем претендентов для ветвления, т.е. те пары (i, j) i=l, 2, ...,  j = l, 2, ..., i ≠ j, для которых S_ij^(k)=0 и вычислим для всех таких S_ij^(k) величины

4. Выберем для ветвления ту пару (i, j) из претендентов на ветвление, для которой θ_ij  получится максимальным.

5. В качестве оценки множества всех маршрутов, не содержащих выбранную пару (i, j), возьмем оценку того множества, которое разветвляли плюс max θ_ij.

6. Так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз, то строку "i" и столбец "j" можно из дальнейшего рассмотрения исключить. Чтобы не получить замкнутых не­полных циклов, нужно наложить необходимые запреты, в частности, на переезд из ''j" в "i" то есть положить S_ij=∞.

7. Если полученная после вычеркивания строки и столбца и наложения запретов матрица имеет размерность 2x2, то определяемые ею пары городов завершают маршрут. Приводя эту матрицу и добавляя приводящую константу к оценке последнего разветвляемого множества, получим оценку маршрута.

Если эта оценка не больше оценки всех тупиковых ветвей, то маршрут, описываемый деревом ветвей, является оптимальным, иначе процесс ветвления должен быть продолжен, исходя из множества с меньшей оценкой.

8. Если усеченная матрица не имеет размерности 2x2, то приводим полученную матрицу и находим оценку множества {i, j}, то есть множества маршрутов, содержащих пару (i, j), как сумму приводящей константы и оценки разветвляемого множества.

Переходим к п. 3.

Пример 3.1.Имеется четыре пункта, расстояние между которыми описано матрицей расстояний. Найти оптимальный (минимальный) замкнутый маршрут объезда городов.

  1234

1   13 12 4

2 13 ∞ 7 8

3 12 7 ∞ 5

1. Приводим матрицу S:

12      34            1234                123  4   

1    13 12 4 4       1     9  8  0           1    7 8 0

2 13     7  8 7 →    2 6      0  1  →  2  6   0  1

3 12   7    5 5       3 7 2    0           3   7 0    0

4 4 8 5   4            4 0 4  1                4   0 2 1

                                     0   2  0    0 

2. Найдем сумму приводящих констант: h=4+7+5+4+2=22.

Найдем оценку множества G₀ : ω(G₀ )=22.

3. Укажем претендентов на ветвление и осуществим выбор пары для ветвления:

S₁₄=0,      S₂₃= 0,      S₃₂=0,      S₃₄=0,       S₄₁= 0,

 θ₁₄ =7+0=7,    θ₂₃=1+1=2,    θ₃₂ = 0 +2=2, θ₃₄=0 +0=0, 

   θ₄₁= 6 + 1=7,        max θ_ij=θ₁₄ = 7 ( можно θ₄₁ = 7 ).

4. Итак, для ветвления выбираем пару (1,4) и начинаем строить дерево ветвей (рисунок 3.4). Найдем оценку множества {1,4}−множества всех маршрутов не содержащих пару (1,4): ω({1, 4})=ω(G₀)+θ(1,4)=22+7=29.

5. Вычеркнем строку "1", столбец "4" и положим запрет на переезд из "4" в"1": 

                                     1     2      3             

                                               2  6       0  

                                               3  7  0     .     

                                               4      2    1

Приводим матрицу

123                123                    123     

2   6    0 0        2 6      0           2 0    0      

3   7 0     0 → 3  7 0      →   3 1 0       

4      2 1 1        4    1 0             4    1 0                                                 

6. Найдем h = 1 + 6 = 7 и оценку {1, 4 }.

ω({1, 4})=ω(G₀)+h=22+7=29.

7. Укажем претендентов для ветвления и выберем пару для ветвления:

S₂₁ = 0, S₂₃ = 0, S₃₂ = 0, S₄₃ = 0,

θ₂₁ = 0 + 1 = 1, θ₂₃ = 0 + 0 = 0 , θ₃₂ = 1+ 1 = 2,

θ₄₃=1+0 = 1, max θ_ij = θ₃₂ = 2.

Итак, для ветвления берем пару (3,2).

Найдем оценку .

8. Вычеркнем строку "3", столбец "2" и наложим запрет на переезд из "2" в "3".

                1  3

          2 0    − матрица приведенная, следовательно h=0 и

          4   0

ω({3, 2})=ω({1, 4})+h=29.

9. Так как матрица размерности 2x2, то не запрещенные пары (2,1) и (4,3) завершают маршрут (рисунок 3.4).

Рисунок 3.4 − Маршрут объезда пунктов

Поскольку оценка последнего подмножества не больше оценок тупиковых ветвей, то пары (1,4), (3,2), (2,1), (4,3) задают оптимальный маршрут, который можно представить, скажем так: 1→4 →3 →2 →1 с расстоянием S_min=29.

3.2.4 Аппроксимация решения задачи о коммивояжере

Приведенный в предыдущем пункте алгоритм является чрезвычайно трудоемким даже при использовании ЭВМ. В практически приемлемое время он позволяет решать лишь задачи небольшой размерности. В [5] предложено производить декомпозицию задачи большой размерности на ряд задач приемлемой размерности разбиением на группы (зоны) "близких" друг к другу объектов. В каждой группе выбираются объекты (вообще говоря разные), которые служат представителями группы (зоны) при определении минимальных расстояний между группами (зонами).

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