Алгоритм решения частично целочисленной задачи

Пусть в исходной ЗЛП условие целочисленности наложено только на некоторые переменные. Это значит, что предыдущий алгоритм применять нельзя.

Пусть х_k - переменная частично целочисленной задачи, принимающая целое значение. Если х_k в решении ЗЛП без условия целочисленности является дробной, то с ней связано производящее уравнение

x_k  + å a _{k j} w_j = b _k.

Преобразуем это уравнение, используя соотношение:

b _k = [ b _k ] + f_k,

где f_k   - дробная часть b _k.

Производящее уравнение будет иметь вид:

x_k  -  [ b _k ] = f_k - å a _{k j} w_j .

Здесь некоторые из переменных w_j  - нецелочисленные. Для целочисленной переменной x_k  выполняется одно из неравенств:

x_k   £ [ b _k ] или x_k   ³ [ b _k ] + 1.

С учетом последнего соотношения для производящей строки получим:

f_k - å a _{k j} w_j £ 0 или f_k - å a _{k j} w_j ³ 1

Преобразуем данные неравенства:

å a _{k j} w_j ³ f_k 0 или å a _{k j} w_j £ f_k - 1

Обозначим:

J ⁺  - множество значений j, для которых a _{k j} ³ 0,

J ^-  - множество значений j, для которых a _{k j} £ 0.

Тогда:

                             (*)

Используя два эти неравенства, получим следующее соотношение:

,

где величина .

Данное неравенство сводится к первому из соотношений (*), если второе слагаемое умножить на , и сводится ко второму соотношению (*), если первое слагаемое умножить на ,

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

Данное уравнение вставляется в симплекс-таблицу. Оптимальное решение находится двойственным симплекс-методом /2/.

Следует отметить, что существуют и более эффективные отсечения, учитывающие целочисленность некоторых переменных w_j.

Пример. Рассмотрим задачу из предыдущего примера, но с другим условием целочисленности переменных:

           max z = 7x₁ + 9x₂

                  -x₁ + 3x₂ £ 6

                  7x₁ + x₂ £ 35

                    x_i ³ 0, х₁ - целая.

Решаем задачу без условия целочисленности. Оптимальная симплекс-таблица была получена ранее:

БП	х1	х2	х3	х4	Решение
z	0	0	28/11	15/11	63
х2	0	1	7/22	1/22	7/2
х1	1	0	-1/22	3/22	9/2

x₁ = 9/2, то есть нарушается условие целочисленности этой переменной. Значит cтрока таблицы, связанная с x₁  будет производящей:

х₁ - 1 /22 x ₃ + 3/22 x ₄ = 9/2

Таким образом:

a ₁₃ = -1/22; a ₁₄ = 3/22; f₁ = 1/2.

J⁺ = {4}; J ^- = {3}.

Отсечение Гомори будет иметь вид:

S₁ - [3/22x₄ + (-1)(-1/22)x₃] = -1/2

или

S₁ - 1/22x₃ - 3/22x₄ = -1/2.

Включаем это отсечение в симплекс-таблицу. Новая таблица имеет вид:

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	28/11	15/11	0	63
x 2	0	1	7/22	1/22	0	7/2
x 1	1	0	-1/22	3/22	0	9/2
S 1	0	0	- 1 /22	- 3 /22	1	-1/2

 

Двойственным симплекс-методом находим оптимальное решение задачи (за 1 итерацию):

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	23 / 11	0	10	58
x 2	0	1	10/33	0	-1/3	10/3
x 1	1	0	-1/11	0	1	4
x 4	0	0	1/3	1	-22/3	11/3

Условие целочисленности переменной x₁ соблюдается. Значит, получена оптимальная симплекс-таблица и решение задачи имеет вид:

x₁ = 4, х₂ = 10 /3, z = 58.

 

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

 

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

Сначала решается ЗЛП без условия целочисленности переменных. Пусть переменная x_r - целочисленная переменная, которая в оптимальном решении ЗЛП без условия целочисленности принимает дробное значение x_r ^*. Очевидно, что интервал значений [x_r ^* ] < x_r < [x_r ^* ] + 1 не содержит оптимального решения задачи. Значит оптимальное решение задачи должно удовлетворять одному из неравенств:

x_r £ [x_r ^* ] или x_r ³ [x_r ^* ] + 1.

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

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

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

Пример. Решить полностью целочисленную задачу:

           max z=2x₁ + 3x₂

           5x₁  + 7x₂ £ 35

           4x₁  + 9x₂ £ 36                                                                                      

            x_i ³ 0 - целые

Сначала решаем ЗЛП без условия целочисленности. Получим следующее оптимальное решение:

z = 14 ⁶/₁₇; x₁ = 3 ¹²/₁₇; x₂ = 2 ⁶/₁₇.

 Представим дальнейшие вычисления в виде следующей схемы:

 

1 z = 14 6/17 x1 = 3 12/17 x2 = 2 6/17

 

 

 

 

 

2 z = 14 6/17 x1 = 3 12/17 x2 = 2 6/17

3 z = 13 1/2 x1 = 2 1/4 x2 = 3

 

4 z = 14 x1 = 4 x2 = 2

5 z = 14 2/7 x1 = 5 x2 = 1 3/7

 

Использовался следующий порядок расчета:

1. Вершина (1) - решение исходной ЗЛП.  

2. Вершина (2) - решение исходной ЗЛП с ограничением x₂ £ 2.

3. Вершина (3) - решение исходной ЗЛП с ограничением x₂ ³ 3.

4. Вершина (4) - решение исходной ЗЛП с ограничениями x₂ £ 2; x₁ £ 4. Так как решение задачи целочисленное, то значение целевой функции данного решения объявляется текущей границей: z _г = 14.

5. Вершина (5) - решение исходной ЗЛП с ограничениями x₂ £ 2; x₁ ³ 5. Так как значение целевой функции z может быть в этой задаче только целочисленным, а при ветвлении значение z только ухудшится, то лучшее целое значение целевой функции на ветке (5) z = 14, то есть улучшить текущую границу z _г на этой ветке не удастся. Следовательно, данная ветка прозондирована.

6. Вершина (3) считается прозондированной, так как значение целевой функции в этой вершине z = 13 ¹/₃ меньше текущей границы, а при ветвлении ее значение не возрастает.

Так как все подзадачи прозондированы, то решение, соответствующее текущей границе является оптимальным, то есть z = 14; x₁ = 4; x₂ = 2.

 

Задание к лабораторной работе

 

Задания к лабораторной работе берутся из сборника вариантов контрольных работ /4/. С помощью программы "Решение задач целочисленного программирования" необходимо решить задачу 1а своего варианта. С помощью метода ветвей и границ по программе "Решение задач линейного программирования" найти решение задачи 1а. Типовой отчет по лабораторной работе приведен ниже.