Решение транспортной задачи венгерским методом на ЭВМ

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

 

 

Рис. 5.1. Исходные матрицы для решения транспортной задачи.

 

Суммарная эффективность определяется, как СУММПРОИЗВ(C8:G12;C17:G21).

Для решения транспортной задачи венгерским методом в таблице результатов решения задаются проверки ограничений:

3. Определяются суммы по строкам (СУММ С17:G17).

4. Определяются суммы по столбцам (СУММ С17:С21).

Для решения транспортной задачи в Microsoft Excel воспользуемся функцией «Поиск решений». В меню «Сервис», переходим в пункт «Надстройки», в доступных надстройках выбираем «Поиск решения».

При выполнении функции «Поиск решения» необходимо установить целевую ячейку.

Целевая ячейка для примера 1 будет равна максимальному значению, а для примера 2 -минимальному значению. Целевая ячейка задается в ячейке, где определяется суммарная эффективность решения задачи. Далее, указываем диапазон ячеек, где подбирается возможный вариант решений ($C$176: $G$21). Задаем ограничения, согласно условиям транспортной задачи (рис.5.2.).

 

 

Рис. 5.2. Поиск решения транспортной задачи для примера 1.

 

Выполнив функцию «Поиск решения», получаем оптимальное решение транспортной задачи венгерским методом. Рисунок 5.3. - для примера 1 (определение максимальной суммарной эффективности), а рисунок 5.4. – для примера 2 (определение минимальной суммарной эффективности).

 

Рис. 5.3. Результаты решения транспортной задачи (пример 1).

 

Рис. 5.4. Результаты решения транспортной задачи (пример 2).

 

Варианты заданий.

Задача: Имеются 5 лесопунктов и 5 комплектов лесозаготовительного оборудования (5 технологических линий). Каждая технологическая линия может дать производительность С(ij).

Выполнить: Распределить технологические линии по лесопунктам, чтобы общая производительность была максимальной или минимальной.

5. Сформулировать задачу. Привести математическую постановку задачи.

6. Решить задачу с краткими пояснениями.

7. Решить задачу на ЭВМ.

8. Сделать выводы по полученному результату.

Задание выбирается по последней и предпоследней цифре зачетной книжки. Исходные данные берутся в таблице по последнему номеру зачетной книжки (таблица 5.1). Если предпоследняя цифра зачетной книжки четная- то производительность должна быть максимальной, если -нечетная, то производительность должна быть минимальной.

 

Таблица 5.1.