Страница
3
v1 + u1 = 12; v2 + u3 = 11; v3 + u3 = 0.
v1 + u3 = 11; v3 + u2 = 0;
Полагая, что v3 = 0, последовательно получаем: u2 = 0, u3 = 0, v2 = 11, v1 = 11, u1 = 1.
Так как задача решается на максимум, то для оптимальности плана распределения, сумма потенциалов в незанятых клетках должна быть не меньше тарифов этих клеток. В нижних левых углах незанятых клеток выписаны суммы потенциалов. Вс
е они превосходят соответствующие тарифы, т.е. начальный план закрепления покупателей за производителями по товару оптимален.
Аналогично, таблица 1.3 заполнена в следующей последовательности:
(3,2) – 320, (1,1) – 130, (1,3) – 280, (3,3) – 160, (2,3) – 550. Полученный план невырожденный, так как содержит 3 + 3 – 1 = 5 занятых клеток. Проверим его на оптимальность. Выпишем систему уравнений для нахождения потенциалов:
v1 + u1 = 9; v3 + u1 = 0; v3 + u3 = 0.
V2 + u3 = 11; v3 + u2 = 0;
Полагая, что u3 = 0, последовательно получаем: v3 = 0, u2 = 0, u1 = 0, v2 = 11, v1 = 9.
План распределения товара T2, заданный таблицей 2, оптимален.
Сумма прибыли = (12*400 + 11*80 + 11*270) + (9*130 + 11*320) = = 8650 + 4690 = 13340.
ОТВЕТ:
X111 = 400, X311 = 80, X321 = 270, X112 = 130, X322 = 320. Остальные = 0. Максимальная прибыль равна 13340.
Задача 2-1
С помощью алгоритма венгерского метода найти план закрепления работ за исполнителями, максимизирующий прибыль, связанную с выпуском всех пяти видов продукции. Матрица эффективности AN =, где – прибыль, получаемая при выполнении j-й работы i-м исполнителем, N - номер варианта, имеет вид:
40 |
28 |
44 |
38 |
46 | ||
36 |
52 |
51 |
43 |
30 | ||
A12= |
40 |
29 |
48 |
45 |
34 |
, |
56 |
54 |
53 |
46 |
49 | ||
51 |
41 |
50 |
55 |
41 |
РЕШЕНИЕ:
I этап: приведение матрицы А12.
Алгоритм венгерского метода предназначен для решения задачи о назначениях по критерию минимизации суммарных затрат (задача на минимум). При решении задачи на максимум (так как – прибыль), ее следует свести к задаче на минимум. Для этого в каждом столбце матрицы определяем максимальный элемент и из него вычитаем все элементы столбца.
40 |
28 |
44 |
38 |
46 |
16 |
26 |
9 |
17 |
3 | ||||
36 |
52 |
51 |
43 |
30 |
20 |
2 |
2 |
12 |
19 | ||||
A12= |
40 |
29 |
48 |
45 |
34 |
→ A121= |
16 |
25 |
5 |
10 |
15 |
→ | |
56 |
54 |
53 |
46 |
49 |
0 |
0 |
0 |
9 |
0 | ||||
51 |
41 |
50 |
55 |
41 |
5 |
13 |
3 |
0 |
8 | ||||
56 |
54 |
53 |
55 |
49 |
Так как в строках 1, 2, 3 нулей не оказалось, то вычитаем из элементов этих строк минимального из них, то есть вычитаем из строки 1 число 3, из строки 2 число 2, из строки 3 число 5. Получаем нули в этих строках.
13 |
23 |
6 |
14 |
0 | ||
18 |
0 |
0 |
10 |
17 | ||
→ A122= |
11 |
20 |
0 |
5 |
10 |
→ |
0 |
0 |
0 |
9 |
0 | ||
5 |
13 |
3 |
0 |
8 | ||