3.2. Методы построения исходного плана.

Для решения исходные данные транспортной задачи (4) сводятся в таблицу (табл. 3.1). Из условия (3.2) следует, что любое ограничение транспортной задачи является линейной комбинацией остальных. Следовательно, система ограничений транспортной задачи линейно зависима и содержит только m + n - 1 независимых уравнений. Поэтому исходный допустимый невырожденный базисный план должен иметь m + n - 1 базисную переменную и его легко можно получить непосредственно из данных таблицы. Все остальные переменные - небазисные и их значения равны нулю. Условимся эти нули в таблице не отражать, то есть клетку, соответствующую небазисной переменной, оставлять незаполненной.

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

3.2.1 Метод северо-западного угла

Определение значений начинается с левой верхней клетки таблицы (это соответствует северо-западному углу на географической карте). Находим значениеиз соотношения:

(3.16)

Возможны три варианта:

1) если , то, строкаi = 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя (столбец j = 1) уменьшается на величину ;

2) если , то, столбецj = 1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика (строкаi = 1) уменьшается на величину ;

3) если , то, строкаi = 1 и столбец j = 1 исключаются из дальнейшего рассмотрения. Данный вариант приводит к вырождению исходного плана.

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

После завершения описанного процесса необходимо произвести проверку полученного плана на вырожденность. Если количество заполненных клеток равно m + n - 1, то план является невырожденным, в противном случае – вырожденным.

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

3.2.2. Метод минимального элемента

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

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

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

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

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

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

Пример 3.1. Определим исходный базисный план методом северо-западного угла для транспортной задачи, исходные данные которой сведены в табл. 3.2, и отразим его в табл. 3.3.

Таблица 3.2

	10		8		7
11		8		6		5
14		4		5		7

Таблица 3.3

	10		7 8		7
111	10	8	1	6		5
714		4	7	5	7	7

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

2. , строка 1 исключается из дальнейшего рассмотрения, а потребность второго потребителя (столбец 2) уменьшается на 1 и становится равной 7 единицам.

3. , столбец 2 исключается из дальнейшего рассмотрения, а наличие груза у второго поставщика (строка 2) уменьшается на 7 единиц и становится равным 7 единицам.

4. Поскольку в таблице осталась одна строка (строка 2) и один столбец (столбец 3) - это последний шаг процесса, .

Количество заполненных клеток в табл. 3 равно 4, m + n – 1 = 2 + 3 – 1 = 4. Следовательно, полученный план невырожденный. Значения базисных переменных: . Остальные переменные - небазисные и их значения равны нулю. Транспортные расходы.

Пример 3.2. Теперь для той же задачи (табл. 3.2) определим исходный базисный план методом минимального элемента и отразим его в табл. 3.4.

Таблица 3.4

	10		4 8		7
411		8	4	6	7	5
414	10	4	4	5		7

1. Переменной соответствует клетка с минимальной стоимостью перевозки,. Столбец 1 исключается из дальнейшего рассмотрения, а наличие груза у второго поставщика (строка 2) уменьшается на 10 единиц.

2. В оставшейся части таблицы переменным исоответствуют клетки с минимальными стоимостями перевозок,. Выбираем первую по порядку клетку,. Столбец 3 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика (строка 1) уменьшается на 7 единиц.

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

4. Поскольку в таблице осталась одна строка (строка 1) и один столбец (столбец 2) - это последний шаг процесса, .

Количество заполненных клеток в табл. 4 равно 4, m + n – 1 = 2 + 3 – 1 = 4. Следовательно, полученный план невырожденный. Значения базисных переменных: . Остальные переменные – небазисные и их значения равны нулю. Транспортные расходы.

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