Решение задачи о назначениях

Еще одна из выделенных задач линейного программирования, о которой важно упомянуть - это задача о назначениях. Вообще говоря, можно считать, что это частный случай транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность). Если на примерах, это может быть задача назначения работников на должности (с достижением максимальной эффективности, или, может, минимальных затрат на зарплату), назначение машин на производственные линии и т.п., при этом один исполнитель (человек, машина, орудие и т.п.) может выполнять только одну работу.

Так же как для решения транспортной задачи был модифицирован симплекс-метод и разработан метод потенциалов, так и для задачи о назначениях был создан более подходящий (более краткий) метод решения. Чаще всего используется так называемый венгерский метод (см. решение примера 1 ниже).

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

Задача о назначениях: примеры решений онлайн

Задача 1. Решить задачу об оптимальном назначении с матрицей эффективностей A.

Решение венгерским методом (pdf, 30 Кб)

Задача 2. Решить задачу о назначениях.

Решение задачи о назначениях (pdf, 85 Кб)

Задача 3. Четыре работника должны выполнять четыре вида работ. Назначить работников на работы методами динамического программирования и ветвей и границ таким образом, чтобы затраты труда были минимальны.

Решение задачи о назначениях методом ветвей и границ (pdf, 97 Кб)


Решим задачу о назначениях на заказ