Решение транспортной задачи венгерским методом на ЭВМ
Для решения данной задачи используем программу 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.