Требуется выбрать и дать техническое и экономическое
 Скачать 216.11 Kb.
|
Таблица8
При этом индексы Ui, записывают в клетки вспомогательного столбца, а индексы Vj - в клетки вспомогательной строки (табл. 8). Для определения индексов используют следующие правила: индекс первой клетки вспомогательного столбца всегда равен нулю (Ui = 0); для каждой занятой клетки матрицы сумма соответствующих ей индексов U и V (записанных против нее сверху и сбоку во вспомогательных клетках) равна расстоянию, указанному в данной клетке. Из последнего правила следует, что если у занятой клетки один из индексов известен, то другой равен разности ее расстояния и известного индекса, т.е. Ui = Lij-Vj и Vj = Lij-Ui (1) Запишем в матрицу индекс Ui = 0. Тогда у занятых клеток A1Б1 А1Б3 и А1Б4 один индекс известен и можно, используя равенство (1), определить индексы V1, V2 и V4 (табл.9): V1=L11-U1 = 9-0=9 V3 = L13- U1 = 5-0=5 V4 = L14 – U1 = 8-0=8 Теперь у занятой клетки А2Б1 известен индекс V1 и можно найти индекс U2 = L22 U2 = 4-9 = -5. После этого определяем индекс V2, а затем индекс U3: V2=L22 - U2 = 9 - (-5) = -5 и U3 = L32 - V2 = 22 - 14 = 8 Таблица9
Таким образом, все индексы найдены (табл. 9) и можно приступить к проверке плана, которая сводится к сравнению расстояния каждой незанятой клетки матрицы с суммой соответствующих ей индексов с целью выявления клеток, в которых расстояние меньше указанной суммы. В нашем примере имеем: (U1 + V2 = 0 + 14)<(L12=15) (U2 + V3 = -5 + 5)<(L23=6) (U2 + V4 = -5 + 8)<(L24=5) (U3 + V1 = 8 + 9 =17) > (L31 = 16) (U3 + V3 = 8 + 5 = 13) > (L33 = 10) (U3 + V4 = 8 + 8)<(L34=18) У незанятых клеток А3Б1 и А3Б3 расстояние меньше суммы их индексов. Следовательно, составленный план не является оптимальным. 4. Улучшение неоптимального плана. Выявленные на предыдущем этапе вычислений клетки А3Б1 и А3Б3 являются резервом улучшения плана и потому их называют потенциальными, а превышение суммы индексов над расстоянием потенциалом. Процедура улучшения неоптимального плана сводится к перемещению загрузок в потенциальные клетки матрицы. Поскольку нельзя просто переставить в потенциальную клетку одну из загрузок, не нарушив итоги по строкам и столбцам, разработан специальный способ перемещения загрузок. Он состоит из составления цепочки возможных перемещений загрузок в матрице, определения величины загрузки, подлежащей перемещению, и собственно перемещения. Цепочку возможных перемещений определяют следующим образом. Для потенциальной клетки с наибольшим потенциалом строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна ее вершина лежала в данной потенциальной клетке, а все остальные - в занятых клетках. Такую цепочку всегда можно построить и притом единственным способом. Ее вершины отмечают клетки матрицы, которые должны участвовать в перераспределении загрузок с целью улучшения плана. Возможны различные конфигурации цепочек. Составив цепочку, помечают знаком «+» ее нечетные вершины (считая первой вершину в потенциальной клетке), а четные знаком «—». Наименьшая из четных загрузок определяет величину перемещаемой загрузки. Уменьшив на эту величину объемы перевозок, записанные в клетках со знаком минус, и увеличив на ту же величину объемы клеток со знаком плюс, получают новый вариант плана с меньшей транспортной работой. В рассматриваемом примере построена цепочка для потенциальной клетки А3Б3 и расставлены знаки (табл. 10).  Таблица10
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||