Задачи транспортного типа

Постановка задачи. Пусть имеется пунктов производства и пунктов потребления однородного продукта. Объем производства в пункте производства равен ; объем потребления в пункте потребления равен (i = 1, 2,..., m; j = 1, 2,..., n).

Предполагается, что производство и потребление сбалансированы, т.е.

.

Задана матрица транспортных расходов: затраты на перевозку единицы продукции из пункта производства в пункт потребления .

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

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

при ограничениях

Транспортная задача ‑ это задача линейного программирования, число переменных которой равно , число ограничений равно . Ранг матрицы транспортной задачи не превосходит . Известно, что условие сбалансированности производства и потребления является необходимым и достаточным условием разрешимости транспортной задачи.

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

Целочисленность базисных решений транспортной задачи не связана с конкретным вычислительным алгоритмом, а является следствием теоремы 3.1.

Переформулируем эту теорему применительно к транспортной задаче.

Теорема 3.2. Каждая перевозка любого базисного решения транспортной задачи является линейной комбинацией чисел с коэффициентами 0, .

Доказательство этой теоремы основано на следующей лемме.

Лемма. Любой минор матрицы условий транспортной задачи равен 0 или .

Другими словами, матрица условий транспортной задачи – унимодулярна.