1.6.2. Методы нахождения начального допустимого плана перевозок груза

 

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

 

1. Правило "северо-западного yглa"

Условия задачи записываем в виде таблицы. Распределение поставок по данному правилу проиллюстрируем на примере. Начинают распределение поставок из первого пункта производства к первому пункту потребления, т. е. с верхней левой клетки таблицы. После ее заполнения следующей должна загружаться одна из соседних к ней клеток: либо в той же строке, либо в том же столбце. Если ни в одну из соседних клеток нечего поставить (т.е. возможности соответствующих строки и столбца уже исчерпаны), то в любую из них ставится нуль и от нее продолжается процесс последовательнoго распределения поставок груза. Этот прием гарантирует получение в исходном плане необходимого количества занятых клеток, равного m+n-1.

аi bj	150	120	80	50
100	3 100	5	7	11
130	1 50	4 80	6	3
170	5	8 40	12 80	7 50

 

2. Метод наименьшей стоимости

В методе "северо-западного угла" первоначальный план совершенно игнорирует стоимости перевозок, так что он значительно отличается от оптимального плана. Рассмотрим теперь другой метод построения начального плана перевозок груза, получивший название "метод наименьшей стоимости". В этом методе учитывается матрица С транспортных издержек. Суть метода наименьшей стоимости состоит в следующем: в первую очередь заполняются клетки с минимaльной во всей таблице стоимостью перевозки груза (Сij). Грузопоток Xij определяется точно так же, как в методе "северо-западного угла", т. е. равняется наименьшему значению из остатка груза в i-м пункте отправления и недостающего груза в j-м пункте назначения.

В приведенном примере укажем последовательность заполнения клеток таблицы: x₂₁ =130 , х₁₁= 20 , х₁₂ = 80 , х₃₄ = 70, х₃₂ =40, х₃₃ =80.

Заполненные клетки таблицы, даже с нулевыми поставками, называются загруженными клетками, а пустые - свободными.

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

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

 

Проверка оптимальности плана и определение тек изменений, которые надо в него внести, могут производиться различными методами. Изложим один из них, основанный на вычислении для каждого пункта производства и каждого пункта потребления особых показателей, названных пoтeнцuaлами. Решение транспортной задачи этим методом состоит в нахождении такой системы потенциалов, при которой соблюдаются некоторые условия оптимальности. Идея этого метода принадлежит известному русскому математику Л.В. Канторовичу.

Критерий оптимальности решения транспортной задачи:

Допустимый план является оптимальным в том и только том случае, если каждому пункту производства и каждому пункту потребления могут быть поставлены в соответствие такие числа u_i и v_j (называемые потенциалами), которые удовлетворяют следующим условиям:

v_j-u_i<=с_ij - для свободных клеток таблицы;

v_j- u_i = с_ij - для загруженных клеток таблицы (х_ij > 0).

Объясним смысл этого положения. Если план оптимален, то грузам в пунктах отправления и назначения можно присвоить такие оценки (потенциалы), при которых перевозка из любого пункта отправления в любой пункт назначения не могла бы принести прибыль и чтобы в то же время перевозки, внесенные в план, являлись безубыточными.