Транспортная задача (1 а л.) 1 Определение транспортной модели
Определение оптимального плана перевозок методом потенциалов
жүктеу/скачать 0.49 Mb.
|
| 3.2.2 Определение оптимального плана перевозок методом потенциалов
Для определения оптимального плана транспортной задачи наиболее часто применяется метод потенциалов. Полученное на предыдущем этапе решение методом северо-западного угла следует проверить на оптимальность. Для этого, для каждого из пунктов отправления и назначения определяют числа ui и vj, которые называются потенциалами соответственно пунктов отправления и пунктов назначения. Эти числа находят из системы ui + vj = cij (3.6), где cij- тарифы, стоящие в занятых клетках. Так как число заполненных клеток равно (m+n-1), то система (3.6) с (m+n) неизвестными имеет (m+n-1) уравнений, т.е. число неизвестных превышает на единицу число уравнений. В этом случае, любому из неизвестных можно приписать значение, равное 0, а затем из системы (3.6) найти значения остальных неизвестных. После того, как потенциалы, найдены для каждой свободной клетки, определяют числа kij = ui+vj- cij (3.7), которые называются оценками плана. Е сли среди чисел kij нет положительных, то найденное решение является оптимальным. Если для некоторой свободной клетки kij >0, то опорное решение не является оптимальным, и необходимо перейти к новому опорному решению. Для этого рассматриваются все свободные клетки, для которых kij >0, и среди данных чисел выбирают максимальное. Клетку, которой соответствует это число, следует заполнить. Заполняя эту клетку, следует изменить объемы поставок в некоторых других занятых клетках, связанных с данной клеткой циклом. Циклом в таблице условий в транспортной задаче называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья вдоль строк и столбцов, причем в каждой вершине встречаются ровно два звена, одно из которых находится в строке, а другое в столбце. Если ломаная линия, образующая цикл пересекается, то точки пересечения не являются вершинами. При правильном построении опорного решения, для любой свободной клетки можно построить лишь один цикл. После того, как для выбранной свободной клетки, построен цикл, следует перейти к новому опорному решению. Для этого, нужно переместить грузы в пределах клеток, связанных с данной заполненной клеткой, это перемещение проводят по следующим правилам: В каждой из клеток, связанной циклом с данной свободной приписываем определенный знак, причем в свободной клетке ставим “+”, а всем остальным поочередно “-” и “+”, поэтому клетки называют минусовыми и плюсовыми. В данную свободную клетку переносят меньшее из чисел xij стоящее в минусовых клетках, одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая была свободной, становится занятой, а минусовая клетка, содержащая минимум xij становится свободной. В результате указанных перемещений грузов в пределах клеток, связанных циклом, получается новое опорное решение. Описанный выше переход от одного опорного решения к другому называется сдвигом по циклу пересчета. Следует заметить, что число связанных клеток при этом остается неизменным. Полученное новое опорное решение проверяется на оптимальность. В результате данного итерационного процесса, после конечного числа шагов, получают оптимальное решение. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|