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

Пусть оптимальный план, полученный симплекс-методом для задачи (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). Это следует и из таблицы симплекс-метода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этой переменной соответствует строка симплексной таблицы, называемая строкой, производящей отсечение (производящей строкой ).

Для изложения метода вводим следующие понятия. Пусть 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 при
.

Замечания :

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

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

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

Пусть Х* = (х1, х2, …,хm, …, хn) – оптимальный план найденный по симплекс методу, где базисом являются векторы А1, А2,…,Аm. Пусть хi дробное число (число в столбце В в iой строке). Тогда возможно, что в iой строке:

1. все хij целые, это означает, что задача не имеет целочисленного решения

2. некоторые хij дробные

Пусть [хi] и [хij] целые части чисел хi и хij, а {хi } и { хij } – дробные части.

Обозначим qi = {хi} и qij = { хij } и составим разности.

(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0

Преобразуем неравенство в уравнение умножив его на (-1) и добавив новую переменную Хn+1 и добавив новую строку в симплекс таблице (а значит и столбец). Решаем далее двойственным симплекс методом, если найденный план не является целочисленным, то процесс добавления новой переменной, строки и столбца в симплекс таблице повторяем.

Если в оптимальном плане несколько нецелочисленных компанент, то дополнительное ограничение составляем для максимального qi.

Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 47 Метод Гомори: основные идеи и краткое описание алгоритма. Экономический смысл введения дополнительного ограничения.:

  1. 25.Экономические методы управления, их целевое назначение. Виды и основное содержание методов экономического воздействия. Краткая характеристика и особенности применения экономических методов

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

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

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

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

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

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

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

Утверждены на заседании кафедры Протокол № 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 - оптимальный нецелочисленный план.