Формулы для определения потенциалов каждой строки или столбца матрицы. Улучшение опорного плана

Страницы работы

9 страниц (Word-файл)

Содержание работы

Формулы для определения потенциалов каждой строки или столбца матрицы:

Vj=Ui+Cij ;                                                     (12)

Ui=Vj-Cij ;                                                      (13)

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

Принимаем Ui =

Все расчеты сведены в таблицу 12.

Таблица 12.

I

J

1

2

3

4

5

6

Ui

Bi

Ai

Vj

Для каждой незаполненной клетки подсчитывается разность:

∆=Vi+Ui-Cij<0

11=

12=

13=

14=

22=

23=

25=

31=

34=

35=

36=

41=

43=

44=

46=

53=

54=

55=

56=

Проверка  показала, что  план  не  является оптимальным, так как разность ∆ в клетках

2-3, 3-6, 5-3, 5-4 положительна. Максимальное нарушение условия оптимальности в клетке 5-3, ∆53=0,09.

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

Улучшение опорного плана.

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

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

Если выполняется условие m+n-1≤10, то для каждой незаполненной клетки матрицы можно построить единственный цикл перераспределения.

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

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

3-2                                           3-3 

40+40=80 40-40=0                                                    

40-40=0              0+40=40

5-2                                           5-3

Таблица 13.

I

J

1

2

3

4

5

6

Ui

Bi

Ai

Vj

В матрице зачеркиваем старые величины поставок и записываем новые. Дальнейшие расчеты повторяют вышеизложеное.

11=

12=

13=

14=

22=

23=

25=

31=

34=

35=

36=

41=

43=

44=

46=

53=

54=

55=

56=

Проверка показала, что нарушение оптимальности имеется в следующих клетках:

3-6 и 5-4.  Максимальное нарушение условия оптимальности в клетке 3-6 ∆36=0,05.

План не является оптимальным, поэтому его необходимо скорректировать.

2-1  2-6

60+40=100                                                                                           40-40=0

3-2                                  

80-40=40                                                       0+40=40

3-6

140-40=100                                                  0+40=40

5-1                              5-2           

Таблица 14.              

I

J

1

2

3

4

5

6

Ui

Bi

Ai

Vj

Похожие материалы

Информация о работе