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

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

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

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

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

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

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

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

при условиях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8х 1 + 4х 2 ≤ 38

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

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

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

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

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

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

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

Базис	С	План					θ
Х 1	Х 2	Х 3	Х 4
X 1 →Х 3							20/5=4 min
Х 4							38/8=4,75
f(x) = 0	-7	-3
X 1				2/5	1/5		4:2/5=10
X 2 →X 4				4/5	-8/5		6:4/5=7,5 min
f(x) =28		-1/5	7/5
X 1						-1/2
X 2		7,5			-2	5/4
f(x) =29,5				1/4

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

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

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

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

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

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

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

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

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

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

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

0,25X 4 ≡ 0,5.

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

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

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

0,25X 4 ≥ 0,5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А.

В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечания :

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

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

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

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

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

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

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

жающие основные переменные *1, *2, новные переменные Хт+1, Хт+2, ..., Хт+1, решения

Хт через неос- х„ оптимального

(8.5)

нецелая компонента. В этом случае можно доказать, что неравен­ство

{Р, } - {а," т+\}хт+1 ■ -~{ат }Хп ^ 0, (* )

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

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

1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочис­ленного программирования (8.1)-(8.4). Если первая задача (8.1)-

(8.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразре­шима.

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

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

{Р(} - |а/ т+1 }*т+1- ■-{а|"л }хп + хп+1 > (®*^)

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

4. Полученную расширенную задачу решить симплексным ме­тодом. Если найденный оптимальный план будет целочисленным,

то задача целочисленного программирования (8.1)-(8.4) решена. В противном случае вернуться к п. 2 алгоритма.

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

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

^ 8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать обо­рудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с уче­том проходов) и обеспечивающие производительность за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м и обеспечивающие производитель­ность за смену 3 т сортового зерна.

Требуется составить оптимальный план приобретения оборудо­вания, обеспечивающий максимальную общую производитель­ность при условии, что фермер может приобрести не более 8 ма­шин типа В.

Решение. Обозначим через х\, х2 количество машин соот­ветственно типа А и В, через Z - общую производительность. Тогда математическая модель задачи примет вид:

На рис. 8.2 ОКЬМ - область допустимых решений задачи (8.1") - (8.3"), ограниченная прямыми (1), (2), (3) и осями координат; />(2/3; 8) - точка оптимального, но нецелочисленного решения зада­чи (8.1") - (8.3"); (4) - прямая, отсекающая это нецелочисленное решение; 0№М - область допустимых решений расширенной зада­чи (8.1’) - (8.3’), (8.61); М2; 7) - точка оптимального целочисленно­го решения.

I шаг. Основные переменные х3, х4, *5; неосновные перемен­ные Х\, Х2.

х3	= 60 -	Зх! - 5х2,
х4	= 34 -	Зх) - 4х2,
х5	= 8	- *2>
	Z = 2х)	+ Зх2.

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

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

Хг = 1ШП|т;т;Т| = 8,

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

II шаг. Основные переменные х2, х3, х*; неосновные пере­менные Хь Х5.

{

(8.6)

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

~1*5 + Хб = °" ^8"7 ^

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

IV шаг. Основные переменные Х), *2, хз> *б‘> неосновные пе­ременные *1, *2-

Х1 = з - 3*4 +

х3 = 18 + х4 +___ х5,

х6 - + ^х4 + з"х5-

Базисное решение Х4 = (у; 8; 18; 0; 0; -у) - недопусти­мое. (Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение).

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

V шаг. Основные переменные Х\, Х2, Х3, Х5; неосновные пере­менные Я], Х£

Получим после преобразований:

ЛГ| = 2 - х4 + 2х6,

*2 = 7 + 2х* ~ 2Х("

х3 = 19 + -х4 + -х6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|х4--|х6.

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

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

Итак, 2тах = 25 при оптимальном целочисленном решении X* - Х$ =(2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа А и 7 машин типа В\ при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выде­ленных равны 0, в резерве для покупки - 1 машина типа В (шестая компонента содержательного смысла не имеет).

Замечание. Для геометрической интерпретации на плос­кости Ох\Хг (см. рис.8.2) отсечения (8.6") необходимо вхо­дящие в него переменные х4 и х$ выразить через перемен­ные XI и х2. Получим (см. 2-е и 3-е уравнения системы ог­раничений (8.5")):

у - у (34 - Зх, - 4х2) - у (8 - х2) £ 0 или х, + 2х2 £ 16.

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

^ 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 м и длиной 0,9 м, причем заготовок каждого вида должно быть полу­чено не менее 50 шт. и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способа­ми: 1) на 2 заготовки по 1,2 м; 2) на 1 заготовку по 1,2 м и 2 заго­товки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен,

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

Решение. Обозначим через х\, хі, хт, число бревен, распили­ваемых соответственно 1,"2-и 3-м способами. Из них можно полу­чить 2хі + *2 заготовок по 1,2 м и 2л\ + Зх2 заготовок по 0,9 м. Общее количество бревен обозначим I. Тогда математическая модель задачи примет вид:

I 2х, + х2 - х4 = 50, }