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

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

.

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

Теорема 3. Любой опорный план имеет не более

положительных компонент.

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

Действительно, исходная система содержит всего ограничений типа равенств:

, то есть m ограничений;

то есть n ограничений.

Однако в силу соотношения одно из этих ограничений является следствием всех остальных. Действительно, сложим все первые m ограничений

(1)

а из второй группы сложим первые n 1 ограничение

(2)

Вычитая теперь (2) из (1), получим:

,

и мы получили последнее, n-ое ограничение второй группы.

Таким образом, независимых ограничений всего не более . Поэтому

каждый опорный план имеет не более

компонент.

Следствие. Оптимальный план содержит не более, чем перевозку.

4.3. Методы определения первоначального опорного плана

4.3.1. Построение исходного опорного плана (метод северо-западного угла)

Для начала решения транспортной задачи необходимо иметь какой-то исходный опорный план, то есть оказаться в какой-то вершине допустимой области. Приведем конструктивный прием построения такого опорного плана, получивший название "метод северо-западного угла".

Итак, пусть имеется m складов с запасами

и n пунктов

потребления с потребностями .

Пусть запасы и потребности

сбалансированы, то есть .

Представим это в виде таблицы,

			...

где в столбце справа указаны запасы, в строке снизу  потребности, а пустые клетки оставлены для будущего плана перевозок.

Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла". Вместо впишем число . Возможны два варианта.

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

Ну, а потребность в первом пункте потребления останется в объеме . Наша таблица примет вид:

	0	0	...	0	0
			...

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

 

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

Ну, а в первом складе еще останется запасов продукта. Наша таблица примет вид:

0
0
0
0			...

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

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

У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не

более

компонент.

Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше , то он называется вырожденным.

Рассмотрим два примера. С целью экономии места, вся таблица не переписывается, а лишь приписываются последние строки и столбцы.