Решение открытой транспортной задачи

    Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равно разности двух сумм: = , где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком  «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком

 «-».

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

    

    Если  разность сумм для свободной клетки (l, k) меньше нуля, т.е. <0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z( ) на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками , для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие    =0.           (11)

    Для решения транспортной задачи распределительным  методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину = . В результате получится новое опорное решение.

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

     2.Разработка  и описание алгоритма  решения задачи

     2.1. Содержательная постановка  задачи 

      Составить экономико-математическую модель задачи. Найти оптимальное распределение поставок и минимальные затраты на перевозку. Первоначальное распределение поставок выполнить методом северо-западного угла.

Таблица№2 

 
 
 
 

     2.2.Построение  математической модели  задачи

          Метод Северо-западного угла.

     При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка ("северо-западный угол") оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки переменного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок.

Таблица №3 

=          

18*5+21*7+11*6+22*5+18*0+20*0=413

     2.3.Решение  задачи вручную  

Находим значение потенциалов:

U_i+V_j=C_i,j(i=1..m, j=1..n),

U₁ + V₁=5

U₁ + V₂=7

U₁  + V₃=6

U₂ + V₃=5

U₂ + V₄=0

U₃ + V₄=0

U₁ =0

U₂=-1

U₃=-1

V₁=5

V₂=7

V₃=6

V₄=1

Определяем  значения оценок _ij=C_ij-U_i-V_j для всех свободных клеток:

=

= =2

= =0

3

=0

Строим  оценочную матрицу:

=

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

Находим число пересчета по циклу =min , которое равно минимальному

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

 
 
 

Составляем  новую матрицу, добавив  в клетки отмеченные плюсом прибавляем, и отнимаем из значение из клеток отмеченные минусом. Получаем новое решение X

 

=

18*5+1*7+31*6+2*5+38*0+20*4=373

В оценочной  матрице подчеркиваем элементы соответствующие  базисным в новом решении. Строим цепочку выделения. Она строится от особо выделенного элемента (элемент )  по строкам, затем по столбцам. Каждый элемент, попавший в цепочку выделяет и строку, и столбец кроме выделенного элемента.

Прибавляем  к выделенным строкам  (выделенный элемент по модулю), из столбца вычесть.

=

 

=

18*5+1*7+31*0+33*5+7*0+20*4=342 

=

=min =1

=

=

Так как  в оценочной матрице  , нет отрицательных элементов матрица Х_3,  становиться оптимальна.

18*5+32*0+1*6+33*5+6*0+20*4=341 
 

 
 
 
 

   

   

      2.4. Решение задач  с помощью Excel

Таблица №4 

      

        

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

    Рассмотрим, как это можно сделать в  среде электронных таблиц Microsoft Excel.

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

   1. Введите  в ячейки диапазона A6:D8 значения спроса

   2. Введите  в диапазон ячеек A9:D9 матрицу расходов.

   3. Введите  в ячейки диапазона E6:E8 запасы.

   4. В  ячейку E9 выводиться оптимальное решение

   =СУММПРОИЗВ(A1:D3;A6:D8). Сделать это можно при помощи  мастера функций выбрав в разделе. Математические функцию СУММПРОИЗВ и указав необходимый диапазон.

   

    

    

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

    В диалоговом окне Параметры поиска решения установить флажок Линейная модель. После нажатия кнопки. Выполнить средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы.

    

    

   

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