3. Построим первое опорное решение транспортной задачи методом минимальной стоимости (минимального тарифа).

bj ai	150	130	150	140
200	7 *	8 *	1 150	2 50
180	4 150	5 *	9 *	8 30
190	9 *	2 130	3 *	6 60

Найдем клетку с минимальным тарифом. Это клетка (1,3) с тарифом

c₁₃ =1. Построение исходного опорного плана начинаем с занесения поставки груза в клетку с наименьшей стоимостью c₁₃. Заполняем клетку x₁₃ = 150. Оставшиеся клетки третьего столбца заполняем точками, так как потребности третьего получателя полностью удовлетворены. У первого поставщика осталось 50 единиц груза. Ищем следующую клетку с минимальным тарифом. Таких клеток две: c₁₄ =2, c₃₂ =2. Заполним сначала клетку (3,2). Поставим в нее x₃₂=min (190, 130)=130. Второй столбец заполняем точками. У третьего поставщика осталось 60 единиц груза. Ищем следующую клетку с наименьшим тарифом – это клетка (1,4). В нее помещаем 50 единиц груза, min(50,140)=50. Первую строку заполняем точками, так как от первого поставщика вывезен весь груз. Четвертому получателю недопоставлено 90 единиц. Аналогичным образом распределяем весь имеющийся груз и получаем первый опорный план перевозок.

Подсчитаем затраты на перевозку по этому плану.

.

Итак, в каждой строке и в каждом столбце таблицы заполнена хотя бы одна клетка, циклов по заполненным клеткам нет, число заполненных клеток m+n-1=6, следовательно, план опорный и невырожденный.

4. Проверка первого опорного плана (решения) на оптимальность. Метод потенциалов

После построения исходного опорного плана приступаем к проверке его на оптимальность методом потенциалов, который заключается в последовательном улучшении опорных планов транспортной задачи на основе информации, полученной с помощью чисел, называемых потенциалы поставщиков и потребителей ( , - двойственные переменные, то есть переменные задачи, двойственной к транспортной). Потенциалы находим из условия , где c_ij - тарифы заполненных клеток. Будем проверять на оптимальность первый опорный план, построенный методом минимального тарифа. В двойственной задаче одна свободная переменная, поэтому возьмем одну любую из двойственных переменных и приравняем ее к нулю. Возьмем, например, (выгоднее брать в качестве нулевой переменной ту, которая соответствует строке или столбцу с наибольшим количеством заполненных клеток).

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

Из этой системы находим

bj ai	150	130	150	140
200	7 *	8 *	1 150	2 50	=2
180	4 150	5 *	9 *	8 30	=8
190	9 *	2 130	3 *	6 60	=6

Считаем оценки для свободных клеток:

Запишем получившиеся оценки в левом верхнем углу свободных клеток.

bj ai	150	130	150	140
200	9>0 7 *	10>0 8 *	1 150	2 50	=2
180	4 150	1>0 5 *	2>0 9 *	8 30	=8
190	7>0 9 *	2 130	-2<0 3 *	6 60	=6

Так как среди оценок имеются отрицательные , то данный план не является оптимальным. Его можно улучшить перераспределением поставок. Для этого выбираем свободную клетку с наименьшим отрицательным значением (наибольшим по абсолютной величине). В данном случае это клетка (3,3).

bj ai	150	130	150	140
200	7 *	8 *	1 150--	2 50+	=2
180	4 150	5 *	9 *	8 30	=8
190	9 *	2 130	3 * +	6 60--	=6

Сроим цикл пересчета, начиная с клетки (3,3), в которую нужно поместить поставку груза (её отмечают знаком «+»), и двигаясь по занятым клеткам (в данном случае это клетки (3,4), (1,4), (1,3)), поочередно отмечая их знаками «-», «+». Если в клетку (3,3) добавили + , то в смежных по циклу клетках необходимо вычесть для сохранения баланса перевозок по третьей строке и третьему столбцу. Звенья цикла должны быть параллельны строкам или столбцам таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое – в столбце. Количество вершин в цикле должно быть четно. В результате построения цикла в соответствующих строках и столбцах должно быть парное количество знаков «-», «+».

Определяем величину поставки в клетку (3,3), как минимальную величину из поставок, стоящих в отрицательных клетках, то есть . Перераспределяем по циклу поставки на величину . Значение записываем в незанятую клетку (3,3), отмеченную знаком «+», двигаясь по циклу, прибавляем эту величину к поставкам в клетках со знаком «+», вычитаем в клетках со знаком «-».

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

bj ai	150	130	150	140
200	7 *	8 *	1 90	2 110
180	4 150	5 *	9 *	8 30
190	9 *	2 130	3 60	6 *

Если освобождается больше одной клетки, то есть число заполненных клеток меньше числа m + n - 1, то такой план называется вырожденными, и для определения потенциалов необходимо ввести недостающее количество нулевых элементов в число основных базисных переменных. Свободные клетки заполняют нулевыми поставками так, чтобы они не образовывали цикл по заполненным клеткам, и чтобы в каждой строке и в каждом столбце находилась хотя бы одна заполненная клетка. Проверим новый опорный план на оптимальность. Пусть =0. Тогда найдем все остальные потенциалы, рассматривая только заполненные клетки и помня, что для них , то есть что сумма потенциалов должна быть равна тарифу, стоящему на пересечении соответствующих потенциалам строки и столбца.

bj ai	150	130	150	140
200	7 *	8 *	1 90	2 110	=0
180	4 150	5 *	9 *	8 30	=6
190	9 *	2 130	3 60	6 *	=2

Число заполненных клеток k=m+n-1, следовательно, план невырожденный. Найдем оценки для всех клеток с точками, где стоят свободные переменные. Данный опорный план не является оптимальным, так как не все оценки для свободных клеток , а именно, .

bj ai	150	130	150	140
200	9>0 7 *	8>0 8 *	1 90	2 110	=0
180	4 150	-1<0 5 *	2>0 9 *	8 30	=6
190	9>0 9 *	2 130	3 60	2>0 6 *	=2

Возьмем клетку (2,2) за начало цикла пересчета. Цикл будет проходить по клеткам (2,2), (3,2), (3,3), (1,3), (1,4), (2,4) и опять вернется в (2,2).

bj ai	150	130	150	140
200	9>0 7 *	8>0 8 *	1 90-	2 110++	=0
180	4 150	-1<0 5 * +	2>0 9 *	8 30-	=6
190	9>0 9 *	2 1 30-	3 60+	2>0 6 *	=2

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

bj ai	150	130	150	140
200	7 *	8 *	1 60	2 140
180	4 150	5 30	9 *	8 *
190	9 *	2 100	3 90	6 *

Проверяем данный опорный план на оптимальность

bj ai	150	130	150	140
200	8>0 7 *	8>0 8 *	1 60	2 140	=0
180	4 150	5 30	3>0 9 *	1>0 8 *	=5
190	8>0 9 *	2 100	3 90	2>0 6 *	=2

Полученный опорный план является оптимальным, так как все оценки для свободных клеток . Выписываем оптимальный план: x₁₁ = 0; x₁₂ = 0; x₁₃ = 60; x₁₄ =140; x₂₁ = 150; x₂₂ = 30; x₂₃ = 0; x₂₄ = 0; x₃₁ = 0; x₃₂ = 100; x₃₃ = 90; x₃₄ = 0. Или в матричной форме

Высчитываем минимальные затраты на транспортировку продукции: