s=s+C33=0+6=6.

2-ое назначение:

Сij0

j0

5

7

3

3

3

5

4

11

6

3

3

5

С =

-

-

4

7

10

9

4

1

5

5

6

5

5

1

Сi0j

3

5

-

6

3

i0

3

3

-

2

1

Выбран элемент С24 = 6.

s=s+C24=6+6=12.

Далее процесс продолжается аналогично.

В результате получим следующий план:

0

0

0

0

1

0

0

0

1

0

X* =

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

s=6+6+5+7+3=27 (слагаемые соответствуют шагам алгоритма).

2.8.3. Метод на основе принципа минимального риска

1.  Устанавливаем суммарную цену s=0.

2.  Определяем в каждой строке i два минимальных элемента ai1, аi2 и разность между ними Dai.

3.  Определяем в каждом столбце j два минимальных элемента а1j, а2j и разность между ними Daj.

4.  Определяем max (D ai, Daj) и номер строки (i*) или столбца (j*), в котором находится максимальное значение разности.
Если Dai > Daj, то i*=i, а j* выбираем равным адресу столбца, в котором находится первый минимум строки i*. Если Daj > Dai, то j*=j, а i* выбираем равным адресу строки, в которой находится первый минимум столбца j*.

5.  Вычисляем s=s+ai*j*. Строка i* назначается столбцу j*. Удаляем строку i* и столбец j* из матрицы А (записываем Б).

6.  Если в матрице есть неудаленные строки, то переходим к п.2, в противном случае - к п.7.

7.  Конец алгоритма.

Пример: Рассмотрим работу алгоритма на том же примере [15], что и в алгоритме на основе принципа максимина.

Вот как выглядит процедура выбора 1-го назначения.

Сi1

Ci2

Сj

5

7

10

8

3

3

5

2

4

11

7

6

3

3

4

1

С =

3

5

6

7

4

3

4

1

4

7

6

10

9

4

6

2

5

5

7

6

5

5

5

0

С1j

3

5

6

6

3

С2j

4

5

6

6

3

Сj

1

0

0

0

0

Максимальный риск определяется значением 2, что определяет назначение на этом этапе элемента, соответствующего С15. s=s+C15= 0+3=3.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13