Методы оптимизации ПИ 202з Тихонов РГР v2
.0.docШаг3. Ищем максимальную разность минимальных элементов в строках и в столбцах:
|
|
B1 40 |
B2 0 |
B3 20 |
B4 70 |
B5 50 |
Шаг1 |
Шаг2 |
Шаг3 |
|
A1 120 |
X11
7 |
X12 0 9 |
X13
10 |
X14
6 |
X15
5 |
1 |
1 |
1 |
|
A2 60 |
X21
12 |
X22 0 8 |
X23
6 |
X24
5 |
X25
13 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
Однозначно определен столбец B5 с разностью =8. Заполняем минимальный элемент X15:
|
|
B1 40 |
B2 0 |
B3 20 |
B4 70 |
B5
|
Шаг1 |
Шаг2 |
Шаг3 |
|
A1
|
X11
7 |
X12 0 9 |
X13
10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
|
A2 60 |
X21
12 |
X22 0 8 |
X23
6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
Шаг4. Ищем максимальную разность минимальных элементов в строках и в столбцах:
|
|
B1 40 |
B2 0 |
B3 20 |
B4 70 |
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
|
A1 70 |
X11
7 |
X12 0 9 |
X13
10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
1 |
|
A2 60 |
X21
12 |
X22 0 8 |
X23
6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
Однозначно максимальная разность = 5 в столбце B1. Заполняем маршрут с минимальным тарифом в этом столбце X11 :
|
|
B1
|
B2 0 |
B3 20 |
B4 70 |
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
|
A1
|
X11 40 7 |
X12 0 9 |
X13
10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
1 |
|
A2 60 |
X21 0 12 |
X22 0 8 |
X23
6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
Шаг5. Ищем максимальную разность минимальных элементов в строках и в столбцах:
|
|
B1 0 |
B2 0 |
B3 20 |
B4 70 |
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
Шаг5 |
|
A1 30 |
X11 40 7 |
X12 0 9 |
X13
10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
1 |
4 |
|
A2 60 |
X21 0 12 |
X22 0 8 |
X23
6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
|
|
Шаг5 |
- |
- |
4 |
1 |
- |
|
|
|
|
|
Определена максимальная разность 4 в столбце B3 и строке A1. Стоимость минимальных тарфиов одинакова, выбираю любой – X23 и заполняю его:
|
|
B1 0 |
B2 0 |
B3
|
B4 70 |
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
Шаг5 |
|
A1 30 |
X11 40 7 |
X12 0 9 |
X13 0 10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
1 |
4 |
|
A2
|
X21 0 12 |
X22 0 8 |
X23 20 6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
1 |
1 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
- |
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
|
|
Шаг5 |
- |
- |
4 |
1 |
- |
|
|
|
|
|
Шаг6. Ищем максимальную разность минимальных элементов в строках и в столбцах:
|
|
B1 0 |
B2 0 |
B3 0 |
B4 70 |
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
Шаг5 |
Шаг6 |
|
A1 30 |
X11 40 7 |
X12 0 9 |
X13 0 10 |
X14
6 |
X15 50 5 |
1 |
1 |
1 |
1 |
4 |
0 |
|
A2 40 |
X21 0 12 |
X22 0 8 |
X23 20 6 |
X24
5 |
X25 0 13 |
1 |
1 |
1 |
1 |
1 |
0 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
- |
|
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
|
|
|
Шаг5 |
- |
- |
4 |
1 |
- |
|
|
|
|
|
|
|
Шаг6 |
- |
- |
- |
1 |
- |
|
|
|
|
|
|
В таблице осталось два маршрута, очевидно, что в X24 пойдет оставшийся в A2 40ед. ресурса, а в X14 оставшиеся в А1 30 ед. ресурса:
|
|
B1 0 |
B2 0 |
B3 0 |
B4
|
B5 0 |
Шаг1 |
Шаг2 |
Шаг3 |
Шаг4 |
Шаг5 |
Шаг6 |
|
A1
|
X11 40 7 |
X12 0 9 |
X13 0 10 |
X14 30 6 |
X15 50 5 |
1 |
1 |
1 |
1 |
4 |
0 |
|
A2
|
X21 0 12 |
X22 0 8 |
X23 20 6 |
X24 40 5 |
X25 0 13 |
1 |
1 |
1 |
1 |
1 |
0 |
|
A3 0 |
X31 0 6 |
X32 60 2 |
X33 0 8 |
X34 10 2 |
X35 0 4 |
0 |
2 |
- |
- |
- |
|
|
Шаг1 |
1 |
6 |
2 |
3 |
1 |
|
|
|
|
|
|
|
Шаг2 |
1 |
- |
2 |
3 |
1 |
|
|
|
|
|
|
|
Шаг3 |
5 |
- |
4 |
1 |
8 |
|
|
|
|
|
|
|
Шаг4 |
5 |
- |
4 |
1 |
- |
|
|
|
|
|
|
|
Шаг5 |
- |
- |
4 |
1 |
- |
|
|
|
|
|
|
|
Шаг6 |
- |
- |
- |
1 |
- |
|
|
|
|
|
|