Экономико математические методы и модели 3 (стр. 2 из 5)
Полученный начальный план проверим на оптимальность. План невырожденный, так как число занятых клеток (3+3-1=5) равно m + n – 1 (m и n – число строк и столбцов распределительной матрицы). Обозначим через
и 
потенциалы строк и столбцов. Для их нахождения отметим, что в занятых клетках сумма потенциалов строки и столбца должна равняться тарифу клетки. Получаем в данном случае 5 уравнений с 6-ю неизвестными: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.С помощью алгоритма венгерского метода найти план закрепления работ за исполнителями, максимизирующий прибыль, связанную с выпуском всех пяти видов продукции. Матрица эффективности 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:
Таблица 3.1.1
| Производствотоваров | Внутреннее потребление | Конечныйспрос | ||
| цех 1 | цех 2 | цех 3 | ||
| цех 1 | 240 | 72 | 140 | 348 |
| цех 2 | 80 | 264 | 180 | 76 |
| цех 3 | 0 | 120 | 400 | 480 |
Таблица 3.1.2
| Первичныересурсы | Расходы ресурса за год | ||
| цех 1 | цех 2 | цех 3 | |
| А | 180 | 30 | 50 |
| Б | 1200 | 1500 | 0 |
| В | 400 | 1200 | 300 |
| Г | 160 | 600 | 1000 |
ТРЕБУЕТСЯ:
1) найти матрицы коэффициентов прямых товаро-затрат и ресурсо-затрат на основании данных за предыдущий год;
2) найти план полных выпусков продукции каждого цеха на следующий год, обеспечивающих выполнение госзаказа по отгрузке продукции в объемах c1=360, c2=90, c3=450 соответственно;
3)определить необходимый запас первичных ресурсов каждого вида.
РЕШЕНИЕ:
Если обозначить через
полные выпуски продукции каждым цехом, то можно составить следующие соотношения 
где
– непосредственный натуральный расход продукции i-го цеха для обеспечения выпуска всей продукции j-го цеха. Числа 
называются коэффициентами прямых товаро-затрат. Их можно определить по статистическим данным за предыдущий год, т.е. 
Смысл коэффициента 
– количество продукции i-го цеха, используемое для производства 1 единицы продукции j-го цеха.Аналогично, расход
k-го ресурса j-м цехом представим в виде 
Тогда коэффициенты 
называются коэффициен-тами прямых ресурсо-затрат. Они определяют количество k-го ресурса, необходимое для производства единицы продукции j-го цеха и находятся по результатам статистических данных за предыдущий год.1. Для определения коэффициентов
найдем полные выпуски продукции каждым цехом за предыдущий год хj:x1 = 240 + 72 + 140 + 348 = 800;
x2 = 80 + 264 + 180 + 76 = 600;
x3 = 0 + 120 + 400 + 480 = 1000;
Тогда матрицы A и B коэффициентов
и принимают вид: | 240 | 72 | 140 | 0.30 | 0.12 | 0.14 |
| 800 | 600 | 1000 | |||
| 0.10 | 0.44 | 0.18 | , | ||
| A= | 80 | 264 | 180 | = | |
| 800 | 600 | 1000 | 0.00 | 0.20 | 0.40 |
| 0 | 120 | 400 | |||
| 800 | 600 | 1000 |
| 180 | 30 | 50 | 0.23 | 0.05 | 0.05 |
| 800 | 600 | 1000 | |||
| 1.50 | 2.50 | 0.00 | , | ||
| B= | 1200 | 1500 | 0 | = | |
| 800 | 600 | 1000 | 0.50 | 2.00 | 0.30 |
| 400 | 1200 | 300 | 0.20 | 1.00 | 1.00 |
| 800 | 600 | 1000 | |||
| 160 | 600 | 1000 | |||
| 800 | 600 | 1000 |
2. Заменяя выражения
найденными коэффициентами получаем систему уравнений для определения искомых полных выпусков продукции:  | x1 = 0.30*x1 + 0.12*x2 + 0.14*x3 + 360,x2 = 0.10*x1 + 0.44*x2 + 0.18*x3 + 90,x3 = 0.00*x1 + 0.20*x2 + 0.40*x3 + 450. |
Эту систему можно записать в матричной форме
где E – единичная матрица, X – матрица-столбец из неизвестных, C – матрица-столбец из чисел c1=360, c2=90, c3=450. Решая полученное матричное уравнение, найдем полные выпуски продукции. Его решение имеет вид: 
Строим обратную матрицу 
Для этого найдем алгебраические дополнения 
и определитель 
для матрицы 
Имеем: