ИсследОпераций

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

т.д. до тех пор, пока решение очередной ЗЛП не будет удовлетворять требованию целочисленности.

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

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

§ 2. Построение правильного отсечения методом Гомори

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

Рассмотрим предложенный Гомори метод построения правильного отсечения для полностью целочисленных ЗЛП. Не умаляя общности рассуждений, ограничимся случаем ЗЛП с четырьмя переменными и двумя ограничениями

Отбросив условие целочисленности (2.2), получим каноническую ЗЛП (2.1). В предположении, что решение этой задачи существует, решим ее сим- плекс-методом.

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

93

Известно, что система (2.3) равносильна системе ограничений задачи (2.1), а ее основное опорное решение x 0, 0, b1, b2 является оптимальным планом зада-

чи (2.1).

Теорема 2.1. Если число bk ( k 1 или 2) – нецелое, то неравенство

ak1 x1 ak 2 x2 bk

удовлетворяет всем требованиям, содержащимся в определении правильного отсечения.

Подставив компоненты плана x в неравенство (2.4), получим 0 b1 , что невозможно, так как по условию b1 – нецелое и, следовательно, b1 0. Значит,

оптимальный нецелочисленный план задачи (2.1) не удовлетворяет неравенству

(2.4).

Пусть теперь x x1, x2, x3, x4 – произвольный целочисленный план задачи

(2.1), (2.2). Его компоненты удовлетворяют системе ограничений задачи (2.1), а, следовательно, и равносильной ей системе (2.3). Подставив компоненты плана x в первое уравнение системы (2.3), запишем коэффициенты этого уравнения в виде суммы их целых и дробных частей

a11 a11 x1 a12 a12 x2 x3 b1 b1 .

Перепишем полученное равенство следующим образом

Левая часть равенства (2.5) является целым числом, тогда и правая часть – целое число. Кроме того

Учитывая неравенство (2.6) и доказанную целочисленность его левой части, получаем, что

b1 a11 x1 a12 x2 0

или

a11 x1 a12 x2 b1 .

Таким образом, все целочисленные планы задачи (2.1), (2.2) удовлетворяют

неравенству (2.4), а для компонент плана x это неравенство не выполняется. Следовательно, неравенство (2.4) является правильным отсечением.

94

§ 3. Алгоритм метода Гомори

Пусть дана полностью целочисленная ЗЛП. Процесс ее решения методом Гомори включает следующие этапы:

1.Используя симплекс-метод, находим решение исходной ЗЛП без учета требования целочисленности переменных.

2.Если все элементы столбца B завершающей симплексной таблицы целые числа, то основной опорный план, построенный по этой таблице, является оптимальным решением исходной целочисленной ЗЛП.

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

венство (3.1) в равенство. Изменяя знак у обеих частей полученного равенства (так чтобы новая переменная xn 1 входила в него с коэффициентом 1), приведем

его к виду

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

шив полученную ЗЛП, возвращаемся к этапу 2 данного алгоритма.

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

Пример 1. Решить ЗЛП

min z 3x1 x2 ,

Р е ш е н и е. Применяя метод Гомори, решаем сначала данную ЗЛП без учета требования целочисленности переменных. Для этого преобразуем задачу к канонической форме

min z 3x1 x2 ,

5,

x x 2,

2 44x1 x2 x3

инайдем симплекс-методом ее решение (табл. 9).

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

записанное по первой строке завершающей симплексной таблицы (табл. 9). Преобразовав неравенство (3.4) к виду

составим первую симплексную таблицу новой задачи (табл. 10). Она получается из завершающей таблицы (табл. 9) добавлением строки соответствующей новому ограничению (3.5) и столбца переменной x5

96

Применяя двойственный симплекс-метод, получаем следующую таблицу.

97

ГЛАВА 6. ТРАНСПОРТНАЯ ЗАДАЧА

§ 1. Постановка транспортной задачи

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

щика к j -му потребителю. Требуется установить такие объемы перевозок xij от

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

m

Очевидно, что общий объем возможных поставок продукции равен ai , а

т.е. сумма возможных поставок в точности равна сумме потребностей, то соответствующая ТЗ называется закрытой. Если же равенство (1.1) не выполняется, то говорят об открытой ТЗ.

Обычно условие закрытой ТЗ записывают в виде транспортной таблицы (табл. 12).

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

ствующей перевозки xij .

Отметим очевидные свойства транспортной таблицы (табл. 12):

1)сумма значений xij в клетках i -ой строки равна ai ;

2)сумма значений xij в клетках j -го столбца равна b j ;

98

3) сумма элементов последнего столбца равна сумме элементов последней строки.

Систему ограничений получаем из следующих условий закрытой ТЗ: а) все запасы продукции у поставщиков должны быть вывезены, т.е.

n

xij ai , i 1, m ;

j 1

б) все запросы потребителей должны быть удовлетворены, т.е.

Таким образом, математическая модель закрытой ТЗ имеет следующий вид

Очевидно, что это каноническая ЗЛП с m n переменными и m n ограничениями.

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

§ 2. Разрешимость закрытой ТЗ

Теорема 2.1. Любая закрытая ТЗ имеет решение.

Д о к а з а т е л ь с т в о. Пусть дана задача (1.2), у которой

Кроме того очевидно, что

100

Объединяя неравенства (2.1), (2.2) в одно двойное, получаем, что для любого

плана задачи (1.2)

0 z c S .

Таким образом, допустимое множество задачи (1.2) не пусто, а ее целевая функция ограничена на этом множестве. Следовательно, по теореме 3.1 главы 2 задача 2.1 имеет решение.

§3. Понятие цикла. Теорема о существовании цикла

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

1) в этом наборе не менее четырех клеток; 2) любые две последовательные клетки данного набора, включая послед-

нюю и первую, расположены в одном ряду (строке или столбце) таблицы; 3) никакие три последовательные клетки этого набора не находятся в одном

итом же ряду таблицы.

Так, например, в табл. 13 размером 5 6 циклами являются следующие наборы клеток:

1)(1,1), (1,2), (4,2), (4,1);

2)(4,4), (4,6), (1,6), (1,5), (5,5), (5,4).

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

Теорема 3.1. Если в таблице размером m n m 1, n 1 произвольным

образом выделено m n клеток, то в этой таблице существует по крайней мере один цикл, состоящий только из выделенных клеток.

Д о к а з а т е л ь с т в о. Рассмотрим произвольную таблицу размером m nm 1, n 1 , в которой выделено m n клеток. Вычеркнем в этой таблице все ее

101

строки, содержащие ровно по одной выделенной клетке; затем вычеркнем все столбцы, содержащие ровно по одной выделенной клетке; затем снова строки и т.д. до тех пор, пока будут оставаться ряды, содержащие (без учета уже вычеркнутых рядов) ровно по одной выделенной клетке. Не умаляя общности рассужде-

Покажем, что вычеркнуты не все выделенные клетки. Действительно, всего было вычеркнуто m m1 m2 ... mk строк и N n1 n2 ... nk 1 столбцов.

Очевидно, что M m , N n , где m и n соответственно число строк и столбцов в исходной таблице. Но равенство N n невозможно, так как при его выполнении после k 1 -го шага вычеркнута вся исходная таблица и на k -м шаге нельзя вы-

черкнуть ни одной строки. Значит

M m, N n . (3.1)

Поскольку в каждом вычеркнутом ряду содержалась одна выделенная клетка, количество вычеркнутых выделенных клеток M N . Но, ввиду неравенств (3.1), M N m n . Следовательно, в исходной таблице остались невычеркнутыми некоторые выделенные клетки. Кроме того в любом невычеркнутом ряду этой таблицы либо нет ни одной выделенной клетки, либо находится не менее двух выделенных клеток.

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

§ 4. Циклические и ациклические планы

Пусть дана закрытая ТЗ с некоторым планом перевозок. Запишем условия данной задачи и ее план перевозок в виде транспортной таблицы. Клетки транспортной таблицы, в которых находятся отличные от нуля перевозки xij , называ-

ются занятыми, остальные клетки – свободными. Свободные клетки принято заполнять прочерками.

102