Введение
Большой класс прикладных задач оптимизации сводится к задачам целочисленного линейного программирования. Для решения этих задач широко применяются методы отсечения, предназначенные для решения общей целочисленной задачи, сопоставляя ей некоторую нецелочисленную задачу, по решению которой и позволяет найти решение.
Первый методов решения целочисленной задачи линейного программирования
отсечением был предложен Гомори и получил название алгоритма Гомори.
1.
Постановка задачи
Метод Гомори предназначен для решения целочисленных задач линейного программирования. При рассмотрении метода Гомори будем решать данную задачу в канонической форме.
1.1 Каноническая форма
Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности:
Где
c = (c 1 , c 2 , … , c n)
, x = (x 1 ,
x 2 , … , x n)
- вектора размерности n
,
Условие
целочисленности существенно осложняет задачу линейного программирования (1.1),
(1.2). Так может случиться, что задача (1.1)-(1.3) обладает допустимыми
(целочисленными) планами, целевая функция ограничена на допустимом множестве,
однако ее максимум не достигается. Например в задаче:
не существует целочисленных решений, в то время как без этого условия
решением служит любой вектор вида
.
В связи со сказанным, при обосновании численных алгоритмов решения задач типа (1.1)-(1.3) приходится накладывать различные дополнительные условия.. Будем считать, что множество X планов задачи (1.1), (1.2) (без условия целочисленности) ограничено, то есть является многогранником.
Из этого условия вытекает, что множество X * всех целочисленных планов задачи (1.1)-(1.3) конечно.. Будем предполагать, что все коэффициенты c j , j=1 , 2 , …, n , целевые функции - целые числа.
Из условия II вытекает, что для всякого целочисленного плана x Î X * значение <c , x > максимизируемой линейной формы - целое число. В этом случае говорят, что гарантирована целочисленность целевой функции.
Хотя условия I и II на задачу (1.1) - (1.3) довольно жесткие, ослабить их, для получения необходимых результатов, можно лишь немного.
1.2 Приведение к канонической форме
Задача целочисленного линейного программирования может формулироваться
несколько иначе, нежели это было приведено выше. Так, например, вместо условия
(1.2) может иметь место другая форма записи ограничений
От подобной записи к (1.2) можно перейти, прибавив к каждому уравнению по
одной новой переменной, тогда ограничения примут вид
Добавленные переменные будут иметь нулевой вес в целевой функции.
Отметим, что для получения, в зависимости от вида неравенства, следует не только прибавлять, но и вычитать переменную в зависимости от знака неравенства, учитывая условие (1.3).
Если в исходной задаче не для некоторой переменной x i
не выполнено условие положительности, то ее следует заменить на разность двух
новых, положительных, переменных.
2. Общие идеи методов отсечения
Существует принципиальная возможность свести решение задачи (1.1) - (1.3)
к нахождению оптимального плана некоторой задачи линейного программирования
(без условия целочисленности переменных). Пусть X
- многогранное
множество, определяемое условиями (1.1), (1.2). Через X *
обозначим множество всех целочисленных векторов x *
, лежащих в
X
. Другими словами X *
задается условиями (1.1)-(1.3),
т.е.
По определению X * Í X . Будем обозначать через X z выпуклую оболочку множества X * . Тогда X z Í X .
Таким образом, мы сопоставили многогранному множеству X некоторое выпуклое множество X z ÍX согласно следующему правилу: X z есть минимальное выпуклое множество, содержащие все целочисленные векторы из X .
По предположению I, X является многогранником, следовательно множество X * конечно. Тогда выпуклое множество X z так же является многогранником, а следовательно, имеем, что X z можно задать конечным числом линейных неравенств.
Чтобы подчеркнуть основное отличие множества X z от множества X , дадим следующее определение.
Определение 1 . Многогранник, все крайние точки которого целочисленны (т.е. все их координаты целые числа), называются целочисленным многогранником.
Очевидно, что многогранник X z - целочисленный, по скольку его крайними точками являются лишь точки множества X * целочисленных планов.
Оправданием для изучения соответствия X ® X z является следующий простой факт.
Теорема 1 . Любой оптимальный опорный план задачи линейного программирования является решением задачи (1.1)-(1.3).
Доказательство.
Пусть `x *
- оптимальный опорный план задачи
(2.1), x *
- какое то решение исходной задаячи (1.1)-(1.3). `x *
ÎX z
ÍX
, то
<c
,`x *
> £ <c
, x *
>.
С другой стороны, так как x *
- целочисленный план, то x *
ÎX *
ÍX z
, и поэтому
<c
,`x *
> ³ <c
, x *
>,
откуда
<c
,`x *
> = <c
, x *
>.
Доказательство теоремы закончено.
Подчеркнем, что теорема 1 утверждает лишь принципиальную возможность сведения решения задачи целочисленного линейного программирования к поиску опорных планов задачи линейного программирования вида (2.1). Основная трудность в использовании этой возможности состоит в явном задании многогранника X z системой линейных неравенств с тем, что бы затем применить для решения задачи (2.1) численные методы линейного программирования. Вероятнее всего, что в вычислительном отношении эта проблема столь же сложна, как и исходная задача поиска оптимального целочисленного плана.
Несмотря на это, идея «сужения» множества X оказалась полезной и привела к созданию нескольких алгоритмов решения целочисленных задач линейного программирования, носящих название «методы отсечения».
Изложим идею методов отсечения. Допустим, что удалось построить последовательность {L r }, r = 0 , 1 , 2 , …, задач линейного программирования, каждая из которых определяется своим многогранником X r и одной для всех целевой функцией <c , x >:
при чем эта последовательность задач обладает следующими свойствами:
) X 0 =X , т.е. в качестве X 0 берется множество планов задачи (1.1),(1.2);
) X r z = X z , r=1,2, … ;
) если при решении задачи L r полученный оптимальный вектор x r * не удовлетворяет условию целочисленности, то он не является планом задачи L r+1 , т.е. x r * ÏX r+1 .
Отметим, что если на каком то шаге r вектор x r * - решение задачи L r - оказался целочисленным, то он является решением исходной задачи (1.1)-(1.3) в силу свойства 2) последовательности L r .
Интуитивно ясно, что последовательное построение задач L r , r=1,2, …, дает в некотором смысле аппроксимацию множества X z с помощью множества X r .
Способы построения последовательности {L r
},
обеспечивают конечность процесса решения задачи (1.1)-(1.3), были впервые
предложены Гомори.
3. Описание метода Гомори
Рассмотрим теперь алгоритм Гомори для решения целочисленных задач
линейного программирования. Этот метод принадлежит к числу методов отсечения и
реализует идеи, изложенный в предыдущем пункте.
3.1 Понятие правильного отсечения и простейший способ его построения
алгоритм гомора линейное программирование
Введем правильного отсечения, которое лежит в основе многих численных методов решения целочисленных задач линейного программирования.
Определение 2
. Пусть x* - оптимальный план задачи (1.1), (1.2), не
являющийся целочисленным. Неравенство
где g = (g 1 , g 2 , …, g n ), называется правильным отсечением, если оно удовлетворяет требованиям:
а) для вектора x *
неравенство не выполняется, т.е.
б) если x - целочисленный план задачи (1.1), (1.2) (т.е. план задачи (1.1)-(1.3)), то x - удовлетворяет (3.1) (условие правильности).
Понятно, что добавление неравенства (3.1) к условиям (1.1), (1.2) сужает допустимое множество X , сохраняя при этом все его целочисленные точки. Тем самым последовательное применение этого приема дает как бы многоэтапную аппроксимацию многогранника X z с помощью линейных ограничений.
В связи с понятием правильного отсечения возникают две проблемы. Первая из них состоит в том, что бы сформулировать общий алгоритм отсечения для произвольной целочисленной задачи линейного программирования. Вторая проблема состоит в построении правильного отсечения таким образом, что бы обеспечить решение задачи (1.1)-(1.3) за конечное число шагов, т.е. чтобы от множества X всякий раз отсекались достаточно большие участки.
Отметим, что второе требование является довольно тонким. В качестве подтверждения рассмотрим способ построения правильного отсечения, предложенный Данцигом.
Пусть x *
- опорный оптимальный план задачи (1.1),
(1.2), s и w - списки номеров соответственно базисных и не
базисных переменных, отвечающих некоторому базису плана x *
.
Тогда x j *
= 0 при j
Îw. С учетом этого свойства нетрудно
построить правильное отсечение для плана x*, если он является не целочисленным:
в качестве такого может служить неравенство
В самом деле, условие отсечения тривиально выполняется, поскольку . Условие правильности так же соблюдено, так как если x = (x 1 , x 2 , …, x n ) - целочисленный план задачи (1.1), (1.2), то величина с учетом условий x j ³ 0, j Îw , может быть меньше единицы лишь в том случае, когда x j = 0 при всех j Îw . Но в таком случае план x - опорный, и в качестве его базиса можно принять базис плана x * . Опорный план однозначно определяется своим базисом, откуда получаем, что из неравенства вытекает x=x * . Последнее, однако, невозможно, так как x - целочисленный вектор, а x * таковым не является.
Указанный прием построения правильного отсечения, несмотря на его простоту, оказался малоэффективным, поскольку конечность процесса решения обеспечивается лишь для узкого класса целочисленных задач линейного программирования.
Опишем способ построения правильного отсечения, предложенный Гомори. Для произвольного числа a , через [a ] будем обозначать его целую часть, т.е. [a ] есть наибольшее целое число k непревосходящее число a .
Дробной частью {a } числа a называется число {a } = a - [a ]. Отметим очевидное свойство дробной части произвольного числа: 0£{a }<1, причем {a } = 0 в том и только в том случае, когда a - целое число.
Пусть
x *
- опорное решение задачи (1.1), (1.2), не являющееся
целочисленным, 
- его базис и B
- соответствующая
симплекс-таблица в координатной форме.
Рассмотрим
приведенную систему уравнений, отвечающую данному базису (и таблице B
)
плана
x *
: 
Поскольку x j * = 0 при j Îw, то нецелочисленными могут быть лишь величины x 0 * = <c , x * >, x i * , i Îs.
Пусть s - такой индекс (0 £ s £ n ), что число x s * - не целое. Рассмотрим s -ю строку в симплексной таблице B (s -е уравнение в системе (3.2), (3.3)) и составим выражение
Теорема 2
. Если x
ÎX *
- целочисленный план задачи (1.1), (1.2), то
Доказательство.
Используя соотношение
a sj = [a sj ] + {a sj }, j = 0, 1, 2, … , n , из (3.3) при i = s получаем
откуда
В левой части данного неравенства стоит целое число, следовательно, число
также целое. Из того, что x j
³ 0, j
Îw, используя свойство дробной части,
получаем
т.е. - z s (x ) < 1, или z s (x ) > -1. Учитывая, что z s (x ) - целое, окончательно примем z s (x ) ³ 0.
Следствие. Если x s * (= a s0 ) - нецелое число и Множество X * планов целочисленной задачи (1.1)-(1.3) непусто, то среди чисел {a sj }, j =1, 2, …, n , есть положительные.
В самом деле, все числа {a sj }, очевидно неотрицательны. Допустим, что {a sj } = 0, j = 1, 2, …, n .
Если X * непусто и x * Î X * , то z s (x * )= - {a s0 }, о том, что z s (x * ) - целое число, так как 0 < {a s0 } < 1.
Замечание. В доказательстве теоремы 2 мы воспользовали предположением II
о том, что гарантирована целочисленность целевой функции. Действительно в
случае s
= 0 величина
является целой (при условии, что x Î X * ) лишь тогда когда число x 0 = < c , x > - целое.
Отсюда вытекает
Теорема 3.
Если число x s *
- нецелое, то
неравенство
является правильным отсечением.
Доказательство.
Проверим условие отсечения в определении 2. Так как x s *
= a
s0
, то из того, что x s *
- нецелое, получаем неравенство {a
s0
} > 0. Поскольку x j *
= 0 при j
Î w, то
и поэтому вектор x *
не удовлетворяет неравенству (3.5).
Условие правильности следует из утверждения z s
(x
) ³ 0 в теореме 2.
3.3 Первый
алгоритм Гомори
Перейдем к изложению первого алгоритма Гомори.
Обозначим задачу (1.1), (1.2) через L 0 . Гомори предложил на первом этапе своего алгоритма находить лексикографический максимум задачи L 0 . Будем обозначать через
x
(0) = (x
0 (0), x
1 (0),
…, x
n (0))
(n+1)-мерный вектор такой, что (x 1 (0), x 2 (0), …, x n (0)) - решение лексикографической задачи L 0 , а x 0 (0) = - значение линейной формы. В тех случаях когда это не вызывает недоразумения, будем называть x (0) - оптимальным планом лексикографической задачи L 0 (хотя по общепринятой терминологии планом называется вектор, составленный из последних n координат вектора x (0)).
Отметим также, что x (0) будет являться опорным планом, а так же строго допустимым псевдопланом задачи L 0 .
Если x(0) - целочисленный вектор, то он, очевидно, и является решением задачи (1.1) - (1.3).
В противном случае отыскивается минимальный индекс s, 0 £ s £ n, для которого величина x s (0) не является целой. Пусть B (0) - симплексная таблица в координатной форме, соответствующая вектору x (0). С помощью коэффициентов s -й строки этой таблицы (т.е. коэффициентов приведенной системы (3.2), (3.3)) приемом, описанным выше, строится правильное отсечение.
Вводится
вспомогательная переменная x n
+1 и рассматривается
задача L
1:
Следующий этап состоит в нахождении лексикографического максимума задачи L
1 .
Важным достоинством алгоритма Гомори является тот факт, что начальный
допустимый строгий псевдоплан для применения двойственного симплекс-метода к
задаче L
1 находится без труда. Действительно, легко видеть,
что в качестве такого псевдоплана можно взять вектор
В
самом деле, очевидно, что y
(1) удовлетворяет (вместе с вектоорм x
(0)) ограничениям (3.6), (3.7) задачи L
1 , а из ограничений (3.8)
нарушается лишь одно: x n
+1 (0)= - {a s
0 } < 0. Кроме того, y
(1) является опорным для
системы уравнений (3.6), (3.7), поскольку, если 
-
базис плана x
(0) то система
линейно независима и служит базисом для y
(1). Покажем, что y
(1)
- строго допустимый псевдоплан. С этой целью построим симплексную таблицу,
соответствующую указанному базису вектора y
(1). Для этого нужно лишь
приписать снизу к таблице B
(0) строку
Где w = {j
1 ,
j
2 , …, j n
-m
} - список
номеров небазисных переменных, соответствующих таблице B
(0) опорного
плана x
(0). Поскольку x
(0) - строго допустимый псевдоплан, то
всякий столбец b j
, j
Îw, таблицы B
(0)
лексикографически положителен: bj
> 0, j
Îw. Отсюда вытекает, что и в
симплексной таблице в координатной форме, отвечающей опорному вектору y
(1),
всякий столбец (кроме первого, совпадающего с y
(1)) лексикографически
положителен:
Таким образом, имея в своем распоряжении решение x (0) лексикографической задачи L 0 и соответствующую симплекс таблицу в координатной форме B (0), без каких либо дополнительных вычислений находим начальный строго допустимый псевдоплан y (1) для задачи L 1 и строим соответствующую ему симплексную таблицу в координатной форме.
Может случиться, что лексикографическая задача L 1 не имеет решения. В этом случае решение целочисленной задачи (1.1) - (1.3) следует прекратить поскольку имеет место
Теорема 4. Если в задаче L 1 не существует лексикографического максимума, то множество X * целочисленных точек задачи (1.1) - (1.3) пусто.
Доказательство. Поскольку множество X векторов, удовлетворяющих условиям Ax = b , x ³ 0, согласно предположению I ограничено, то ограниченным является и множество планов задачи L 1 . Поэтому единственной причиной, по которой эта задача может не иметь лексикографического минимума, может быть только то что множество ее планов пусто. Покажем что в таком случае множество X * также пусто.
Предположим противное, т.е. что X
* ¹ Æ, и пусть x
* = (x
1 * , x
2 * ,
…, x n
*) Î X*. По теореме 2 получаем, что величина
неотрицательна. Но это означает, что вектор = (x 1 * , x 2 * , …, x n * , x n +1 *) является планом задачи L 1 , в противоречие с вышесказанным. Теорема доказана.
Пусть x (1) = (x 0 (1), x 1 (1), …, x n (1), x n +1 (1)) - решение лексикографической задачи L 1 . Отправляясь от задачи L 1 и вектора x (1), аналогичным образом строятся задачи L r , r = 2, 3, …, и решения x (r ) Î Â n +1+r соответствующим им лексикографическим задач.
Заметим, что алгоритм Гомори однозначно определяет последовательность x (r ), r = 0, 1, 2, …, что следует из однозначности выбора s . Обратим так же внимание на то, что индекс s всегда не превосходит n: 0 s n. В самом деле, если все x j (r ) при j = 0, 1, 2, …, n - целые числа, то из теоремы 2 вытекает, что x n +1 (r ), x n +2 (r ), … - также целые.
Если на каком - то шаге r вектор
x
(r
) = (x
0 (r
),
x
1 (r
), …, x n
(r
), …, x n
+r
(r
))
оказывается целочисленным, то вектор (x 0 (r ), x 1 (r ), …, x n (r )) является решением задачи (1.1) - (1.3). Доказательство этого утверждения очевидно.
Переход от вектора x (r ) к вектору x (r +1) с помощью описанного алгоритма Гомори называется большой итерацией, в отличие от промежуточных итераций двойственного симплекс-метода, которые называются малыми.
Основной вопрос, относящийся к первому алгоритму Гомори таков: всегда ли за конечное число больших итераций можно получить целочисленный вектор x (r ).
Докажем конечность первого Алгоритма Гомори. Будем использовать следующие обозначения:
x
(0) = (x
0 (0), x
1 (0),
…, x n
(0));
где (x 1 (0), …, x n (0)) - решение лексикографической задачи L0, а x (0) = - соответствующее значение линейной формы (целевой функции).
y
(1) = (x
0 (0), x
1 (0),
…, x n
(0), x n
+1),
вектор y(1) служит начальным строго довпустимым псевдопланом при решении задачи L1 двойственным симплексным методом в координатной форме: `y (1) = (`y 0 (1), `y 1 (1), …, `y n (1), `y n +1 (1)) - вектор, получающийся из y (1) в результате первой (малой) итерации двойственного симплекс метода в координатной форме.
Аналогично вводятся обозначения
x
(r
), y
(r
+ 1), `y
(r
+ 1), r
= 1, 2, …
Из свойств двойственного симплекс метода в координатной форме следует
y (r ) >`y (r ) ³ x (r ).
Лемма 1.
Пусть s
- минимальный индекс, для которого число xs(0) - не
целое. Тогда
Доказательство.
Поскольку из (3.9) следует y
(1) >`y
(1), то возможно два случая:
В случае 1 утверждение леммы выполняется тривиально по определению лексикографического порядка.
Рассмотри случай 2. Согласно правилам двойственного симплекс-метода на
первой (малой) итерации решения задачи L
1 выводу из числа
базисных подлежит переменная x n
+1 , поскольку в
векторе y
(1) x j
(0) ³ 0, j
Î w, x n
+1
< 0. Пусть k
Î w - такой индекс, что
Для любого j Î w, если -{a sj } < 0. По правилам симплексного метода в число базисных вводится переменная x k .
Случай 2 возможен лишь при условии b ik
= 0, i
= 0, 1, 2, …, s
- 1. Поскольку x
(0)
- строго допустимый псевдоплан задачи L
0 , то все ее столбцы b j
, j
Î w, симплекс таблицы B
(0) лексикографически
положительны; в частности b k
> 0 . Следовательно, координата b sk
данного столбца должна быть неотрицательной. Заметим, что b sk
= a sk
(т.е. 0 £ s
£ n
и s
Î w), по условию (3.10) число a sk
- не нуль. Поэтому
a sk
> 0 и a sk
³ {a sk
}
По формуле преобразования симплекс-таблицы имеем
Вспоминая, что xs(0) = as0, получаем:
.
С учетом (3.11) получим оценку:
Лемма доказана.
Замечание. Если исходная задача (1.1) - (1.3) допустима, то согласно следствию из теоремы 2 индекс k, удовлетворяющий условию (3.10), существует.
Следствие. Справедливо соотношение
Действительно при r = 1 это неравенство вытекает из леммы и второго неравенства (3.9) . Что бы получить это утверждение при произвольном r , нужно воспользоваться тем, что y j (r ) = x j (r ) при 0 £ j £ n , и неравенством y (r ) ³ x (r ) в (3.9).
Теорема 5 . Если выполнены предположения I и II, то первый алгоритм Гомори требует лишь конечного числа больших итераций.
Что бы убедиться в истинности теоремы, необходимо показать, что при некотором r вектор x (r ) = (x 0 (r ), x 1 (r ), …, x n +r (r )) - целочисленный. Для этого, в свою очередь, достаточно доказать целочисленность вектора (x 0 (r ), x 1 (r ), …, x n (r )), поскольку из теоремы 2 тогда вытекает, что все числа x n +1 (r ), x n +2 (r ), …, x n +r (r ) также целые. Вспомним также, что минимальный индекс s, при котором число xs(r) - нецелое, всегда не превосходит n: 0 £ s £ n. Прежде чем переходить к основному доказательству докажем следующую лемму:
Лемма 2. Для любого j , 0 £ j £ n , существует такой номер R j , что при r ³ R j все числа x j (r ) - целые и равны одному и тому же целому числу x j (R j ).
Доказательство.
Пусть s
, 0 £ s
£ n
, - минимальный индекс для которого
утверждение Леммы не выполняется. Обозначим
В том случае когда s = 0, положим R = 0.
Пусть r
, l
- такие индексы, что R
£ r
£ l, и числа x s
(r
),
x s
(l
) - нецелые. Покажем, что тогда [x s
(r
)]
> [x s
(l
)]. Действительно по определению s
имеем
В таком случае s - минимальный индекс, для которого число x s (r ) - нецелое. По следствию из леммы 1 имеем [x s (r )] ³ x s (l ).
Учитывая, что x s (l ) - не целое число, имеем x s (l ) > [x s (l )], откуда и получаем нужное утверждение. Поскольку множество X планов задачи (1.1) - (1.3) ограничено, то ограничена любая величина x s (r ), 0 £ s £ n , r = 1, 2, … . Поэтому бесконечной цепочки неравенств вида [x s (r )] > [x s (l )] > … существовать не может, а, следовательно, в последовательности x s (r ), r = 0, 1, …, не может быть бесконечно много нецелых чисел. Аналогично доказывается, что в этой последовательности не может быть бесконечно много различных целых чисел.
Лемма доказана.
Вернемся к доказательству теоремы. Пусть
где числа R j фигурируют в формулировке леммы 2. Тогда согласно этой лемме все числа x j (R ), 0 £ j £ n , - целые. Из теоремы 2 получаем, что вектор x (R ) - целочисленный. Следовательно алгоритм Гомори требует не более R итераций.
Теорема доказана.
3.5 Замечания по практической
реализации первого алгоритма Гомори
При практической реализации первого алгоритма Гомори важной проблемой является нарастание количества ограничений, что ведет к увеличению размеров симплексных таблиц. Гомори предложил способ устранения этого недостатка алгоритма, заключающийся в следующем.
) В ходе решения задачи L r двойственным симплексным методом на каждой малой итерации следует пользоваться уточненным правилом вывода из числа базисных векторов для решения задач линейного программирования симплекс-методом: если в первом столбце симплексной таблицы имеется несколько отрицательных элементов b i 0 (= x i ), i =1, 2, …, n , …, n + r , то выводить из числа базисных надо переменную с минимальным номером.
) Если в ходе очередной малой итерации при реализации задачи L r все основные переменные x 1 , x 2 , …, x n оказались неотрицательными, то дальнейшее применение двойственного симплекс-метода к задаче L r следует прекратить, несмотря на то, что ее лексикографический максимум, быть может, еще не достигнут. Если при этом все переменные x j , j = 1, 2, …, n , оказались целочисленными, то по теореме 2 все вспомогательные переменные x n +k , k = 1, 2, …, r , целочисленны и неотрицательны. Это означает, как уже известно, что вектор (x 0 , x 1 , x 2 , … , x n ) является решением исходной целочисленной задачи. В противном случае переходим к новой большой итерации.
) Строка симплексной таблицы, соответствующая вспомогательной переменной x n +r , удаляется, как только переменная x n +r объявляется небазисной. Напомним, что это происходит на первой же малой итерации решения задачи L r .
) Если в ходе решения задачи L r переменная x n +r вновь попадает в число базисных, то то соответствующая ей строка не восстанавливается.
Понятно, что при выполнении правил 3), 4) размеры симплексной таблицы в первом алгоритме Гомори не увеличиваются - в каждой таблице содержится n + 2 строк, отвечающие основным переменным x 0 , x 1 , … , x n и текущей вспомогательной переменной x n +r в момент ее введения) и n - m +1 столбцов (поскольку число n - m небазисных переменных не меняется).
) На первой малой итерации решения задачи L r +1 в качестве переменной, выводимой из базиса, выбирается именно x n +r +1 , не смотря на то, что значения остальных вспомогательных переменных в этот момент так же могут быть отрицательными.
Заметим, что правило 5) на самом деле избыточно, поскольку при выполнении правил 3) и 4) мы ничего не знаем о значении остальных переменных x n +1 , …, x n +r в момент перехода к задаче L r +1 . Данное правило выделено лишь для того, чтобы подчеркнуть отличие рассматриваемых алгоритмов.
Отметим, что при использовании правила 2) возникающая последовательность x ’ (r ) может не быть лексикографическим максимумом задачи L r , поскольку значения некоторых из вспомогательных переменных могут быть отрицательными.
Тем не менее, для последовательности x ’ (r ), r = 0, 1, 2, …, получаемой с использованием правил 1) и 2), сохраняется важное свойство: эта последовательность единственна.
Осталось лишь доказать, что при использовании правил 1) - 4) алгоритм Гомори остается конечным, поскольку его конечность и будет означать, что он приводит к цели - нахождению целочисленного решения задачи (1.1) - (1.3). В самом деле, конечность числа R больших итераций означает, что вектор x ’ (R ) целочисленный.
Отметим, во-первых, что при использовании правила 2) число малых итераций решения задачи L r конечно - не больше, чем требуется для нахождения ее лексикографического максимума.
Теорема 6. Последовательность x’(r), возникающая в процессе применения алгоритма Гомори, уточненного правила 1) - 4), конечна.
Доказательство. Заметим, что в доказательстве теоремы 5 о конечности последовательности x(r) использовались лишь два обстоятельства, регулирующие возникновение этой последовательности: способ построения правильного отсечения и тот факт, что во всякой текущей симплекс-таблице вс столбцы b j , j Îw, лексикографически положительны. Таким образом, удаление строки, соответствующей вспомогательной переменной, может повлиять лишь на последнее обстоятельство. Этого, однако, так же быть не может, как показано в следующей лемме.
Лемма 3.
В любой симплекс-таблице, возникающей в ходе алгоритма Гомори,
уточненного правилами 1) - 4), для любого столбца
имеет место неравенство
Доказательство.
Допустим, что утверждение леммы не выполняется для
некоторого k
Î w. Поскольку b k
, то данное предположение означает,
что
По определению симплексной таблицы в координатной форме, имеем
Для любого x Î R n +1+r , если утверждение леммы нарушается в ходе решения задачи L r . Формула (3.13) с учетом (3.12) означает, что изменение значения переменной x k не влияет на значение x i , i = 0, 1, 2, …, n . Другими словами, при одном и том же наборе величин x i , 0£i £n , переменная x k может принимать произвольное значение. Отсюда следует, во-первых, что k ³ n + 1, а во-вторых, что принятое допущение (3.13) неверно, поскольку поскольку значение любой вспомогательной переменной x k , k ³ n + 1, как вытекает из (3.7), однозначно определяется значениями основных переменных.
Поскольку удаление строк, соответствующих вспомогательных переменным, не влияет на свойство столбцов b j , j Î w, быть лексикографически положительными, то эти строки вообще не нужны. Действительно, с учетом правил 1) - 2) переменная x n +r , попав в число базисных, так и остается базисной до конца вычислений, и ее строка не потребуется для определения переменной, вводимой в базис согласно правилам симплекс-метода.
Таким образом, элементы строки, соответствующие переменной x n +r , не участвуют в формулах двойственного симплекс-метода для вычисления значений всех остальных переменных.
Поскольку, как отмечалось, индекс s
, регулирующий формирование
правильного отсечения, не превосходит n
, 0 £ s
£ n
, то и для этих целей
вспомогательные переменные не потребуются.
4. Реализация на ЭВМ
В данном курсовом проекте программа предназначена для нахождения решения целочисленной задачи линейного программирования методом Гомори.
В программном модуле используется алгоритм описанный в теоретической части с учетом замечаний по практическому применению метода, сделанных Гомори.
Ввод данных в программном модуле производится из файла. Вывод результатов
работы программы может производится в файл, на дисплей или на принтер. Формат
входного файла:
где n - количество переменных, m - количество ограничений, c 1 , c 2 , … , c n - коэффициенты максимизируемой линейной формы, a ij - элементы матрицы A, b j - компоненты вектора b . A, b - характеризуют ограничения [см. (1.2)].
Пример входного файла:
2 5 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 12
2 5 0 1 0 0 0 0 0 30
3 2 0 0 1 0 0 0 0 22
2 -1 0 0 0 1 0 0 0 12
1 -3 0 0 0 0 1 0 0 0
2 5 0 0 0 0 0 -1 0 10
5 1 0 0 0 0 0 0 -1 5
Список литературы:
1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. - Л.: Изд-во ЛГУ, 1981. -328 с.
Белоусова Г.С. Линейное программирование. Учебное пособие. -Красноярск: Наука, 1975. -107 с.
Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. - 2-е изд., перераб. и доп. -М.: Высшая школа, 1980. -300 с.
Ашманов С.А., Линейное программирование. М.: Наука. 1969. -240 с
Габасов
Р.И. Кириллова Ф.М., Методы линейного программирования. Минск: Наука. 1977.
-174 с
Для решения целочисленных задач линейного программирования с произвольным числом переменных можно использовать метод Гомори, с помощью которого от области программ отсекаются точки с нецелочисленными координатами. Сформулируем алгоритм Гомори для решения целочисленной задачи линейного программирования в стандартной форме
Алгоритм Гомори
ГП С помощью симплекс-метода находим оптимальную программу. Если получились целочисленные значения для всех Xj , то задача решена. В противном случае среди Xj имеются нецслочисленные значения.
|~2~1 Среди нецелых Xj выбираем произвольный элемент х г и в задаче добавляем еще одно ограничение
что равносильно добавлению в симплекс-таблице еще одной строки, после чего она перестает соответствовать допустимому базисному решению новой задачи линейного программирования, которую она описывает. В ограничении применяются дробные части элементов строки, в которой находится х г. Применяемое обозначение для дробной части исходит из того, что всякое действительное число у можно представить в виде суммы у = [у] + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.
[з] Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I = п + 1.
- а) Если все коэффициенты уц > 0, то задача не имеет решения (т.е. целочисленная задача решена).
- б) В противном случае находим индекс к такой, что
(критерий входа в новый базис). Заметим, что выбор разрешающего элемента у и* не изменяет знак у критериев Aj.
[4] Если в новой таблице имеется хотя бы один х 3 s и повторить указанные процедуры необходимое число раз.
[~5~| Если полученное оптимальное решение целочисленно, то поставленная задача решена. В противном случае надо вернуться к пункту .
Пример 4.6.1. Решить методом Гомори целочисленную задачу
Решение. После добавления вспомогательных переменных имеется следующая задача линейного программирования в стандартной форме:
с матрицами
|
Таблица 1 |
||||||
|
Х 4 |
||||||
к = 1 Т
С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 6*.
|
Таблица 2 |
х 2 |
|||||
|
„ _ 1 Ж Z ~_3_ |
||||||
к" = 2 Т
Разрешающий элемент - 1/2*.
Х в ^ 0). Следовательно, программа {xi = 11/3, х 2 = 5} даст максимум экономической функции z, равный 1370/3 = 45б|, т.с. z = z max = 456§. "
Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей се элементов, выбираем вторую строку (индекс 7’ = 1). Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями для дополнительной переменной Ж5 и дополнительный столбец. Получаем
к" = 4 Т
После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. /" = 5.
Находим разрешающий столбец, т.с. индекс к" такой, что
(критерий входа в новый базис). Разрешающий элемент - (-2/3*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.
Заполним симплекс-таблицу 4.
|
Таблица 4 |
Х 2 |
||||||
|
Х 2 |
|||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 3, ж 2 = 6, х± = 1} дает максимум экономической функции г, равный 450, т.с. z = z ma ^ = 450. Эта оптимальная программа является целочисленной. ?
Пример 4.6.2. Решить методом Гомори целочисленную задачу
Решение. Имеется задача линейного программирования с матрицами
Заполним симплекс-таблицу с начальной программой.
|
Таблица 1 |
|||||||
к = 1 Т
С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 1*.
|
Таблица 2 |
Х 2 |
||||||
Разрешающий элемент - 5*.
|
Таблица 3 |
|||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 12/5, 24 = 1/5, 25 = 28/5} дает минимум экономической функции г, равный -11/5 = -2.2, т.с. z =
~min = -2.2.
Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей сс элементов, выбираем, например, третью етроку (индекс г = 5) с максимальной дробной частью. Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями третьей строки для дополнительной переменной xq (эта строка позволяет отсечь от области программ части, содержащие точки с нецслочислснными координатами) и дополнительный столбец. Получаем
|
Таблица 3" |
||||||||
|
г - -И |
||||||||
к" = 3 Т
После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I" = 6.
Находим разрешающий столбец, т.е. индекс к" такой, что
(критерий входа в новый базис). Разрешающий элемент - (-3/5*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.
Заполним симплекс-таблицу 4.
|
Таблица 4 |
||||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {х = 2, Х 2 = 0, хз = 1, х 4 = 0, ж 5 = 5} даст минимум экономической функции z 9 равный (-2), т.с. z = -min = - 2. Эта оптимальная программа является целочисленной. ?
Задача 4.6.1. Решить методом Гомори целочисленную задачу
Ответ. Программа
дает минимум экономической функции z, равный (-31), т.с. z = 2 m i n = -31. Эта оптимальная программа является целочисленной.
Экономическая и геометрическая интерпретация задачи целочисленного программирования. Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
В математической модели задачи целочисленного программирования как целевая функция, так и функции в системе ограничений могут быть линейными, нелинейными и смешанными. Ограничимся случаем, когда целевая функция и система ограничений задачи являются линейными.
Пример 20.
В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., а II вида – 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Зная что для установки одного комплекта оборудования I вида требуется 2 м 2 площади, а оборудования II вида – 1 м 2 площади определить такой набор дополнительного оборудования, которых дает возможность максимально увеличить выпуск продукции
Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет x 1 комплектов оборудования I вида и комплектов оборудования II вида. Тогда переменные x 1 и должны удовлетворять следующим неравенствам:
Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит
По своему экономическому содержанию переменные x 1 и могу принимать лишь целые неотрицательные значения, т. е.
x 1 , – целые. (73)
Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (71) при вы полнении условий (70), (72) и (73). Так как неизвестные могут принимать только целые значения, то задача (70) – (73) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого прежде всего построим многоугольник решений задачи, состоящей в определении максимального значения линейной функции (71) при выполнении условий (70) и (72) (рис. 11). Координаты всех точек построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (70) и условию неотрицательности переменных (72). Вместе с тем условию (73), т. е. условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF , содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (71) на многоугольнике OKEMNF , то координаты этой точки и определят оптимальный план задачи.
Для этого построим и прямую проходящую через многоугольник решений OKEMNF (число 12 взято произвольно). Построенную прямую передвигаем в направлении вектора до тех пор, пока она не пройдет через последнюю общую точку ее с данным многоугольником. Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является максимальным.
В данном случае искомой является точка E (1; 3), в которой целевая функция принимает максимальное значение С ледовательно, координаты точки Е определяют оптимальный план задачи (70) – (73). В соответствии с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуск продукции, равное 14 ед. в смену.
Пример 21.
Для выполнения работ могут быть использованы п механизмов. Производительность i –го механизма при выполнении j – й работы равна . Предполагая, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами, обеспечивающее максимальную производительность. Построить математическую модель задачи.
Решение. Введем переменную x ij , значение которой равно 1, если при выполнении i–й работы используется j – й механизм, и равно 0 в противном случае. Тогда условия использования каждого механизма только на одной работе выражаются равенствами
(74)
а условия выполнения работы только одним механизмом – равенствами
(75)
Таким образом, задача состоит в
определении таких значений неизвестных 
, удовлетворяющих системам
уравнений (74) и (75) и условию (76), при которых достигается максимальное
значение функции
Сформулированная задача является задачей целочисленного программирования.
Определение оптимального плана задачи целочисленного программирования. Рассмотрим задачи целочисленного программирования, в которых как целевая функция, так и функции в системе ограничений являются линейными. В связи с этим сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения. В общем виде эту задачу можно записать так: найти максимум функции
при условиях
(79)
– целые (81)
Если найти решение задачи (78) – (81) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером , решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (78) – (81) требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори , в основе которого лежит описанный выше симплексный метод.
Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) – (80) переменная принимает дробное значение, то к системе уравнений (79) добавляют неравенство
(82)
и находят решение задачи (78) – (80), (82).
В неравенстве (82) и – преобразованные исходные величины и значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (78) – (80) дробные значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной частью.
Если в найденном плане задачи (78) – (80), (82) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.
Если требование целочисленности (81) относится лишь к некоторым переменным, то такие задачи называются частично целочисленными. Их решение также находят последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения. В этом случае такое ограничение имеет вид
где определяются из следующих соотношений:
1) для , которые могут принимать нецелочисленные значения,
(84)
2) для , которые могут принимать только целочисленные значения,
(85)
Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы :
1. Используя симплексный метод, находят решение задачи (78) – (80) без учета требования целочисленности переменных.
2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане задачи (78) – (81) должна быть целочисленной.
3. Используя двойственный , находят решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.
4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (78) – (81) или установления ее неразрешимости.
Пример 22.
Методом Гомори найти максимальное значение функции
при условии
(87)
– целые (89)
Решение. Для определения оптимального плана задачи (86) – (89) сначала находим оптимальный план задачи (86) – (88) (табл. 22).
Таблица 22
|
С б |
Р 0 |
|||||||
Как видно из
табл. 22, найденный
оптимальный план 
задачи (86) – (88) не является оптимальным планом задачи (86) –
(89), поскольку две компоненты и имеют нецелочисленные значения. При этом дробные части этих
чисел равны между собой. Поэтому для одной из этих переменных составляется
дополнительное ограничение. Составим, например, такое ограничение для
переменной Из
последней симплекс–таблицы (табл. 22) имеем
Таким образом, к системе ограничений задачи (86) – (89) добавляем неравенство
или
Таблица 23
|
С б |
Р 0 |
||||||||
Находим теперь максимальное значение функции (86) при выполнении условий (87), (88) и (90) (табл. 23).
Из таблицы 23 видно, что исходная задача
целочисленного программирования имеет оптимальный план
П
ри этом плане значение целевой функции равно .
Дадим геометрическую интерпретацию решения задачи. Областью допустимых
решений задачи (86) – (88) является многоугольник OABCD
(рис. 12).
Из рис. 12 видно, что максимальное значение целевая функция принимает в
точке С
(19/2; 7/2), т. e
. что Х =
(19/2; 7/2; 0; 0; 34) является
оптимальным планом. Это непосредственно видно и из таблицы 22. Так как
Х
= (19/2; 7/2; 0; 0; 34) не является оптимальным планом задачи
(86) – (89) (числа и – дробные), то
вводится дополнительное ограничение . Исключая
из
него и подстановкой вместо них соответствующих значений из уравнений
системы ограничений (87), получим отсекающий от многоугольника
OABCD
треугольник EFC.
Как видно из
рис
. 12, областью допустимых решений полученной
задачи является многоугольник OABEFD
. В точке Е
(9; 4) этого
многоугольника целевая функция данной задачи принимает максимальное
значение. Так как координаты точки Е
– целые числа и неизвестные
,
и принимают целочисленные
значения при подстановке в уравнение (87) значений и , то
является оптимальным планом задачи (86) – (89). Это следует и из
таблицы 23.
Пример 23.
Методом Гомори найти решение задачи, состоящей в определении максимального значения функции
при условиях
– целые. (94)
Дать геометрическую интерпретацию решения задачи.
Решение. Сформулированную задачу перепишем так: найти максимальное значение функции
при условиях
(96)
– целые. (98)
Задача (95) – (98) является частично целочисленной, так как переменные и могут принимать нецелочисленные значения.
Находим симплексным методом решение задаяи (95) – (97) (таблица 24).
Таблица 24
|
С б |
Р 0 |
|||||||
|
С б |
Р 0 |
|||||||
|
–1/3не является планом задачи (95) – (98), так как переменная |
По смыслу значительной части экономических задач, относящихся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие.
Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) i, при котором линейная функция
принимает максимальное или минимальное значение при ограничениях
(8.2)
(8.3)
– целые числа. (8.4)
Следует отметить, что классическая транспортная задача и некоторые другие задачи транспортного типа "автоматически" обеспечивают решение задачи в целых числах (если, конечно, целочисленны параметры условий). Однако в общем случае условие целочисленности (8.4), добавляемое к обычным задачам линейного программирования, существенно усложняет ее решение.
Для решения задач линейного целочисленного программирования используется ряд методов. Самый простой из них – обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочисленными, их округляют до ближайших целых чисел. Этот метод применяют тогда, когда отдельная единица совокупности составляет малую часть объема всей совокупности. В противном случае округление может привести к далекому от оптимального целочисленному решению, поэтому используют специально разработанные методы.
Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинаторные методы; в) приближенные методы. Остановимся подробнее на методах отсечения.
Методы отсечения. Метод Гомори
Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленное™. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением .
Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с оптимальной точкой с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся
в первоначальном многограннике решений, и соответственно полученное при этом многограннике оптимальное решение будет целочисленным (рис. 8.1).
Один из алгоритмов решения задачи линейного целочисленного программирования (8.1)-(8.4), предложенный Р. Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.
Пусть задача линейного программирования (8.1)-(8.3) имеет конечный оптимум, и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные 
через неосновные переменные оптимального решения:
(8.5)
так что оптимальным решением задачи (8.1)-(8.3) является i, в котором, например, β; – нецелая компонента. В этом случае можно доказать, что неравенство, сформированное по i- му уравнению системы (8.5), обладает всеми свойствами правильного отсечения.
Для решения задачи целочисленного линейного программирования (8.1)-(8.4) методом Гомори используется следующий алгоритм.
- 1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (8.1)-(8.4). Если первая задача (8.1)-(8.3) неразрешима (т.е. нс имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразрешима.
- 2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (8.5) сформировать правильное отсечение (8.6).
- 3. Неравенство (8.6) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение и включить его в систему ограничений (8.2).
- 4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (8.1)–(8.4) решена. В противном случае вернуться к п. 2 алгоритма.
Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.
1 В неравенстве (8.6) присутствует символ { }, означающий дробную часть числа. Целой частью числа а называется наибольшее целое число [в], не превосходящее а, дробной частью числа – число {а}, равное разности между этим числом и его целой частью, т.е. {а} = а-[в].
Например, для (обратите внимание, именно -3, а не -2) и
Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения.
8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с учетом проходов), и производительностью за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м, и производительностью за смену 3 т сортового зерна.
Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фермер может приобрести не более 8 машин типа В.
Решение. Обозначим черезколичество машин соответственно типа А и В, через Z – общую производительность. Тогда математическая модель задачи примет вид
(!!!8.8)
при ограничениях:
(8.2)
– целые числа. (8.4)
Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные. Получим систему ограничений:
(8.5)
Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 8.2).
На рис. 8.2 OKLM – область допустимых решений задачи (8.Г)–(8.3"), ограниченная прямыми (1), (2), (3) и осями координат; L (2/3; 8) – точка оптимального, но нецелочисленного решения задачи (8.1")–(8.3"); (4) – прямая, отсекающая это нецелочисленное решение; OKNM – область допустимых решений расширенной задачи (8.1")–(8.3"), (8.6"); N(2; 7) – точка оптимального целочисленного решения.
I шаг. Основные переменные Неосновные переменные
Первое базисное решение– допусти
мое. Соответствующее значение линейной функции
Переводим в основные переменные переменную, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной, которое "позволяет"
принять система ограничений, из условия минимума соответствующих отношений:
т.е. разрешающим (выделенным) является третье уравнение. При х. 2 = 8 в этом уравнении х- = 0, и в неосновные переходит переменная х 5.
II шаг. Основные переменные х 2, х 3, х 4.
Неосновные переменные.г, ху
После преобразований получим
Переводим в основные переменную
а в неосновные х4.
III шаг. Основные переменные х, х 2, х 3.
Неосновные переменные х4, х5.
После преобразований получим
Базисное решение X., оптимально для задачи (8.1")–(8.3") (), так как в выражении линейной функции
отсутствуют неосновные переменные с положительными коэффициентами.
Однако решение Х 3 не удовлетворяет условию целочисленности (8.4") По первому уравнению с переменной х, получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (8.6):
Обращаем внимание на то, что согласно (8.5) и (8.6) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х- – с противоположными знаками.
Так как дробные части
,
, го последнее неравенство запишем
(8.6")
Введя дополнительную целочисленную переменную х6 ≥ 0, получим равносильное неравенству (8.6") уравнение
(8.7")
Уравнение (8.7") необходимо включить в систему ограничений (8.5") исходной канонической задачи, после чего повторить процесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (8.7") в систему, полученную на последнем шаге решения задачи (без условия целочисленности).
IV шаг. Основные переменные x v х 2, х3, χβ.
Неосновные переменные х4, х5. 
Базисное решение – недопусти
мое. (Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение.)
Для получения допустимого базисного решения необходимо перевести в основные переменную, входящую с положительным коэффициентом в уравнение, в котором свободный член отрицательный, т.е. х, или х. (на этом этапе линейную функцию не рассматриваем). Переводим в основные, например, переменную х5 .
V шаг. Основные переменные х, х2, х3, х5.
Неосновные переменные х4, х6.
Получим после преобразований
Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х 5 – оптимальное решение.
Итак, Zmax = 25 при оптимальном целочисленном решении X* = Х 5 = (2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа Л и 7 машин типа В при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выделенных равны нулю, в резерве для покупки – 1 машина типа В (шестая компонента содержательного смысла не имеет).
Замечание. Для геометрической интерпретации на плоскости Ох,х2 (см. рис. 8.2) отсечения (8.6") необходимо входящие в него переменные х 4 и х- выразить через переменные х, и х2. Получим (см. 2-е и 3-е уравнения системы ограничений (8.5"))
- (см. отсечение прямой (4) на рис. 8.2).
- 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 и 0,9 м, причем заготовок каждого вида должно быть получено не менее 50 и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способами: 1) на 2 заготовки но 1,2 м; 2) па 1 заготовку 1,2 м и 2 заготовки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен, распиливаемых каждым способом, с тем чтобы заготовок любого вида было получено из наименьшего числа бревен.
Решение. Обозначим через х {} х2, х3 число бревен, распиливаемых соответственно 1, 2 и 3-м способами. Из них можно получить 2xj +х2 заготовок по 1,2 м и 2х х +3х2 заготовок по 0,9 м. Общее количество бревен обозначим Z. Тогда математическая модель задачи примет вид
при ограничениях:
Введя дополнительные переменныепри
ведем систему неравенств к равносильной системе уравнений:
(8.5")
Решая полученную каноническую задачу (без условия целочисленности) симплексным методом, на последнем, III, шаге решения найдем следующие выражения основных переменных и линейной функции через неосновные переменные (рекомендуем студентам получить их самостоятельно).
III шаг. Основные переменные x v х 2.
Неосновные переменные х у х А, х 5.
т.е.при оптимальном решении
Получилось, что две компоненты оптимального решения 
не удовлетворяют условию целочисленности (8.4"), причем бо́льшую целую часть имеет компонента х
2. В соответствии с ∏. 2 алгоритма решения задачи целочисленного программирования (см. с. 166) по второму уравнению, содержащему эту переменную х
2, составляем дополнительное ограничение (8.6):
Найдем дробные части
и запишем последнее неравенство в виде
(8.6")
Введя дополнительную переменнуюполучим
равносильное неравенству (8.6") уравнение:
(8.7")
Выразим из (8.7") дополнительную переменную х6 и полученное уравнение введем в систему ограничений, которую мы имели на последнем, III, шаге решения задачи (8.1")– (8.3") (без условия целочисленности).
IV шаг. Основные переменные х {, х у х 6.
Неосновные переменные х 3, х4, х 5.
Решая эту расширенную задачу симплексным методом (предлагаем студентам выполнить самостоятельно), получим следующее.
V шаг. Основные переменные х); х 2, х3.
Неосновные переменные х4, х5, хб.
т.е.при оптимальном решении
Полученное оптимальное решение расширенной задачи (8.1")–(8.3"), (8.6") вновь не удовлетворяет условию целочисленности (8.4"). По первому уравнению с переменной Xj, получившей нецелочисленное значение в оптимальном
решении (), еоставляем второе дополнительное ограни
чение (8.6):
которое приводим к виду
С помощью дополнительной переменнойприво
дим это неравенство к равносильному уравнению, которое включаем в систему ограничений, полученную на последнем, V, шаге решения расширенной задачи (8. Г")–(8.3"), (8.6") симплексным методом.
VI шаг. Основные переменные x v х 2, х у х т
Неосновные переменные х 4, X-, х 6.
Опуская дальнейшее решение задачи симплексным методом (предлагаем сделать это самим студентам), на заключительном, VII, шаге получим.
VII шаг. Основные переменные x v х т х3, х г
Неосновные переменные x v х 6, х т
Так как в выражении линейной функции нет неосновных переменных с отрицательными коэффициентами, то Х 7 – оптимальное целочисленное решение исходной задачи.
Следует обратить внимание на то, что в полученном выражении линейной функции Z отсутствуют неосновные переменные х
Г) и х
6. Это означает, что, вообще говоря, существует бесконечное множество оптимальных решений (любых, не обязательно целочисленных), при которых Z" = Zmjn = 46. Эти решения получаются при значении неосновной переменной х
7 (входящей в выражение для Z), равной нулю (т.е. при х
7 = 0), и при любых
значениях неосновных переменных ж5 и х
6 (не входящих в выражение для Z), которые "позволяет" принять система ограничений: 0<лг5
Наличие альтернативных оптимальных целочисленных решений позволяет осуществить выбор одного из них, руководствуясь дополнительными критериями, не учитываемыми в математической модели задачи. Например, из условия данной задачи следует, что распиливание бревен не дает отходов лишь по 3-му способу, поэтому естественно при выборе одного из четырех оптимальных решений отдать предпочтение решению Х^ 3 при котором максимальное число бревен (х 2 = 41) распиливается без отходов.
Итак, Zmin=46 при оптимальных целочисленных решениях (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). При записи оптимальных решений мы оставили лишь первые три компоненты, выражающие число бревен, распиливаемых соответственно 1, 2 и 3-м способами, и исключили последние четыре компоненты, не имеющие смыслового значения.
Недостатком метода Гомори является требование целочисленности для всех переменных – как основных (выражающих, например, в задаче об использовании ресурсов единицы продукции), так и дополнительных (выражающих величину неиспользованных ресурсов, которые могут быть и дробными).
- Можно убедиться, что при этом решение задачи короче.
Пусть
оптимальный план, полученный
симплекс-методом для задачи (5.1)-(5.3),
следующий:
и получен на базисе
Тогда последняя симплексная таблица
имеет следующий вид:
Таблица 5.1
Приведённая к базису симплексная таблица для задачи целочисленного программирования
Предположим,
что
дробное;
тогда некоторое
также дробное (в противном случае задача
не имеет целочисленного решения).
Обозначим через
и
целые части чисел
и
,
т.е. наибольшие целые числа, не
превосходящие числа
и
.
Тогда величины дробных частей
и
чисел
и
определяются как разности:
где
и
Например,
.
Так
как по условию
– неотрицательные целые числа, то и
разностьтакже целое неотрицательное число.
Преобразуя
это неравенство в уравнение, вычитая
из его левой части целую неотрицательную
дополнительную переменную
умножим уравнение на –1, добавим к
последней симплексной таблице и, применяя
симплексный метод (желательно
двойственный), находим новый план. Если
он не является целочисленным, то по
последней симплексной таблице составляем
новое дополнительное ограничение.
Если
в оптимальном плане задачи (5.1)-(5.3)
несколько дробных
то дополнительное ограничение составляют
дляmax
.
Это ускоряет процесс получения
оптимального целочисленного решения.
Рассмотрим
геометрический смысл введения
дополнительного ограничения (см. рис.
5.2). Пусть в точке A
многогранника
решений Q
функция Z
достигает максимального значения
Z
(A
)=max,
но координаты точки A
– дробные. Тогда введенные ограничения
по целочисленности I
и II
от области
Q
отсекают область
с угловой точкой
,
координаты которой целочисленные и в
которой линейная функция достигает
максимального значения.
Рис.5.2. Геометрический смысл ограничения Гомори
Метод Гомори рассмотрим на примере следующей задачи.
Пример 5.1. Найти максимальное значение функции
|
|
при условиях
Дать геометрическую интерпретацию решения задачи.
Решение. Для определения оптимального плана задачи (5.5)-(5.8) сначала находим оптимальный план задачи (5.5)-(5.7):
Таблица 5.2
базис
план
– неоптимальный,
.
Таблица 5.3
Симплекс-таблица,
приведённая к базису
,
– неоптимальный,
базис
,
.
Таблица 5.4
Симплекс-таблица,
приведённая к базису
Оптимальный
план
,
базис
.
Этот оптимальный план не является
оптимальным планом задачи (5.5)-(5.8),
поскольку две компоненты
и
имеют нецелочисленное значение. При
этом дробные части этих чисел
равны между собой. Поэтому для одной из
этих переменных составляется дополнительное
ограничение. Составим, например, такое
ограничение для переменной
(чаще берут первую строку). Из последнейсимплекс-таблицы
имеем:
.
Таким образом, к системе ограничений задачи (5.5)-(5.7) добавляем неравенство
|
|
Теперь находим максимальное значение функции (5.5) при выполнении условий (5.6), (5.7) и (5.9). В условие (5.9) вводим дополнительную переменную :
Таблица 5.5
Ввод
в симплекс-таблицу дополнительной
переменной
Выберем
.
базис.
Таблица 5.6
Приведение
симплекс-таблицы к базису
Базис
.
.
Запишем
оптимальный план для исходной задачи:
При этом плане значение целевой функции
равно
.
Геометрическая интерпретация решения задачи.
Рис.5.3. Геометрическая интерпретация решения задачи
Областью
допустимых решений задачи (5.5)-(5.7) является
многоугольник ОАВС
D
(рис. 5.3). Из рисунка видно, что максимальное
значение целевая функция принимает в
точке
т.е.
является оптимальным планом. Так как
этот план не является оптимальным планом
задачи (5.5)-(5.8) (числа
и–
дробные), то вводится дополнительное
ограничение
Исключая
из этого неравенства
и
подстановкой вместо них соответствующих
значений из уравнений системы ограничений
(5.6), получим
.
.
Этому
неравенству соответствует полуплоскость,
ограниченная прямой
отсекающей отмногоугольника
ОАВСD
треугольник
EFC
.
Как
видно из рисунка, областью допустимых
решений полученной задачи является
многоугольник OABEFD
.
В точке E
(9;4)
этого многоугольника целевая функция
данной задачи принимает максимальное
значение. Так как координаты точки Е
– целые числа и неизвестные
и
принимают целочисленные значения при
подстановке в уравнения (5.6) значений
и
то
является оптимальным планом задачи
(5.5)-(5.8). Это следует и из таблицы
симплекс-метода.
Замечание к использованию метода Гомори: если в первоначальный базис задачи входили искусственные векторы, то при составлении дополнительного ограничения искусственные переменные необходимо опустить.
Вопросы для самопроверки
Области применения целочисленного программирования.
Постановка задачи целочисленного программирования.
Графический способ решения задачи целочисленного программирования.
Алгоритм метода Гомори.
Правило составления дополнительного ограничения (сечения Гомори).
Геометрический смысл введения сечения Гомори.
