Составление дополнительного ограничения метод гомори. Модели целочисленного линейного программирования

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

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

Пример 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), так как переменная

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

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

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

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

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

Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полученное при этом многограннике оптимальное решение будет целочисленным (рис. 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	х 2
х 3
х 4
х 5

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

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

,

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

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

	х 1	х 5
х 3		-5
х 4		-4
х 2
		-3	-24

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

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

	х 4	х 5				х 4	х 5
х 3	-3	-3		х 3	-1	-1
х 1		-4		х 1	1/3	-4/3	2/3
х 2				х 2
	-2	-1	-76		-2/3	-1/3	-76/3

Базисное решение Х 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
х 1	1/3	-4/3	2/3
х 2
х 3	-1	-1
х 6	-1/3	-2/3	-2/3
	-2/3	-1/3	-76/3

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

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

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

	х 4	х 6				х 4	х 6
х 1	-6/9	4/3	-12/9	х 1		-2
х 2	1/3	-1	-14/3	х 2	-1/2	3/2
х 3	1/3		38/3	х 3	-1/2	-3/2
х 5	-1/3		-2/3	х 5	1/2	-3/2
	3/9	1/3	150/9		-1/2	-1/2	-25

Х 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).

Пусть оптимальный план, полученный симплекс-методом для задачи (5.1)-(5.3), следующий: и получен на базисе
Тогда последняя симплексная таблица имеет следующий вид:

Таблица 5.1

Приведённая к базису симплексная таблица для задачи целочисленного программирования

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

где и

Например,

.

Так как по условию
– неотрицательные целые числа, то и разностьтакже целое неотрицательное число.

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

Если в оптимальном плане задачи (5.1)-(5.3) несколько дробных
то дополнительное ограничение составляют дляmax. Это ускоряет процесс получения оптимального целочисленного решения.

Рассмотрим геометрический смысл введения дополнительного ограничения (см. рис. 5.2). Пусть в точке A многогранника решений Q функция Z достигает максимального значения Z (A )=max, но координаты точки A – дробные. Тогда введенные ограничения по целочисленности I и II от области Q отсекают область с угловой точкой
, координаты которой целочисленные и в которой линейная функция достигает максимального значения.

Рис.5.2. Геометрический смысл ограничения Гомори

Метод Гомори рассмотрим на примере следующей задачи.

Пример 5.1. Найти максимальное значение функции

при условиях

Дать геометрическую интерпретацию решения задачи.

Решение. Для определения оптимального плана задачи (5.5)-(5.8) сначала находим оптимальный план задачи (5.5)-(5.7):

Таблица 5.2

базис
план
– неоптимальный,
.

Таблица 5.3

Симплекс-таблица, приведённая к базису

,
– неоптимальный, базис
,
.

Таблица 5.4

Симплекс-таблица, приведённая к базису

Оптимальный план
, базис
. Этот оптимальный план не является оптимальным планом задачи (5.5)-(5.8), поскольку две компонентыиимеют нецелочисленное значение. При этом дробные части этих чисел
равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной(чаще берут первую строку). Из последнейсимплекс-таблицы имеем:

.

Таким образом, к системе ограничений задачи (5.5)-(5.7) добавляем неравенство

Теперь находим максимальное значение функции (5.5) при выполнении условий (5.6), (5.7) и (5.9). В условие (5.9) вводим дополнительную переменную :

Таблица 5.5

Ввод в симплекс-таблицу дополнительной переменной

Выберем .
базис.

Таблица 5.6

Приведение симплекс-таблицы к базису

Базис
.
.

Запишем оптимальный план для исходной задачи:
При этом плане значение целевой функции равно
.

Геометрическая интерпретация решения задачи.

Рис.5.3. Геометрическая интерпретация решения задачи

Областью допустимых решений задачи (5.5)-(5.7) является многоугольник ОАВС D (рис. 5.3). Из рисунка видно, что максимальное значение целевая функция принимает в точке
т.е.
является оптимальным планом. Так как этот план не является оптимальным планом задачи (5.5)-(5.8) (числаи– дробные), то вводится дополнительное ограничение

Исключая из этого неравенства иподстановкой вместо них соответствующих значений из уравнений системы ограничений (5.6), получим
.

.

Этому неравенству соответствует полуплоскость, ограниченная прямой
отсекающей отмногоугольника ОАВСD треугольник EFC .

Как видно из рисунка, областью допустимых решений полученной задачи является многоугольник OABEFD . В точке E (9;4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты точки Е – целые числа и неизвестные
ипринимают целочисленные значения при подстановке в уравнения (5.6) значений
и
то
является оптимальным планом задачи (5.5)-(5.8). Это следует и из таблицы симплекс-метода.

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

Вопросы для самопроверки

Области применения целочисленного программирования.

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

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

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

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

Геометрический смысл введения сечения Гомори.

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

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

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

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

При этом ограничения типа x i ≥ 0 не учитывайте.

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

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

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

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

Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членов b i и целыми коэффициентами a ij , то данная задача не имеет целочисленного оптимального решения.

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

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

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

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

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

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

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

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

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

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

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

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

Первая итерация Гомори. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольшее по модулю. Ведущей будет пятая строка, а переменную x 7 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует пятому столбцу, т.е. переменную x 5 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-16 / 33).

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

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

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

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


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



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

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

Вторая итерация Гомрои. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных наибольшей по модулю является переменная x 8 . Ее следует вывести из базиса.
3. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x 7 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Выполняем преобразование Новых отсечений Гомори.

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

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

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

Третья итерация методом Гомори. Переменную x 9 следует вывести из базиса. Минимальное значение θ соответствует восьмому столбцу, т.е. переменную x 8 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Выполняем преобразование.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F(X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

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