ГУАП
КАФЕДРА №41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
Б.К. Акопян |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №6
ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С ОГРАНИЧЕНИЯМИ
по курсу: Прикладные методы оптимизации
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Изучение методов составления опорных планов и оптимизации решения транспортной задачи с ограничениями на пропускную способность.
Индивидуальный вариант
Индивидуальный вариант номер 10 в соответствии с таблицей 1.
Таблица 1 – Индивидуальный вариант задания
|
Ход работы |
|
|
|
|
|
|
|
|
|
B1 |
|
B2 |
|
B3 |
|
B4 |
|
|
A1 |
10 |
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
A2 |
inf |
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
A3 |
12 |
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
|
25 |
|
20 |
|
25 |
|
15 |
|
85 |
1.Представление исходной ТЗ в сетевой форме в соответствии с рисунком 1
Рисунок 1 – Сетевое представление транспортной задачи
2
|
|
|
2. |
|
Построили опорный план исходной задачи БЕЗ учета ограничений способом |
|||||||||||||||||||||
северо-западного угла и определить его стоимость. |
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B1 |
|
|
|
B2 |
|
|
|
B3 |
|
|
B4 |
|
|
|
|
|
||||||
|
A1 |
|
|
|
|
5 |
|
|
|
|
7 |
|
|
|
|
3 |
|
|
|
|
|
4 |
|
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
25 |
|
|
|
|
5 |
|
|
|
|
0 |
|
|
|
|
0 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
A2 |
|
|
|
|
6 |
|
|
|
|
4 |
|
|
|
|
5 |
|
|
|
|
|
4 |
|
28 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
0 |
|
|
|
|
15 |
|
|
|
|
13 |
|
|
|
|
0 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
A3 |
|
|
|
|
5 |
|
|
|
|
3 |
|
|
|
|
7 |
|
|
|
|
|
6 |
|
27 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
0 |
|
|
|
|
0 |
|
|
|
|
12 |
|
|
|
|
15 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
25 |
|
|
|
|
20 |
|
25 |
|
|
|
|
|
15 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Значение целевой функции для этого опорного плана равно:
F(x) = 5*25 + 7*5 + 4*15 + 5*13 + 7*12 + 6*15 = 459
3.Оптимизировали опорный план ТЗ без ограничений методом потенциалов.
|
v |
|
5 |
|
|
7 |
|
8 |
|
7 |
|
u |
|
B1 |
|
|
B2 |
|
B3 |
|
B4 |
|
|
0 |
A1 |
|
|
5 |
|
7 |
|
3 |
|
4 |
30 |
25 |
|
|
5 |
- |
0 |
5 |
0 |
3 |
|||
|
|
|
|
|
|||||||
-3 |
A2 |
|
|
6 |
|
4 |
|
5 |
|
4 |
28 |
0 |
|
|
15 |
+ |
13 |
- |
0 |
|
|||
|
|
|
|
|
|
||||||
-1 |
A3 |
|
|
5 |
|
3 |
|
7 |
|
6 |
27 |
0 |
|
|
0 |
3 |
12 |
|
15 |
|
|||
|
|
|
|
|
|
|
|||||
|
|
|
25 |
|
20 |
|
25 |
|
15 |
|
|
|
Max(5,3,3) = 5; ячейка (1,3) |
|
|
|
|
|
|||||
|
v |
|
5 |
|
|
2 |
|
3 |
|
2 |
|
u |
|
B1 |
|
|
B2 |
|
B3 |
|
B4 |
|
|
0 |
A1 |
|
|
5 |
|
7 |
|
3 |
|
4 |
30 |
25 |
- |
|
0 |
|
5 |
+ |
0 |
|
|||
|
|
|
|
|
|
||||||
2 |
A2 |
|
|
6 |
|
4 |
|
5 |
|
4 |
28 |
0 |
|
1 |
20 |
|
8 |
|
0 |
|
|||
|
|
|
|
|
|
|
|||||
4 |
A3 |
|
|
5 |
|
3 |
|
7 |
|
6 |
27 |
0 |
|
4 |
0 |
3 |
12 |
- |
15 |
|
|||
|
|
|
|
|
|||||||
|
|
|
25 |
|
20 |
|
25 |
|
15 |
|
|
|
Макс(1,3,4) = 4 |
(3,1) |
|
|
|
|
|
|
|||
3
|
v |
|
5 |
2 |
|
3 |
|
6 |
|
|
u |
|
B1 |
|
B2 |
B3 |
|
B4 |
|
|
|
0 |
A1 |
|
5 |
|
7 |
3 |
|
|
4 |
30 |
13 |
- |
0 |
17 |
+ |
0 |
|
2 |
|||
|
|
|
|
|||||||
2 |
A2 |
|
6 |
|
4 |
5 |
|
|
4 |
28 |
0 |
1 |
20 |
8 |
- |
0 |
|
4 |
|||
|
|
|
|
|||||||
0 |
A3 |
|
5 |
|
3 |
7 |
|
|
6 |
27 |
12 |
+ |
0 |
0 |
|
15 |
- |
|
|||
|
|
|
|
|
||||||
|
|
|
25 |
|
20 |
25 |
|
|
15 |
|
|
Макс 4 (2,4) |
|
|
|
|
|
|
|
||
|
v |
|
5 |
3 |
|
3 |
|
3 |
|
|
u |
|
B1 |
|
B2 |
B3 |
|
B4 |
|
|
|
0 |
A1 |
5 |
7 |
3 |
|
4 |
30 |
5 |
0 |
25 |
0 |
|
|||
|
|
|
|
||||
1 |
A2 |
6 |
4 |
5 |
|
4 |
28 |
0 |
13 |
0 |
15 |
|
|||
|
|
|
|
||||
0 |
A3 |
5 |
3 |
7 |
|
6 |
27 |
20 |
7 |
0 |
0 |
|
|||
|
|
|
|
||||
|
|
25 |
20 |
25 |
|
15 |
|
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
F(x) = 5*5 + 3*25 + 4*13 + 4*15 + 5*20 + 3*7 = 333
4.Составить математическую модель задачи с учетом ограничений.
5.Составили опорный план задачи с ограничениями с помощью модифицированного метода северо-западного угла, показывая процесс удаления фиктивных клеток таблицы.
|
B1 |
|
B2 |
|
B3 |
|
B4 |
|
|
|
|
A1 |
10 |
5 |
15 |
7 |
12 |
3 |
20 |
4 |
|
|
30 |
10 |
- |
15 |
|
5 |
+ |
0 |
|
|
|
||
|
|
|
|
|
|
||||||
A2 |
inf |
6 |
8 |
4 |
7 |
5 |
6 |
4 |
|
|
28 |
15 |
|
5 |
|
7 |
|
1 |
|
|
|
||
|
|
|
|
|
|
|
|
||||
A3 |
12 |
5 |
10 |
3 |
11 |
7 |
14 |
6 |
inf |
М |
27 |
0 |
+ |
0 |
|
11 |
|
14 |
|
2 |
- |
||
|
|
|
|
|
|||||||
|
|
|
|
|
inf |
М |
|
|
inf |
М |
|
|
|
|
|
|
2 |
- |
|
|
М |
+ |
|
|
|
25 |
|
20 |
|
25 |
|
15 |
85 |
|
|
Можем перенести 2 |
|
|
|
|
|
|
|
|
|
||
4
|
B1 |
|
B2 |
|
B3 |
|
B4 |
|
|
A1 |
10 |
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
8 |
|
15 |
|
7 |
|
0 |
|
||
|
|
|
|
|
|
||||
A2 |
inf |
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
15 |
|
5 |
|
7 |
|
1 |
|
||
|
|
|
|
|
|
||||
A3 |
12 |
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
2 |
|
0 |
|
11 |
|
14 |
|
||
|
|
|
|
|
|
|
|
25 |
|
20 |
|
25 |
|
15 |
85 |
|
|
6. |
Оценили оптимальность полученного опорного плана, используя метод |
||||||||
потенциалов. |
|
|
|
|
|
|
|
|
|
|
|
v |
0 |
|
-2 |
|
-2 |
|
-2 |
|
|
u |
|
B1 |
|
B2 |
|
B3 |
|
B4 |
|
|
5 |
A1 |
10 |
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
8 |
|
15 |
|
7 |
|
0 |
|
|||
|
|
|
|
|
|
|
||||
6 |
A2 |
inf |
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
15 |
|
5 |
|
7 |
|
1 |
|
|||
|
|
|
|
|
|
|
||||
5 |
A3 |
12 |
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
2 |
|
0 |
|
11 |
|
14 |
|
|||
|
|
|
|
|
|
|
||||
|
25 |
20 |
25 |
15 |
85 |
|
|
|
|
|
|
||
Опорный план |
является оптимальным, так |
все |
оценки свободных клеток |
|||
удовлетворяют условию ui + vj ≤ cij.
F(x) = 8*5 + 15*7 + 7*3 + 15*6 + 5*4 + 7*5 + 1*4 + 2*5 + 11*7 + 14*6 =486
7.Процесс оптимизации полученного опорного плана методом потенциалов.
|
v |
|
5 |
|
3 |
|
4 |
|
|
3 |
|
u |
|
B1 |
|
B2 |
|
|
B3 |
|
B4 |
|
|
0 |
A1 |
10 |
5 |
15 |
|
7 |
12 |
3 |
20 |
4 |
30 |
8 |
|
15 |
- |
|
7 |
|
0 |
+ |
|||
|
|
|
|
|
|
||||||
1 |
A2 |
inf |
6 |
8 |
|
4 |
7 |
5 |
6 |
4 |
28 |
15 |
|
5 |
|
|
7 |
|
1 |
|
|||
|
|
|
|
|
|
|
|
||||
3 |
A3 |
12 |
5 |
10 |
|
3 |
11 |
7 |
14 |
6 |
27 |
2 |
|
0 |
+ |
|
11 |
|
14 |
- |
|||
|
|
|
|
|
|
||||||
|
|
|
25 |
|
|
20 |
|
25 |
|
15 |
85 |
|
F = 426 |
|
|
|
|
|
|
|
|
|
|
5
|
v |
|
0 |
|
-2 |
|
|
-2 |
|
-2 |
|
u |
|
B1 |
|
|
B2 |
|
B3 |
|
B4 |
|
|
6 |
A1 |
10 |
|
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
8 |
|
|
5 |
|
7 |
+ |
10 |
- |
|||
|
|
|
|
|
|
||||||
6 |
A2 |
inf |
|
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
15 |
- |
|
5 |
|
7 |
|
1 |
+ |
|||
|
|
|
|
|
|
||||||
5 |
A3 |
12 |
|
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
2 |
+ |
|
10 |
|
11 |
- |
4 |
|
|||
|
|
|
|
|
|
||||||
|
|
|
|
25 |
|
20 |
|
25 |
|
15 |
85 |
|
F = 426 |
|
|
|
|
|
|
|
|
|
|
|
v |
|
0 |
|
3 |
|
|
-2 |
|
4 |
|
u |
|
B1 |
|
|
B2 |
|
B3 |
|
B4 |
|
|
4 |
A1 |
10 |
|
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
8 |
- |
|
5 |
|
12 |
|
5 |
+ |
|||
|
|
|
|
|
|
||||||
0 |
A2 |
inf |
|
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
10 |
|
|
5 |
|
7 |
|
6 |
|
|||
|
|
|
|
|
|
|
|
||||
0 |
A3 |
12 |
|
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
7 |
+ |
|
10 |
|
6 |
|
4 |
- |
|||
|
|
|
|
|
|
||||||
|
|
|
|
25 |
|
20 |
|
25 |
|
15 |
85 |
F = 401
|
|
v |
5 |
3 |
|
7 |
|
|
|
|
||||
u |
|
|
B1 |
B2 |
B3 |
|
|
B4 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
A1 |
10 |
5 |
15 |
7 |
12 |
3 |
20 |
4 |
30 |
4 |
+ |
5 |
- |
12 |
|
9 |
|
|||
|
|
|
|
|
||||||
1 |
A2 |
inf |
6 |
8 |
4 |
7 |
5 |
6 |
4 |
28 |
10 |
- |
5 |
+ |
7 |
|
6 |
|
|||
|
|
|
|
|
||||||
0 |
A3 |
12 |
5 |
10 |
3 |
11 |
7 |
14 |
6 |
27 |
11 |
|
10 |
|
6 |
|
0 |
|
|||
|
|
|
|
|
|
|
||||
|
|
|
25 |
|
20 |
|
25 |
|
15 |
85 |
|
F = 393 |
|
|
|
|
|
|
|
|
|
6
|
|
v |
|
|
5 |
|
3 |
|
7 |
|
|
|
2 |
|
|
|
|||||||||
u |
|
|
|
|
B1 |
|
|
|
|
B2 |
|
|
B3 |
|
|
B4 |
|
|
|
|
|
||||
2 |
|
A1 |
|
|
10 |
|
|
5 |
|
15 |
|
|
7 |
|
12 |
|
|
3 |
|
20 |
|
|
4 |
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
7 |
|
|
|
|
2 |
|
|
|
|
12 |
|
|
|
|
9 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
2 |
|
A2 |
|
|
inf |
|
|
6 |
|
8 |
|
|
4 |
|
7 |
|
|
5 |
|
6 |
|
|
4 |
28 |
|
|
|
|
7 |
|
|
|
|
8 |
|
|
|
|
7 |
|
|
|
|
6 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0 |
|
A3 |
|
|
12 |
|
|
5 |
|
10 |
|
|
3 |
|
11 |
|
|
7 |
|
14 |
|
|
6 |
27 |
|
|
|
|
11 |
|
|
|
|
10 |
|
|
|
|
6 |
|
|
|
|
0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
25 |
|
|
|
|
20 |
|
|
|
|
25 |
|
|
15 |
85 |
|
||
|
F = 381 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
7
8. |
Решение |
исходной |
транспортной |
задачи |
без |
ограничений |
(средствами MS Excel)
8
Вывод
Входе данной лабораторной работы был изучен метод составления опорных планов
иоптимизации решения транспортной задачи с ограничениями на пропускную способность.
9