ТОП 10:

Алгоритм расчета потенциалов



 

В данном алгоритме введен механизм пометок. Строка или столбец помечены знаком '+', если соответствующий потенциал найден, знаком '–' в противном случае.

В начале все строки и столбцы таблицы помечаем символом '–'

1 –ый шаг. u1:=0 , 1–ую строку помечаем символом '+' (это означает, что потенциал для данной строки найден ).

k ый шаг.

a) Для каждой строки i, помеченной символом '+', выполнить:

для каждого столбца j=1,2,3,...,n такого, что клетка (i, j) базисная и j – ый столбец помечен символом '–' vj :=ui+cij,столбец помечаем символом '+'.

b) Для каждого столбца j , помеченного символом '+', выполнить:

для каждой строки i=1,2,3,...,n такой, что клетка (i, j)базисная, и i–я строка помечена символом '–' ui:=vj–cij,строку помечаем символом '–'.

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

 

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

Для того, чтобы базисное решение xij, i=1,2,3,...,m, j=1,2,3,...,n,было оптимальным, необходимо и достаточно, чтобы для всех i=1,2,3,...,m, j=1,2,3,...,n было справедливо неравенство dij=vj–ui–cij£0. Таким образом, для проверки найденного решения на оптимальность достаточно выполнить следующий алгоритм

1. Для всех i=1,2,3,...,m, j=1,2,3,...,n положить dij=vj–ui–cij.

2. Найти такие (k, p), что d kp =max{ dij| i=1,2,3,...,n, j=1,2,3,...,m }

3. Если dkp£0, то полученное базисное решение является оптимальным и транспортная задача решена, иначе необходимо перейти к новому базису.

Алгоритм перехода к новому базису.

Вводим в базис клетку (k, p). Для определения клетки (q, l), выводимой из базиса, воспользуемся следующим алгоритмом:

1. Строим последовательность клеток

П={(i1, j1), (i2, j2),...(i, j),... )}такую, что

a) (k,pП;

b) все остальные клетки базисные;

с) последовательность П образует цикл (смотри транспортную задачу в сетевой постановке).

2. Задаем направление обхода этого цикла, совпадающего с направлением kÞp. В клетку (k, p)заносим символ '+'. Для остальных клеток (i, jП, если направление iÞj совпадает с направлением обхода цикла с направлением обхода цикла, то заносим в позицию q символ '+', в противном случае заносим '–' .

3. Определяем клетку (q, l), для которой х(q, l)=min xij , где (i, j) – пробегает все клетки из П, помеченные символом '–'.

Полагаем Q=x(q, l).Из базиса выводится клетка (q, l).

4. Для всех (i, jП, если клетка помечена символом '+', то полагаем xij=xij+Q, в противном случае xij=xijQ.

5. Перейти к выполнению проверки критерия оптимальности.

Замечание 1.Иногда минимум достигается на нескольких клетках одновременно. В этом случае в качестве клетки (q, l) выбирается произвольно только одна из них.

Замечание 2.При заполнение таблицы для нового базиса значения xij вносятся только в базисные клетки.

Пример. Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов. Значения ai, bj, cij (i=1,2,3, j=1,2,3,4), заданы в таблице

 

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1           u1
               
i=2 a2           u2
               
i=3 a3           u3
               
           
v1 v2 v3 v4

 

Начинаем с определения исходного базиса методом северо–западного угла. Таковым является клетка (1,1), для нее x11=min (11,10)=10, это число заносим в эту клетку. Изменяем a1 и b1. Так как b1=0, затемняем столбец j=1.


 

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1         u1
               
i=2 a2           u2
               
i=3 a3           u3
               
           
v1 v2 v3 v4

В незатемненной части таблицы северо–западный угол (1,2), для нее x12=min (1,16)=1, это число заносим в эту клетку. Изменяем a1 и b2. Так как a1=0, затемняем строку i=1.

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1       u1
               
i=2 a2           u2
               
i=3 a3           u3
               
           
v1 v2 v3 v4

Продолжая аналогично далее, получим следующую таблицу:

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1       u1
               
i=2 a2       u2
               
i=3 a3       u3
               
           
v1 v2 v3 v4

В ней восстановлены значения ai, bj, а также затемнены базисные клетки. Значение функционала на этом решении будет равно

F=2´10+7´1+4´15+3´2+3´12+7´12=213.

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

1. ,

2. Число базисных клеток должно быть равно n+m–1.

 







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.146.112 (0.008 с.)