Вырожденные случаи метода потенциалов. Открытые транспортные задачи

1.

Липецкий государственный технический университет
Кафедра прикладной математики
Прикладная математика
Лекция 6
Вырожденные случаи метода потенциалов.
Открытые транспортные задачи.
Транспортная задача с минимизацией времени.
1

2.

Вырожденные случаи метода потенциалов
Вырожденные случаи транспортной задачи возникают, когда
минимальное значение при нахождении опорного плана или
пересчёте
цикла
достигается
в
нескольких
значениях.
Преодолеваются вырожденные случаи двумя способами:
1. Можно попытаться выбрать другой опорный план или другой
цикл.
2. Ввести в некоторые клетки , считая по ходу решения задачи
> 0 и меньше всех других величин количества груза в таблице, а
затем положить = 0.
2

3.

Пример 1
B1
B2
Всего
B3
A1
1
3
2
15
A2
2
4
3
25
A3
5
2
3
10
Всего
15
25
10
50
3

4.

Пример 1
B1
A1
15
B2
1
A2
2
A3
5
Всего
15
25
3
2
15
4
3
25
3
10
2
25
Всего
B3
10
10
50
Такой план является вырожденным для метода потенциалов.
4

5.

Пример 1
B1
B2
Всего
B3
A1
1
3
2
15
A2
2
4
3
25
A3
5
2
3
10
Всего
15
25
10
50
5

6.

Пример 1
B1
B2
A1
1
3
A2
2
A3
5
Всего
15
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
6

7.

Пример 1
B1
B2
A1
1
A2
2
A3
5
Всего
15
5
25
Всего
B3
3
2
15
4
3
25
2
3
10
10
10
50
7

8.

Пример 1
B1
B2
A1
1
5
3
A2
2
20
A3
5
Всего
15
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
8

9.

Пример 1
B1
A1
A2
5
15
5
3
2
20
25
Всего
B3
1
5
A3
Всего
B2
2
15
4
3
25
2
3
10
10
10
50
9

10.

Пример 1
B1
A1
B2
1
5
3
20
A2
5
2
A3
10
5
Всего
15
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
Получен невырожденный план.
10

11.

Пример 1
B1
B2
Всего
B3
A1
1
3
2
15
A2
2
4
3
25
A3
5
2
3
10
Всего
15
25
10
50
Попробуем найти невырожденный план с меньшей стоимостью
перевозок. Для этого будем сначала заполнять клетки с меньшими
стоимостями перевозок, если это возможно.
11

12.

Пример 1
B1
B2
A1
1
3
A2
2
A3
5
Всего
15
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
12

13.

Пример 1
B1
B2
A1
1
A2
2
A3
5
Всего
15
5
25
Всего
B3
3
2
15
4
3
25
2
3
10
10
10
50
13

14.

Пример 1
B1
B2
A1
1
A2
2
A3
5
Всего
15
5
10
25
Всего
B3
3
2
15
4
3
25
2
3
10
10
10
50
14

15.

Пример 1
B1
B2
A1
1
5
3
A2
2
10
A3
5
10
Всего
15
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
15

16.

Пример 1
B1
A1
A2
15
A3
Всего
15
B2
1
5
3
2
10
5
10
25
Всего
B3
2
15
4
3
25
2
3
10
10
10
50
Получен невырожденный план с меньшей стоимостью перевозок.
16

17.

Пример 2
B1
B2
Всего
B3
A1
1
3
2
20
A2
2
4
3
20
A3
5
2
3
20
Всего
20
20
20
Для нахождения невырожденного плана
необходимо ввести фиктивные величины.
60
в
этом
примере
17

18.

Пример 2
B1
B2
A1
20
1
A2
2
5
A3
Всего
20
Всего
B3
3
2
20
20
4
3
20
2
3
20+
20
20
20
60
Для нахождения невырожденного опорного плана в этом примере
необходимо ввести фиктивные величины.
18

19.

Открытые транспортные задачи
Задачи, в которых σ