Экономико-математический практикум (стр. 6 из 9)

Итак, полученный план является опорным, так как удовлетворяет всем требованиям опорного плана. Значение функции, которое соответствует построенному плану равно

.

Проверку плана на оптимальность осуществим с помощью метода потенциалов.

Одной из вершин (например, 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 намечен сплошной линией.

Рис.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 - базисная переменная. Вычеркнем второй столбец.

Шаг 15. Из невычеркнутых элементов матрицы максимальным элементом является с_2,5=17. Вторая невеста назначается пятому жениху, вычеркиваем вторую строку.

В табл. 5.1 номер шага, на котором были получены базисные переменные, указан в скобках. После 15 шага получим пробный вариант назначения Х₀: х_1,7=х_2,5= х_3,4=х_4,3=х_5,8=х_6,2= х_7,1=х_8,6=1. Это означает, что первая невеста выходит замуж за седьмого жениха, вторая невеста за пятого жениха, третья невеста за четвертого жениха, четвертая невеста за третьего жениха, пятая невеста за восьмого жениха, шестая невеста за второго жениха, седьмая невеста за первого жениха, восьмая невеста за шестого жениха.

Таблица 5.1.

31	13	11	41	10	17	38	25
0(7)	0(13)	1(8)
35	20	26	8	17	14	38	36
0(11)	0(14)	0(12)	1(15)	0(7)	0(10)
12	37	38	49	38	22	10	13
1(1)
28	21	48	43	44	29	26	12
1(4)
37	22	39	46	26	20	44	49
1(2)
22	49	19	2	20	30	45	16
1(3)
45	27	5	21	30	21	34	23
1(6)
43	33	20	29	3	46	33	21
1(5)

Суммарная эффективность, отвечающая полученному варианту выбора равна: