yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->            7.3. Критерий оптимальности базисного распределения поставок

Исследование операций

            7.3. Критерий оптимальности базисного распределения поставок

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

            Запишем функцию цели в виде

                                   ,

где F0 – суммарные затраты на перевозку данного распределения поставок,

      βij – коэффициент при xij свободной переменной,

      xij – свободная переменная, которая в транспортной задаче отождествляется с пустой (i,j)-той клеткой,

     многоточием обозначены все остальные свободные переменные и коэффициенты при них.

Положим , т.е. единичную поставку в -тую клетку, тогда

                       

Коэффициент βij будет равен приращению затрат, вызванных единичной поставкой -тую клетку. При , при .

            Таким образом, для уменьшения затрат следует производить поставки в клетки, имеющие отрицательную оценку. Коэффициент βij называется оценкой свободной клетки и определяется по так называемому циклу пересчета.

            Цикл пересчета – это несколько клеток таблицы поставок, из которых одна свободная, все остальные заполненные, соединенные замкнутой ломаной линией, делающей поворот на 90о в каждой клетке. Свободной клетке присваивается знак «+». Это значит, что в нее будет осуществлена поставка. Знаки в остальных клетках чередуются. Цикл, снабженный знаками клеток, называется означенным.

            Оценка свободной клетки равна алгебраической сумме коэффициентов затрат клеток, входящих в цикл пересчета.

            Определим, например, оценку свободной клетки (2,1) для таблицы поставок 7.2,

 

 

 

 

 

Означенный цикла для определения свободной клетки (3,1)

 

 

 

 

 

 

 

 

 

 

 

21