МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

3. ЦЕЛОЧИСЛЕННЫЕ И ДИСКРЕТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Задача о назначениях. Имеется п видов различных работ и п кандидатов для их выполнения. Предполагается, что каждый кандидат назначается на один и только один вид роботы. Обозначим Судоход, получаемый при назначении г-го кандидата на j-й вид работы. Необходимо распределить кандидатов на работутак, чтобы суммарный доход от произведенных назначений был максимальным.

Положим

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

1, если г-й кандидат назначен на j-ю работу; О     в противном случае.

п

п

1=1 j=l

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

п

п

1=1

3=1

(xij = 0   либо   Xij = 1).

47

Задача о ранце. Имеются различные предметы те наименований. Путешественник, собираясь в поход, должен упаковать некоторые из них в ранец. Ранец имеет тег ограничений по весу, объему, линейным размерам и т. п. Пусть (щ — г-я характеристика (г = 1,2,... ,т) предмета j-ro наименования (j = 1,2,... ,п); Ь, — ограничения по весу, объему, линейным размерам и т. д. Пусть Xj — количество предметов j-ro наименования, запланированных к загрузке в ранец, a Cj — полезность одного предмета j-ro наименования. Тогда математическая постановка задачи приобретает следующий вид: максимизировать

п

і=і

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

п

OijXj <bi,      і = 1,2,..., тег;

і=і

х. > о — целое,      j = 1,2,...,те.

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

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

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

Пусть по j-му маршруту за сезон перевозится человек. Перевозку пассажиров по этому маршруту можно осуществлять тег различными типами судов. Для каждого г-го типа судов (г = 1,2,..., тег) известны следующие характеристики:

1) cl°P — грузоподъемность (количество мест);

2) а^> — численность обслуживающего персонала;

48

3) а  — расход горючего за сезон;

4) су — прибыль за сезон от использования г-го судна по j-му маршруту.

Необходимо выбрать парк судов для каждого маршрута, при котором максимизируется прибыль пароходства при соблюдении ограничений: общий расход горючего за сезон не может превышать Ьз единиц, а общая численность обслуживающего персонала — Ь2 человек.

Теперь приведем формальное определение задачи целочисленного программирования (в стандартной форме): найти вектор х = = (х\,..., хп), минимизирующий линейную функцию

п

F(x) = J2C3X3 3=1

и удовлетворяющий системе ограничений

п

Х/'<.» •''./'    ''і     г' = l,2,...,m;

3=1

Xj > 0,      Xj — целое,   j = 1,2,..., те.

Приведенная формулировка отличается от обычной ЗЛП лишь условием целочисленности, которое накладывается на переменные X. Это требование приводит к таким специфическим особенностям, что иногда эту задачу относят к нелинейному программированию.

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

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

Часто при первом ознакомлении с целочисленной ЗЛП возникает естественное желание решить эту задачу без учета целочисленности X, а затем округлить результат до ближайшего целого. Но такой

49

непосредственный подход может увести далеко от действительного оптимума.

Пример 1. В задаче

х\ — 3^2 + Зжз —¥ max, 2xi +  Х2 —  жз < 4, І.гі — З.г-2 < 2,

— З.Г|   + 2X2 +    ■>';■    < 3.

Жу > 0;   Жу — целое; j = 1,2,3.

Решением является точка ж* = (2; 2; 5), а без требования целочис-ленности решение ЗЛП имеет вид х* = (1/2; 0; 9/2). Очевидно, никакие варианты округления решения вспомогательной ЗЛП не дают даже допустимого решения исходной задачи целочисленного линейного программирования.

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

Х2П

Но если в обычной ЗЛП перейти от допустимой области D к области £>ц, решение такой задачи будет целочисленным.

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

50

Методы отсечения

Идея методов отсечения состоит в следующем. Решается ЗЛП, полученная из целочисленной задачи отбрасыванием условия целочис-ленности. Если решение вспомогательной ЗЛП целочисленное, то оно же является и решением исходной задачи. Если оптимальное решение вспомогательной задачи не целочисленное, то к решенной ЗЛП добавляют новое линейное ограничение; оно удовлетворяет целочисленным решениям исходной целочисленной задачи, но не удовлетворяет полученному нецелочисленному решению первоначальной ЗЛП. Указанное дополнительное линейное ограничение определяет некоторую отсекающую плоскость и называется правильным отсечением. Новые правильные отсечения добавляют к первоначальной вспомогательной ЗЛП до тех пор, пока на некотором шаге не будет получено целочисленное решение вспомогательной задачи, являющееся, очевидно, оптимальным решением исходной задачи целочисленного линейного программирования.

Одним из методов отсечения является метод Гомори.

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

п

CjXj —^ max,

i=i

а\\Х\ + аі2Ж2 + ---+ alnxn = bi, (3-1)

«ml^l ™Ь «m2<^2 ""Ь ' ' ' ""Ь 0>шпХп   — Ьш,

где X = (хі, Х2, ■ ■ ■, хп) — целочисленный вектор.

Наряду с ней рассматривается вспомогательная ЗЛП

п

CjXj —^ max,

i=i

ацХі + аі2Х2 + ••• + alnxn = b\,

(3.2)

Х1,Х2,---,Хп>0,

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

51

сти вектора X. Задача (3.2) решается симплекс-методом. Пусть на последней итерации ограничения этой задачи приняли вид

хл + ■■■ + а1:Ю+1хт+1 + ■■■ + а1пхп = А, х2 + ■■■ + a2,m,+ixm+1 + ■■■ + а2пхп = &,

Хщ ™Ь Q°m:m-\-lXm-\-l ""Ь ' ' ' ™Ь CkmnXn   — ßmКак известно, оптимальным решением задачи (3.2) будет вектор х* = (А) • • • j /5г»; 0;.. •,0). Пусть существует номер і такой, что ßi — нецелое (в противном случае целочисленный вектор х* является оптимальным решением и задачи (3.1)).

Обозначим, как обычно, [z] и {z} соответственно целую и дробную части числа z. Заметим, что если /3, — нецелое число, то {ßi} ф 0.

Согласно общей идее метода отсечения необходимо перейти к решению новой вспомогательной ЗЛП, у которой наряду с исходными ограничениями рассматривается дополнительное ограничение, осуществляющее правильное отсечение. Рассмотрим ограничение

п

{ßi} ^ °> (3-3)

j=m+l

которое соответствует /3, такому, что {ßi} ф 0. Имеет место следующее утверждение.

Теорема. Дополнительное линейное ограничение (3.3) является правильным отсечением для задачи целочисленного линейного программирования (3.1).

Пример 2. Решить целочисленную ЗЛП

—Жі + х2 — 2.г:» —¥ min, х\ +        5жз = 4, х2 + 5жз = 1, Xj > 0;   Xj — целое; j = 1,2,3.

Решаем вспомогательную ЗЛП, полученную из исходной отбрасыванием условия целочисленности Xj, j = 1,2,3. Вычисления выполняем в виде симплекс-таблицы.

52

 

 

 

 

 

Базис

Ао

-1

1

-2

в

п/п

сбаз

At

А2

А3

0

-1 1

Х-2

4 1

1 0

0

1

5

@

4/5 1/5

 

 

А

 

0

0

-2

 

1

-1 2

XI Х'і

3

1/5

1 0

-1

1/5

0 1

 

 

 

А

 

0

2/5

0

 

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

Х\ —    Ж2 = 3,

1 1

По второму ограничению строим правильное отсечение, определяемое соотношением (3.3), а именно:

^ — \х2 < 0   или   ж2 > 15 5

Строим новую вспомогательную ЗЛП, добавляя ограничение Хч > 1. Чтобы ограничение "канонизировать", используем дополнительную, переменную Х4_. Получаем задачу

— Жі +    Х2 — 2ж3 Х\ — Ж2 1

-ж2 + х3 5

—     Ж2 + Ж4

Так как последняя компонента в векторе свободных членов является отрицательной, полученную ЗЛП решаем двойственным симплекс-методом. Вычисления выполняем в виде симплекс-таблицы.

—^ mm

= 3, 1

" 5' = 1.

53

Л» п/п

сбаз

Базис

Ао

At

А2

Аі

a4

 

-1

XI

3

1

 

-1

 

0

0

0

2

Х'і

1/5

0

 

1/5

 

1

0

 

0

Ха

-1

0

 

-1

 

0

1

 

 

А

 

0

2/5

0

0

 

-1

XI

4

1

 

0

 

0

-1

1

2

Х'і

0

0

 

0

 

1

1/5

 

1

Х-2

1

0

 

1

 

0

-1

 

 

 

 

 

 

 

 

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

Вычисления в двойственном симплекс-методе заканчиваются после того, как в столбце свободных членов Aq не остается отрицательных элементов.

Таким образом, на первом шаге двойственного симплекс-метода получено оптимальное целочисленное решение х* = (4; 1; 0; 0) вспомогательной ЗЛП, следовательно, решением целочисленной задачи будет х* = (4;1;0).

Заметим, что в практических вычислениях сходимость этого метода очень медленная; реализация приведенного алгоритма с повышением размерности затрудняется.

Метод ветвей и границ

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

Идея метода такова. Вычисляется нижняя (для задачи минимизации) оценка целевой функции F(x) на допустимом множестве решений D (причем способ вычисления границы для каждой конкретной задачи решается особо).

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

54

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

Проверяется оптимальность вновь полученных решений. Для этого используется очевидный признак оптимальности, суть которого в следующем. Пусть D состоит из объединения подмножеств Dk'1, I = 1,г, а хк'1 — оптимальное решение ЗЛП на соответствующем подмножестве Dk'1. Если при этом

F{xk>v) = z(Dh<v) < z(DK'1), l=hr,

то решение xk,v оптимальное. (При решении задачи максимизации знак последнего неравенства меняется на противоположный.)

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

Рассматривается частично целочисленная ЗЛП: минимизировать

п

Р(Ж) = 5>А. (3.4)

i=i

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

п

Y^aijXj < bi,      і = l,m, (3.5)

i=i

Xj — целые; j = щ < n; 0 < Xj < dj; j = l,n. (3.6)

Некоторые из чисел dj могут равняться +оо. Предполагается, что многогранное множество, заданное этими ограничениями, ограничено.

Как и при решении подобных задач методами отсечения, рассматриваем вспомогательную ЗЛП, полученную из исходной отбрасыванием условия целочисленности. Пусть х° = (х®,... ,ж°) — оптимальное решение указанной вспомогательной ЗЛП. Если вектор х удовлетворяет условию целочисленности, он является оптимальным решением исходной задачи. В противном случае величина z(D°) = = F(xq) дает нижнюю оценку целевой функции F(x) на множестве D, заданном ограничениями (3.5) и (3.6) (D° = D).

Пусть некоторая координата вектора х° не является целочисленной. В этом случае проводим ветвление множества D0 на подмножества D1'1 и D1'2, добавляя к исходным ограничениям, задающим D0,

55

ограничения соответственно Xj < [ж°] и Xj > [ж°] + 1, где [•] — целая часть числа. Затем решаем новые вспомогательные ЗЛП, соответствующие подмножествам D1'1 и D1'2, и вычисляем оценки F(x) на этих множествах и т. д.

При дальнейшем ветвлении естественно выбрать множество Dk'v с наименьшей оценкой целевой функции. Процесс продолжается до тех пор, пока не будет получено оптимальное решение, удовлетворяющее условию целочисленности. Не исключено, что ветвления придется проводить до тех пор, пока все решения ЗЛП (если они допустимы) не будут удовлетворять условию целочисленности. В этом случае выбирают решение, которому соответствует минимальное значение Fix'1'1').

Заметим, что для полностью целочисленной ЗЛП в случае, когда коэффициенты Cj (j = 1,п) целевой функции F(x) целые, оценка z может быть заменена на более сильную оценку

z=]F(xk'v)[,

ГдЄ j . [ — наименьшее целое число, не меньшее и (]и[= min те; те —

п>и

целое). Например, ]1,5[= 2; ] —1,5[= —1. Пример 3. Решить задачу

F(x) = —xi — 3*2 -* min

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

Х\ + 4x2 < 14, 2.Г, + Зж2 < 12, Х\ > 0; Х2 > 0; Xi,X2 — целые.

Обозначим D область, заданную ограничениями задачи.

1. Решаем вспомогательную ЗЛП (без условия целочисленности переменных Х\ и 12):

F(x) = —xi — 3*2 -* min, xi + 4x2 < 14,

1

2.гі + Зж2 < 12, Xi > 0;   Х2 > 0.

56

X-2      I 1

Решение задачи (1) имеет вид

х° = (6/5; 16/5);      F(x°) = -54/5.

Проводим ветвление множества D°: D° = D = D1,1 U D1/

D1'1 = {х: X Є D°, X! < [6/5] + 1}; D1'2 = {х: X Є D°, X! > [6/5] + 1 + 2}.

Вычисляем границу z(D°) = F(x°):

F(x°) =} -54/5[=] -10 -4/5[= -10.

2. Решаем вспомогательные ЗЛП:

F(x) = —xi — 3*2 -* min,      ж Є D1'1;

Р(ж) = — x\ — 3*2 -* min,      x Є Г*1'2. Решения задач (2) и (3) имеют вид соответственно

ж1'1 = (1,13/4); Fix1'1) = -43/4;

ж1'2 = (2,8/3); Р(ж1'2) = -10,

значит,

z (D1*1) =]-43/4[= -10; z (D1'2) =]-10[= -10.

Проводим ветвление множества D1'1: D1'1 = D2'1 U D2'2, где

D2'1 = {х: ж Є D1'1, х2 < [13/4] = 3}; D2'2 = {х: же D1'1, х2 > [13/4] + 1=4}.

Полагаем D2'3 = D1'2.

Решаем вспомогательные ЗЛП:

F(x) = —xi — З.г-j —¥ min,      X Є D2'1;

F(x) = —Xi — З.г-j —)min,      ж Є Г*2'2. Решение задачи (4) имеет вид ж2'1 = (1;3); F(x2'r) = —10.

58

Задача (5) решения не имеет, поскольку множество D2'2 пустое.

Полагаем z(D2>v) =] —10[= —10; z(D2'2) = +00. Анализируя решение ЗЛП, связанных с областями D2'1, D2'2 и D2'3, и используя признак оптимальности F(x2,1) < z(D2'1), I = 1,3, заключаем, что оптимальное решение исходной целочисленной задачи имеет вид

ж* = (1;3);       F(x*) = -10.

Схематически решение выглядит так.

1.

ж Є D°, х° = (6/5; 16/5) F(x°) = -54/5; z(F) = -10

2.

3.

ж Є D1'1, ж1'1

(і; 13/4)

Fix1'1) = -43/4; z(F) = -10

ж Є D1'2, ж1'2 = (2; 8/3)

Fix1

-10; z(F) = -10

X Є £>2'3, D2'3 = D1'2, X2,3 = (2; 8/3) F(x2>3) = -10, z(F) = -10

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

59

 

 ...  6



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх