Экономмико-математические методы и модели

     Задача  состоит в определении такого плана перевозок, при котором  весь продукт вывозится из пунктов  А_i в пункты  В_j в соответствии с потребностью и общая величина транспортных издержек будет минимальной. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью.

     Стоимости  С_ij перевозки единицы продукции заданы в виде таблицы 9.

     Решение:

     1) Для первоначального (опорного) закрепления потребителей за поставщиками воспользуемся методом северо-западного угла.

     Число занятых клеток m + n – 1 = 4  + 5 = 8. 

                                                                                                                                              Таблица 9.     

 
     

     Пусть пункт В₁ подал заявку на 28 единиц груза. Удовлетворим её из запасов А₁. Но так как запасов А₁ не хватило для удовлетворения всего спроса, то оставшиеся 28 – 25 = 3 единиц продукции мы возьмем у второго поставщика. После этого у поставщика А₂ осталось еще        45 – 3 = 42 единицы продукции. Из этого остатка удовлетворим потребность пункта В₂ в продукции, которая составляет 25 единиц. Рассуждая подобным образом составим таблицу 10, в которой в левом углу укажем стоимости С_ij перевозки единицы груза из А_i в В_j, а внизу клетки – перевозку X_ij.  

                                                                                                                           Таблица 10.     

     Суммарные затраты на реализацию данного плана перевозок составят:

       (X) = 9*25 + 7*5 + 8*10 + 10*30 + 10*2 + 12*33 + 12*7 + 16*38 = 1406 

     Данный  результат явно не является оптимальным. Попробуем составить план перевозок  с помощью другого метода распределения  и сравним полученный результаты.

     2) Метод наименьших стоимостей или метод двойной оценки.

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

     В клетки, отмеченные двумя плюсами, помещают максимально возможное число единиц продукции, разрешенное ограничениями на поставку и потребление. Далее идет распределение в клетки, отмеченные одним плюсом. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы полностью удовлетворены.

     В таблице 11. показан результат распределения продукции по данному методу.

                                                                                                                        Таблица 11.     

 

     Суммарные затраты на реализацию данного плана перевозок составят:

       (X) = 6*25 + 10*13 + 10*2 + 8*32 + 8*40 + 7*30 + 14*8 = 1048

     Следовательно, данный план перевозок ближе к  оптимальному, чем план, составленный по методу северо-западного угла.

2.5. Проверка оптимальности полученных планов перевозок методом потенциалов

     1) Рассмотрим процесс нахождения потенциалов для базисного распределения по методу северо-западного угла по данной формуле v_j – u_i = C_ij и представим в виде таблице 12.  

                                                                                                                                         Таблица 12.

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

                                     d_ij  = (u_i + C_ij) - v_j

      Оценки клеток удобно представить в виде матрицы оценок. Для распределения, полученного методом северо-западного угла, матрица оценок имеет вид:

               0   0   6  -3   -8                   

               2   0   0  -4   -1                   

d_ij  =             -4  2   0   0   -2

               6   2   0   0    0

     Наличие большого числа отрицательных оценок свободных клеток свидетельствует  о том, что данный план перевозок  долек от оптимального. Что бы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой, если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой.  В нашем случае этой клеткой может служить клетка (5; 1).

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

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

     Результат указанных операций для представленного  в таблице 10 распределения поставок показан в таблице 13.

                                                                                                                                   Таблица 13.