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

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

Обозначим x_ij -количество груза, перевозимого из пункта А_i в пункт В_j. Тогда математическая модель закрытой транспортной задачи имеет вид

Оптимальным решением является матрица Хmxn, удовлетворяющая системе ограничений и доставляющая минимум целевой функции L(X).

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

· Нахождение исходного опорного решения

· Проверка этого решения на оптимальность

· Переход от одного опорного решения к другому

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

Для нахождения исходного опорного плана часто применяется метод минимального тарифа.

 

Решение транспортной задачи рассмотрим на примере.

Пример 1.

Исходные данные.

На складах А₁, А₂, А₃ имеются запасы продукции в количествах 90, 400, 110 т. соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в количествах 140, 300, 160 т. соответственно. Расходы по перевозке 1 т. (тарифы) продукции заданы матрицей С (в у.е.)

С=

Данная транспортная задача является закрытой, так сумма запасов равна сумме потребностей.

Найдем исходное опорное решение

Представим задачу в табличной форме

Исходные данные Табл.1

 

Потребности   bj
Запасы, аi

 

Исходное опорное решение найдем по методу минимального тарифа. Решение снова представим в табличной форме.

 

Исходное опорное решение Табл. 2

 

Потребности   bj
Запасы, аi

 

Число занятых клеток в таблице 2 равно 5, m+n-1=3+3-1 =5, условие не вырожденности задачи выполнено, исходный опорный план, матрица Х , стоимость перевозок при этом плане равна

 

L(X_опт1) = 90*2+50*3+300*1+100*5+60*8 = 1610 усл. ед.

 

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

Будем применять метод потенциалов, согласно которому опорное решение является оптимальным, если ему соответствуют m+n действительных чисел u_i и v_j называемых потенциалами. Для занятых клеток u_i + v_j = c_ij, для свободных клеток u_i + v_j - c_ij ≤ 0

Одному из потенциалов дается произвольное значение, например, 0. тогда остальные потенциалы определяются однозначно. Если известен u_i, то v_j = c_ij - u_i и наоборот, u_i = c_ij - v_j.

В методе потенциалов также вычисляют оценки свободных клеток

. Если все , то опорное решение является оптимальным.

Продолжим рассмотрение примера 1. Проверим исходный опорный план на оптимальность. Положим u₁ =0. Тогда v₁ = c_1,1 – u₁ = 2-0 =2.

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

Последовательность пересчетов следующая:

Клетка (3,1). u₃ +v₁ =c_3,1 = 3; u₃ =c_3,1 - v₁= 3 – 2 =1; u₃ =1

Клетка (3,3) u₃ +v₃ =c_3,3 =8 v₃ =8 - u₃ =8 -1 = 7; v₃ =7

Клетка (2,3) u₂ = 5 - v₃ = 5-7 =-2 u₂ =- 2

Клетка (2,2) v₂ = 1 - u₂ = 1 –(-2) =3 v₂ =3

Данные заносим в таблицу потенциалов 3.

Таблица потенциалов 3

Потребности bj				ui
Запасы, аi
					-2
vj

 

 

Вычислим оценки свободных клеток

Так как , план не оптимален, необходимо одну из базовых переменных заменить на одну из свободных переменных

Для этого строится цикл для , все вершины которого, кроме одной, находятся в занятых клетках, клетках рассмотренного выше опорного плана.

Вершины с координатами таблицы 3 (1,1), (1,3), (3,1), (3,3) являются вершинами цикла Свободная клетка отмечается знаком +, остальные поочередно отмечаются знаками (-) и (+)

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

Первоначальный цикл Новый цикл

 

	+		-
	-		+

	-		+
	+		-

 

 

Предыдущее опорное решение Новое опорное решение

Изменение стоимости перевозок

L(X_опт1) = 90*2+50*3+300*1+100*5+60*8 = 1610 усл. ед.

L(X_опт2) = 30*2+60*2+300*1+100*5+ 110*3 = 1610 усл. ед., целевая функция не уменьшилась, поиск решения продолжается.

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

L(X_опт) = 30*4+110*3+300*1+90*2+70*5 = 1280 усл. ден. ед.

Это – минимальные расходы по перевозке всех грузов от поставщика потребителю.