Определить начальное решение  транспортной задачи, используя правило  «северо-западного угла».

1) Заполним транспортную таблицу.

№	1	2	3	4	Предложение
1	90^3	200^4	^5	^6	110
2	^7	130^5	10^8	^1	140
3	^9	^2	150^3	40^4	190
Спрос	90	150	160	40

Решение:

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

2) Остаток сырья в первом пункте составляет: 110-90=20 у.е. Двигаемся по первой строке вправо . Предложение поставщика исчерпано, первая строка вычеркивается.

3) Второму потребителю не хватает 150-20=130 у.е. Двигаемся по второму столбцу вниз . Второй столбец вычеркивается.

4) Двигаемся по второй строке вправо . Вторая строка вычеркивается.

5) Двигаемся по третьему столбцу вниз . Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо . Спрос третьего потребителя удовлетворен.

6) Двигаемся по третьей строке вправо .

 Таблица заполнена. Начальный план перевозок имеет вид:

Стоимость перевозок по этому плану составляет

 Использование данного правила - наиболее простой способ  нахождения начального решения транспортной задачи. План перевозок, полученный этим способом  обычно бывает далек от оптимального. Это происходит потому, что при его построении никак не учитываются значения тарифов с _ij.   В связи с этим на практике для получения исходного плана используется другой способ – метод «минимального элемента», в котором при распределении объемов перевозок в первую очередь заполняются клетки с наименьшими тарифами.

 

 

Построение начального решения транспортной задачи

Методом  «минимального элемента»

Алгоритм.

1. Составляют транспортную таблицу.

2. Выбирают клетку таблицы, которой соответствует минимальное значение тарифа. Если клеток с одним и тем же минимальным тарифом несколько - выбирают любое из них.

3. В выбранную клетку аналогично правилу  «северо-западного» угла помещают максимально возможное количество единиц продукции, разрешенное ограничениями на спрос и предложение. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку; если удовлетворен спрос - соответствующий столбец.

4. Если все клетки заполнены или вычеркнуты, то план перевозок построен.   В противном случае, переходят к шагу 2 без учета заполненных и вычеркнутых клеток.

Пример.

Найдем начальное решение предыдущего примера методом «минимального элемента».

№	1	2	3	4	Предложение
1	90^3	^4	20^5	^6	110
2	^7	^5	100 ^8	40^1	140
3	^9	150^2	40   ^3	^4	190
Спрос	90	150	160	40

 

Минимальный тариф   Спрос 4-го потребителя удовлетворен – соответственно 4-ый столбец вычеркиваем.

 Минимальный тариф для оставшихся клеток   Спрос 2-го потребителя удовлетворен – 2-ой столбец вычеркиваем.

Для оставшихся клеток минимальный тариф:

  Спрос 1-го потребителя удовлетворен - вычеркиваем 1-ый столбец.

Для оставшихся клеток минимальный тариф:

Предложение 3-его поставщика исчерпано – вычеркиваем 3-ю строку.

Следующий минимальный тариф для оставшихся клеток: ,  Предложение 1-го поставщика исчерпано – вычеркиваем 1-ую строку.

Для последней оставшейся клетки:

.

План перевозок, полученный по методу минимального элемента, имеет вид:

Стоимость перевозок по этому плану составляет

 у.е.

 Видим, что стоимость перевозок, полученных по методу минимального элемента, меньше стоимости перевозок, полученных  с использованием правила  «северо – западного угла» на 60 у.е. План, полученный данным методом более близок к оптимальному.