308 |
14. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ |
14.2.Пример
Пусть требуется найти максимум
х0 = |
—1 0 ^! — 14х2 — 2 1 ж3 |
при условиях |
|
|
|
2xj —{- |
2х2 4~ 7х3 ^ |
14, |
8xi + |
11х 2 + |
9х 3>>12, |
9х^-{- 6х2 |
Зх3 |
Ю, |
Xi х2, х3> 0 (целые).
Задачу можно свести в табл. 14.2, где первый столбец лексико графически минимален и все элементы производящей строки — отрицательны.
|
Таблица 14.2 |
|
|
|
|
1 |
-X , |
— X » |
- * з |
|
|
х 0 |
1 |
10 |
14 |
21 |
|
|
Xi |
0 |
- 1 |
0 |
0 |
|
|
х2 |
0 |
0 |
—1 |
-0 |
|
|
*3 |
0 |
0 |
0 |
—1 |
|
|
хк |
- 1 4 |
—2 |
—2 |
—7 |
■Производящая строка |
Хь |
- 1 2 |
- 8 |
- И |
- 9 |
|
|
Хв |
—10 —9 |
—6 |
—3 |
|
|
«1 |
—4 |
—1* —1 |
—2 |
X — 7/2 |
|
р1 == 1 , 1 0 <-J-4- , |
^ = [ ж ] |
Юг 21_ |
1 |
|
|
Ра |
йз |
2.
х’ = ц = - г -
?i,= max^2 , 2 , у ) = -|- .
Отсечение * = [ — £ ] - [ н г ] |
Р Й |
[ н г ] *3’ |
Sj = —4 Xj + х2 4- 2х3 ^ 0.
Полученное отсечение записывается внизу табл. 14.2. Шаги итераций приводят к табл. 14.3, 14.4, 14.5 и 14.6. Оптимальное решение получается в табл. 14.6: х0 — —52, xt = 1, хг = О,
Г Л А В А 1 5
СМЕШАННЫЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
15.1.Введение (Гомори [81J)
Вэтой главе будут изучены такие задачи целочисленного программирования, в которых требование целочисленности рас пространяется не на все переменные, а только на некоторое под множество из них. Будут обсуждены два типа методов решения таких задач; первый излагается по работе Гомрри [81], второй —
по работе Вендерса [18].
Первый алгоритм в основном совпадает с алгоритмом, изло женным в гл. 13.
Ша г 1. Начать с оптимальной таблицы непрерывной задачи линейного программирования.
Ша г 2. Выбрать производящую строку.
Ша г 3. Составить по производящей строке отсечение и при
писать |
его |
внизу таблицы. |
Полученная |
строка |
используется |
в качестве производящей. |
|
|
|
|
|
Ш а г |
4. |
Провести |
итерацию двойственного симплекс-метода |
и вернуться к шагу 2 . |
|
|
|
|
|
Единственное отличие предлагаемого алгоритма от описанного |
в гл. 13 |
состоит в получении отсечения из производящей строки. |
Пусть |
требуется |
найти максимум |
|
|
|
|
|
|
X q |
H qq |
|
CIq ^ X i |
^ 02 ^2 |
• • • |
^0 п ^ п |
( 1 ) |
при условиях |
|
|
|
|
|
|
|
|
|
|
%n-И. — |
^ п - И , |
0 |
&п+1, |
1%1 |
• • * |
&п-И, п |
|
|
|
|
|
|
|
|
|
|
|
|
( 2) |
|
|
% п-1-т —■& п + т , О |
Q -n+ m t 1^1 |
• • • |
Яп + т , п % п ^ |
0) |
X j > 0 (; = 1 , . . . . /г).
Некоторые переменные xj должны быть целочисленными. Будем решать данную задачу как задачу линейного программирования, используя двойственный симплекс-метод. Если в таблице aoj ^ 0
0 = 1 , . . ., п), ai0 ^ 0 0 = 1 , . . ., п + т) и все переменные,
на которые наложено требование целочисленности, имеют целые значения, то, очевидно, получено оптимальное решение поставлен ной задачи. Поэтому предположим, что на переменную xt нало жено требование целочисленности, и ai0 ^ 0 — нецелое. Пере пишем соответствующее уравнение, опуская индекс строки:
Поскольку х должно быть целым, х == 0 (mod 1). По предполо жению а0 — нецелое, а0 = / 0 (mod 1). Отсюда любое целочислен ное оптимальное решение задачи (2 ) должно удовлетворять усло
вию
2 aixi = /о (modi). |
(4) |
1 |
|
Пусть коэффициенты левой части сравнения (4) разбиты на два множества / + = {/ | ^ 0} и /" = {/ | а;- < 0}. Тогда
2 ®А’+ |
2 a i x i == /о (mod 1), |
(5) |
5EJ+ |
i£J- |
|
где 0 < /о < 1.
Левая часть сравнения (5) является либо положительной, либо отрицательной. Если она положительна,' то принимает значения / 0, 1 + / 0, и т. д. Тогда
2 a i x i > |
2 a i x i + 2 «Я4'>/о• |
(6) |
i£J+ |
i£J- |
|
Если левая часть сравнения (5) отрицательна, то ее значениями
должны |
быть —1 + |
/о, —2 + |
/ 0 и т. д. Имеем |
|
|
2 |
2 ajX)+ |
2 a j X j ^ — 1 + fo. |
(7) |
|
5£J- |
i £ J + |
j £ J ~ |
|
|
Умножив |
обе части неравенства (7) на |
> получим |
|
|
|
2 Т ^ Т аА > / о - |
|
(8) |
|
|
j £ J ~ |
|
|
|
Таким образом, имеет место либо неравенство (6 ), либо неравен
ство (8 ). |
Поскольку левые |
части неравенств |
(6) и (8 ) неотрица |
тельны и |
одна из них больше или равна / 0, |
то |
|
|
2 a i x i + |
2 T ^ u a j X ^ f ° |
- |
(9) |
|
•j £ J + |
j £ J ~ |
|
|
Любое целочисленное решение должно удовлетворять нера венству (9). Текущее решение ему не удовлетворяет, поскольку,
312 |
ГЛ. 15. СМЕШАННЫЙ АЛГОРИТМ |
подставив Xj = 0, получим в левой части неравенства (9) нуль. Следует заметить, что при получении неравенства (9) использо валось лишь условие целочисленности х в левой части (3) и неотри цательности Xj в правой части уравнения (3). Таким образом, получение ограничения (9) не зависит от того, было ли наложено ограничение целочисленности на переменную Xj. Вводя неотрица тельную слабую переменную s, можно переписать неравенство (9) в виде уравнения
( 10)
j£J+
которое записывается внизу таблицы, после чего таблица пере стает быть прямо допустимой. Затем проводится итерация двой ственного симплекс-метода с использованием строки (1 0 ) в каче
стве ведущей. Если на некоторые Xj в левой части неравенства (9) наложено требование целочисленности, то этим фактом можно воспользоваться для того, чтобы усилить неравенство (9), т. е.
мы хотим сделать коэффициенты a,] (j £ / +) и у з у (/ 6 J~)
насколько возможно малыми. Поскольку неравенство (9) полу чено из соотношения (4), рассмотрим в этом соотношении член акхк, где на xk наложено требование целочисленности. Очевидно, увеличение или уменьшение ak на целое число не нарушит Спра ведливости соотношения (4). Минимальным допустимым числом,
полученным из ап ^ 0 (к £ / +), является f k. |
А для ak < |
0 вели |
чиной, дающей наименьшее значение |
а |
будет |
fh — 1 . |
Поэтому было бы желательно увеличивать или уменьшать в соот ношении (5) ак на целое число таким образом, чтобы получать минимальное значение коэффициентов в неравенстве (9), т. е. найти минимум из
( Заметим, что функция g(y) |
возрастает с ростом у при |
! /< ! • ) Очевидно, что |
|
/ь (1 —/ о Х / о ( 1 —к ), |
если / ь < / 0, |
или, что равносильно, |
|
|
если / h< /o , |
и |
|
/ ь > 7 = 7 ^ 1 —^ ’ если /* > /о-
