2. Сведение открытой транспортной задачи к закрытой

Решение транспортной задачи начинается с выяснения вопроса о том, является ли задача открытой или закрытой.

Если задача является открытой, то необходимо провести процедуру сведения задачи к закрытой (закрытие задачи).

С этой целью при a < b добавляется фиктивный поставщик с запасом груза , если же a > b , то добавляется фиктивный потребитель с заказом груза .

В обоих случаях соответствующие фиктивным объектам тарифы перевозок полагаются равными нулю. В результате суммарная стоимость перевозок не изменяется.

3. Первоначальный план перевозок

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

• составление первоначального плана перевозок;

• последовательные улучшения плана перевозок (перераспределение поставок) до тех пор, пока план перевозок не станет оптимальным.

Решение ОЗЛП начинается с нахождения опорного плана. Для транспортной задачи такой план всегда существует. Ниже описываются два метода составления опорного плана (первоначального плана перевозок). При этом ненулевые элементы плана перевозок будем записывать в соответствующие пустые клетки транспортной таблицы с исходными данными задачи, а символом (i, j) будем обозначать клетку таблицы, содержащую информацию о перевозках груза от поставщика к потребителю .

3.1.Составление первоначального плана перевозок с помощью метода северо-западного угла

Составление первоначального плана перевозок начинается с перевозки запасов поставщика (находящегося в «северо-западном» угле таблицы). Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя , затем и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика не окажется меньше заказа очередного потребителя. Для выполнения этого последнего (по строке) заказа используем остатки запаса поставщика , а недостающую часть добавим из запасов поставщика , то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика , затем и так далее.

Теорема. Решение, построенное по методу северо-западного угла является опорным.

Проиллюстрируем алгоритм метода северо-западного угла на следующем примере.

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

Таблица.

		100			40			80			60
				4			8			10			5
	160		100			40			20
				4			6			2			3
	30								30
				4			4			6			5
	90								30			60

Распределяя запасы поставщика сначала потребителю , а затем , получаем: = 100 , =40. После этого у поставщика остается еще 20 единиц груза, а потребителю нужно 80 единиц. Удовлетворим спрос потребителя , отправив ему 20 единиц груза, оставшихся у поставщика , 30 единиц груза от поставщика и 30 единиц груза от поставщика . Следовательно, = 20 , = 30 и = 30, причем у поставщика остается 60 единиц груза. Этот груз отправим потребителю . Таким образом = 60 , все запасы груза вывезены и все потребители удовлетворены.

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

z = 4 ×100 + 8 × 40 +10 × 20 + 2 ×30 + 6 ×30 + 5 × 60 = 1460 .

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