Математическое программирование

 
 
 
 
 
 
 
 
 
 
 
 
 

Запишем матрицу  распределения груза:

     

     Стоимость перевозки согласно новому опорному плану равна:

     F=15*8+20*5+25*6+20*8+30*7+30*6=120+100+150+160+210+180=920

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

             

Произведем оценку свободных клеток: 

     Т.к. среди оценок есть отрицательная (-1), то найденный опорный план также  не является оптимальным.

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

     

Согласно новому циклу пересчета строим таблицу

 
 
 
 
 
 
 
 
 
 
 
 

Запишем матрицу  перевозок:

     

     Стоимость перевозки согласно новому опорному плану равна: 

     F=15*7+30*6+10*6+35*8+35*5+15*7=105+180+60+280+175+105=905 

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

               

Произведем оценку свободных клеток:

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

 и минимальная стоимость  перевозки равна F=905 (ден. ед.) 

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

      1). Находят опорный план. При этом число заполненных клеток должно быть равным n+m-1.

      2). Находят потенциалы U_i и V_j соответственно пунктов отправления и назначения.

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

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

      5) Полученный опорный план проверяют  на оптимальность, т.е. снова  повторяют все действия, начиная  с этапа 2. 
 
 

      Замечание.

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

      7.2. Решение задач  открытого типа. 

      Рассмотрим  задачу открытого типа (количество запасов превышает количество потребностей).

      Данные  к задаче приведены в таблице: 

      Суммарное значение запасов равно:

      Суммарное значение потребностей равно:

      Следовательно, для того, чтобы задача стала закрытой, необходимо ввести фиктивного потребителя В₅ с тарифами на перевозку, условно равными нулю и потребностью, составляющей разность между суммарной потребностью и суммарным запасом (560-480=80). 

 

      С помощью метода минимального элемента распределим груз. Данному распределению будет соответствовать матрица перевозок

      

      Стоимость перевозки, соответствующая данной матрице будет равна

      F=120*1+220*2+10*3+60*1+70*2=120+30+440+60+140=790

Проверим полученный опорный план на оптимальность.

               

      Произведем  оценку свободных клеток:

      Среди полученных оценок нет ни одной отрицательной, значит полученный опорный план можно считать оптимальным. Таким образом оптимальный план перевозки грузов соответствует матрице перевозок X₁ и стоимость такой перевозки равна 790 денежных единиц.

      Аналогично  решается задача, в которой суммарный  запас груза меньше потребности в нем. В этом случае вводится фиктивный пункт отправления с тарифами, условно равными нулю. Далее задача решается рассмотренным выше способом. 

     7.3. Определение оптимального плана транспортной задачи, имеющей усложнения в условиях. 

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

1. В реальных условиях перевозки груза из определенного пункта отправления A_i в пункт назначения B_j не могут быть осуществлены. В этом случае предполагают, что тариф, соответствующий C_ij, является сколь угодно большим и полагают его равным М. Затем решают задачу известными методами. В оптимальном плане этой задачи исключается перевозка груза из A_i в B_j. Такой подход к решению транспортных задач называется запрещением перевозок или блокированием соответствующей клетки.
2. В некоторых транспортных задачах необходимо обеспечить перевозки по указанным маршрутам определенного количества груза: из п.А_i в п.В_j требуется обязательно перевести аij единиц груза. Тогда в клетку на пересечении строки A_i и столбца B_j записывают это количество груза а_ij, присваивают сколь угодно большой тариф М и считают клетку свободной. Затем решают транспортную задачу обычными методами.
3. Из п.А_i в п.В_j должно быть завезено не менее заданного количества грузов а_ij. Для определения оптимального плана такой транспортной задачи уменьшают запасы п.А_i и потребности п.В_j на а_ij единиц.
4. В некоторых транспортных задачах из пункта отправления А_i в п. назначения В_j должно быть переведено не более а_ij, т.е. . В этом случае вводится дополнительный столбец , т.е. вводят дополнительный план назначения. В новом столбце записывают те же тарифы, что и в столбце В_j, кроме клетки, на пересечении с i–ой строкой, тариф k–й строки считают равным сколь угодно большому числу М. Потребности п. B_j считают равными a_ij , а потребности дополнительного столбца полагают равными b_j-a_ij. Решение полученной транспортной задачи может быть найдено методом потенциалов.

 

     Пример. Найти решение транспортной задачи при дополнительных условиях:

     1). из А1 в В1 должно быть  перевезено не менее 50 единиц  груза ( );

     2). из А3 в В5 - не менее 60 единиц  груза ( );

     3). из А2 в В4 – не более  40 единиц груза ( ). 

 

Учитывая  условие 1, уменьшим запас А₁ и потребность В₁ на 50 единиц (110 и 40 соответственно).

Учитывая  условие 2, уменьшим запас А₃ и потребность В₅ на 60 единиц груза (30 и 80 соответственно).

Учитывая  условие 3, введем дополнительный пункт  назначения с потребностями 70-40=30 единиц груза, а потребности п.В₄ составляют 40 единиц груза.