§ 2. Теорема Гомори и Баумоля

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

Здесь

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

Иначе говоря, нельзя ли для задачи получить некий аналог теорем 1.1 и 1.2, установленных выше для задачи

Очевидно, что перенос теорем 1.1 и 1.2 на задачу (с использованием оценок х) невозможен. Действительно, допустим, что для некоторого

Тогда

и, если следовать теоремам 1.1 и 1.2, то ресурс должен быть недефицитным. Но это, вообще говоря, неверно, — достаточно сослаться на пример (1.6) -(1.9), разобранный в § 1.

И все же, как показали Гомори и Баумоль [90], информация, полученная при решении задачи С) ((1.1) - (1-4)) по первому алгоритму Гомори, может быть использована для выявления недефицитных ресурсов.

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

Здесь номер строки, по которой строится правильное отсечение на большой итерации:

Заметим, что

Введем обозначение

и перепишем (2.3) следующим образом:

Пусть

Через обозначим некоторое фиксированное натуральное число, удовлетворяющее условию

Обозначим

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

Напомним, что симплексная таблица имеет вид

или, в развернутой записи,

Через обозначается таблица с приписанной снизу строкой

Каждая из таблиц может рассматриваться как форма записи некоторой задачи линейного программирования Здесь

т. е. каждая из задач эквивалентна исходной задаче

Через обозначим задачу, которая получается из при замене на

2.3. Введем величины которые непосредственно используются в формулировке результата Гомори и Баумоля.

Сначала зададим

Теперь воспользуемся тем фактом, что

и определим рекуррентно

Теорема 2.1. Пусть

Тогда

Теорема 2.1 дает достаточный признак недефицитности ресурса На примерах легко показать, что этот признак не является необходимым.

Заметим, что теорема 2.1 является некоторой модификацией результата Гомори и Баумоля [90]. Гомори и Баумоль вводят перераспределенные двойственные оценки к с помощью этого понятия формулируют свой результат:

Если перераспределенная двойственная оценка, соответствующая ресурсу равна 0, то ресурс является недефицитным.

Поскольку основную полезную информацию несет знак перераспределенной двойственной оценки, целесообразно соответствующим образом модифицировать изложение.

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

Здесь

наименьшее общее кратное знаменателей несократимых рациональных дробей

Замечание 2.1. То, что числа рациональны, непосредственно следует из целочисленности коэффициентов задачи (1.1) — (1.3), правил -метода и правил первого алгоритма Гомори.

Замечание 2.2. Из определения следует, что делится также на знаменатель каждой из несократимых рациональных дробей

Введем обозначения:

Из определения чисел следует, что целые, а из замечания 2.2, что также целые.

2.5. Переходим к доказательству теоремы 2.1.

Лемма 2.1. Пусть

Тогда

Доказательство леммы 2.1.

Отсюда, проводя те же рассуждения, что и при доказательстве теоремы 2.1 из гл. 5, получаем

Далее

т. е.

Из (2.19), (2.20), (2.21) получаем

Лемма 2.1 доказана.

2.6. Числа определим следующим образом;

Из определения множеств следует, что

Воспользуемся формулой (2.23) и рекуррентно введем числа

Лемма 2.2. Пусть Тогда числа обладают следующими свойствами:

Свойство 1) следует из определения чисел Свойство 5) получается непосредственно из (2.9) и (2.22). Докажем свойства 2), 3) и 4).

Сначала рассмотрим случай Согласно (2.17)

где целые.

Из (2.30) и (2.24) получаем

Далее

Вводя обозначение

получаем

где целое неотрицательное число.

С другой стороны

так что

Лемма 2.2 доказана при Допустим теперь, что лемма 2.2 доказана для и докажем ее для

По предположению индукции каждое из чисел делится на так что

где целое число.

Из (2.31), (2.32) и (2.33) получаем

Вводя обозначение

получаем

где

С другой стороны (см. 2.10)),

По предположению индукции

Отсюда получаем

Так как все члены суммы, стоящей в правой части последнего равенства, неотрицательны, то

Лемма 2.2 доказана.

2.7. Рассмотрим задачу линейного программирования и обозначим через множество индексов входящих в нее переменных

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

на следующие условия:

Очевидно, что

Лемма 2.3. Задачи обладают следующими свойствами:

Доказательство проведем по индукции. Сначала докажем лемму 2.3 при Из (2.41) сразу следует, что

и (2.42) доказано при

Для доказательства (2.43) (при ) понадобится лемма 2.1 при следующих условиях:

Применяя лемму 2.1, получаем: если

то

целое.

Из (2.24), (2.26) и (2.44) следует, что

Лемма 2.3 доказана при

Теперь допустим, что лемма 2.3 уже доказана при и докажем ее при

По предположению индукции лемма верна для задачи Следовательно, она верна и для задачи поскольку а таблица получается из таблицы после нескольких итераций -метода. Формула (2.42) доказана при

Доказательство же (2.43) при проводится совершенно аналогично доказательству (2.43) при с использованием лемм 2.1 и 2.2. В лемме 2.1 следует положить

Лемма 2.3 доказана.

2.8. Переходим непосредственно к доказательству теоремы 2.1.

При теорема 2.1 тривиально верна. В дальнейшем считаем, что

Выпишем условия задачи Максимизировать

при условиях

Заметим, что в силу -нормальности таблицы

Следовательно, из (2.45) и (2.47) получаем

Введем обозначения:

Из (2,22) и из -нормальности таблицы следует, что

т. е.

Если множество пусто, то из (2.49) и (2.48) получаем

Предположим, что множество не пусто. Согласно (2.13) и (2.49) имеем

По определению чисел

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

Из (2.51), (2.52), (2.53) получаем

С другой стороны, согласно лемме 2.2

так что

Подставляем (2.56) в (2.49):

т. е.

Из (2.57) и (2.48) вытекает, что

Итак, во всех случаях (см. (2.50) и (2.58))

Из (2.59) и (2.42) получаем

Очевидно, что вектор является планом задачи так что

т. е.

Объединяя (2.60) и (2.61), получаем

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

Отметим в заключение, что модифицированная теорема Гомори и Баумоля легко выводится как частный случай из следующей теоремы, полученной Ю. Ю. Финкельштейном.

Теорема 2.2. При любом имеет место оценка

где

ЛИТЕРАТУРА

(см. скан)

(см. скан)