Решение открытой транспортной задачи (стр. 3 из 5)

Пусть известен потенциал U_i; тогда из равенства ( 5 ) следует

V_j = C_ij - U_i .

Если известен потенциал V_j , то из того же равенства имеем

U_i = C_ij - V_j .

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

Набором называется произвольная совокупность перевозок транспортной таблицы.

Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.

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

1.5.Критерий оптимальности базисного решения транспортной задачи

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

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

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

Один из наиболее простых методов решения транспортной задачи – распределительный метод.

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

и вычислено значение целевой функции на этом решении Z( ). По теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину = , можно получить новое опорное решение Х₂.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции

равно разности двух сумм: = , где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком

«-».

В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции Z(

), а в клетках, отмеченных знаком «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е.

<0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z( ) на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками , для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие =0. (11)

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку

. Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину = . В результате получится новое опорное решение.

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

, так как решается задача на нахождение минимума.

2.Разработка и описание алгоритма решения задачи

2.1. Содержательная постановка задачи

Составить экономико-математическую модель задачи. Найти оптимальное распределение поставок и минимальные затраты на перевозку. Первоначальное распределение поставок выполнить методом северо-западного угла.

Таблица№2

Поставщики	Потребители			Запасы груза
А1	5	7	6	50
А2	6	6	5	40
А3	8	4	5	20
Потребность в грузе	18	21	33

2.2.Построение математической модели задачи

Метод Северо-западного угла.

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка ("северо-западный угол") оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки переменного

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

Таблица №3

Поставщики	Потребители				Запасы груза
А1	5 18	7 21	6 11	0	50
А2	6	6	5 22	0 18	40
А3	8	4	5	0 20	20
Потребители В грузе	18	21	33	38