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

Известно, что двойственные оценки в задаче линейного программирования могут быть истолкованы как измерители дефицитности ресурсов. Соответствующая математическая формулировка дана в § 1. Там же обсуждается постановка задачи в целочисленном случае и возникающие при этом трудности.

В § 2 излагается один результат Гомори и Баумоля [90], позволяющий использовать двойственные оценки для выявления недефицитных ресурсов в случае задачи целочисленного линейного программирования (дальнейшее продвижение по этому пути осуществили Алькали и Клеворик [46]).

§ 1. Постановка задачи и некоторые предварительные сведения

1.1. Рассмотрим задачу целочисленного линейного программирования.

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

при условиях

Числа считаем целыми.

Задача (1.1) — (1.4) может быть переписана в эквивалентной форме. Максимизировать

при условиях

В дальнейшем будем считать, что:

1) задача имеет решение

2) -задача (1-30) имеет решение. Из условий 1) и 2) следует, что оптимальный план может быть получен по первому алгоритму Гомори.

1.2. Если предположить, что

то задачу (1.1) — (1.4) можно интерпретировать следующим образом. Имеется видов продукции видов ресурсов, причем запасы ресурса ограничены заданной величиной Каждый из видов продукции может выпускаться только в неделимых единицах (условие целочисленности (1.4)). Известно, что производство единицы продукции дает единиц прибыли и связано с расходом а единиц ресурса. Ищется план производства, дающий максимальную прибыль.

1.3. Большой интерес представляет следующий вопрос.

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

Если воспользоваться экономической интерпретацией, данной в п. 1.2, то этот вопрос прозвучит следующим образом.

Как будет изменяться оптимальная величина прибыли при изменении запасов ресурсов?

Проблема оказывается достаточно сложной, и прежде чем переходить непосредственно к ее исследованию, вспомним, как влияет изменение величин на целевую функцию нецелочисленной задачи (1.1) — (1.3) (или, что то же самое — задачи (1.1) — (1.3)).

1.4. Пусть оптимальный план задачи

Сосредоточим свое внимание на величинах и соответствующих им номерах ресурсов

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

Если ресурс использован полностью, и можно предполагать, что увеличение

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

Ресурс в этом случае естественно назвать дефицитным.

Все эти интуитивные соображения могут быть формализованы. Пусть опорный оптимальный план, которому соответствуют:

1) множество индексов небазисных переменных

2) симплексная таблица

Имеет место следующая теорема

Теорема 1.1. Пусть задана (1.3) не вырождена.

Тогда при

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

Можно доказать также следующую теорему.

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

Тогда

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

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

Рис. 18.1.1.

Рассмотрим следующий пример.

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

при условиях

Как показывает рис. 18.1.1, оптимальное значение целевой функции задачи ((1.6) -(1.9)) следующим образом зависит от величины запасов второго ресурса:

Таким образом, из недефицитности ресурса (2) при малом увеличении его запаса еще не следует

недефицитность ресурса (2) при большем увеличении его запаса.

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

Тем не менее, как показали Гомори и Баумоль [90], двойственные оценки все же оказываются полезными и в целочисленном случае. Результат Гомори и Баумоля будет изложен в § 2.