Транспортная задача. Метод потенциалов.

Введение
1. Общая постановка транспортной задачи
2. Построение математической модели
3. Методы решения транспортной задачи
3.1 Методы построения первоначального плана перевозок
3.1.1 Построение первоначального Т-плана методом северо-западного угла
3.1.2. Построение первоначального Т-плана методом наименьшей стоимости
3.2. Методы отыскания оптимального решения
3.2.1. Метод потенциалов
3.2.2. Распределительный метод
Заключение
Литература

Транспортная задача. Метод потенциалов.

1
4
6
2
В
(130)
1
4
6
2
130
130
С
170
5
8
12
7
С
170
5
8
12
7
- Выделим клетку (1,2), так как ей соответствует наименьшая удельная стоимость из числа оставшихся. Внесем в нее объем поставки х12 = minа1,b2= min80,120=80. Таким образом, со склада А вывезли весь груз (1-ю строку вычеркиваем), а потребности 2-го потребителя сократились на 80 усл.ед. (Табл.12)
- На данном этапе наименьшая удельная стоимость соответствует клетке (3,4). Следовательно х34 = minа3,b4= min170,50=50. Это означает, что запросы пункта д удовлетворены полностью (столбец №4 вычеркиваем), а запасы груза на складе С уменьшились на 50 усл.ед. (Табл.13).
- Выделим клетку (3;2) с наименьшей из числа оставшихся удельной стоимостью и х32 = minа3,b2= min120,40=40. Потребности пункта б удовлетворены полностью – вычеркиваем 2-й столбец таблицы. Объем груза на складе С уменьшается на 40 усл.ед., т.е. b2= 120-40=80 (Табл.14).
- Осталась одна свободная клетка (3;3) - выделим ее. Впишем в нее величину поставки х33 = minа3,b3= min80,80=80. Получили, что со склада С вывезли весь оставшийся груз, и потребности пункта с полностью выполнены (Табл. 15).
Таблица 12 Таблица 13
а
б
с
д
а
б
с
д
(150)
(120)
80
50
(150)
(120)
80
(50)
+0
40
+0
40
+0
А
(100)
3
5
7
11
А
(100)
3
5
7
11
20
80
20
80
В
(130)
1
4
6
2
В
(130)
1
4
6
2
130
130
С
170
5
8
12
7
С
(170)
120
5
8
12
7
50
Таблица 14 Таблица 15
а
б
с
д
а
б
с
д
(150)
(120)
80
(50)
(150)
(120)
(80)
(50)
+0
+0
+0
+0
+0
+0
+0
А
(100)
3
5
7
11
А
(100)
3
5
7
11
20
80
20
80
В
(130)
1
4
6
2
В
(130)
1
4
6
2
130
130
С
(170)
80
5
8
12
7
С
(170)
5
8
12
7
40
50
40
80
50
Построенный первоначальный план перевозок проверим на возможные ошибки:
1 строка: 100=20+80; 2 строка: 130=130; 3 строка: 170= 40+80+50.
1 столбец: 150=20+130; 2 столбец: 120=80+40; 3 столбец: 80=80; 4 столбец: 50=50.
Таким образом проверка показала, что первоначальный план перевозок построен верно. Дадим экономическую интерпретацию полученных результатов:
1). В пункт а перевезли 20 и 130 усл.ед груза со складов А и В соответственно; в пункт б – 80 и 40 усл.ед. груза со складов А и С соотв.; в пункт с – 80 усл.ед груза со склада С и в пункт д – 50 усл.ед груза со склада С.
2). Суммарные затраты при этом будут равны L=3*20+1*130+5*80+8*40+12*80+7*50=2220 (ден.ед.).
Построенный первоначальный Т-план необходимо проверить на оптимальность.
3.2. Методы отыскания оптимального решения
После построения первоначального плана перевозок необходимо проверить его на оптимальность и при необходимости найти оптимальное решение.
При решении транспортной задачи выделяют два метода отыскания оптимального решения:
1. Метод потенциалов. Суть этого метода состоит в предварительном нахождении потенциалов поставщиков и получателей, и в последующем вычислении алгебраической суммы тарифов для каждой пустой клетки с помощью потен­циалов.
2. Распределительный метод. Суть этого метода состоит в построении цикла для каждой пустой клетки и вычислении алгебраической суммы тарифов для каждого цикла.
3.2.1. Метод потенциалов
Содержание метода:
1) Каждому поставщику поставим в соответствие действительное число – потенциал строки ui. Каждому потребителю – потенциал столбца vj . Числа ui и vj расчитывают по формуле:

ui + vj = сij
Где сij – удельная стоимость в выделенной клетке с адресом (i,j) построенной Т-таблицы. Причем один из потенциалов можно задать произвольно. Как правило u1=0.
2) Найдем оценку ∆ ij для каждой невыделенной клетки по формуле:
∆ ij = сij – (ui + vj),
где ui , vj – найденные потенциалы, сij – удельная стоимость перевозок в невыделенной клетке (i,j).
Если оценка каждой невыделенной клетки не отрицательная, т.е. ∆ ij  0, то найденный Т-план является оптимальным. В противном случае построенный план перевозок не гарантирует минимальных затрат на перевозку груза и необходимо перейти к улучшенному Т-плану.
3). Для построения нового Т-плана, отвечающему меньшим суммарным затратам на перевозку груза, выполним следующие действия:
Определим какой из невыделенных клеток соответствует наименшая оценка. Предположим это клетка с адресом (l,k). Отметим ее знаком +. Клетка (l,k) – первая выделенная клетка нового Т-плана.
Двигаясь от клетки (l,k) по тому же столбцу отмечаем знаком (-) выделенную клетку, затем отмечаем знаком (+) выделенную клетку, стоящую в той же строке, что и предыдущая. В столбце, в котором находится последняя отмеченная клетка, отметим выделенную клетку знаком (-) и так далее до получения замкнутого контура.
Сравним величину поставок (хi j) в каждой выделенной клетке со знаком (-). Пусть -величина наименьшей поставки. Исключим соответствующую ей клетку из числа базисных. В клетке (l,k), отмеченной знаком (+), положим xl,k =. Во всех остальных базисных клетках со знаком (+) увеличим величину поставок на , со знаком (-) - уменьшим на . Получили улучшенный Т-план.
4). Необходимо проверить на оптимальность новый Т-план перевозок груза. Для этого вернемся к пункту 1) схемы метода и далее выполним последовательно его шаги.
Замечание 6: замкнутый контур, полученный при построении улучшенного Т-плана, содержит четное число вершин, причем число клеток со знаком (+) совпадает с числом клеток со знаком (-).
Найдем оптимальный план перевозок для задачи (*). Для этого необходимо взять любой первоначальный Т-план из двух построенных выше. К примеру возьмем Т-план, построенный по методу наименьшей стоимости. Рассмотрим таблицу перевозок, полученную при этом (Табл.15).
1). Рассчитаем потенциалы строк и столбцов, используя удельные стоимости перевозок в выделенных клетках по формуле: ui + vj = сij.
Пусть u1=0, тогда v1= с11- u1=3-0=3; v2= с12- u1=5-0=5.
Так как v1=3, то u2= с21- v 1=1-3=-2.
Известно значение v 2= 5, значит u3= с32- v 2=8-5=3.
В свою очередь, зная значение потенциала 3-й строки, можно найти потенциал 3-го и 4-го столбцов: v3= с33- u3=12-3=9 и v4= с34- u3=7-3=4.
Заметим, что найденные потенциалы строк и столбцов удобно вносить в соответствующую данному шагу Т-таблицу (Табл.16)
2). Используя найденные потенциалы строк и столбцов оценим каждую из невыделенных клеток по формуле: ∆ ij = сij – (ui + vj).
13= с13–(u1 + v3)=7-(9+0)= -2<0; 14= с14–(u1 + v4)=11-(4+0)= 7>0;
22= с22 – (u2 + v2)=4-(5-2)= 1>0; 23= с23 – (u2 + v3)=6-(9-2)= -1<0;
24= с24 – (u2 + v4)=2-(4-2)=0; 31= с31 – (u3 + v1)=5-(3+3)= -1<0.
Так как не все значения ∆ ij  0, то можно сделать вывод, построенный Т-план не является оптимальным.
3). Построение нового Т-плана начнем с клетки (1;3), так как оценка этой клетки наименьшая. Отметим клетку (1;3) знаком (+) и выделим ее. Начнем движение от этой клетки по 3-у столбцу до выделенной клеткии (3;3), которую отметим знаком (-). Далее продолжим движение по 2 –й строке до выделенной клетки (3;2), отметим ее знаком (+). Последняя вершина замкнутого контура – клетка (1;2), ее отметим знаком (-). Получили контур, состоящий из четного числа вершин и содержащий равное число положительных и отрицательных вершин (Табл.16) сравним величины поставок в отрицательных вершинах контура.
Минимальный объем поставки, равный =80, соответствует двум отрицательным вершинам контура: (1;2) и (3;3). Удалим из числа выделенных клетку (3;3), так как ей соответствует наибольшая удельная стоимость. В остальных вершинах контура объемы перевозок распределятся следующим образом: х13==80, х32=40+=40+80=120, х12=80-=80+80=0. Получили новый Т-план. Внесем полученные изменения в таблицу 17. Убедимся в правильности расчетов:
А) 1 строка: 100=20+0+80; 2 строка: 130=130; 3 строка: 170=120+50; 1 столбец: 150=20+130; 2 столбец: 120=0+120;
3 столбец: 80=80; 4 столбец: 50=50.
Б) Каждый новый Т-план должен гарантировать уменшение затрат на перевозку груза. Предыдущий план перевозок требовал 2220 ден.ед. Новый Т-план:
L=3*20+5*0+7*80+1*130+8*120+7*50=1850
Таким образом, транспортные затраты уменьшились.
В) Полезно проверить сохранилось ли число выделенных клеток таблицы. В нашем случае их число не изменилось.
Выполнение пунктов проверки А),Б),В) показало, что новый Т-план построен верно. Проверим его на оптимальность. Для этого:
рассчитаем потенциалы строк и столбцов, внесем полученные величины в таблицу 17;
вычислим оценки невыделенных клеток таблицы
14=7>0; 22= 1>0; 23=1>0;24=0;31= -1<0; 33=1>0.
Поскольку среди вычисленных оценок есть отрицательная, то можно утверждать, что построенный Т-план не является оптимальным. Построение улучшенного Т-плана начнем с клетки (3;1), так как ей соответствует наименьшее значение ∆ ij.
Таблица 16 Таблица 17
L=2220
=80
а
б
с
д
ui
L=1850
=20
а
б
с
д
ui
150
120
80
50
150
120
80
50
А
100
3
5
7
11
А
100
3
5
7
11
20
-80
+
-20
+0
80
В
130
1
4
6
2
-2
В
130
1
4
6
2
-2
130
130
С
170
5
8
12
7
3
С
170
5
8
12
7
3
+40
-80
50
+
-120
50
vi
3
5
9
4
vi
3
5
7
4
4) Построим замкнутый контур, начиная с клетки (3;1). Отобразим его в таблице 17. Наименьшая величина поставки в отрицательных вершинах контура равная 20 соответствует клетке (1;1). Исключим ее из числа выделенных. При этом х12=0+=20, х32=120-=100 и х31==20. Внесем изменения в таблицу 18 (замечание: правильность построения Т-плана примем как факт, проверку упустим для краткости), в ней же отобразим значения потенциалов сторк и столбцов.
Рассчитаем оценки невыделенных клеток: 11=1>0; 14=7>0; 22=0; 23=0; 24=-1<0; 33=2>0. Полученный Т-план оптимальным не является.
Таблица 18 Таблица 19
L=1340
=50
а
б
с
д
ui
L=1990
а
б
с
д
ui
150
120
80
50
150
120
80
50
А
100
3
5
7
11
А
100
3
5
7
11
20
80
20
80
В
130
1
4
6
2
-1
В
130
1
4
6
2
-1
-130
+
80
50
С
170
5
8
12
7
3
С
170
5
8
12
7
3
+20
100
-50
70
100
vi
2
5
7
4
vi
2
5
7
3
5) Построение нового Т-плана начнем с клетки (2;4), так как ей соответствует наименьшая оценка. Построенный контур отразим в таблице 18. Сравним объемы поставок в отрицательных вершинах контура. Наименьшая величина поставки =50 находится в клетке (3;4). Это означает, что данную клетку необходимо исключить из числа выделенных, а в остальных вершинах контура объемы поставок распределятся следующим образом: х24==50, х31=20+=70 и х21=130-=80. Отобразим изменения в таблице 19 (замечание: правильность построения Т-плана примем как факт, проверку упустим для краткости).
Потенциалы строк и столбцов внесем в таблицу 19. Вычислим оценки невыделенных клеток таблицы: 11=1>0; 14=7>0; 22=0; 23=0; 32=2>0; 34=1>0. Согласно требованиям данного метода можно утверждать, что данный Т-план является оптимальным.
Сделаем выводы:
1. Оптимальный план заключается в перевозке груза в пункт а со складов В и С в объеме 80 и 70 усл.ед соответственно; в пункт б со складов А и С в объеме 20 и 100 усл.ед.; 80 усл.ед в пункт с со склада А и 50 усл.ед. в пункт д со склада В.
2. Транспортные издержки при этом будут равны L=5*20+7*80+1*80+2*50+5*70+8*100=1990 ден.ед.
3.2.2. Распределительный метод
Содержание метода:
1). Для каждой невыделенной клетки построим замкнутый контур следующим образом:
начиная с невыделенной клетки по кратчайшему пути обходятся выделенные клетки по горизонтальному или вертикальному направлению;
всем клеткам в строгом чередовании присваиваются знаки (+) или (-), причем первой присвивают знак (+) невыделенной клетке, с которой было начато построение контура.
2). Будем считать величину поставки и стоимость перевозки положительными, если клетка отмечена знаком (+) и отрицательными, если клетка отмечена знаком (-).
3). Вычислим алгебраическую сумму стоимостей перевозки с учетом знака клетки для каждого построенного контура - оценку клетки. Обозначим ее через δij , где (i,j)- невыделенная клетка, с которой было начато построение замкнутого контура.
4). Если все δij≥0, то построенный Т-план считают оптимальным. Остается вычислить затраты на перевозку груза. В противном случае – план перевозок не оптимальный и необходимо составить улучшенный Т-план (п.5).
5). Для построения улучшенного Т-плана выберем клетку (и соответствующий ей контур) с отрицательной оценкой, которой соответствует наименьшая удельная стоимость. Найдем в отрицательных вершинах этого контура минимальную по абсолютному значению величину поставки. Пусть это будет поставка xlk. Тогда:
клетку (l,k) исключим из числа выделенных и обнулим соответствующую ей величину поставки;
величину поставки в положительных клетках контура увеличим на xlk, а в отрицательных клетках – уменьшим на xlk.
6). Получили новый Т-план (он отличается от предыдущего одной выделенной клеткой). Необходимо проверить его на оптимальность (начать с п.1).
Замечание 7: замкнутый контур, полученный при построении улучшенного Т-плана, содержит четное число вершин, причем число клеток со знаком (+) совпадает с числом клеток со знаком (-).
Замечание 8: Во избежание арифметических ошибок после построения нового Т-плана необходимо проверить совпадает ли сумма поставок в стоке с объемом груза, имеющегося в наличии у соответствующего поставщика. Также сумма поставок в столбце должна совпадать с объемом поставки, необходимой соответствующему потребителю.
Найдем оптимальный план перевозок для задачи (*), используя распределительный метод. Для этого необходимо взять любой первоначальный Т-план из двух построенных ранее. К примеру возьмем Т-план, построенный по методу наименьшей стоимости. Рассмотрим таблицу перевозок, полученную при этом (Табл.15).
Таблица 15
а
б
с
д
150
120
80
50
А
100
3
5
7
11
20
80
В
130
1
4
6
2
130
С
170
5
8
12
7
40
80
50
1). Чтобы определить является ли найденный Т-план оптимальным рассчитаем оценки каждой невыделенной клетки. Для этого необходимо для каждой из них построить замкнутый контур (6 невыделенных клеток – 6 контуров).
Клетка (1,3): Клетка (1,4): Клетка (2,2):
с12=5
- (1,2)
с13=7
+ (1,3)
с12=5
- (1,2)
с14=4
+ (1,4)
с11=3
+ (1,1)
с14=5