Венгерский метод

2.  Венгерский метод.

Предварительный этап. Исходная матрица C:

Шаг 1. Обозначим через  наибольший элемент столбца  матрицы  (r₁=45, r₂=49, r₃=48, r₄=49, r₅=44, r₆=46, r₇=45, r₈=49). Каждый элемент -го столбца вычтем из , результаты вычислений будем помещать на место вычитаемого. Аналогичные преобразования проводим в остальных столбцах. Получим неотрицательную матрицу , в каждом столбце которой есть хотя бы один нуль.

Шаг 2. Преобразуем матрицу . Для этого обозначим через  минимальный элемент строки , который последовательно вычтем из элементов той же строки, результаты поместим на место уменьшаемого. Наименьший элемент первой строки матрицы  равен 7. Проведем вычисления для элементов первой строки: (d₁₁=7, d₁₂=29, d₁₃=30, d₁₄=1, d₁₅=27, d₁₆=22, d₁₇=0, d₁₈=17). Такие же вычисления проведем для остальных строк, получим неотрицательную матрицу , в каждом столбце и каждой строке которой есть хотя бы один нуль.

Основной этап. После второго шага предварительного этапа получим неотрицательную матрицу , эквивалентную матрице эффективностей :

П.1. В первом столбце матрицы  отметим звездочкой 0^*_7,1 ,во втором столбце – 0_6,2 , в третьем столбце – 0_4,3, в четвертом столбце – 0^*_3,4 , в шестом столбце – 0_8,6, в седьмом столбце – 0_{1,7 ,} в восьмом столбце – 0_5,8. Нули в пятом столбце – 0_4,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 0_4,3,. Число звездочек равно семи, что меньше размерности матрицы (8), переходим к п.2.

 ε=2

П.2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находится в четвертой строке пятого столбца 0_{4,5 ,} во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0^'_{4,5 ,} 0^'_{2,7 ,} 0'_6,7. Переходим к пункту 3.

П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.

П.2. Незанятых нулей нет, переходим к п.5.

П.5. Среди незанятых элементов находим минимальный, который обозначим через , ε=d_3,5=6. Преобразуем матрицу : незанятые элементы уменьшим на 6; дважды занятые увеличим на 6; остальные элементы оставим без изменения. Получим матрицу , в которой имеется один незанятый нуль, переходим к четвертому абзацу п.2.

П.2. Незанятый нуль находится в третьей строке пятого столбца 0_3,5 . Помечаем штрихом 0^'_3,5. Во второй строке седьмого столбца находится нуль со штрихом. Помечаем штрихом 0^'_2,7 и считаем седьмой столбец незанятым, знак «+» сверху снимаем, а вторую строку объявляем занятой и помечаем знаком «+» справа.

П.5. Переходим к пункту 2. Помечаем звездочкой 0*_6,5, штрихом 0^'_8,3, 0^'_2,7. В третьей нет , следовательно, переходим к пункту 4, ε=d_6,4=7 после преобразований, получим матрицу D₃

П.4. Строим цепочку из нулей. Начиная от только что отмеченного штрихом нуля (0^’_2,7), идем по строке до _5,2 цепочка состоит из двух элементов Ц: 0_7,2, 0^’_5,2. В матрице такие цепочки обозначают так . После преобразования получим новый набор нулей со звездочкой (), который содержит на одну звездочку больше, чем предыдущий набор.

Проводим следующие пересчеты.

Процесс окончен, так как число нулей со звездочкой равно размерности матрицы эффективности.

Оптимальный вариант выбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второго жениха, вторая невеста седьмого жениха, третья –восьмого, четвертая первого, пятая четвертого, шестая – шестого, седьмая невеста пятого жениха, а восьмая невеста выберет третьего жениха.

При этом максимальная суммарная эффективность (суммарная продолжительность жизни всех семей) равна:  (единиц эффективности)

Похожие работы

Экономико-математические методы и модели

Скачать

40642

1

0

... Ю.Н. Математические методы в экономике: Учебник.2-е изд. – М.: МГУ им. М.В. Ломоносова, Издательство «Дело и Сервис», 1999. – 368 с. 7.  Монахов А.В. Математические методы анализа экономики. – Спб: Питер, 2002. – 176 с. 8.  Экономико-математические методы и прикладные модели: Учеб. пособие для вузов /В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др., Под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999. ...

Экономико-математическая модель оптимизации распределения трудовых ресурсов

Скачать

82483

8

16

... того чтобы получить оптимальное решение нужно перейти на лист «Расчет» через основное меню, нажав кнопку «Расчеты». На листе «Расчет» представлена математическая модель оптимизации распределения трудовых ресурсов (рис 3.3) описанная в разделе 3.2. Данная модель использует надстройку «Поиск решений» MS Excel Рис 3.3. Для запуска надстройки «Поиск решений» MS Excel, необходимо в главном меню ...

Нахождение оптимальных планов производства продукции и их экономико-математический анализ

Скачать

11478

5

0

... продукции. Кроме того, т.к. объем ресурсов для оборудования дается в часах, а производительность оборудования в м¤/час, то необходимо перейти к соизмеримости. Таким образом, задача сводится к нахождению оптимального плана производства продукции каждого вида с целью получения максимальной прибыли. ЗЛП будет выглядеть так: Целевая функция: min Z = 0.51x1+0.57x2+0.13x3+0.33x4+0.38x5+0.72x6+0.23x7+0. ...

Функционирование рынка ценных бумаг в условиях нестабильной экономики России

Скачать

185716

7

6

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