Математическая модель задачи

• Ограничения:

• Граничные условия:

• Целевая функция:

Транспортная задача является задачей линейного программирования специального типа. В частности, коэффициенты в ограничениях принимают значения 0 или 1 и каждая переменная входит только в два ограничения.

Методы решения транспортной задачи

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

Алгоритм последовательного улучшения плана предусматривает два этапа решения задачи:

• определение исходного опорного решения;

• последовательное улучшение опорного решения и приближение к оптимальному плану.

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

Таблица 3. Поиск опорного решения

	Строительные объекты
Заводы		80	120	200	30
	100	2 80	3 20	4	1
	150	3	3 100	6 50	2
	180	3	2	4 150	5 30

Заполнение таблицы начинаем с клетки (1,1), которая находится в северо-западном углу таблицы, отсюда и название метода.

и первый столбец закрыт, потребности строительного объекта удовлетворены. Переходим к клетке (1,2).

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

, закрыт 2-й столбец, потребности строительного объекта удовлетворены. Переходим к третьему столбцу.

, закрыта вторая строка, мощности завода исчерпаны. Переходим к третьей строке.

, закрыт 3-й столбец, потребности строительного объекта удовлетворены. Переходим к четвертому столбцу.

, закрыты все строки и столбцы.

Получили опорное решение. Этому решению соответствуют затраты:

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

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

В рассматриваемом примере и Опорный план (таблица 3) имеет 6 заполненных клеток, т.е. выполняется условие и опорный план невырожденный.

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

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

Поставим задачу: как можно больше перевозить с минимальной стоимостью. Эта идея заложена в методе минимальной стоимости. В этом случае на каждом шаге заполняют клетку таблицы с наименьшей стоимостью доставки единицы продукции. При этом необходимо учитывать это обстоятельство для всех поставщиков. Расчет выполнен в таблицах 4-6.

Начинаем заполнение таблицы 4 с клетки (1,4), затем переходим к клетке (1,1), потом к клетке (2,1) и т.д., при этом каждый раз фиксируем остатки на заводах и объектах. В итоге такого распределения получим транспортные расходы:

Таблица 4. Вариант 1 улучшенного плана

	Строительные объекты
Заводы		80	120	200	30	Остаток
	100	2 50	3	4 20	1 30	70, 20,0
	150	3 30	3 120	6	2	120, 0
	180	3	2	4 180	5	0
	Остаток	30, 0	0	20, 0	0

Таблица 5. Вариант 2 улучшенного плана

	Строительные объекты
Заводы		80	120	200	30	Остаток
	100	- 2 70- =50	3	+ 4	1 30	70, 0
	150	+ 3 10+ =30	3 120	- 6 20- =0	2	140, 20 0
	180	3	2	4 180	5	0
	Остаток	10, 0	0	20, 0	0

Таблица 6. Вариант 3 улучшенного плана

	Строительные объекты
Заводы		80	120	200	30	Остаток
	100	2	3	4 70	1 30	70, 0
	150	3 80	3 70	6	2	70, 0
	180	3	2 50	4 130	5	130, 0
	Остаток	0	50, 0	130, 0	0

Планы, полученные в таблицах 4-6 допустимы, невырождены и ацикличны. Как видим, расходы уменьшаются, но нет уверенности в том, что полученные планы оптимальны.

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