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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) i, при котором линейная функция

принимает максимальное или минимальное значение при ограничениях

(8.2)

(8.3)

– целые числа. (8.4)

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

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

Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинаторные методы; в) приближенные методы. Остановимся подробнее на методах отсечения.

Методы отсечения. Метод Гомори

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

• оно должно быть линейным;
• должно отсекать найденный оптимальный нецелочисленный план;
• не должно отсекать ни одного целочисленного плана.

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

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

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

Один из алгоритмов решения задачи линейного целочисленного программирования (8.1)-(8.4), предложенный Р. Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Пусть задача линейного программирования (8.1)-(8.3) имеет конечный оптимум, и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные через неосновные переменные оптимального решения:

(8.5)

так что оптимальным решением задачи (8.1)-(8.3) является i, в котором, например, β; – нецелая компонента. В этом случае можно доказать, что неравенство, сформированное по i- му уравнению системы (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) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение и включить его в систему ограничений (8.2).
• 4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (8.1)–(8.4) решена. В противном случае вернуться к п. 2 алгоритма.

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

1 В неравенстве (8.6) присутствует символ { }, означающий дробную часть числа. Целой частью числа а называется наибольшее целое число [в], не превосходящее а, дробной частью числа – число {а}, равное разности между этим числом и его целой частью, т.е. {а} = а-[в].

Например, для (обратите внимание, именно -3, а не -2) и

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

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

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

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

(!!!8.8)

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

(8.2)

– целые числа. (8.4)

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

(8.5)

Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 8.2).

На рис. 8.2 OKLM – область допустимых решений задачи (8.Г)–(8.3"), ограниченная прямыми (1), (2), (3) и осями координат; L (2/3; 8) – точка оптимального, но нецелочисленного решения задачи (8.1")–(8.3"); (4) – прямая, отсекающая это нецелочисленное решение; OKNM – область допустимых решений расширенной задачи (8.1")–(8.3"), (8.6"); N(2; 7) – точка оптимального целочисленного решения.

I шаг. Основные переменные Неосновные переменные

Первое базисное решение– допусти

мое. Соответствующее значение линейной функции

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

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

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

II шаг. Основные переменные х 2, х 3, х 4.

Неосновные переменные.г, ху

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

Переводим в основные переменнуюа в неосновные х4.

III шаг. Основные переменные х, х 2, х 3.

Неосновные переменные х4, х5.

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

Базисное решение X., оптимально для задачи (8.1")–(8.3") (), так как в выражении линейной функции

отсутствуют неосновные переменные с положительными коэффициентами.

Однако решение Х 3 не удовлетворяет условию целочисленности (8.4") По первому уравнению с переменной х, получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (8.6):

Обращаем внимание на то, что согласно (8.5) и (8.6) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х- – с противоположными знаками.

Так как дробные части,

, го последнее неравенство запишем

(8.6")

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

(8.7")

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

IV шаг. Основные переменные x v х 2, х3, χβ.

Неосновные переменные х4, х5.

Базисное решение – недопусти

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

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

V шаг. Основные переменные х, х2, х3, х5.

Неосновные переменные х4, х6.

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

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

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

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

• (см. отсечение прямой (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 м. Найти число бревен, распиливаемых каждым способом, с тем чтобы заготовок любого вида было получено из наименьшего числа бревен.

Решение. Обозначим через х {} х2, х3 число бревен, распиливаемых соответственно 1, 2 и 3-м способами. Из них можно получить 2xj +х2 заготовок по 1,2 м и 2х х +3х2 заготовок по 0,9 м. Общее количество бревен обозначим Z. Тогда математическая модель задачи примет вид

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

Введя дополнительные переменныепри

ведем систему неравенств к равносильной системе уравнений:

(8.5")

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

III шаг. Основные переменные x v х 2.

Неосновные переменные х у х А, х 5.

т.е.при оптимальном решении

Получилось, что две компоненты оптимального решения не удовлетворяют условию целочисленности (8.4"), причем бо́льшую целую часть имеет компонента х 2. В соответствии с ∏. 2 алгоритма решения задачи целочисленного программирования (см. с. 166) по второму уравнению, содержащему эту переменную х 2, составляем дополнительное ограничение (8.6):

Найдем дробные части

и запишем последнее неравенство в виде

(8.6")

Введя дополнительную переменнуюполучим

равносильное неравенству (8.6") уравнение:

(8.7")

Выразим из (8.7") дополнительную переменную х6 и полученное уравнение введем в систему ограничений, которую мы имели на последнем, III, шаге решения задачи (8.1")– (8.3") (без условия целочисленности).

IV шаг. Основные переменные х {, х у х 6.

Неосновные переменные х 3, х4, х 5.

Решая эту расширенную задачу симплексным методом (предлагаем студентам выполнить самостоятельно), получим следующее.

V шаг. Основные переменные х); х 2, х3.

Неосновные переменные х4, х5, хб.

т.е.при оптимальном решении

Полученное оптимальное решение расширенной задачи (8.1")–(8.3"), (8.6") вновь не удовлетворяет условию целочисленности (8.4"). По первому уравнению с переменной Xj, получившей нецелочисленное значение в оптимальном

решении (), еоставляем второе дополнительное ограни

чение (8.6):

которое приводим к виду

С помощью дополнительной переменнойприво

дим это неравенство к равносильному уравнению, которое включаем в систему ограничений, полученную на последнем, V, шаге решения расширенной задачи (8. Г")–(8.3"), (8.6") симплексным методом.

VI шаг. Основные переменные x v х 2, х у х т

Неосновные переменные х 4, X-, х 6.

Опуская дальнейшее решение задачи симплексным методом (предлагаем сделать это самим студентам), на заключительном, VII, шаге получим.

VII шаг. Основные переменные x v х т х3, х г

Неосновные переменные x v х 6, х т

Так как в выражении линейной функции нет неосновных переменных с отрицательными коэффициентами, то Х 7 – оптимальное целочисленное решение исходной задачи.

Следует обратить внимание на то, что в полученном выражении линейной функции Z отсутствуют неосновные переменные х Г) и х 6. Это означает, что, вообще говоря, существует бесконечное множество оптимальных решений (любых, не обязательно целочисленных), при которых Z" = Zmjn = 46. Эти решения получаются при значении неосновной переменной х 7 (входящей в выражение для Z), равной нулю (т.е. при х 7 = 0), и при любых значениях неосновных переменных ж5 и х 6 (не входящих в выражение для Z), которые "позволяет" принять система ограничений: 0<лг5 х 5 ≤ 1 и 0 < x (i ≤ 1. Но в силу условия целочисленности переменные х- и х (> могут принять только значения 0 или 1. Поэтому задача будет иметь четыре целочисленных оптимальных решения, когда х. и *6 в любой комбинации принимают значения 0 или 1, а х 7 = 0. Подставляя эти значения в систему ограничений на VII шаге, найдем эти оптимальные решения:

Наличие альтернативных оптимальных целочисленных решений позволяет осуществить выбор одного из них, руководствуясь дополнительными критериями, не учитываемыми в математической модели задачи. Например, из условия данной задачи следует, что распиливание бревен не дает отходов лишь по 3-му способу, поэтому естественно при выборе одного из четырех оптимальных решений отдать предпочтение решению Х^ 3 при котором максимальное число бревен (х 2 = 41) распиливается без отходов.

Итак, Zmin=46 при оптимальных целочисленных решениях (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). При записи оптимальных решений мы оставили лишь первые три компоненты, выражающие число бревен, распиливаемых соответственно 1, 2 и 3-м способами, и исключили последние четыре компоненты, не имеющие смыслового значения.

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

• Можно убедиться, что при этом решение задачи короче.

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

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

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

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

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

Геометрически добавление ка­ждого линейного ограничения отвечает проведению прямой (ги­перплоскости), которая отсекает от многоугольника (многогран­ника) решений некоторую его часть вместе с оптимальной точ­кой с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранни­ка. В результате новый много­гранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полу­ченное при этом многограннике оптимальное решение будет целочисленным (рис. 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, + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.

[з] Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I = п + 1.

• а) Если все коэффициенты уц > 0, то задача не имеет решения (т.е. целочисленная задача решена).
• б) В противном случае находим индекс к такой, что

(критерий входа в новый базис). Заметим, что выбор разрешающего элемента у и* не изменяет знак у критериев Aj.

[4] Если в новой таблице имеется хотя бы один х 3 s и повторить указанные процедуры необходимое число раз.

[~5~| Если полученное оптимальное решение целочисленно, то поставленная задача решена. В противном случае надо вернуться к пункту .

Пример 4.6.1. Решить методом Гомори целочисленную задачу

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

с матрицами

Таблица 1
	Х 4

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 6*.

Таблица 2				х 2
		„ _ 1 Ж Z ~_3_

к" = 2 Т

Разрешающий элемент - 1/2*.

Х в ^ 0). Следовательно, программа {xi = 11/3, х 2 = 5} даст максимум экономической функции z, равный 1370/3 = 45б|, т.с. z = z max = 456§. "

Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей се элементов, выбираем вторую строку (индекс 7’ = 1). Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями для дополнительной переменной Ж5 и дополнительный столбец. Получаем

к" = 4 Т

После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. /" = 5.

Находим разрешающий столбец, т.с. индекс к" такой, что

(критерий входа в новый базис). Разрешающий элемент - (-2/3*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.

Заполним симплекс-таблицу 4.

Таблица 4				Х 2
	Х 2

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 3, ж 2 = 6, х± = 1} дает максимум экономической функции г, равный 450, т.с. z = z ma ^ = 450. Эта оптимальная программа является целочисленной. ?

Пример 4.6.2. Решить методом Гомори целочисленную задачу

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

Заполним симплекс-таблицу с начальной программой.

Таблица 1

к = 1 Т

С помощью метода вращения заполним следующие таблицы. Разрешающий элемент - 1*.

Таблица 2				Х 2

Разрешающий элемент - 5*.

Таблица 3

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {xi = 12/5, 24 = 1/5, 25 = 28/5} дает минимум экономической функции г, равный -11/5 = -2.2, т.с. z =

~min = -2.2.

Так как эта оптимальная программа не является целочисленной, применим алгоритм Гомори для нахождения целочисленной оптимальной программы. В качестве строки, на базе которой образуем дополнительную строку из дробных частей сс элементов, выбираем, например, третью етроку (индекс г = 5) с максимальной дробной частью. Заполним таблицу 3", добавив в таблицу 3 дополнительную строку (4.14) с дробными частями третьей строки для дополнительной переменной xq (эта строка позволяет отсечь от области программ части, содержащие точки с нецслочислснными координатами) и дополнительный столбец. Получаем

Таблица 3"
		г - -И

к" = 3 Т

После добавления новой строки симплекс-таблица 3" перестает соответствовать допустимому базисному решению задачи, которую она описывает. Находим допустимое базисное решение, считая новую строку разрешающей, т.е. I" = 6.

Находим разрешающий столбец, т.е. индекс к" такой, что

(критерий входа в новый базис). Разрешающий элемент - (-3/5*). Заметим, что такой выбор разрешающего элемента не изменяет знак у критериев Aj.

Заполним симплекс-таблицу 4.

Таблица 4

Значения всех критериев ^ 0, (Х в ^ 0). Следовательно, программа {х = 2, Х 2 = 0, хз = 1, х 4 = 0, ж 5 = 5} даст минимум экономической функции z 9 равный (-2), т.с. z = -min = - 2. Эта оптимальная программа является целочисленной. ?

Задача 4.6.1. Решить методом Гомори целочисленную задачу

Ответ. Программа

дает минимум экономической функции z, равный (-31), т.с. z = 2 m i n = -31. Эта оптимальная программа является целочисленной.