ЧАСТЬ V. НЕКОТОРЫЕ ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ

В этом разделе книги излагаются некоторые вопросы дискретного программирования, представляющие теоретический интерес и не связанные непосредственно с вычислительными методами.

Глава 17 посвящена целочисленным многогранным множествам. В гл. 18 рассматривается вопрос о двойственных оценках в целочисленных задачах линейного программирования.

ГЛАВА 17. ЦЕЛОЧИСЛЕННЫЕ МНОГОГРАННЫЕ МНОЖЕСТВА

В этой главе исследуются целочисленные многогранные множества, т. е. многогранные множества, все опорные планы (вершины) которых целочисленны. Этот вопрос весьма важен, поскольку метод последовательного улучшения плана (прямой симплекс-метод), как и другие конечные методы линейного программирования, определяет именно опорный оптимальный план (если задача имеет решение). Поэтому, если все опорные планы некоторой задачи линейного программирования целочисленны, то обычный аппарат линейного программирования позволяет найти оптимальный (опорный) план, удовлетворяющий также и требованию целочисленности и являющийся, следовательно, также оптимальным планом соответствующей задачи целочисленного линейного программирования.

В § 1 излагается некоторое необходимое и достаточное условие целочисленности многогранников, данное Гофманом и Краскалом [97]. § 2 посвящен задачам транспортного типа (см. Хеллер и Томпкинс [95], а также Гофман и Краскал [97]); в частности, здесь показано, что все опорные планы обычной транспортной задачи целочисленны (что позволяет понять, почему при

целочисленных коэффициентах обычные методы решения транспортной задачи позволяют всегда получить оптимальный план, автоматически удовлетворяющий условию целочисленности — см. § 1 гл. 2).

§ 1. Условие целочисленности многогранных множеств

1.1. Напомним, что многогранное множество называется целочисленным, если все его вершины (опорные планы) целочисленны (т. е. все их компоненты — целые числа).

Рассмотрим многогранное множество

Естественно было бы поставить вопрос: каким условиям должны удовлетворять матрица

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

1.2. Гофман и Краскал [97] исследовали задачу в несколько ослабленной (но также весьма интересной) постановке. Задана фиксированная матрица все элементы которой — целые числа и ранг которой равен Каким условиям должна удовлетворять матрица чтобы при любом целочисленном векторе правых частей многогранное множество было целочисленным?

Ответ на этот вопрос дает следующая

Теорема 1.1. Пусть фиксированная матрица ранга все элементы которой —

целые числа. Для того чтобы многогранное множество было целочисленным, необходимо и достаточно, чтобы любой минор порядка матрицы А был равен либо 0, либо ±1.

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

1.3. Докажем достаточность. Каждый опорный план (вершина) многогранного множества однозначно определяется заданием индексов базисных переменных. При этом векторы условий должны быть линейно независимыми, минор а следовательно, по условию теоремы Небазисные переменные равны нулю, а базисные однозначно определяются из системы линейных уравнений

определитель которой равен Вычисляя из (1.3), получаем по правилу Крамера

Здесь столбцы матрицы По условию теоремы все элементы этой матрицы — целые числа, откуда и следует целочисленность Достаточность доказана.

1.4. Докажем необходимость. Требуется доказать, что если линейно независимы, то

Перенумерацией столбцов матрицы (и переменных можно заменить на так что достаточно (не нарушая общности) доказать,

что если линейно независимы, то

Итак, пусть линейно независимы. Рассмотрим систему линейных уравнений

Здесь достаточно большое натуральное число, символ Кронекера, т. е.

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

В силу предположения о линейной независимости система (1.5) имеет единственное решение следующего вида:

Так как достаточно велико, то

Отсюда получаем, что многогранник имеет вершину с базисными переменными вычисляемыми по формуле (1.8).

Разлагая определитель по столбцу и используя (1.8), (1.7), (1.6), получаем

Здесь алгебраическое дополнение элемента в матрице

По условию из целочисленности следует целочисленность , а так как целое, то в соответствии с (1.9)

Известно, что для матрицы обратной к матрице имеет место формула

Из (1.10) и (1.11) получаем, что все элементы матрицы целые числа.

Так как все элементы матрицы целые числа, то

Так как все элементы матрицы целые числа, то

С другой стороны, известно, что

Следовательно,

Необходимость доказана.

1.5. Из теоремы 1.1 непосредственно следует условие целочисленности многогранных множеств первоначально заданных системой неравенств

Здесь любое из отношений - целые числа.

Запишем условия (1.13) — (1.14) в канонической форме

Здесь это знак если есть отношение и знак если есть отношение

Применим теорему 1.1 к многогранникам Это возможно, поскольку ранг матрицы

равен Имеет место

Теорема 1.2. Пусть - фиксированная матрица, все элементы которой — целые числа. Для того чтобы многогранное множество было целочисленным при любом целочисленном необходимо и достаточно, чтобы любой минор матрицы А был равен либо 0, либо ±1.

Определение 1.1. Матрицу все миноры которой равны или ±1, назовем унимодулярной матрицей.

1.6. Докажем теорему 1.2. По теореме 1.1 целочисленность (а следовательно, и при любом целочисленном эквивалентна тому, что любой минор порядка матрицы А (1.15) равен или ±1.

Рассмотрим такой минор Он содержит столбцы матрицы и столбцы матрицы (см. (1.15)), содержащие ±1 в строках соответственно (остальные строки А имеют номера Разлагая последовательно по столбцам получаем

Следовательно, равенство нулю или ±1 произвольного минора порядка матрицы эквивалентно равенству или ±1 произвольного минора матрицы откуда и следует теорема 1.2.

1.7. Поясним на двух примерах смысл теоремы 1.2. Пример 1.1.

Здесь целочисленный вектор. Непосредственной проверкой убеждаемся, что матрица унимодулярная. Следовательно, по теореме 1.2 многогранник целочисленный при любом (целочисленном) 6, что здесь легко установить и непосредственно, рассмотрев следующие случаи.

а) Хотя бы одно из чисел отрицательно. Многогранник пуст.

б) состоит из одной вершины

в) содержит две вершины: и .

г) содержит три вершины:

д) содержит четыре вершины:

Пример 1.2.

Здесь целочисленный вектор.

Так как то матрица не унимодулярна. По теореме 1.2 существует такой (целочисленный) вектор что многогранник не является целочисленным. Действительно, при многогранник содержит три вершины:

(геометрическая иллюстрация этого примера приведена на рис. 17.1.1).

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

Рис. 17.1.1,

Рис. 17.1.2.

Действительно, при многогранник содержит три вершины: (0,0), (2,0) и (1,1) (геометрическая иллюстрация этого примера приведена на рис. 17.1.2).