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

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

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

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

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

при условиях

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. Метод «ветвей и границ»

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

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

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

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

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

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

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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) 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-м способами, и исключили последние четыре компоненты, не имеющие смыслового значения.

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

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

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

Алгоритм Гомори

ГП С помощью симплекс-метода находим оптимальную программу. Если получились целочисленные значения для всех Xj , то задача решена. В противном случае среди Xj имеются нецслочисленные значения.

|~2~1 Среди нецелых Xj выбираем произвольный элемент х г и в задаче добавляем еще одно ограничение

что равносильно добавлению в симплекс-таблице еще одной строки, после чего она перестает соответствовать допустимому базисному решению новой задачи линейного программирования, которую она описывает. В ограничении применяются дробные части элементов строки, в которой находится х г. Применяемое обозначение для дробной части исходит из того, что всякое действительное число у можно представить в виде суммы у = [у] + {?у}, где [у] - целая часть и {у} = У ~ [у] ~ дробная часть.

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