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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограниче­ние и т. д.

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

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

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

Пусть задача линейного программирования (8.1)—(8.3) име­ет конечный оптимум и на последнем шаге ее решения сим­плексным методом получены следующие уравнения, выра­жающие основные переменные х₁, х₂, ..., х_j, ..., х_т через неос­новные переменные х_т+1 ,х_т+2, ..., *ю+/, —> ^хп оптимального решения

(S.5)

так, что оптимальным решением задачи (8.1)—(8.3) является X ='(PbP2»••■»P/t -эР/яАО,...,0), в котором, например (J, —

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

(8.6)

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

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

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

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

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

(8.7)

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

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

¹ В неравенстве (8.6) присутствует символ { }, означающий дробную часть числа. Целой частью числа а называется наибольшее целое число [а]_% не превосходящее а, а дробной частью числа — число {а}, равное разности между этим числом и его целой частью, т.е. {а} = а - [а]. На­пример, для а = 2— [а] = 2, [а] = 2-- 2 = -; для а = -2— [а] = ~3

1 2

(обратите внимание, именно -3, а не -2) и {#} = -2 — - (-3) = —.

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

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

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

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

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

Z = 2х_{ + Зх₂ -» max (8. Г)

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

(8.2')

х_{ > 0, х₂ £ 0 , (8.3')

х\, х₂— целые числа. (8.4')

Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные *з, ^х4, ^х5- Получим систему ограни­чений:

(8.5')

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

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

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

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

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

II шаг.Основные переменные х₂, хз, х^; неосновные пере­менные X_i? X5.

Х₂ = (0; 8; 20; 2; 0); Z₂ = 24. Переводим в основные пвремен-

. Г 20 2] 2

ную х_ь Х| = min^oo;—;-4 = — а в неосновные Х4-

III шаг.Основные переменные х_ь х₂, х₃; неосновные пере­менные Х4, Х₅.

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

Базисное решение Х$ оптимально для задачи (8.Г) - (8.3^Г) (%тах = Z₃ = 25 — ), так как в выражении линейной функции от­сутствуют неосновные переменные с положительными коэффи­циентами.

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

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

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

(8.6')

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

(8.7')

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

IV шаг.Основные переменные x_h x₂, х₃, х^; неосновные пе­ременные Х\, *2-

2 2

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

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

V шаг.Основные переменные х\, *2> ^хз> ^х5\ неосновные пере­менные Хи Х2-

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

6 Исследование операций в экономике

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

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

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

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

2 1 2

— - -(34 - Зх_{ - 4х₂) - — (8 - х₂) ^ 0 или х, + 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 м. Найти число бревен,

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

Решение. Обозначим через х\, Х2, х$ число бревен, распили­ваемых соответственно 1^2-и 3-м способами. Из них можно полу­чить 2х[ + Х2 заготовок по 1,2 м и 2х\ + 3x2 заготовок по 0,9 м. Общее количество бревен обозначим Z Тогда математическая модель задачи примет вид:

Z = х_{ + х₂ + х₃ -> min (8.1")

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

(8,2")

xj>0, у- 1,2,3, (8.3")

xj — целые числа. (8.4")

Введя дополнительные переменные х₄ > 0, х₅ > 0, приведем систему неравенств к равносильной системе уравнений

(8.5")

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

III шаг.Основные переменные х\₉ х^, неосновные перемен­ные Л/j, Xj, Хс.

^те- ^mm-45 — при оптимальном решении Х_ъ = (4-~; 40~;

0; 0; 0).

Получили, что две компоненты оптимального решения

х, = 4-j и х₂ = 40— не удовлетворяют условию целочисленно-

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

 

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

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

виде

(8.6")

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

(8.7")

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

целочисленности).

IV шаг.Основные переменные jq, х₂, х^\ неосновные пере­менные *з, *4> *5-

 

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

V шаг.Основные переменке х_ь х₂, ху, неосновные перемен­
ные Х4, Х₅, Xf>. f<\^y *к

т.е. Z_min =45— при оптимальном решении Х₅ =(5~; 39; 1; 0;

0; 0).

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

шеи нецелочисленное значение в оптимальном решении (5~),

составляем второе дополнительное ограничение (8.6):

8.3. Понятие о методе ветвей и границ

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

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

Пусть задача 1 (задача (8.1)—(8.3) максимизации линейной функции Z (без учета целочисленности переменных) решена сим­плексным методом и известны нижняя и верхняя границы для каждой целочисленной переменной Xj\ Vj ^ Xj < Wj (J = 1, 2, ...,

л), а также нижняя граница линейной функции Zq, т.е. при лю­бом плане X Z(X)> Z₀. Предположим для определенности, что

только первая компонента х[ оптимального плана X* задачи 1 не удовлетворяет условию целочисленности. Тогда из области допус­тимых решений задачи 1 исключается область: [х\] < х\ < [х[] + 1,

где [х{] — целая часть числа х,*. В результате из задачи 1 форми­руют две задачи: 2 и 3, отличающиеся друг от друга тем, что в задаче 2 кроме ограничений (8.2) задачи 1 добавлено ограничение V! < х\ < [х\]1щ а в задаче 3 кроме тех же ограничений (8.2) до­бавлено ограничение [xj*] + 1<Xj* < Wj. Получим список из двух

задач: 2 и 3.

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

Если в результате решения одной из задач 2 или 3 получен не­целочисленный оптимальный план, для которого Z(X*) < Z₀, то

данная задача исключается из списка. Если Z{X*) > Z₀, то из данной задачи формируются новые две задачи.

Если полученное решение X* удовлетворяет условию целочис­ленности и Z(Jf*)>Z₀, то значение 2Ь исправляется и за вели-

чину Zq принимается оптимум линейной функции полученного оптимального целочисленного плана.

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

Проиллюстрируем метод ветвей и границ на примере. 8.3. Решить задачу

Z = 3*! +Х₂ -> ^тах

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

Х[, xi — целые числа.

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. 2о = Z (0; 0) = 0.

I этап. Решая задачу симплексным методом, получим 2^ = 13"? при Х\ = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х\ дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х\, т.е. 4 < х\ < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Zq — 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом.

Получим, что условия задачи 3 противоречивы.

ПЬзэтап. Решаем задачу 2 симплексным методом. Получим

Z_mj4*j при X; = [4;|;0;|;0; ^). Хотя Z(X\) = 4| > Z₀ = 0,

по-прежнему сохраняется Zq — 0, ибо план Хз нецелочислен­ный. Так как х*₂ — дробное число, из области решений ис­ключаем полосу 0 < Х2 < 1 и задачу 2 разбиваем на две задачи

4 и 5.

Список задач: 4 и 5. Значение 2q = 0.

IV этап. Решаем задачу 4 симплексным методом.

Получим Z_max = 12 при Х\ = (4; 0; 2; 2; 0*/0). Задачу исключа­ем из списка, но при этом меняем Zq, Z₀ = Z{X\) - 12, ибо план Х\ целочисленный.

V этап. Решаем задачу 5 симплексным методом. ' ^ !
Получим Z_max = 12,25 при Х'₅= (3,75; 1; 0; 0,25; 0,25; \ $. Zq

не меняется, т.е. Zq = 12, ибо план Х*_ь нецелочисленный. Так как х\ — дробное, из области решений исключаем полосу 3<jq<4, и задача 5 разбивается на две задачи: 6 и 7.

Список задач: 6 и 7. Значение Zq = 12.

VI этап. Решаем одну из задач списка, например задачу 7,
симплексным методом.

Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплексным методом. Получим
2^ах = 10,5 «при Х\ = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как

Z{X\) = 10,5 < Z_Q = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным

решением исходной задачи будет X = ЛГ₄ = (4; 0; 2; 2; 0; 0), а

оптимум линейной функции 2^_ах = 12>

Замечание 1.Нетрудно видеть, что каждая последующая за­дача, составляемая з процессе применения метода ветвей и границ, отличается от предыдущей лишь одним неравенством — ограничением. Поэтому при решении каждой последующей

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