ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

§ 1. Транспортная задача

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

1.1. Постановка транспортной задачи заключается в следующем. Имеется пунктов производства («поставщиков»)

некоторого однородного продукта и пунктов его потребления. Для каждого пункта производства и для каждого пункта потребления заданы величины: объем производства в пункте производства объем потребления в пункте потребления затраты на перевозку единицы продукта от пункта производства до пункта потребления При этом чаще всего предполагается, что суммарное производство и суммарное потребление сбалансированы, т. е.

Требуется составить план перевозок: а) не выводящий за пределы производительности поставщиков,

б) полностью обеспечивающий всех потребителей и

в) дающий минимум суммарных затрат на перевозку. Введем переменные представляющие собой объемы перевозок от каждого поставщика до каждого потребителя Естественно, что

Очевидно, что требование а) отражается условием

а требование б) — условием

Наконец, суммарные затраты при этом равны

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

1.2. В явном виде требование целочисленности на переменные в задаче не наложено. Однако имеет место следующая важная теорема,

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

Теорема 1.1. При любых целых значениях транспортная задача всегда имеет целочисленный оптимальный план — независимо от коэффициентов линейной формы

Этот важный факт можно установить непосредственно, как следствие известных методов решения транспортной задачи. Здесь будет дан эскиз доказательства; для его проведения фактически нужно лишь осмыслить некоторые детали вычислительного процесса.

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

1°. Существует исходный опорный целочисленный план.

2°. При переходе от одного опорного плана к другому целочисленность сохраняется.

Действительно, из и 2° сразу следует целочисленность всех опорных планов транспортной задачи, а это как раз то, что нам и нужно.

Целочисленный опорный план, существование которого утверждается в предложении 1°, будет указан путем прямого построения. Процесс заключается в следующем: 1

1) Рассмотреть матрицу и найти Пусть этот минимум достигается в клетке

2) Положить в качестве первой базисной переменной

3) Если минимум в (1.6) есть то вычеркнуть строку и заменить на .

3") Если минимум в (1.6) есть то вычеркнуть столбец и заменить на .

3") Если то вычеркнуть либо строку либо столбец (но не оба одновременно).

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

Отметим, что если при применении правила сокращенная матрица будет иметь одну строку и несколько столбцов, то следует вычеркнуть столбец если же она имеет один столбец и несколько строк, то вычеркивается строка

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

Фактически здесь дано формальное описание метода минимального элемента для построения начального приближения в транспортной задаче. Легко видеть, что к тому же выводу можно было бы прийти, анализируя любой другой прием построения исходного плана (например, метод северо-западного угла).

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

(см. скан)

Как видим, значения переменных при этом изменяются на целое число Ввиду целочисленности предыдущего плана улучшенный план также будет целочисленным, Таким образом, установлено и предложение

Более подробное изложение этого вопроса можно найти, например, в монографии Данцига [66].

1.3. Установленная сейчас целочисленность планов транспортной задачи имеет место и для любых ее частных случаев. Важнейшими из них являются задача о назначениях (задача выбора), рассматриваемая в § 3 настоящей главы, и задача о потоке в сети. При всем большом самостоятельном значении теории потоков в сети эти вопросы лежат в стороне от предмета данной работы. Читателю, интересующемуся специально потоками в сетях, можно рекомендовать монографию Форда и Фалкерсона [75]. Отметим лишь, что целочисленность решений для задачи о назначениях и задачи о потоке можно не только вывести из соответствующего свойства транспортной задачи, но и доказать непосредственно.

1.4. Целочисленность планов транспортной задачи, в которой мы убедились при анализе хода ее решения, в действительности не связана с конкретными вычислительным методами, а имеет гораздо более глубокие причины. Дело в том, что если ограничения транспортной задачи (1.3), (1.4) записать в форме ограничений общей задачи линейного программирования (т. е. привести их к виду ), то получающаяся при этом матрица А будет иметь весьма специфическую структуру. Эта проблема имеет большой принципиальный интерес; ее полное рассмотрение будет пока отложено до гл. 17.