160

480

0

bj1 130 320 990 1440 – vj 9 11 0 – –

Начальные планы распределения товаров определены по методу максимальной прибыли, т.е. в первую очередь заполнялись по максимуму клетки с наибольшими тарифами. Более конкретно, просматривая таблицу 1.2, замечаем, что максимальный тариф 12 стоит в клетке (1,1). В эту клетку ставим число 400. При этом запасы производителя А₁ исчерпан. Далее, в клетку (3,1) ставим 80, а в клетку (3,2) ставим 270. Из запасов производителя А₃ осталось 70, так как 420-80-270=70, ставим их в клетку (3,3). Потребность покупателей В₁ и В₂ в товарах исчерпаны, следовательно, оставшиеся 480 товаров производителя А₂ ставим в клетку (2,3). При этом товар производителей полностью распределён.

Полученный начальный план проверим на оптимальность. План невырожденный, так как число занятых клеток (3+3-1=5) равно m + n – 1 (m и n – число строк и столбцов распределительной матрицы). Обозначим через и потенциалы строк и столбцов. Для их нахождения отметим, что в занятых клетках сумма потенциалов строки и столбца должна равняться тарифу клетки. Получаем в данном случае 5 уравнений с 6-ю неизвестными:

v₁ + u₁ = 12; v₂ + u₃ = 11; v₃ + u₃ = 0.

v₁ + u₃ = 11; v₃ + u₂ = 0;

Полагая, что v₃ = 0, последовательно получаем: u₂ = 0, u₃ = 0, v₂ = 11, v₁ = 11, u₁ = 1.

Так как задача решается на максимум, то для оптимальности плана распределения, сумма потенциалов в незанятых клетках должна быть не меньше тарифов этих клеток. В нижних левых углах незанятых клеток выписаны суммы потенциалов. Все они превосходят соответствующие тарифы, т.е. начальный план закрепления покупателей за производителями по товару оптимален.

Аналогично, таблица 1.3 заполнена в следующей последовательности:

(3,2) – 320, (1,1) – 130, (1,3) – 280, (3,3) – 160, (2,3) – 550. Полученный план невырожденный, так как содержит 3 + 3 – 1 = 5 занятых клеток. Проверим его на оптимальность. Выпишем систему уравнений для нахождения потенциалов:

v₁ + u₁ = 9; v₃ + u₁ = 0; v₃ + u₃ = 0.

V₂ + u₃ = 11; v₃ + u₂ = 0;

Полагая, что u₃ = 0, последовательно получаем: v₃ = 0, u₂ = 0, u₁ = 0, v₂ = 11, v₁ = 9.

План распределения товара T ₂ , заданный таблицей 2, оптимален.

Сумма прибыли = (12*400 + 11*80 + 11*270) + (9*130 + 11*320) = = 8650 + 4690 = 13340.

ОТВЕТ:

X₁₁₁ = 400, X₃₁₁ = 80, X₃₂₁ = 270, X₁₁₂ = 130, X₃₂₂ = 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

II этап: поиск назначения.

Выбираем один из нулей, помечаем его, например, точкой или звездочкой или обводим его другим цветом (в дальнейшем, звездочкой), а остальные нули строки и столбца, в которых стоит выбранный помеченный нуль, перечеркиваем. Далее переходим к следующему нулю. И так до тех пор, пока каждый нуль будет либо помечен, либо перечеркнут.

13	23	6	14	0*
18	0*	Ø	10	17
→ A122=	11	20	0*	5	10
0*	Ø	Ø	9	Ø
5	13	3	0*	8

Помеченные нули составили полное назначение (количество помеченных нулей равно 5).

Следовательно, 1 исполнитель назначается на 5-ю работу, 2→2, 3→3, 4→1, 5→4.

Задача 3-1

Предприятие включает в себя три цеха по производству различной продукции и использует при этом четыре вида первичных ресурсов. Продукция, выпускаемая каждым цехом, частично отгружается за пределы предприятия (для удовлетворения конечного спроса), а частично распределяется внутри предприятия между цехами в качестве вторичных ресурсов. Баланс предприятия в натуральном выражении за прошедший год приведен в следующих двух таблицах 3.1.1 и 3.1.2: