Н.Ю. Коломарова Решение задач линейного целочисленного программирования методом гомори. Составление дополнительного ограничения (сечения Гомори)
Графический метод решения задач целочисленного программирования.
При наличии в задаче линейного программирования двух переменных, а в системе ограничения – неравенств, она может быть решена графическим методом без требований целочисленных переменных.
Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.
Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:
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 |
Оптимальное решение расширенной ЗЛП удовлетворяет ограничению целочисленности.
Экономическая и геометрическая интерпретация задачи целочисленного программирования. Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
В математической модели задачи целочисленного программирования как целевая функция, так и функции в системе ограничений могут быть линейными, нелинейными и смешанными. Ограничимся случаем, когда целевая функция и система ограничений задачи являются линейными.
Пример 20.
В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., а II вида – 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Зная что для установки одного комплекта оборудования I вида требуется 2 м 2 площади, а оборудования II вида – 1 м 2 площади определить такой набор дополнительного оборудования, которых дает возможность максимально увеличить выпуск продукции
Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет x 1 комплектов оборудования I вида и комплектов оборудования II вида. Тогда переменные x 1 и должны удовлетворять следующим неравенствам:
Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит
По своему экономическому содержанию переменные x 1 и могу принимать лишь целые неотрицательные значения, т. е.
x 1 , – целые. (73)
Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (71) при вы полнении условий (70), (72) и (73). Так как неизвестные могут принимать только целые значения, то задача (70) – (73) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого прежде всего построим многоугольник решений задачи, состоящей в определении максимального значения линейной функции (71) при выполнении условий (70) и (72) (рис. 11). Координаты всех точек построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (70) и условию неотрицательности переменных (72). Вместе с тем условию (73), т. е. условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF , содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (71) на многоугольнике OKEMNF , то координаты этой точки и определят оптимальный план задачи.
Для этого построим и прямую проходящую через многоугольник решений OKEMNF (число 12 взято произвольно). Построенную прямую передвигаем в направлении вектора до тех пор, пока она не пройдет через последнюю общую точку ее с данным многоугольником. Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является максимальным.
В данном случае искомой является точка E (1; 3), в которой целевая функция принимает максимальное значение С ледовательно, координаты точки Е определяют оптимальный план задачи (70) – (73). В соответствии с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуск продукции, равное 14 ед. в смену.
Пример 21.
Для выполнения работ могут быть использованы п механизмов. Производительность i –го механизма при выполнении j – й работы равна . Предполагая, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами, обеспечивающее максимальную производительность. Построить математическую модель задачи.
Решение. Введем переменную x ij , значение которой равно 1, если при выполнении i–й работы используется j – й механизм, и равно 0 в противном случае. Тогда условия использования каждого механизма только на одной работе выражаются равенствами
(74)
а условия выполнения работы только одним механизмом – равенствами
(75)
Таким образом, задача состоит в
определении таких значений неизвестных 
, удовлетворяющих системам
уравнений (74) и (75) и условию (76), при которых достигается максимальное
значение функции
Сформулированная задача является задачей целочисленного программирования.
Определение оптимального плана задачи целочисленного программирования. Рассмотрим задачи целочисленного программирования, в которых как целевая функция, так и функции в системе ограничений являются линейными. В связи с этим сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения. В общем виде эту задачу можно записать так: найти максимум функции
при условиях
(79)
– целые (81)
Если найти решение задачи (78) – (81) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером , решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (78) – (81) требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори , в основе которого лежит описанный выше симплексный метод.
Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) – (80) переменная принимает дробное значение, то к системе уравнений (79) добавляют неравенство
(82)
и находят решение задачи (78) – (80), (82).
В неравенстве (82) и – преобразованные исходные величины и значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (78) – (80) дробные значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной частью.
Если в найденном плане задачи (78) – (80), (82) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.
Если требование целочисленности (81) относится лишь к некоторым переменным, то такие задачи называются частично целочисленными. Их решение также находят последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения. В этом случае такое ограничение имеет вид
где определяются из следующих соотношений:
1) для , которые могут принимать нецелочисленные значения,
(84)
2) для , которые могут принимать только целочисленные значения,
(85)
Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы :
1. Используя симплексный метод, находят решение задачи (78) – (80) без учета требования целочисленности переменных.
2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане задачи (78) – (81) должна быть целочисленной.
3. Используя двойственный , находят решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.
4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (78) – (81) или установления ее неразрешимости.
Пример 22.
Методом Гомори найти максимальное значение функции
при условии
(87)
– целые (89)
Решение. Для определения оптимального плана задачи (86) – (89) сначала находим оптимальный план задачи (86) – (88) (табл. 22).
Таблица 22
|
С б |
Р 0 |
|||||||
Как видно из
табл. 22, найденный
оптимальный план 
задачи (86) – (88) не является оптимальным планом задачи (86) –
(89), поскольку две компоненты и имеют нецелочисленные значения. При этом дробные части этих
чисел равны между собой. Поэтому для одной из этих переменных составляется
дополнительное ограничение. Составим, например, такое ограничение для
переменной Из
последней симплекс–таблицы (табл. 22) имеем
Таким образом, к системе ограничений задачи (86) – (89) добавляем неравенство
или
Таблица 23
|
С б |
Р 0 |
||||||||
Находим теперь максимальное значение функции (86) при выполнении условий (87), (88) и (90) (табл. 23).
Из таблицы 23 видно, что исходная задача
целочисленного программирования имеет оптимальный план
П
ри этом плане значение целевой функции равно .
Дадим геометрическую интерпретацию решения задачи. Областью допустимых
решений задачи (86) – (88) является многоугольник OABCD
(рис. 12).
Из рис. 12 видно, что максимальное значение целевая функция принимает в
точке С
(19/2; 7/2), т. e
. что Х =
(19/2; 7/2; 0; 0; 34) является
оптимальным планом. Это непосредственно видно и из таблицы 22. Так как
Х
= (19/2; 7/2; 0; 0; 34) не является оптимальным планом задачи
(86) – (89) (числа и – дробные), то
вводится дополнительное ограничение . Исключая
из
него и подстановкой вместо них соответствующих значений из уравнений
системы ограничений (87), получим отсекающий от многоугольника
OABCD
треугольник EFC.
Как видно из
рис
. 12, областью допустимых решений полученной
задачи является многоугольник OABEFD
. В точке Е
(9; 4) этого
многоугольника целевая функция данной задачи принимает максимальное
значение. Так как координаты точки Е
– целые числа и неизвестные
,
и принимают целочисленные
значения при подстановке в уравнение (87) значений и , то
является оптимальным планом задачи (86) – (89). Это следует и из
таблицы 23.
Пример 23.
Методом Гомори найти решение задачи, состоящей в определении максимального значения функции
при условиях
– целые. (94)
Дать геометрическую интерпретацию решения задачи.
Решение. Сформулированную задачу перепишем так: найти максимальное значение функции
при условиях
(96)
– целые. (98)
Задача (95) – (98) является частично целочисленной, так как переменные и могут принимать нецелочисленные значения.
Находим симплексным методом решение задаяи (95) – (97) (таблица 24).
Таблица 24
|
С б |
Р 0 |
|||||||
|
С б |
Р 0 |
|||||||
|
–1/3не является планом задачи (95) – (98), так как переменная |
Метод Гомори решения задач целочисленного программирования является методом отсечения .
Суть метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана. Для этого сначала решается ослабленная задача линейного программирования без учета условия целочисленности переменных.
Если полученное решение задачи линейного программирования является целочисленным, то задача целочисленного программирования также решена и найденное решение является оптимальным и для нее. Если же в найденном решении задачи линейного программирования одна или большее число переменных не целые, то для отыскания целочисленного решения задачи добавляются новое линейное ограничение, которое отсекает нецелочисленные решения. При продолжении решения расширенной задачи двойственным симплексным методом с учетом этого ограничения получается целочисленный план.
Для нахождения целочисленного решения задачи методом Гомори используется следующий алгоритм.
Оно должно быть линейным;
Должно отсекать найденный оптимальный нецелочисленный план;
Не должно отсекать ни одного целочисленного плана.
Если
нецелых базисных переменных несколько,
то для составления ограничения выбираем
компоненту оптимального плана
с
наибольшей дробной частью
(если таких переменных несколько, то
выбираем любую).
Этой переменной соответствует строка симплексной таблицы, называемая строкой, производящей отсечение (производящей строкой ).
Для изложения метода вводим следующие понятия. Пусть a – действительное число.
Под целой частью некоторого числа а понимается максимальное целое число [a ], не превосходящее данного.
Под
дробной
частью
некоторого числа а
понимается наименьшее неотрицательное
число
такое, что разность между ним иа
есть
[a
]
– целая часть числа).
Для
выбранной базисной переменной
с
наибольшей дробной частью
находим дробную часть
этой переменной и дробные части всех
коэффициентов при переменныхi
- й строки системы ограничений
(производящей
строкой).
Обозначим
и
целые
части чисел
и
.
Величины дробных частей
и
(
)
определяются следующим образом
Для этого по производящей строке симплексной таблицы выписывается уравнение, предполагая, что первые 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 при
.
Замечания :
Если
в процессе решения в симплексной таблице
появится уравнение с нецелой компонентой
и целыми коэффициентами в соответствующей
строке системы ограничений
,
то данная задача не имеет целочисленного
решения.
Обычно в задачах линейного программирования не требуется, чтобы координаты плана были целыми числами. Однако в практике часто приходится сталкиваться с задачами, в которых координаты оптимальных планов должны быть целыми числами, и такие задачи называются задачами . При решении задач линейного программирования графическим методом и симплекс-методом нет гарантий, что координаты оптимального плана будут целыми числами.
В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 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-й задаче верхней границей для является .
Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.Пусть найдено решение задачи ЛП: . Решение L i будет целым числом, если
т.е. 
. {β i } - дробная часть нецелочисленного оптимального решения x i , {d i } - дробная часть не базисных переменных. Данное соотношение определяет (см. рисунок).
Назначение сервиса . Онлайн-калькулятор применяется для решения задач целочисленного линейного программирования методом отсечений. В ходе решения используются симплексные таблицы. (см. пример).
Инструкция . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения методом Гомори). Дополнительно создается шаблон решения в формате Excel .
При этом ограничения типа x i ≥ 0 не учитывайте.Виды алгоритма Гомори
- Первый алгоритм Гомори решения полностью целочисленных задач.
- Второй алгоритм Гомори для частично целочисленных задач линейного программирования .
Алгоритм Гомори для полностью целочисленных задач включает в себя следующие этапы:
- Решается задача линейного программирования без учета целочисленности.
- Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
- Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
- Полученная задача решается двойственным симплекс-методом .
Пример
. Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 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