Транспортная задача (1 а л.) 1 Определение транспортной модели
жүктеу/скачать 0.49 Mb.
|
| 3.4 Задача о назначениях
Математическую постановку транспортной задачи, можно применить к некоторым другим задачам специального вида. Рассмотрим задачу о назначениях. В общем виде она звучит следующим образом. Требуется распределить m работ или исполнителей по n станкам, cij - затраты выполнения i-ой работы на j-том станке. Надо распределить работы по станкам так, чтобы затраты на выполнение всей работы были минимальны. Можно рассматривать эту задачу как транспортную, где работы интерпретируются как исходные пункты, а станки - конечные. При этом все ai и bj равны 1. Если на i-ом станке работу j выполнить нельзя, то данное назначение не рассматривается вообще. При данном подходе исходные данные задачи о назначениях представляются в следующей таблице: Объем запасов станки 1 2 n 1 с11 с12 ... с1n 1 работы 2 с21 с22 ... с2n 1 .... ... ... ... ... ... m сm1 сm2 ... сmn 1 Спрос 1 1 ... 1 Матрица, в которой задаются стоимости cij выполнения работ, называется матрицей стоимостей. Чтобы решить задачу о назначении методом транспортной задачи, она должна быть сбалансированной. Для задачи о назначении это означает, что число работ должно быть равно числу исполнителей. Для ликвидации дисбаланса необходимо вводить фиктивные работы или станки. При этом стоимости cij для фиктивных станков или работ выбираются равными штрафу за простой станка или невыполнение работы. Далее рассматривается сбалансированная задача о назначениях, которой соответствует квадратная матрица стоимостей (n=m). Пусть хij = 0, если j-я работа выполняется на i-ом станке, и хij 0, если j-я работа не выполняется на i-ом станке. Тогда задача о назначениях формализуется, как задача линейного программирования, в следующем виде: Для решения задачи о назначениях используется более эффективный алгоритм, чем алгоритм транспортной задачи, который называется венгерским методом. Согласно данному методу оптимальное решение задачи не изменится, если к любой строке или столбцу матрицы стоимостей прибавить или вычесть постоянную величину. Если при этом можно построить новую матрицу стоимостей cij' с нулевыми элементами и эти элементы соответствуют допустимому решению, то такое решение будет оптимальным. В случае, если не удается сразу организовать оптимальное решение по нулевым элементам, то в соответствие с венгерским алгоритмом надо выполнить следующую процедуру: Проводится минимальное число прямых через некоторые строки и столбцы с тем, чтобы все нули были вычеркнуты. Затем выбирается меньший не вычеркнутый элемент и он прибавляется к каждому элементу, стоящему на пересечении проведенных прямых, и вычитается из каждого не вычеркнутого элемента. В результате увеличивается количество нулевых элементов. Если после этого шага не удается организовать оптимальное решение, то процедура вычеркивания нулей продолжается. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|