183894 (584851), страница 6
Текст из файла (страница 6)
3) пересчитанные по методу потенциалов – 6118 у.е.,
4) методом Фогеля соответственно – 6390 у.е.
Наименьшие транспортные расходы составили расходы, рассчитанные по методу потенциалов.
Задача № 4
Сетевая задача
Ниже приведено 10 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов 
, на вершинах (в кружках) — значения запасов-потребностей 
. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
30
0
20
10
23
34
18
19
3
10
18
-35
3
-40
30
15
30
45
9
2
6
2
-40
8
6
5
16
8
2
2
-35
-40
45
-10
8
Решение. Построим пробный опорный план (рис.1).
3/30
7/0
12/20
10
23
34
18
2/-35
19
3
10
18
4/-40
3
9/30
10/30
15
9
2
6
2
6/-40
13/45
8
6
5
16
8
2
2
1/-35
8/-40
11/45
8
5/-10
Рис. 1. Пробный план перевозок по сети.
В качестве начальной выберем вершину 12, которая является поставщиком с запасами в 20 единиц продукции. Из этой вершины отправим транзитом через 13 с запасами 45 ед. и 10 вершину с запасами 30 единиц в 8 вершину и удовлетворяем её потребности в 40 единиц. Оставшиеся 55 единиц отправим в 6 вершину с потребностями 40 единиц, оставшиеся 15 единиц отправляем в 5 вершину с потребностями 10 единиц, оставшиеся 5 единиц направим в 1 вершину, потребности которой составляют 35 единиц.
Из 11 вершины с запасами 45 единиц направим транзитом через 9 вершину , всего запасов стало 75 единиц, направим их транзитом через 7 вершину в 4 вершину, потребности которой составляют 40 единиц, оставшиеся 35 единиц направим во 2 вершину и удовлетворим ее потребности.
Из 3 вершины с запасами 30 единиц направим транзитом через 7 вершину в 1 вершину, потребности которой удовлетворим.
В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены.
В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены. Число базисных ребер здесь равно 11, число вершин 13.
Итак, полученный план является опорным, так как удовлетворяет всем требованиям опорного плана. Значение функции, которое соответствует построенному плану равно
.
Проверку плана на оптимальность осуществим с помощью метода потенциалов.
Одной из вершин (например, 1) зададим произвольное значение потенциала α1=0. Запишем его около вершины 1.
Затем, двигаясь по базисным ребрам, вычисляем потенциалы остальных вершин.
; 
;
;
;
;
;
; 
;
После вычисления потенциалов находим оценки для небазисных ребер: (1,2), (2,4),(2,7), (3,7),(7,12), (7,8), (10,12),(4,6). Они определяются по формуле и равны соответственно:
;
;
;
;.
Есть три положительные оценки, значит построенный опорный план не оптимальный.
Наибольшая оценка 
. Ребро (7,8), объявляем разрешающим, направляем разрешающую стрелку (пока пустую) от вершины с меньшим потенциалом к вершине с большим потенциалом, т.е. от 7–й вершины к 8–й (на рис. 2 разрешающая стрелка намечена пунктиром). В результате получаем цикл пересчета, замыкающийся на ребре (7,8). Цикл пересчета на рис.2 намечен сплошной линией.
7/0
10
23
34
18
2/-35
19
3
10
18
4/-40
3
9/30
10/30
15
9
2
6
2
6/-40
13/45
8
6
5
16
8
2
2
1/-35
8/-40
11/45
8
5/-10
Рис.3. пересчет перевозок по потенциалам
Во второй строке выписываем ребра, принадлежащие циклу пересчета. В первой строке, над ребрами с помощью стрелок укажем направление перевозок, а в третьей строке – объем перевозимого груза. В четвертой строке полученной конструкции запишем 
, если направление перевозки совпадает с разрешающей стрелкой и 
, в противном случае.
Изменяем распределение поставок. Определяем 
величину корректировки плана. Поскольку перевозки х8,10,х11,9 направлены против разрешающей стрелки, величина 
полагается меньшей из них 
Включаем в базис ребро (7,8), а объем перевозки полагаем равным величине корректировки 
Ребро (7,9) исключаем из базиса.
После пересчета получим значение функции:
Задача № 5
Задача о назначениях
Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей 
задачи о разборчивой невесте. Решить задачу методом потенциалов и венгерским методом.
| 44 | ||||||||||
| 31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 | |||
| 35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 | |||
| 12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 | |||
| 28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 | |||
| 37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 | |||
| 22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 | |||
| 45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 | |||
| 43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 | |||
Решение.
1. Метод потенциалов.
Начальный вариант выбора 
найдем методом максимального элемента (Табл. 5.1).
Шаг 1. Максимальным элементом является с3,4=49. Назначим третьей невесте четвертого жениха. Вычеркнем третью строку.
Шаг 2. Из невычеркнутых элементов матрицы максимальным элементом является с5,8=49. Назначим пятой невесте восьмого жениха. Вычеркнем пятую строку.
Шаг 3. Из невычеркнутых элементов матрицы максимальным элементом является с6,2=49. Шестая невеста выбирает второго жениха, вычеркиваем шестую строку.
Шаг 4. Из невычеркнутых элементов матрицы максимальным элементом является с4,3=48. Четвертая невеста выбирает третьего жениха, вычеркиваем четвертую строку.
Шаг 5. Из невычеркнутых элементов матрицы максимальным элементом является с8,6=46. Восьмая невеста выбирает шестого жениха, вычеркиваем восьмую строку.
Шаг 6. Из невычеркнутых элементов матрицы максимальным элементом является с7,1=45. Седьмая невеста выбирает первого жениха, вычеркиваем седьмую строку.
Шаг 7. Из невычеркнутых элементов матрицы максимальным элементом является с1,4=41. Но четвертого жениха уже выбрала третья невеста, поэтому в клетку (1,4) поместим 0. В дальнейшем, х1,4=0 будем считать базисной переменной. Вычеркнем четвертый столбец.
Шаг 8. Из невычеркнутых элементов матрицы максимальным элементом является с1,7=38. Первая невеста назначается седьмому жениху, вычеркиваем первую строку.
Шаг 9. Из невычеркнутых элементов матрицы максимальным элементом является с2,7=38. Но седьмой жених уже выбран, поэтому в клетку (2,7) поместим 0. Х2,7=0 - базисная переменная. Вычеркнем седьмой столбец.
Шаг 10. Из невычеркнутых элементов матрицы максимальным элементом является с2,8=36. На восьмой жених уже выбран, поэтому в клетку (2,8) поместим 0. Х2,8=0 - базисная переменная. Вычеркнем восьмой столбец.
Шаг 11. Из невычеркнутых элементов матрицы максимальным элементом является с2,1=35. Но первый жених уже занят, поэтому в клетку (2,1) поместим 0. Х2,1=0 - базисная переменная. Вычеркнем первый столбец.
Шаг 12. Из невычеркнутых элементов матрицы максимальным элементом является Х2,3=26. Но третий жених уже занят, поэтому в клетку (2,3) поместим 0. Х2,3=0 - базисная переменная. Вычеркнем третий столбец.
Шаг 13. Из невычеркнутых элементов матрицы максимальным элементом является Х1,5=23. Но пятый жених уже занят, поэтому в клетку (1,5) поместим 0. Х1,5=0 - базисная переменная. Вычеркнем пятый столбец.
Шаг 14. Из невычеркнутых элементов матрицы максимальным элементом является с2,2=20. Но второй жених уже занят, поэтому в клетку (2,2) поместим 0. Х2,2=0 - базисная переменная. Вычеркнем второй столбец.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
