5.2 Построение исходного опорного плана Правило «северо-западного угла».

Для составления исходного плана перевозок удобно пользо­ваться правилом «северо-западного угла», которое состоит в сле­дующем.

Будем заполнять, начиная с левого верхнего, услов­но называемого «северо-западным углом», двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1; 1) меньшее из чисел и , т. е. . Если , то и первый столбец «закрыт», т. е. спрос первого потребителя удовлетворен полностью. Это означает, что для всех остальных клеток первого столбца количество груза для .

Двигаясь дальше по первой строке таблицы, записываем в со­седнюю клетку (1, 2) меньшее из чисел и , т. е. .

Если , то аналогично «закрывается» пер­вая строка, т. е. , для . Переходим к заполнению соседней клетки (2; 1), в которую заносим .

Заполнив вторую клетку (1; 2) или (2; 1), переходим к за­полнению следующей третьей клетки по второй строке либо по второму столбцу. Будем продолжать этот процесс до тех пор, по­ка на каком-то этапе не исчерпаются ресурсы и потребности . Последняя заполненная клетка окажется лежащей в последнем -м столбце и в последней -й строке.

Правило «минимального элемента».

Исходный опорный план, построенный по правилу «северо-западного угла», обычно оказывается весьма далеким от опти­мального, так как при его определении не учитываются величины затрат . Поэтому в дальнейших расчетах потребуется много ите­раций для достижения оптимального плана. Число итераций мож­но сократить, если исходный план строить по правилу «минималь­ного элемента». Сущность его состоит в том, что на каждом шаге осуществляется максимально возможное «перемещение» груза в клетку с минимальным тарифом .

Заполнение таблицы начинаем с клетки, которой соответст­вует наименьший элемент матрицы тарифов. В клетку с наи­меньшим тарифом помещают меньшее из чисел или . Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответ­ствующий потребителю, спрос которого полностью удовлетворен. Может оказаться, что следует исключить строку и столбец одно­временно, если полностью израсходованы запасы поставщика и полностью удовлетворен спрос потребителя. Далее из оставших­ся клеток таблицы снова выбирают клетку с наименьшим тарифом и процесс распределения запасов продолжают до тех пор, пока все они не будут распределены, а спрос удовлетворен.

5.3 Метод потенциалов

Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи ЛП симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.

Сущность метода потенциалов состоит в следующем. После того как найден исходный опорный план перевозок, каждому по­ставщику (каждой строке) ставим в соответствие некоторое число , называемое потенциалом поставщика , а каждо­му потребителю (каждому столбцу) – некоторое число назы­ваемое потенциалом потребителя .

Стоимость тонны груза в пункте равна стоимости тонны груза до перевозки + затраты на ее перевозку : .

Чтобы решить транспортную задачу методом потенциалов, необходимо:

1. Построить опорный план перевозок по одному из изложенных правил. Число заполненных клеток должно быть .

2. Вычислить потенциалы и соответственно по­ставщиков и потребителей (для занятых клеток): . Число заполненных клеток – , а число уравнений – . Т.к. число уравнений на единицу меньше числа неизвестных, то одно из неизвестных оказывается свободным и может принимать любое числовое значение. Например, . Остальные потенциалы для данного опорного решения определятся однозначно.

3. Проверить на оптимальность, т.е. для свободных клеток вычислить оценки . Если , то перевозка целесообразна и план оптимален – признак оптимальности. Если хотя бы одна разность , то переходят к новому опорному плану. По своему экономическому смыслу величина характеризует то изменение в суммарных транспортных расходах, которое произойдет из-за осуществления единичной поставки м поставщиком му потребителю. Если , то единичная поставка приведет к экономии транспортных расходов, если же – к увеличению их. Следовательно, если среди свободных направлений поставок нет экономящих транспортные расходы направлений, то полученный план оптимален.

4. Среди положительных чисел выбирают максимальное, строят для свободной клетки, которой оно соответствует цикл пересчета. После того как для выбранной свободной клетки цикл построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой циклом пересчета.

Перемещение производят по следующим правилам:

а) Каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем данной свободной клетке «+», а всем остальным клеткам (вершинам цикла) – поочередно знаки «–» и «+». Будем называть эти клетки минусовыми и плюсовыми.

б) В минусовых клетках цикла находим минимальную поставку, которую обозначим через . В данную свободную клетку переносят меньшее из чисел , стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком «+», и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой и входит в опорный план; а минусовая клетка, в которой стояло минимальное из чисел , считается свободной и выходит из опорного плана.

Таким образом определили новый опорный план. Описанный выше переход от одного опорного плана к другому называется сдвигом по циклу пересчета. При сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным . При этом если в минусовых клетках имеется два или более одинаковых числа , то освобождают лишь одну из таких клеток, а остальные оставляют занятыми с нулевыми поставками.

5. Полученный опорный план проверяют на оптимальность, т.е. повторяют все действия с п.2.