Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Постановки задачи:
Пример 13.1. Требуется распределить m работ (или исполнителей) по n станкам. Работа i (i =1,..., m), выполняемая на станке j (j=1,..., n), связана с затратами. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат cij.
Пример 13.2. C= (cij) – стоимость производства детали i на станке j нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.
Пример 13.3. Транспортная задача. Заданы пункты производства товара, пункты потребления товара. Требуется определить оптимальное взаимно-однозначное соответствие между пунктами производства и пунктами потребления, исходя из матрицы стоимостей перевозок C между соответствующими пунктами (т.е. минимизировать суммарную стоимость перевозки).
Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) работы i к станку j равна cij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу.
Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.
Пусть = 0, если j -я работа не выполняется на i -м станке, = 1, если j -я работа выполняется на i -м станке. Таким образом, решение задачи может быть записано в виде двумерного массива . Допустимое решение называется назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в каждом столбце этой матрицы.
Замечание 1. Для заданного значения n существует n! допустимых решений.
Математическая модель задачи:
Минимизировать функцию , при ограничениях:
, (12.1)
, (12.2)
.
Ограничения (12.1) необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения (12.2) гарантируют, что каждому станку будет приписана ровно одна работа.
Пример 13.4. Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками. Стоимость производства детали i на станке j:
Нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.
Специфическая структура задачи о назначениях позволяет использовать эффективный метод для ее решения.
Замечание 2. Оптимальное решение задачи не изменится, если из любой строки или столбца матрицы стоимостей вычесть произвольную постоянную величину.
Приведенное замечание 2 показывает, что если можно построить новую матрицу с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным.
.
Оптимальное назначение: , , , остальные , .
К сожалению, не всегда удается определить решение так просто. Для таких случаев рассмотрим следующий алгоритм.
Дата публикования: 2014-11-02; Прочитано: 754 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!