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

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

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

максимизировать

при условиях

x j ≥ 0, x j – целые.

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

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

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

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

К целочисленным моделям выбора относят некоторые задачи оперативно-календарного планирования, например, задачи об оптимальной последовательности запуска различных изделий (деталей) в производство. Допустим необходимо определить порядок запуска n деталей, каждая из которых последовательно обрабатывается на нескольких станках. Переменные х ij равняются единице, если деталь j должна запускаться за деталью i , и нулю - во всех остальных случаях. Для каждого фиксированного j , так же как и для каждого i , только одна из n переменных может равняться единице, поэтому в число ограничений задачи входят следующие:

Минимизируется общее время обработки всех деталей на станках данной группы. Нецелочисленное решение такой задачи лишено смысла.

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

Рассмотрим математические понятия: конгруэнтности чисел, целой и дробной части числа . Число а конгруэнтно числу b в том и только том случае, когда разность а – b является целым числом. Конгруэнтность обозначают тремя горизонтальными черточками (≡ ); таким образом, а ≡ b , если а – b есть целое число.

Например: 5 / 3 ≡ 2 / 3 , т.к. 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , т.к.- 1 / 3 - 2 / 3 = 1.

Все целые числа конгруэнтны друг другу и конгруэнтны нулю. Нецелочисленные элементы можно представить в виде суммы целой и дробной части числа а = [a ] + {a }. Квадратные скобки означают взятие целой части числа, заключённого в них, фигурные – взятие дробной части числа.

Целой частью числа а называется наибольшее целое число [a ], не превосходящее а .

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

Например, для а = 2 1 / 3 [a ]= 2 {a} = 1 / 3

для a = - 2 1 / 3 [a ]= -3 {a} = 2 / 3

Свойства конгруэнтности чисел:

1. Если а ≡ b , то {а } = {b }.

2. {а +b } = {а } + {b }.

3. Если n - целое число, то для любого а

nа ≡ {nа } ≡ n {а }.

При решении задач целочисленного программирования методом Гомори первый этап совпадает с обычным расчетом по симплексному алгоритму. Полученное решение в общем виде будет удовлетворять всем условиям задачи, кроме требования целочисленности (не исключено, конечно, получение целочисленного решения уже на первом этапе). Если среди значений переменных в оптимальном плане (точка А на рис.13) есть дробные, то составляется дополнительное ограничение, как бы «отсекающее» дробную часть решения (линия 1 на рис.13), но оставляющее в силе все ограничения задачи, которым должен удовлетворять оптимальный план. Дополнительное ограничение присоединяется к исходным ограничениям задачи и к расширенной системе вновь применяется симплексная процедура. Если оптимальное решение снова окажется нецелочисленным (точка В на рис.13), то добавляется еще одно дополнительное ограничение (линия 2 на рис.13) и процесс вычислений повторяется. Алгоритм позволяет за конечное число шагов прийти к оптимальному целочисленному решению (если оно существует) (точка С на рис.13).

Рис. 13. Метод отсечений Гомори

Пример решения задачи целочисленного программирования. На приобретение оборудования для нового производственного участка выделено 20 ден.ед. Оборудование должно быть размещено на площади, не превышающей 38 м 2 . Предприятие может заказать оборудование двух видов: более мощные машины типа А стоимостью 5 ден.ед, требующие производственную площадь 8 м 2 (с учетом проходов) и обеспечивающие производительность 7 тыс, единиц продукции за смену; менее мощные машины типа Б стоимостью 2 ден.ед, занимающие площадь 4 м 2 и дающие за смену 3 тыс, единиц продукции.

Обозначим через х 1 количество приобретаемых машин А и через х 2 - количество приобретаемых машин Б, получаем математические условия задачи:

максимизировать 7х 1 + 3х 2 → max

при условиях: 5х 1 + 2х 2 ≤ 20

8х 1 + 4х 2 ≤ 38

х 1 , х 2 ≥ 0 (целые).

С помощью дополнительных переменных х 3 и х 4 исходные неравенства преобразуются в уравнения (приводятся к каноническому виду):

5х 1 + 2х 2 + х 3 = 20

8х 1 + 4х 2 + х 4 = 38

Если основные переменные х 1 и х 2 - целые числа, то из уравнений непосредственно следует, что и переменные х 3 и х 4 могут принимать только целочисленные значения.

Задача решается вначале без учета требования целочисленности.

Симплексная таблица имеет следующий вид:

В оптимальном плане Х 1 =1, Х 2 =7,5; максимум целевой функции составляет 29,5. Таким образом, необходимо купить один станок типа А и 7 станков типа В (на 8 станков не хватит ни денег, ни места), тогда объём выпуска продукции составит f(x) =7×1+3×7=28 тыс. единиц продукции.

Найдём целочисленное решение методом Гомори. Для переменной Х 2 , получившей нецелочисленное значение в плане, составляем следующее уравнение, непосредственно вытекающее из приведенной симплексной таблицы:

7,5 = Х 2 – 2Х 3 + 1,25Х 4 .

Х 2 = 7,5 + 2Х 3 – 1,25Х 4 .

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

Поскольку Х 2 - целое число, то целым является и выражение в правой части уравнения; следовательно, величина правой части данного уравнения конгруэнтна нулю:

7,5 + 2Х 3 – 1 ,25Х 4 ≡ 0,

–2Х 3 + 1,25Х 4 ≡ 7,5.

Учитывая приведенные выше свойства конгруэнтности, а также и то, что Х 3 и Х 4 - целые числа, это выражение можно преобразовать в следующее:

{-2}X 3 + {1,25}X 4 ≡ {7,5} ;

отсюда получаем:

0,25X 4 ≡ 0,5.

Поскольку X 4 - неотрицательное целое число, имеем:

0,25X 4 = 0,5, или 1,5, или 2,5, ...;

следовательно,

0,25X 4 ≥ 0,5.

Полученное неравенство преобразуется в уравнение и добавляется к исходной системе ограничений, которая содержит теперь следующие три уравнения:

5х 1 + 2х 2 + х 3 = 20

8х 1 + 4х 2 + х 4 = 38

0,25х 4 – x 5 = 0,5.

Повторив процесс решения симплексным методом применительно к расширенной системе ограничений, получим новый оптимальный план, в котором значения переменных, входящих в базис, равны: Х 1 = 2; Х 2 = 5; Х 4 = 2 (остаток свободной площади).

Таким образом, получено оптимальное целочисленное решение задачи: при данных ограничениях максимум производительности (29 тыс. единиц продукции) обеспечивается приобретением 2 машин типа А и 5 машин типа Б.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ

МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

Рассмотрим модель

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

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

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

Обычно H j = 0, но это условие не обязательно. Задача решается симплекс-методом. Если X k принимает дробные значения, то полагаем, что оптимальное решение задачи, будет удовлетворять линейному ограничению X k ≤ D k , либо линейному ограничению X k ≤ D k + 1 , где D k =[X k ] – ближайшее целое число в меньшую сторону от значения X k ; D k + 1 – ближайшее целое в большую сторону от X k . При этом H j ≤ D k ≤ V j – 1 . Тогда необходимо решить пару задач линейного программирования симплекс-методом:

А.

В.

Получаем итерационный процесс, представляемый в виде дерева, вершина которого соответствует решению исходной задачи, а две соединенные с ней ветви являются решениями пары задач линейного программирования А и В. Полученные значения целевых функций при этом могут быть меньше или равны значению целевой функции исходной задачи f(X) A ≤ f(X) ­ 0 ; f(X) B ≤ f(X) ­ 0 . Каждая из двух новых полученных вершин ветвей может иметь свои дальнейшие ветвления.

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

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

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

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

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

Если выбранная задача приводит к обрыву (тупику) или значение функции меньшему, чем в задаче В.1 f(X) A.4 < f(X)­ В,1 ., то происходит возврат к задаче В.1 и происходит новое ветвление.

Рис.14. Блок-схема алгоритма метода ветвей и границ

Рис. 15. Метод «ветвей и границ»

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

Алгоритм Гомори

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

|~2~1 Среди нецелых Xj выбираем произвольный элемент х г и в задаче добавляем еще одно ограничение

что равносильно добавлению в симплекс-таблице еще одной строки, после чего она перестает соответствовать допустимому базисному решению новой задачи линейного программирования, которую она описывает. В ограничении применяются дробные части элементов строки, в которой находится х г. Применяемое обозначение для дробной части исходит из того, что всякое действительное число у можно представить в виде суммы у = [у] + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.

[з] Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I = п + 1.

• а) Если все коэффициенты уц > 0, то задача не имеет решения (т.е. целочисленная задача решена).
• б) В противном случае находим индекс к такой, что

(критерий входа в новый базис). Заметим, что выбор разрешающего элемента у и* не изменяет знак у критериев Aj.

[4] Если в новой таблице имеется хотя бы один х 3 s и повторить указанные процедуры необходимое число раз.

[~5~| Если полученное оптимальное решение целочисленно, то поставленная задача решена. В противном случае надо вернуться к пункту .

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

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

с матрицами

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 6*.

к" = 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.

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 3, ж 2 = 6, х± = 1} дает максимум экономической функции г, равный 450, т.с. z = z ma ^ = 450. Эта оптимальная программа является целочисленной. ?

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

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

Заполним симплекс-таблицу с начальной программой.

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 1*.

Разрешающий элемент - 5*.

Значения всех критериев ^ 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" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I" = 6.

Находим разрешающий столбец, т.е. индекс к" такой, что

(критерий входа в новый базис). Разрешающий элемент - (-3/5*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.

Заполним симплекс-таблицу 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. Эта оптимальная программа является целочисленной.

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

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

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

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

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

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

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

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

Решение.
Экономико-математическая модель задачи.
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

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

Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори . Наибольшая дробная часть находится во втором уравнении у переменной 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).

В полученном оптимальном плане присутствуют дробные числа. По первому уравнению с переменной 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
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

В оптимальном плане присутствуют дробные числа. Наибольшая дробная часть у переменной 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
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

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

· оно должно быть линейным;

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

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

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

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

Один из алгоритмов решения задачи линейного целочисленного программирования (6.59)…(6.62), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Рис. 6.18. Графическая иллюстрация целочисленного решения

Пусть задача линейного программирования (6.52)…(6.55) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные через неосновные переменные оптимального решения

(6.56)

так, что оптимальным решением задачи (6.52)…(6.55) является , в котором, например β i − нецелая компонента. В этом случае можно доказать, что неравенство

сформированное по i -му уравнению системы (6.56), обладает всеми свойствами правильного отсечения.

В неравенстве (6.57) присутствует символ , означающий дробную часть числа. Число а называется конгруэнтным числу в (обозначается ) тогда и только тогда, когда разность а - в − целое число.

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

Для решения задачи целочисленного линейного программирования (6.52)…(6.55) методом Гомори используется следующий алгоритм:

1. Симплексным методом решить задачу (6.52)…(6.55) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (6.52)…(6.55). Если первая задача (6.52)…(6.54) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то вторая задача (6.52)…(6.55) также неразрешима.

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

3. Неравенство (6.57) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение

и включить его в систему ограничений (6.53).

4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (6.52)…(6.55) решена. В противном случае вернуться к п. 2 алгоритма.

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

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

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

Отметим, что переход к каноническому виду в полностью целочисленной задаче линейного программирования, содержащей ограничения − неравенства

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

вспомогательные переменные x n + i не подчинены требованию целочисленности.

Однако если все коэффициенты a ij , b i в (6.59) − целые числа, то условие целочисленности можно распространить и на x n + i , как это сделано при решении примера 6.10.

Полностью целочисленную задачу в каноническом виде можно получить также, если в (6.59) a ij , b i − рациональные числа. Для этого следует умножить (6.59) на общее кратное знаменателей коэффициентов − a ij , b i (т.е. перейти к целым коэффициентам в (6.59)) и лишь после этого ввести вспомогательные переменные .

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

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

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

Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 6.19).

Рис. 6.19. Графическая иллюстрация решения задачи

На рис. 6.19 0KLM – область допустимых решений задачи ограниченная прямыми (1), (2), (3) и осями координат; L (2/3;8) – точка оптимального, но нецелочисленного решения задачи ; (4) – прямая, отсекающая это нецелочисленное решение; 0KNM – область допустимых решений расширенной задачи (6.64") N (2; 7) – точка оптимального целочисленного решения.

I шаг

Первое базисное решение Х 1 = (0;0;60;34;8) – допустимое. Соответствующее значение линейной функции f 1 = 0.

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

,

т.е. разрешающим (выделенным) является третье уравнение. При х 2 = 8 в этом уравнении х 5 = 0, и в неосновные переменные переходит х 5 .

II шаг . Основные переменные ; неосновные переменные .

Х 2 = (0;8;20;2;0); f = 24. Переводим в основные переменные х 1 , , а в неосновные х 4 .

Ш шаг . Основные переменные ; неосновные переменные . После преобразований получим:

Базисное решение Х 3 оптимально для задачи , так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами.

Однако решение Х 3 не удовлетворяет условию целочисленности (6.55"). По первому уравнению с переменной х 1 , получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (6.57):

Обращаем внимание на то, что согласно (6.56) и (6.57) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х 5 − с противоположными знаками.

Так как дробные части

то последнее неравенство запишем в виде

Введя дополнительную целочисленную переменную х 6 ≥ 0, получим равносильное неравенству (6.57") уравнение

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

IV шаг . Основные переменные ; неосновные переменные .

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

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

V шаг . Основные переменные ; неосновные переменные . Получим после преобразований:

Х 5 = (2;7;19;0;1;0); f 5 = 25.

Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х 5 − оптимальное решение.

Итак, f max = 25 при оптимальном целочисленном решении Шестая компонента содержательного смысла не имеет.

Для геометрической интерпретации на плоскости 0х 1 х 2 (см. рис. 6.19) отсечения (6.57") необходимо входящие в него переменные х 4 и х 5 выразить через переменные х 1 и х 2 . Получим (см. 2-е и 3-е уравнения системы ограничений (6.56"):

(см. отсечение прямой (4) на рис. 6.19).

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

В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 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 находим оптимальный план . Поскольку этот оптимальный план не удовлетворяет условию целочисленности, нам нужно составить дополнительное условие. Дробной частью координаты является число , а дробной частью координаты - число .

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

.

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

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

.

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

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

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

.

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

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

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

,

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

.

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

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

Итерация 1.

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

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

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