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

ЦЕЛЬ РАБОТЫ

1)  Приобрести практические навыки и опыт решения транспортной задачи (ТЗ) линейного программирования в матричной постановке;

2)  Научиться анализировать полученное решение и находить альтернативные варианты решения; увидеть связь между ТЗ и общей задачей линейного программирования, между различными моделями ТЗ.

УСЛОВИЕ ЗАДАЧИ

Транспортная фирма обслуживает трех поставщиков однородного груза и пять потребителей этого груза. В течение дня из каждого пункта поставки фирма должна вывезти соответственно 80, 320, 225 тонн груза, а в каждый пункт потребления доставить соответственно 215, 110, 120, 90, 125 тонн. Себестоимость перевозки одной тонны груза от i – го поставщика j – ому потребителю составляет c_ij тыс. руб.

          Найти такой план перевозки грузов, при котором издержки транспортной фирмы будут минимальными.

 

10   8   12   9    6

 5    7   11   6    7      = С_ij  

12   8    9   12  10

1.  МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

A_i – i – ый поставщик (i = 1¸3).

B_j – j – ый потребитель (j = 1¸5).

X_ij – количество груза перевозимого от i – го поставщика к j – ому потребителю.

Потребности:

 x₁₁+x₂₁+x₃₁=215

 x₁₂+x₂₂+x₃₂=110

 x₁₃+x₂₃+x₃₃=120

 x₁₄+x₂₄+x₃₄=90

 x₁₅+x₂₅+x₃₅=125

Запасы:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=80

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=320

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=225

x_ij ³ 0, i=1…3, j=1…5

Целевая функция:

Z= 10x₁₁+8x₁₂+12x₁₃+9x₁₄+6x₁₅+5x₂₁+7x₂₂+11x₂₃+6x₂₄+7x₂₅+12x₃₁+8x₃₂+

+9x₃₃+12x₃₄+10x₃₅à min

2.  РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ PER.

1)  Строим первоначальный опорный план методом северо-западного угла (этот режим используется по умолчанию)

НАЧАЛЬНОЕ решен. по NWC

   +------------------------------------------------------------------------+

   ¦ИЗ \ В  ¦D1      ¦D2      ¦D3      ¦D4      ¦D5      ¦ПОСТАВЩ.¦ U(i)    ¦

   ¦--------+--------+--------+--------+--------+--------+--------+---------¦

   ¦        ¦ ¦ 10.00¦ ¦ 8.000¦ ¦ 12.00¦ ¦ 9.000¦ ¦ 6.000¦        ¦         ¦

   ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

   ¦S1      ¦ 80.00  ¦        ¦        ¦        ¦        ¦ 80.00  ¦   0     ¦

   ¦--------+--------+--------+--------+--------+--------+--------+---------¦

   ¦        ¦ ¦ 5.000¦ ¦ 7.000¦ ¦ 11.00¦ ¦ 6.000¦ ¦ 7.000¦        ¦         ¦

   ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

   ¦S2      ¦ 135.0  ¦ 110.0  ¦ 75.00  ¦        ¦        ¦ 320.0  ¦   0     ¦

   ¦--------+--------+--------+--------+--------+--------+--------+---------¦

   ¦        ¦ ¦ 12.00¦ ¦ 8.000¦ ¦ 9.000¦ ¦ 12.00¦ ¦ 10.00¦        ¦         ¦

   ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

   ¦S3      ¦        ¦        ¦ 45.00  ¦ 90.00  ¦ 90.00  ¦ 225.0  ¦   0     ¦

   ¦--------+--------+--------+--------+--------+--------+--------+---------¦

   ¦        ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦        ¦         ¦

   ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

   ¦Фикт.   ¦        ¦        ¦        ¦        ¦ 35.00  ¦ 35.00  ¦   0     ¦

   ¦--------+--------+--------+--------+--------+--------+--------+---------¦

   ¦ПОТРЕБ. ¦ 215.0  ¦ 110.0  ¦ 120.0  ¦ 90.00  ¦ 125.0  ¦        ¦         ¦

   ¦  V(j)  ¦   0    ¦   0    ¦   0    ¦   0    ¦   0    ¦        ¦         ¦

   +------------------------------------------------------------------------+

                           MIN   величина  ЦФ =  5455

Итерация   1

 +------------------------------------------------------------------------+

 ¦ИЗ \ В  ¦D1      ¦D2      ¦D3      ¦D4      ¦D5      ¦ПОСТАВЩ.¦ U(i)    ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 10.00¦ ¦ 8.000¦ ¦ 12.00¦ ¦ 9.000¦ ¦ 6.000¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S1      ¦ 80.00  ¦        ¦        ¦        ¦  **    ¦ 80.00  ¦   0     ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 5.000¦ ¦ 7.000¦ ¦ 11.00¦ ¦ 6.000¦ ¦ 7.000¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S2      ¦ 135.0  ¦ 110.0  ¦ 75.00  ¦        ¦        ¦ 320.0  ¦-5.000   ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 12.00¦ ¦ 8.000¦ ¦ 9.000¦ ¦ 12.00¦ ¦ 10.00¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S3      ¦        ¦        ¦ 45.00  ¦ 90.00  ¦ 90.00  ¦ 225.0  ¦-7.000   ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦Фикт.   ¦        ¦        ¦        ¦        ¦ 35.00  ¦ 35.00  ¦-17.00   ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦ПОТРЕБ. ¦ 215.0  ¦ 110.0  ¦ 120.0  ¦ 90.00  ¦ 125.0  ¦        ¦         ¦

 ¦  V(j)  ¦ 10.00  ¦ 12.00  ¦ 16.00  ¦ 19.00  ¦ 17.00  ¦        ¦         ¦

 +------------------------------------------------------------------------+

         Текущая   MIN   величина  ЦФ =  5455   с    e( 1, 5) =-11

Итерация   2

 +------------------------------------------------------------------------+

 ¦ИЗ \ В  ¦D1      ¦D2      ¦D3      ¦D4      ¦D5      ¦ПОСТАВЩ.¦ U(i)    ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 10.00¦ ¦ 8.000¦ ¦ 12.00¦ ¦ 9.000¦ ¦ 6.000¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S1      ¦ 5.000  ¦        ¦        ¦        ¦ 75.00  ¦ 80.00  ¦   0     ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 5.000¦ ¦ 7.000¦ ¦ 11.00¦ ¦ 6.000¦ ¦ 7.000¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S2      ¦ 210.0  ¦ 110.0  ¦        ¦        ¦        ¦ 320.0  ¦-5.000   ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦ 12.00¦ ¦ 8.000¦ ¦ 9.000¦ ¦ 12.00¦ ¦ 10.00¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦

 ¦S3      ¦        ¦  **    ¦ 120.0  ¦ 90.00  ¦ 15.00  ¦ 225.0  ¦ 4.000   ¦

 ¦--------+--------+--------+--------+--------+--------+--------+---------¦

 ¦        ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦ ¦   0  ¦        ¦         ¦

 ¦        ¦ +------¦ +------¦ +------¦ +------¦ +------¦        ¦         ¦