Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Для задач(Брошюра).doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
964 Кб
Скачать
☆

2. Метод північно-західного кута

Згідно з цим методом заповнюють клітинки матриці перевезень, починаючи з лівого верхнього кута, послідовно вичерпуючи всі запаси. Детальніше проілюструємо це на прикладі матриці перевезень, заданої табл. 3.3.

Таблиця 3.3

Пункт відправлення

Пункт споживання

Запас

B1

B2

B3

B4

B5

A1

4

1

3

4

4

60

A2

2

3

2

2

3

35

A3

3

5

2

4

4

40

Потреба

22

45

20

18

30

135

Першою заповнюється клітинка А1В1. В неї заноситься min(22,60)=22. Потреба В1 повністю покрита, тому цей стовпець далі не розглядається (можна викреслити). У залишеній таблиці наступною північно-західною клітинкою буде А1В2. Залишок запасу для А1 становитиме 60-22=38. В А1В2 заносимо min(45,38)=38. Запас для A1 повністю покритий (викреслюємо рядок). В А2В2 заносимо min(45-38,35)=7. Викреслюємо В2 і т.д. Отримуємо таблицю 3.4.

Таблиця 3.4

Пункт відправлення

Пункт споживання

Запас

B1

B2

B3

B4

B5

A1

4

22

1

38

3

4

4

60|38|0

A2

2

3

7

2

20

2

8

3

35|28|8|0

A3

3

5

2

4

10

4

30

40|30|0

Потреба

22

0

45

7

0

20

0

18

10

0

30

0

135

3. Метод найменших вартостей

Цей метод аналогічний методу північно-західного кута, проте числа заносяться у клітинку з найменшим значенням вартості у залишеній таблиці (проте фіктивний пункт завжди розглядається останнім). Проілюструємо на прикладі. Найменшу вартість має клітинка А1В2. Тому першою заповнюємо її. Заносимо в неї min(45,60)=45 і викреслюємо стовпець В2. Далі вибираємо найменшу вартість - 2. Оскільки вона відповідає кільком клітинкам, вибираємо будь-яку з них, наприклад А2В1 - min(35,22)=22. Викреслюємо В1. Потім в А2В3 - min(20,13)=13, викреслюємо А2 і т.д. Результат у табл. 3.5.

Таблиця 3.5

Пункт відправлення

Пункт споживання

Запас

B1

B2

B3

B4

B5

A1

4

1

45

3

4

4

15

60|15|0

A2

2

22

3

2

13

2

3

35|13|0

A3

3

5

2

7

4

18

4

15

40|33|0

Потреба

22

0

45

0

20

7

0

18

0

30

15

0

135

Зауваження 3.1. Число базисних клітинок повинно бути m+n-1, інакше їх доповнюють до відповідної кількості з числа вільних клітинок із базисним значенням 0.