Теорема о разрешимости транспортной задачи

Рассмотрим сбалансированную транспортную задачу.

найти минимальное значение линейной функции

; (4.1)

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

= , I = 1, …, m; (4.2)

(4.3)

x_ij ³ 0, i = 1, …, m; j = 1, …, n. (4.4)

. (4.5)

Транспортная задача имеет n + m уравнений с mn неизвестными.

Определение 4.1. Матрицу Х = (х_ij)_{m, n}, удовлетворяющую условиям (4.2) – (4.4), называют планом перевозок транспортной задачи (х_ij - перевозками).

Определение 4.2. План Х*, при котором целевая функция (4.1) обращается в минимум, называется оптимальным.

Теорема 4.1. Для разрешимости транспортной задачи необходимо и достаточно выполнение условия баланса (4.5):

.

Доказательство:

1.Необходимость

Пусть ТЗ - разрешима;

а) Суммируем ограничения «4.2» по i:

б) Суммируем ограничения «4.3» по j:

Т.к левые части выражений а) и б) равны, то равны и правые части,

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

2. Достаточность. Пусть выполнено условие (4.5), т.е.

Построим матрицу Х = (х_ij)_{m, n}, где

(4.6)

Подставляя (4.6) в (4.2)получаем:

Аналогично подставляя (4.6) в (4.3), получим

Кроме того очевидно, что , следовательно матрица X является планом ТЗ, т.е. множество планов ТЗ не пусто.

Для установления разрешимости ТЗ осталось показать, что линейная функция (4.1) ограничена снизу на множестве планов ТЗ. Условия (4.2)-(4.3). обеспечивают выполнение неравенств

Следовательно, для любого плана Х линейная функция (4.1) ограничена снизу на множестве планов ТЗ.

Достаточность условий теоремы можно было доказать по-другому, т.к. множество планов ТЗ – ограниченное множество и, следовательно, любая непрерывная функция достигает своей нижней грани.

Опорный план ТЗ. Алгоритмы нахождения исходного плана.

4.4.1. Определения опорного плана ТЗ.

Определение 4.3. План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов где - векторы при переменных в матрице системы ограничений (4.2.)-(4.3.)

Теорема 4.2. Существует план, содержащий не более (m + n – 1) положительных перевозок, при этом система векторов , соответствующая таким перевозкам (х_ij > 0), линейно независима.

В силу (4.5) система (4.2)-(4.3) содержит не более чем (m + n – 1) независимых уравнений, т.е. ранг системы меньше или равен (m + n – 1). В матрице ограничений (4.2)-(4.3) не трудно обнаружить квадратную матрицу порядка (m + n – 1), с определителем не равным нулю, следовательно ранг системы уравнений равен (m + n – 1).

Таким образом, опорный план транспортной задачи содержит (m + n – 1) положительных перевозок. Если положительных перевозок в плане меньше чем (m + n – 1), то он называется вырожденным.

Дадим другое определение опорного плана.

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

4.4.2. Методы составления первоначальных опорных планов

Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода:

1 шаг. Полагают верхний левый элемент матрицы Х

х₁₁ = min (a₁, b₁).

Возможны три случая:

а) если a₁ < b₁, то х₁₁ = a₁ и всю первую строку, начиная со второго элемента, заполняют прочерками, полагают b₁ : = b₁- a₁

б) если a₁ > b₁, то х₁₁ = b₁, а все оставшиеся элементы первого столбца заполняют прочерками, полагают a_{1 :} = a₁ - b₁

в) если a₁ = b₁, то х₁₁ = a₁ = b₁, а все оставшиеся элементы первых столбца или строки заполняют прочерками, полагают либо a₁ =0, если столбец заполнен прочерками, либо b₁ =0, если строка заполнена прочерками.

Затем проделывают первый шаг с оставшейся незаполненной частью матрицы Х.