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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.1.