Целочисленные задачи линейного программирования. Метод Гомори

08.07.2019
Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП: . Решение L i будет целым числом, если т.е. . {β i } - дробная часть нецелочисленного оптимального решения x i , {d i } - дробная часть не базисных переменных. Данное соотношение определяет (см. рисунок).

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения методом Гомори). Дополнительно создается шаблон решения в формате Excel .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10
При этом ограничения типа x i ≥ 0 не учитывайте.

Виды алгоритма Гомори

  1. Первый алгоритм Гомори решения полностью целочисленных задач.
  2. Второй алгоритм Гомори для частично целочисленных задач линейного программирования .

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

  1. Решается задача линейного программирования без учета целочисленности.
  2. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
  3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
  4. Полученная задача решается двойственным симплекс-методом .
Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членов b i и целыми коэффициентами a ij , то данная задача не имеет целочисленного оптимального решения.

Пример . Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 100 руб., а от единицы изделия типа В - 250 руб.

Сырье Работа в цеху, станко-час Прибыль от реализации, руб.
Цветные металлы Сталь Токарные работы Фрезерные работы
Изделие А 10 25 41 90 100
Изделие В 30 25 90 50 250
Ресурсы 4500 6250 14100 18000

Найти оптимальный план производства для НПО «Стрела» (количество изделия типа А и типа В - целые числа), дающий наибольшую прибыль.

Решение.
Экономико-математическая модель задачи.
x 1 - план производства изделий типа А, x 2 - план производства изделий типа В,
x 1, x 2 - целые числа.
Ограничения по ресурсам
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Целевая функция
100x 1 + 250x 2 → max

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

Базис B x 1 x 2 x 3 x 4 x 5 x 6
x 2 1450 / 11 0 1 41 / 330 0 -1 / 33 0
x 4 17500 / 11 0 0 245 / 66 1 -50 / 33 0
x 1 600 / 11 1 0 -3 / 11 0 1 / 11 0
x 6 6500 0 0 55 / 3 0 -20 / 3 1
F(X3) 422500 / 11 0 0 125 / 33 0 50 / 33 0

x 1 = 54 6 / 11 , x 2 = 131 9 / 11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11

Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори . Наибольшая дробная часть находится во втором уравнении у переменной x 4 (10 / 11). Составляем дополнительное ограничение:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = a 2 6 - = 0 - 0 = 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0

Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 2 1450 / 11 0 1 41 / 330 0 -1 / 33 0 0
x 4 17500 / 11 0 0 245 / 66 1 -50 / 33 0 0
x 1 600 / 11 1 0 -3 / 11 0 1 / 11 0 0
x 6 6500 0 0 55 / 3 0 -20 / 3 1 0
x 7 -10 / 11 0 0 -47 / 66 0 -16 / 33 0 1
F(X0) -422500 / 11 0 0 -125 / 33 0 -50 / 33 0 0

Первая итерация Гомори. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольшее по модулю. Ведущей будет пятая строка, а переменную x 7 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует пятому столбцу, т.е. переменную x 5 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-16 / 33).
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 2 131 9 / 11 0 1 41 / 330 0 -1 / 33 0 0
x 4 1590 10 / 11 0 0 3 47 / 66 1 -1 17 / 33 0 0
x 1 54 6 / 11 1 0 -3 / 11 0 1 / 11 0 0
x 6 6500 0 0 18 1 / 3 0 -6 2 / 3 1 0
x 7 -10 / 11 0 0 -47 / 66 0 -16 / 33 0 1
F(X0) -38409 1 / 11 0 0 -3 26 / 33 0 -1 17 / 33 0 0
θ - - -3 26 / 33: (-47 / 66) = 5 15 / 47 - -1 17 / 33: (-16 / 33) = 3 1 / 8 - -

4. Пересчет симплекс-таблицы выполняем с помощью метода Жордано-Гаусса.
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 2 1055 / 8 0 1 27 / 160 0 0 0 -1 / 16
x 4 6375 / 4 0 0 95 / 16 1 0 0 -25 / 8
x 1 435 / 8 1 0 -13 / 32 0 0 0 3 / 16
x 6 13025 / 2 0 0 225 / 8 0 0 1 -55 / 4
x 5 15 / 8 0 0 47 / 32 0 1 0 -33 / 16
F(X0) -153625 / 4 0 0 -25 / 16 0 0 0 -25 / 8

В полученном оптимальном плане присутствуют дробные числа. По первому уравнению с переменной x 2 , получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 7 / 8 , составляем дополнительное ограничение:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8


q 1 3 = a 1 3 - = 27 / 160 - 0 = 27 / 160



q 1 7 = a 1 7 - = -1 / 16 + 1 = 15 / 16
Дополнительное ограничение имеет вид:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Преобразуем полученное неравенство в уравнение:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
x 2 1055 / 8 0 1 27 / 160 0 0 0 -1 / 16 0
x 4 6375 / 4 0 0 95 / 16 1 0 0 -25 / 8 0
x 1 435 / 8 1 0 -13 / 32 0 0 0 3 / 16 0
x 6 13025 / 2 0 0 225 / 8 0 0 1 -55 / 4 0
x 5 15 / 8 0 0 47 / 32 0 1 0 -33 / 16 0
x 8 -7 / 8 0 0 -27 / 160 0 0 0 -15 / 16 1
F(X0) -153625 / 4 0 0 -25 / 16 0 0 0 -25 / 8 0

Вторая итерация Гомрои. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных наибольшей по модулю является переменная x 8 . Ее следует вывести из базиса.
3. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x 7 необходимо ввести в базис.
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
x 2 131 7 / 8 0 1 27 / 160 0 0 0 -1 / 16 0
x 4 1593 3 / 4 0 0 5 15 / 16 1 0 0 -3 1 / 8 0
x 1 54 3 / 8 1 0 -13 / 32 0 0 0 3 / 16 0
x 6 6512 1 / 2 0 0 28 1 / 8 0 0 1 -13 3 / 4 0
x 5 1 7 / 8 0 0 1 15 / 32 0 1 0 -2 1 / 16 0
x 8 -7 / 8 0 0 -27 / 160 0 0 0 -15 / 16 1
F(X0) -38406 1 / 4 0 0 -1 9 / 16 0 0 0 -3 1 / 8 0
θ - - -1 9 / 16: (-27 / 160) = 9 7 / 27 - - - -3 1 / 8: (-15 / 16) = 3 1 / 3 -

4. Выполняем преобразование Новых отсечений Гомори.
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
x 2 1979 / 15 0 1 9 / 50 0 0 0 0 -1 / 15
x 4 4790 / 3 0 0 13 / 2 1 0 0 0 -10 / 3
x 1 271 / 5 1 0 -11 / 25 0 0 0 0 1 / 5
x 6 19576 / 3 0 0 153 / 5 0 0 1 0 -44 / 3
x 5 19 / 5 0 0 46 / 25 0 1 0 0 -11 / 5
x 7 14 / 15 0 0 9 / 50 0 0 0 1 -16 / 15
F(X0) -115210 / 3 0 0 -1 0 0 0 0 -10 / 3

В оптимальном плане присутствуют дробные числа. Наибольшая дробная часть у переменной x 2 (14 / 15). Составляем дополнительное ограничение: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = a 1 5 - = 0 - 0 = 0
q 1 6 = a 1 6 - = 0 - 0 = 0
q 1 7 = a 1 7 - = 0 - 0 = 0
q 1 8 = a 1 8 - = -1 / 15 + 1 = 14 / 15
Дополнительное ограничение имеет вид:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Преобразуем полученное неравенство в уравнение:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9
x 2 1979 / 15 0 1 9 / 50 0 0 0 0 -1 / 15 0
x 4 4790 / 3 0 0 13 / 2 1 0 0 0 -10 / 3 0
x 1 271 / 5 1 0 -11 / 25 0 0 0 0 1 / 5 0
x 6 19576 / 3 0 0 153 / 5 0 0 1 0 -44 / 3 0
x 5 19 / 5 0 0 46 / 25 0 1 0 0 -11 / 5 0
x 7 14 / 15 0 0 9 / 50 0 0 0 1 -16 / 15 0
x 9 -14 / 15 0 0 -9 / 50 0 0 0 0 -14 / 15 1
F(X0) -115210 / 3 0 0 -1 0 0 0 0 -10 / 3 0

Третья итерация методом Гомори. Переменную x 9 следует вывести из базиса. Минимальное значение θ соответствует восьмому столбцу, т.е. переменную x 8 необходимо ввести в базис.
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9
x 2 131 14 / 15 0 1 9 / 50 0 0 0 0 -1 / 15 0
x 4 1596 2 / 3 0 0 6 1 / 2 1 0 0 0 -3 1 / 3 0
x 1 54 1 / 5 1 0 -11 / 25 0 0 0 0 1 / 5 0
x 6 6525 1 / 3 0 0 30 3 / 5 0 0 1 0 -14 2 / 3 0
x 5 3 4 / 5 0 0 1 21 / 25 0 1 0 0 -2 1 / 5 0
x 7 14 / 15 0 0 9 / 50 0 0 0 1 -1 1 / 15 0
x 9 -14 / 15 0 0 -9 / 50 0 0 0 0 -14 / 15 1
F(X0) -38403 1 / 3 0 0 -1 0 0 0 0 -3 1 / 3 0
θ - - -1: (-9 / 50) = 5 5 / 9 - - - - -3 1 / 3: (-14 / 15) = 3 4 / 7 -

4. Выполняем преобразование.
Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9
x 2 132 0 1 27 / 140 0 0 0 0 0 -1 / 14
x 4 1600 0 0 50 / 7 1 0 0 0 0 -25 / 7
x 1 54 1 0 -67 / 140 0 0 0 0 0 3 / 14
x 6 6540 0 0 234 / 7 0 0 1 0 0 -110 / 7
x 5 6 0 0 317 / 140 0 1 0 0 0 -33 / 14
x 7 2 0 0 27 / 70 0 0 0 1 0 -8 / 7
x 8 1 0 0 27 / 140 0 0 0 0 1 -15 / 14
F(X0) -38400 0 0 -5 / 14 0 0 0 0 0 -25 / 7

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: x 1 = 54, x 2 = 132. F(X) = 38400

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра вычислительной техники и информационных технологий

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ

Методические указания и задания к практическим занятиям по курсу

«Экономико-математические методы» для студентов экономических специальностей

Составитель Н.Ю.Коломарова

Утверждены на заседании кафедры Протокол № 5 от 30.11.99

Электронная копия находится в библиотеке главного корпуса КузГТУ

Кемерово 2000

1. ПОСТАНОВКА ЗАДАЧИ

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

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

ется следующим образом: найти такое решение (план)

Х = (x1 , x2 , ..., xn ),

принимает максимальное или минимальное значение при ограничениях

2. МЕТОД ГОМОРИ

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

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

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

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

Оно должно быть линейным; - должно отсекать найденный оптимальный нецелочисленный

план; - не должно отсекать ни одного целочисленного плана.

Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k -й строке симплексной таблицы записываем ограничение Гомори.

f k = ∑

f kj x j − S * ,S * ≥ 0 ,

где f k

Xj - ;

Zkj - ;

Новая переменная;

Ближайшее целое, не превосходящееx j иz kj соответст-

Составленное ограничение добавляем к имеющимся в сим-

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

вектор, для которого величина

∆ j

минимальна. И если для этого век-

f kj

тора величина θ = min

получается по дополнительной строке, то в

z ij> 0

следующей симплексной таблице будет получен опорный план. Если же величина θ не соответствует дополнительной строке, то необходимо

переходить к М-задаче (вводить искусственную переменную в ограничение Гомори).

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

Замечания:

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

2. Если для дробного x j обнаружится целочисленность всех коэффициентов соответствующего уравнения (строки), то задача не имеет целочисленного решения.

3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ГОМОРИ

Задача: Для приобретения нового оборудования предприятие выделяет 19 ден.ед. Оборудование должно быть размещено на площади, не превышающей 16 кв.м. Предприятие может заказать оборудование двух видов: машины типа «А» стоимостью 2 ден.ед., требующие производственную площадь 4 кв.м и обеспечивающие производительность за смену 8 т продукции, и машины типа «В» стоимостью 5 ден.ед., занимающие площадь 1 кв.м и обеспечивающие производительность за смену 6 т продукции.

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

Решение: Обозначим черезx 1 ,x 2 количество машин соответственно типа «А» и «В», черезL - их общую производительность. Тогда математическая модель задачи:

max L = 8 x1 +6 x2

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

2x 1

5x 2

4x 1

x 1≥

0, x2 ≥ 0

x1 , x2 - целые числа

Решаем задачу симплексным методом без учета целочисленности.

∆ j

∆ j

∆ j

Получен оптимальный нецелочисленный план Х опт = (61/18;22/9).

L max = 376/9.

Т.к. у компоненты плана х 2 максимальная дробная часть: max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - = (2/9 - )x 3 + (-1/9 - [-1/9])x 4 -S 1 , S 1 ≥0 22/9 - 2 = (2/9 - 0)x 3 + (-1/9 - (-1))x 4 -S 1 , S 1 ≥0

4/9 = 2/9x3 + 8/9x4 - S1 , S1 ≥ 0 - первое ограничение Гомори

Составленное ограничение дописываем к имеющимся в симплексной таблице.

После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базис-

ный вектор. Для этого определяем: min

f kj

базис вводим вектор х 4 .

4 / 9

Рассчитываем величину θ =

z ij> 0

8 / 9

Минимальное значение θ получено по дополнительной строке, значит, не прибегая к искусственной переменной, получаем опорный план расширенной задачи.

∆ j

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - = (1/4 - )x 3 + (-1/8 - [-1/8])S 1 -S 2 , S 2 ≥0

1/2 = 1/4x3 + 7/8S1 - S2 , S2 ≥ 0 - второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

2 . Можно

ввести либо x 3 , либоS 1 . Введем векторS 1 .

1/ 2

4 / 7

соответствует дополнительному

7 / 8

ограничению.

∆ j

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

менной S 1 .

В полученном плане максимальную дробную часть имеет компонента х 2 , поэтому записываем дополнительное ограничение по первой строке.

4/7 = 2/7x3 + 6/7S2 - S3 , S3 ≥ 0

Третье ограничение Гомори.

Определяем вектор, вводимый в базис:

вектор х 3 . Минимальное значениеθ = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили:

∆ j

План Х 5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке:

1/2 = 1/4S3 - S4 , S4 ≥ 0

Четвертое ограничение Гомори.

Т.к. базисной компонентой может быть S 3 , определяем величину

0. Минимальное значение θ получилось по 3

строке, а не по строке Гомори, следовательно, переходим к М-задаче:

введем дополнительную переменную х 5

в ограничение Гомори.

С5 ’

Б5 ’

Х5 ’

∆ j

∆ j

∆ j

Дробная часть = max(1/3; 2/3) = 2/3

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

ние записываем по второй строке.

2/3 = 1/3х4 + 2/3S4 - S5

S5 ≥

Пятое ограничение Гомори.

16 / 3

2 вводим х 4 .

Вектор, вводимый в базис: min

2 / 3

θ =

соответствует строке Гомори.

∆ j

План Х 8 = (3; 2; 3; 2) - оптимальный целочисленный.L max = 36.

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа «А» и 2 машины типа «В». При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

Геометрическая интерпретация метода Гомори: строим множе-

ство планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

Графический метод решения задач целочисленного программирования.

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

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

Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:

1. Оно должно быть линейным;

2. Должно отсекать найденный оптимальный не целочисленный план;

3. Не должно отсекать ни одного целочисленного плана.

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

Целочисленного программирования.

1. Построить систему координат x 1 0х 2 и выбрать масштаб.

2. Найти область допустимых решений (ОДР) системы ограничений задачи.

3. Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

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

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

5. Найти координаты, точки экстремума и значение целевой функции в ней. Если полученные значения не целочисленные, то перейти к следующему шагу.

6. Выделить у этих координат область с целочисленными значениями.

7. Определить новые координаты и построить граф.

8. Найти точки с целыми значениями искомых переменных, подставить в уравнение целевой функции и найти её значение. Максимальное из полученных значений целевой функции и будет решением задачи.



Метод Гомори решения задач целочисленного программирования. Примеры решения экономических задач.

Данный метод основан на симплексном методе.

На первом этапе данная задача решается симплекс-методом, если полученное решение не целочисленное, то вводим дополнительное ограничение, которые должны быть:

Линейным;

Отсекать найденный оптимальный не целочисленный план;

Не должно отсекать ни одного целочисленного плана.

Дополнительное ограничение обладающие этими свойствами называются правильным отсечением.

Ограничение накладывается на нецелочисленную переменную или на ту переменную, которая имеет большее дробное значение. Ограничение накладывается на не целочисленную переменную через не основные переменные. Ограничение составляется используя следующее правило: дробная часть свободного члена берётся с тем же знаком, который он имеет и в уравнении, а дробные части неосновных переменных - с противоположным знаком и выделяется положительная дробь. Например, {a}=a, {-a}={-A+a * }, где А - целая часть отрицательное число, а * -положительная дробь.

Получаем новое ограничение, вводим новую основную переменную, приведённое в формуле (1.2.3).

где x n+1 - нововведённая переменная,

x j - переменные не входящие в базис.

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

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

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

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

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

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

Задача. Контейнер объемом помещен на контейнеровоз грузоподъемностью 12т. Контейнер требуется заполнить грузом двух наименований. Масса единицы груза, объем единицы груза, стоимости приведены в таблице:

Вид груза т ден.ед.

Требуется загрузить контейнеровоз таким образом, чтобы стоимость перевозимого груза была максимальной.

Решим задачу методом Гомори.

Введем обозначения: х 1 – количество груза первого вида, х 2 – количество груза второго вида. Тогда экономико-математическая модель задачи примет вид:

Преобразуем математическую модель ЗЛП без учета целочисленности переменных к допустимому предпочтительному виду канонической формы:

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

*
-10 -12*
* 5/2 -1/2 19/2
1/2 1/2 5/2
-4* -30
2/5 -1/5 19/5
-1/5 3/5 3/5
8/5 26/5 -226/5

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

Замечание 9.1. Если имеется несколько дробных , то для той у которой дробная часть больше всего составляется ограничение.

Составим сечение Гомори для первого ограничения оптимальной симплекс-таблицы решения ЗЛП (так как ):

,

.

Преобразуем полученное ограничение к канонической форме с предпочтительной переменной:

.

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

2/5 -1/5 19/5
-1/5 3/5 3/5
-2/5 -4/5 -4/5
8/5* 26/5 -226/5
-5/2
-42

Оптимальное решение расширенной ЗЛП удовлетворяет ограничению целочисленности.

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

В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 499683,3 автомашины, то экономически обосновано округление результата до 499683 или даже до 500000.

Существуют однако задачи, в которых подобное округление может создать большую ошибку. Например, если в оптимальном плане предусмотрено, что следует построить 0,67 заводов, то формальное округление до 0 или 1 недопустимо.

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

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

найти максимум функции цели (линейной формы)

при системе ограничений

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

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

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

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

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

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

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

, где в фигурных скобках - дробные части соответственно свободного члена и коэффициентов при неизвестных.

Например, из симплексной таблицы получаем такое уравнение:

.

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

Аналогично получаем дробные части коэффициентов при неизвестных:

(при x 3 ),

(при x 4 ).

А общее правило нахождения дробных частей таково: целой частью вещественного числа a называется самое большое целое число [a ] , не превыщающее a ; дробной частью вещественного числа a называется разность {a } = a - [a ] самого числа a и его целой части [a ] .

.

В нашем примере по приведённой выше формуле получается следующее уравнение:

.

Пример 1. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Решаем задачу симплекс-методом. Поскольку у нас есть урок по решению задач линейного программирования симплекс-методом , сам метод объясняться здесь не будет, а будут приведены лишь симплексные таблицы.

Дополнительные неизвестные x 3 и x 4 примем за базисные. Выразим базисные неизвестные и функцию цели через неосновные переменные:

Из коэффициентов составим симплексную таблицу:

Составляем следующие таблицы до получения оптимального плана:

Таблица 3
Базисные неизвестные Свободные члены Свободные неизвестные Вспомогательные коэффициенты
X3 X4
X1 19/7 4/7 -1/7 -1/2
X2 4/7 -1/7 2/7
С 65/7 10/7 1/7 1/2

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

Первое уравнение на основании таблицы запишется так:

.

Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие:

или, введя добавочную переменную ,

.

Получаем новую строку в симплексной таблице, полученной из таблицы 3 и добавления коэффициентов из только что полученного уравнения:

Таблица 4
Базисные неизвестные Свободные члены Свободные неизвестные Вспомогательные коэффициенты
X3 X4
X1 19/7 4/7 -1/7 -1/2
X2 4/7 -1/7 2/7
X5 -5/7 -4/7 -6/7
С 65/7 10/7 1/7 1/2

Совершаем шаг симплекс-метода и получаем таблицу:

Таблица 5
Базисные неизвестные Свободные члены Свободные неизвестные Вспомогательные коэффициенты
X3 X4
X1 17/6 2/3 -1/6 1/7
X2 1/3 -1/3 1/3 -2/7
X4 5/6 2/3 -7/6
С 55/6 4/3 1/6 -1/7

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

.

Составляем следующую таблицу:

Таблица 6
Базисные неизвестные Свободные члены Свободные неизвестные Вспомогательные коэффициенты
X3 X4
X1 17/6 2/3 -1/6 1/7
X2 1/3 -1/3 1/3 -2/7
X4 5/6 2/3 -7/6
X6 -5/6 -2/3 -5/6
С 55/6 4/3 1/6 -1/7

Оптимальный план получаем из следующей, завершающей таблицы:

Таблица 7
Базисные неизвестные Свободные члены Свободные неизвестные Вспомогательные коэффициенты
X3 X6
X1 3 4/5 -1/5 1/6
X2 0 -3/5 2/5 -1/3
X4 2 8/5 -7/5 7/6
X5 1 4/5 -6/5
С 9 6/5 1/5 -1/6

Так как найденный оптимальный план удовлетворяет условию целочисленности, задача целочисленного программирования решена. Координаты x 5 и x 6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так:

,

а максимум функции цели равен 9.

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

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

Задание границ, в которых должны находиться значения неизвестных в задаче целочисленного программирования, можно записать так:

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

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

Сначала решается, допустим, симплекс-методом задача линейного программирования, соответствующая задаче целочисленного программирования. Пусть найден оптимальный план в этой задаче и значением какой-либо его координаты является дробное число. Тогда потребуется составить две новые задачи линейного программирования. Как это сделать?

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

.

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

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

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

Лишь в первом случае возможно "ответвление" новых задач способом, показанным выше. Во втором и третьем случае "ветвление" прекращается.

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

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

Согласно алгоритму решения задачи целочисленного программирования методом ветвей и границ, на каждой p -й итерации требуется сделать 4 шага.

Пример 2. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

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

.

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

В списке решаемых задач - 1-я задача:

Итерация 1.

Шаг 1. С помощью симплекс-метода получено решение 1-й задачи:

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Так как оптимальный план имеет дробную координату 1,2, то и . Применяя границы значений неизвестных 1-й задачи, получаем новые задачи. Во 2-й задаче нижней границей для является , а в 3-й задаче верхней границей для является .

Введение

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

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

1. Постановка задачи

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

1.1 Каноническая форма

Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности:

Где c = (c 1 , c 2 , … , c n) , x = (x 1 , x 2 , … , x n) - вектора размерности n , - их скалярное произведение (), называемое так же целевой функцией, A - матрица размерности n ´ m , b - вектор-столбец размерности m .

Условие целочисленности существенно осложняет задачу линейного программирования (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 * > > g 0 (условие отсечения).

б) если 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 с

Похожие статьи