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