Решение задач целочисленного программирования: методы и примеры.
Для решения целочисленных задач линейного программирования с произвольным числом переменных можно использовать метод Гомори, с помощью которого от области программ отсекаются точки с нецелочисленными координатами. Сформулируем алгоритм Гомори для решения целочисленной задачи линейного программирования в стандартной форме
Алгоритм Гомори
ГП С помощью симплекс-метода находим оптимальную программу. Если получились целочисленные значения для всех Xj , то задача решена. В противном случае среди Xj имеются нецслочисленные значения.
|~2~1 Среди нецелых Xj выбираем произвольный элемент х г и в задаче добавляем еще одно ограничение
что равносильно добавлению в симплекс-таблице еще одной строки, после чего она перестает соответствовать допустимому базисному решению новой задачи линейного программирования, которую она описывает. В ограничении применяются дробные части элементов строки, в которой находится х г. Применяемое обозначение для дробной части исходит из того, что всякое действительное число у можно представить в виде суммы у = [у] + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.
[з] Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I = п + 1.
- а) Если все коэффициенты уц > 0, то задача не имеет решения (т.е. целочисленная задача решена).
- б) В противном случае находим индекс к такой, что
![](https://i0.wp.com/bstudy.net/htm/img/4/12135/292.png)
(критерий входа в новый базис). Заметим, что выбор разрешающего элемента у и* не изменяет знак у критериев Aj.
[4] Если в новой таблице имеется хотя бы один х 3 s и повторить указанные процедуры необходимое число раз.
[~5~| Если полученное оптимальное решение целочисленно, то поставленная задача решена. В противном случае надо вернуться к пункту .
Пример 4.6.1. Решить методом Гомори целочисленную задачу
Решение. После добавления вспомогательных переменных имеется следующая задача линейного программирования в стандартной форме:
![](https://i1.wp.com/bstudy.net/htm/img/4/12135/294.png)
с матрицами
![](https://i1.wp.com/bstudy.net/htm/img/4/12135/295.png)
Таблица 1 |
||||||
Х 4 |
||||||
к = 1 Т
С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 6*.
Таблица 2 |
х 2 |
|||||
„ _ 1 Ж Z ~_3_ |
![](https://i0.wp.com/bstudy.net/htm/img/4/12135/296.png)
к" = 2 Т
Разрешающий элемент - 1/2*.
Х в ^ 0). Следовательно, программа {xi = 11/3, х 2 = 5} даст максимум экономической функции z, равный 1370/3 = 45б|, т.с. z = z max = 456§. "
Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей се элементов, выбираем вторую строку (индекс 7’ = 1). Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями для дополнительной переменной Ж5 и дополнительный столбец. Получаем
к" = 4 Т
После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. /" = 5.
Находим разрешающий столбец, т.с. индекс к" такой, что
(критерий входа в новый базис). Разрешающий элемент - (-2/3*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.
Заполним симплекс-таблицу 4.
Таблица 4 |
Х 2 |
||||||
Х 2 |
|||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 3, ж 2 = 6, х± = 1} дает максимум экономической функции г, равный 450, т.с. z = z ma ^ = 450. Эта оптимальная программа является целочисленной. ?
Пример 4.6.2. Решить методом Гомори целочисленную задачу
Решение. Имеется задача линейного программирования с матрицами
![](https://i0.wp.com/bstudy.net/htm/img/4/12135/299.png)
![](https://i0.wp.com/bstudy.net/htm/img/4/12135/300.png)
Заполним симплекс-таблицу с начальной программой.
Таблица 1 |
|||||||
к = 1 Т
С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 1*.
Таблица 2 |
Х 2 |
||||||
Разрешающий элемент - 5*.
Таблица 3 |
|||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 12/5, 24 = 1/5, 25 = 28/5} дает минимум экономической функции г, равный -11/5 = -2.2, т.с. z =
~min = -2.2.
Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей сс элементов, выбираем, например, третью етроку (индекс г = 5) с максимальной дробной частью. Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями третьей строки для дополнительной переменной xq (эта строка позволяет отсечь от области программ части, содержащие точки с нецслочислснными координатами) и дополнительный столбец. Получаем
Таблица 3" |
||||||||
г - -И |
к" = 3 Т
После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I" = 6.
Находим разрешающий столбец, т.е. индекс к" такой, что
![](https://i0.wp.com/bstudy.net/htm/img/4/12135/301.png)
(критерий входа в новый базис). Разрешающий элемент - (-3/5*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.
Заполним симплекс-таблицу 4.
Таблица 4 |
||||||||
Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {х = 2, Х 2 = 0, хз = 1, х 4 = 0, ж 5 = 5} даст минимум экономической функции z 9 равный (-2), т.с. z = -min = - 2. Эта оптимальная программа является целочисленной. ?
Задача 4.6.1. Решить методом Гомори целочисленную задачу
Ответ. Программа
дает минимум экономической функции z, равный (-31), т.с. z = 2 m i n = -31. Эта оптимальная программа является целочисленной.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра вычислительной техники и информационных технологий
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ
Методические указания и задания к практическим занятиям по курсу
«Экономико-математические методы» для студентов экономических специальностей
Составитель Н.Ю.Коломарова
Утверждены на заседании кафедры Протокол № 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 - оптимальный нецелочисленный план.
Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
Оно должно быть линейным;
Должно отсекать найденный оптимальный нецелочисленный план;
Не должно отсекать ни одного целочисленного плана.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением.
Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с оптимальной точкой с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полученное при этом многограннике оптимальное решение будет целочисленным (рис. 8.1).
жающие основные переменные *1, *2, новные переменные Хт+1, Хт+2, ..., Хт+1, решения
Хт через неос- х„ оптимального
(8.5) |
нецелая компонента. В этом случае можно доказать, что неравенство
{Р, } - {а," т+\}хт+1 ■ -~{ат }Хп ^ 0, (* )
сформированное по /-му уравнению системы (8.5), обладает всеми свойствами правильного отсечения.
Для решения задачи целочисленного линейного программирования (8.1)-(8.4) методом Гомори используется следующий алгоритм:
1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (8.1)-(8.4). Если первая задача (8.1)-
(8.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразрешима.
2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (8.5) сформировать правильное отсечение (8.6).
3. Неравенство (8.6) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение
{Р(} - |а/ т+1 }*т+1- ■-{а|"л }хп + хп+1 > (®*^)
и включить его в систему ограничений (8.2).
4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным,
то задача целочисленного программирования (8.1)-(8.4) решена. В противном случае вернуться к п. 2 алгоритма.
Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.
Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения.
^ 8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с учетом проходов) и обеспечивающие производительность за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м и обеспечивающие производительность за смену 3 т сортового зерна.
Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фермер может приобрести не более 8 машин типа В.
Решение. Обозначим через х\, х2 количество машин соответственно типа А и В, через Z - общую производительность. Тогда математическая модель задачи примет вид:
На рис. 8.2 ОКЬМ - область допустимых решений задачи (8.1") - (8.3"), ограниченная прямыми (1), (2), (3) и осями координат; />(2/3; 8) - точка оптимального, но нецелочисленного решения задачи (8.1") - (8.3"); (4) - прямая, отсекающая это нецелочисленное решение; 0№М - область допустимых решений расширенной задачи (8.1’) - (8.3’), (8.61); М2; 7) - точка оптимального целочисленного решения.
I шаг. Основные переменные х3, х4, *5; неосновные переменные Х\, Х2.
х3 | = 60 - | Зх! - 5х2, |
х4 | = 34 - | Зх) - 4х2, |
х5 | = 8 | - *2> |
Z = 2х) | + Зх2. |
Первое базисное решение Х\ = (0; 0; 60; 34; 8) - допустимое. Соответствующее значение линейной функции = 0.
Переводим В основные переменные переменную XI, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной хі, которое “позволяет” принять система ограничений, из условия минимума соответствующих отношений:
Хг = 1ШП|т;т;Т| = 8,
т.е. разрешающим (выделенным) является третье уравнение. При *2 = 8 в этом уравнении Х5 = 0, и в неосновные переходит переменная Х5.
II шаг. Основные переменные х2, х3, х*; неосновные переменные Хь Х5.
{ |
(8.6) |
Введя дополнительную целочисленную переменную х6 > О, получим равносильное неравенству (8.6") уравнение
~1*5 + Хб = °" ^8"7 ^
Уравнение (8.7") необходимо включить в систему ограничений (8.5") исходной канонической задачи, после чего повторить процесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (8.7") в систему, полученную на последнем шаге решения задачи (без условия целочисленности).
IV шаг. Основные переменные Х), *2, хз> *б‘> неосновные переменные *1, *2-
Х1 = з - 3*4 +
х3 = 18 + х4 +___ х5,
х6 - + ^х4 + з"х5-
Базисное решение Х4 = (у; 8; 18; 0; 0; -у) - недопустимое. (Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение).
Для получения допустимого базисного решения необходимо перевести в основные переменную, входящую с положительным коэффициентом в уравнение, в котором свободней член отрицательный, т.е. *1 или х$ (на этом этапе линейную функцию не рассматриваем). Переводим в основные, например, переменную Х5.
V шаг. Основные переменные Х\, Х2, Х3, Х5; неосновные переменные Я], Х£
Получим после преобразований:
ЛГ| = 2 - х4 + 2х6,
*2 = 7 + 2х* ~ 2Х("
х3 = 19 + -х4 + -х6,
*5 = 1 - 2х* + 2Х6’
2 = 25-|х4--|х6.
^5 =(2; 7; 19; 0; 1;0);^ = 25.
Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х5 - оптимальное решение.
Итак, 2тах = 25 при оптимальном целочисленном решении X* - Х$ =(2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа А и 7 машин типа В\ при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выделенных равны 0, в резерве для покупки - 1 машина типа В (шестая компонента содержательного смысла не имеет).
Замечание. Для геометрической интерпретации на плоскости Ох\Хг (см. рис.8.2) отсечения (8.6") необходимо входящие в него переменные х4 и х$ выразить через переменные XI и х2. Получим (см. 2-е и 3-е уравнения системы ограничений (8.5")):
у - у (34 - Зх, - 4х2) - у (8 - х2) £ 0 или х, + 2х2 £ 16.
(см. отсечение прямой (4) на рис 8.2)>
^ 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 м и длиной 0,9 м, причем заготовок каждого вида должно быть получено не менее 50 шт. и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способами: 1) на 2 заготовки по 1,2 м; 2) на 1 заготовку по 1,2 м и 2 заготовки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен,
распиливаемых каждым способом, с тем чтобы заготовок любого вида было получено из наименьшего числа бревен.
Решение. Обозначим через х\, хі, хт, число бревен, распиливаемых соответственно 1,"2-и 3-м способами. Из них можно получить 2хі + *2 заготовок по 1,2 м и 2л\ + Зх2 заготовок по 0,9 м. Общее количество бревен обозначим I. Тогда математическая модель задачи примет вид:
I 2х, + х2 - х4 = 50, , не превосходящее данного.
Под
дробной
частью
некоторого числа а
понимается наименьшее неотрицательное
число
такое, что разность между ним иа
есть
[a
]
– целая часть числа).
Для
выбранной базисной переменной
с
наибольшей дробной частью
находим дробную часть
этой переменной и дробные части всех
коэффициентов при переменныхi
- й строки системы ограничений
(производящей
строкой).
Обозначим
и
целые
части чисел
и
.
Величины дробных частей
и
(
)
определяются следующим образом
![](https://i0.wp.com/studfiles.net/html/2706/164/html_Qi9uzp9YFF.aEhn/img-VJuMHo.png)
Для этого по производящей строке симплексной таблицы выписывается уравнение, предполагая, что первые m переменных являются базисными для данного оптимального плана
или
Переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой:
Так
как <1,
то заменяя в правой части
,
получим строгое неравенство
Так как левая часть неравенства должна принимать целые значения, то, следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:
Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.
Решаем задачу, используя двойственный симплексный метод. Если новый оптимальный план расширенной задачи будет целочисленным, то задача решена. Если же решение нецелое, то нужно повторять алгоритм метода Гомори вплоть до получения целочисленного решения.
Пример
.
Методом Гомори найти решение задачи
целочисленного программирования,
состоящей в определении максимального
значения функции
при условии
Решение . Выравнивая неравенства с помощью вспомогательных переменных х 3 , х 4 , получаем задачу линейного программирования в канонической форме:
Решаем задачу линейного программирования симплексным методом, используя поэтапный переход от одного базиса к другому. Ход решения задачи и полученное оптимальное решение представлены в таблицах.
С Б |
С 2 =11 | |||||
| ||||||
∆ j =Z j –С j |
С Б |
С 2 =11 | |||||
| ||||||
|
|
| ||||
∆ j =Z j –С j |
|
|
|
В найденном оптимальном плане значение переменной х 2 равно дробному числу. Находим его дробную часть и дробные части всех элементов строки, содержащей переменную х 2 , а именно:
Теперь составляем для найденных значений дробных частей неравенство Гомори:
.
х 5 , переносим свободный член уравнения в правую часть и получаем новое ограничение:
.
Добавляем в симплексную таблицу строку, содержащую новое ограничение, и столбец, содержащий новую переменную, и продолжаем решать задачу двойственным симплексным методом, так как теперь в таблице записан псевдоплан.
| |||||||
|
|
| |||||
|
|
| |||||
∆ j =Z j –С j |
|
|
|
С Б |
С 2 =11 | ||||||
|
|
|
|||||
|
|
||||||
∆ j =Z j –С j |
|
|
Полученное оптимальное решение расширенной задачи содержит нецелое значение переменной х 1 , поэтому находим для этой строки дробные части всех нецелых чисел, а именно:
и
новое неравенство Гомори имеет вид:
Выравниваем
неравенство Гомори с помощью новой
вспомогательной переменной х
6 ,
переносим свободный член уравнения в
правую часть и получаем новое ограничение:
.
Добавляем его к решаемой задаче, выравниваем с помощью вспомогательной переменной и решаем расширенную задачу
С Б |
С 2 =11 | |||||||
|
|
| ||||||
|
| |||||||
|
|
| ||||||
∆ j =Z j –С j |
|
|
С Б |
С 2 =11 | |||||||
∆ j =Z j –С j |
Таким
образом, найдено оптимальное решение
задачи целочисленного программирования:
Z
max
=11 при
.
Замечания :
Если
в процессе решения в симплексной таблице
появится уравнение с нецелой компонентой
и целыми коэффициентами в соответствующей
строке системы ограничений
,
то данная задача не имеет целочисленного
решения.