Математическая постановка транспортной задачи линейного программирования и решение её различными методами

Объединяя два последних неравенства в одно двойное, окончательно получаем

C¢¢M ? Z ? C¢ M,

т. е.  линейная функция ограничена на множестве  планов транспортной задачи.

 

1.3. Открытая модель транспортной задачи

 

         Транспортная задача, в которой суммарные запасы и  потребности не совпадают, т. е. не выполняется  условие  , называется открытой. Для открытой модели может быть два случая:

1. суммарные запасы превышают суммарные потребности ;
2. суммарные потребности превышают суммарные запасы .

     Линейная  функция одинакова в обоих  случаях, изменяется только вид системы  ограничений.

 Найти  минимальное значение линейной  функции

 при ограничениях

,    i = 1, 2, ..., m,                           (случай  а)

,    j = 1, 2, ..., n;

,    i = 1, 2, ..., m,                           (случай б)

,   j = 1, 2, ..., n,

x_ij ³ 0   (i = 1, 2, ..., m;    j = 1, 2, ..., n).

     Открытая  модель решается приведением к закрытой модели.

 В  случае (а), когда суммарные запасы  превышают суммарные потребности,  вводится фиктивный потребитель  B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают

 

суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого a_m+1 = .

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

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

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

 
 
 
 
 
 
 
 
 

     Глава 2. Методы нахождения опорных и оптимальных планов.

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

 

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

      Число переменных X_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1  отличных от нуля неизвестных.

      Если  в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.

      Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

    При составлении первоначального  опорного плана методом северо-западного  угла стоимость перевозки единицы  не учитывается, поэтому построенный  план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ.

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

      Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Одна из них - метод потенциалов - рассматривается ниже.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

    Пример.

      
 
 
 
 
 
 

    Заполнение  таблицы начинается с ее северо-западного  угла, т. е. клетки с неизвестным . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .

    Теперь  переходим к заполнению клетки для  неизвестного и т.д.

    Через шесть шагов у нас останется одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными .

Опорный план имеет вид;

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.3. Метод минимального элемента

 

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

Пример 

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

 

Решение:

Задача  сбалансирована.

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

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

 

  

6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).  
    
   

Опорный план имеет вид:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.4. Метод аппроксимации Фогеля

 

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