§ 3. Алгоритм Дальтона и Ллевелина

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

3.1. Частично дискретная задача линейного программирования формулируется следующим образом.

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

при условиях

Здесь и

К условиям (3.2), если это необходимо, добавлены неравенства

так что всякий план X задачи заведомо удовлетворяет условию

3.2. Теорема 3.1. Пусть оптимальный опорный план задачи и

— соответствующая симплексная таблица,

Тогда неравенство

или, что то же самое,

является правильным отсечением. Здесь

3.3. Доказательство теоремы 3.1. Сначала проверим условие отсечения. Действительно,

так что условие отсечения выполняется.

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

Возможны два случая:

Прежде чем разбирать эти случаи, введем некоторые обозначения:

так что

Из определения множеств и неотрицательности переменных следует, что

Разберем случай 1) (3.12). Из (3.12) и (3.14) следует:

откуда, учитывая (3.15), получаем

или, что то же самое,

Переходим к случаю 2) (3.13). Из (3.13) и (3.14) следует

откуда, учитывая (3.16), получаем

Заметим, что в силу (3.15) к (3.16) в обоих случаях имеют место неравенства

Объединяя в случае 1) (3.17) и (3.20), а в случае 2) (3.18) и (3.19), получаем, что в обоих случаях должно

выполняться неравенство

Последнее неравенство можно переписать в следующем виде:

Теорема 3.1 доказана.

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

где числа вычисляются по формулам (3.9) и (3.10) при

3.5. Конечность алгоритма Дальтона и Ллевелина доказывается так же, как и конечность первого алгоритма Гомори. При этом должны соблюдаться условия, аналогичные условиям 1) и 2) из § 3 гл. 5.

1) Целевая функция удовлетворяет условию дискретности. Это учитывается при выборе строки для построения правильного отсечения.

2) Выполнено по крайней мере одно из двух условий: 2) целевая функция ограничена снизу на многограннике

2) задача С) имеет по крайней мере один план.

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

3.7. Следует отметить, что от частично дискретной задачи линейного программирования всегда можно перейти к частично целочисленной задаче линейного программирования с булевыми переменными, вводя новые переменные

Однако количество переменных может при этом существенно возрасти.

3.8. Приведем численный пример: Максимизировать

при условиях

или, что то же самое, Максимизировать

при условиях

Решение примера приведено в табл. 1—8. Оптимальный расширенный план

(см. скан)

(см. скан)