Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

табл. 16.10.

После преобразования получаются табл.'16.11 и 16.12. Чтобы восстановить таблицу в стандартном виде, вычислим

аоо— «оо— 2 bs(p0-asl)‘i=

= 0 — 1 ( _ 3 • 1 )2 —3 - ( — 3 - О)2 — 2 • ( — 3 • О)2 = - 9 ,

в табл. 16.13— 16.18. Каждой таблице соответствует множество небазисных переменных. Линейное преобразование небазисных переменных (2) из § 16.3 обычно не сохраняет стандартного вида параболического ограничения. Поэтому требуется производить восстановление параболического ограничения в стандартном виде. В целях экономии места показаны только таблицы, соответ­ ствующие стандартному виду после каждой итерации.

16.6. Доказательство конечности

Существует два случая окончания работы алгоритма:

1)все элементы производящей строки, кроме а00, неотрица­

тельны;

2)таблица стала прямо допустимой.

В первом случае м ы имеем ограничение вида

«оо— «оьЧ — «огЗ’г— •■•— «ол^п — 2 bs(L s(х))2^0,

$

где а00< 0 , а0г > 0 (г= 1, ...,«).

Поскольку Xj ^ 0, левая часть ограничения отрицательна, и зада­

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

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

ГЛАВА 17

П Р Я М О Й А Л Г О Р И Т М Ц Е Л О Ч И С Л Е Н Н О Г О П Р О Г Р А М М И Р О В А ­

НИ Я х) (Р. Д. Ю Н Г )

17.1.Введение и алгоритм

Термин «прямой», примененный к алгоритму целочисленного, программирования, обозначает метод, который приводит к опти­ мальному решению посредством получения последовательно «улуч­ шаемых» решений. Каждое из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности 12). Одним из вероятных достоинств прямого алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наи­ лучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойствен­ ными алгоритмами, чтобы получать различные составные алго­ ритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.

Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в про­ цессе этого алгоритма получается последовательность двойственно' допустимых полностью целочисленных решений. Следует напом­ нить, что полностью целочисленный алгоритм Гомори представ­ ляет собой модификацию двойственного симплекс-метода. Основ­ ное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом,, равным (— 1). Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк

вдвойственном симплекс-методе. Использование такого отсечения

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

Оказывается, можно аналогично модифицировать симплексметод таким образом, чтобы получить алгоритм, который сохра­

няет прямую допустимость и целочисленность таблиц. Д л я описа-

1)Непосредственным источником для этой главы послужили работы Гловера [76] и Юнга [225]. Алгоритмы, приведенные в этой главе, более похожи на те, которые предлагал Гловер, а доказательство конечности ближе к работе Юнга.

2)Алгоритмы, описанные в гл. 13 и 14, следует классифицировать как двойственные, поскольку получаемые промежуточные решения не являются допустимыми решениями исходной задачи.