Экономико математические методы и модели 3 — страница 3

  • Просмотров 551
  • Скачиваний 12
  • Размер файла 361
    Кб

клетку (3,3). Потребность покупателей В1 и В2 в товарах исчерпаны, следовательно, оставшиеся 480 товаров производителя А2 ставим в клетку (2,3). При этом товар производителей полностью распределён. Полученный начальный план проверим на оптимальность. План невырожденный, так как число занятых клеток (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. Задача 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,