Логистика: задача по грузоперевозке (речной транспорт)

      (тыс. т).

     Удельные  транспортные затраты по перевозкам грузов от поставщика фиктивному потребителю  принимается равным 1000 руб./т.

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

Таблица 1.2  - Матрица исходных данных

 

     Составляется  начальный план методом аппроксимации  Фогеля. По каждой строке и каждому  столбцу матрицы находится разность между двумя наименьшими значениями с_ij. Эти разности заносятся в специальные «поля» разностей по строкам и столбцам, которые достраиваются к исходной матрице справа и снизу (таблица 3). Затем из всех полученных разностей выбирается наибольшее значение. Если это наибольшее значение разностей получилось в столбце, то для анализа выбирается этот столбец, в котором загружается клетка с наименьшим значением с_ij, исходя из условия

      .                                                                                            (1.8)

     Если  наибольшее значение разностей получилось в строке, то анализируются строки и также загружается клетка с  наименьшим значением , исходя из условия (1.8).

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

Таблица 1.3 – Начальный план 1

 

      .

      .

      .

      .

      .

      .

      .

     Значение  целевой функции:

       

     Составляется  начальный план методом минимального элемента.

     Анализируется вся матрица, и все клетки матрицы  нумеруются в порядке возрастания, начиная с минимального. Если в  процессе оказывается две или  более клетки с одинаковыми значениями, то они нумеруются произвольно.

     Далее в той же последовательности загружаются базисные клетки из условия (1.8), исключая те столбцы и строки, ресурсы которых исчерпаны.

     В таблице 1.4 нумерация клеток дана в  правом верхнем углу каждой клетки.                                                                                    

Таблица 1.4 – Начальный план 1

 

      .

     Ресурсы третьего столбца исчерпаны. Следующей  будет загружаться клетка 1-1.

      .

      .

      .

      .

      .

     Проверяются ограничения задачи (1.2), (1.3), (1.4). При  суммировании по столбцам условия выполняются.

     Значение  целевой функции

       

     Для проверки на оптимальность выбирается начальный план, составленный методом минимального элемента. Проверяем план на невырожденность.

      ;                                                                                                 (1.9)

     где - необходимое число базисных клеток в матрице;

           - количество строк в матрице;

           - количество столбцов в матрице.

     В теории линейного программирования доказано, что оптимальный план всегда находится в числе невырожденных планов.

      ,  - следовательно, план невырожденный.

     План считается оптимальным, если выполняется условие для базисных клеток

      ;                                                                                                  (1.10)

     для свободных клеток

      ;                                                                                                  (1.11)

     где и - соответственно потенциалы строк и столбцов.

     Принимаем   .

     Далее по загруженным клеткам рассчитываются остальные потенциалы (таблица 1.4).

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

     Рассчитываем  характеристики свободных клеток

      ;    ; (-)

      ;    ;   (-)

      ;   ;     (+)

      ;    ;   (-)

      ;    ;   (-)

      ;    ;     (-)

      ;      ;     (+)

      ;     . (-)

     План, представленный в таблице 1.4 не оптимален, так как условие (1.11) не выполняется  для клеток (1-2) и (1-4). План может быть улучшен за счет перераспределения порожних перевозок.

     Выбирается  клетка с наибольшим отклонением  от оптимальности. Через эту клетку строится контур перераспределения.

     Перерасчет  неизвестных и контур перераспределения  начинается с клетки (1-2). Эту клетку необходимо загрузить на некоторую  величину .

     Клетка (1-2) ;          ;

     Клетка (1-4) ;        .

     Находим и

      ;    ;   ;

      ;    ;   .

     Минимальный элемент в цепи перераспределения  выбирается из условия

      .

     Подставляя  найденное значение , рассчитываются значения неизвестных и составляется новый план.