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

¦C(7) ¦    6.0000¦    7.0000¦+ бесконеч¦C(17)¦   -1.0000¦    0.0000¦+ бесконеч ¦

¦C(8) ¦    7.0000¦   11.0000¦+ бесконеч¦C(18)¦   -1.0000¦    0.0000¦    0.0000 ¦

¦C(9) ¦- бесконеч¦    6.0000¦    7.0000¦C(19)¦   -1.0000¦    0.0000¦+ бесконеч ¦

¦C(10)¦    6.0000¦    7.0000¦    8.0000¦C(20)¦    0.0000¦    0.0000¦    1.0000 ¦

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

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

¦                        АНАЛИЗ УСТОЙЧИВОСТИ ПР.ЧАСТИ       Стр. : 1           ¦

¦------------------------------------------------------------------------------¦

¦B(i) ¦Min. B(i) ¦ Исходный ¦Max. B(i) ¦B(i) ¦Min. B(i) ¦ Исходный ¦Max. B(i)  ¦

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

¦B(1) ¦    0.0000¦   80.0000¦   80.0000¦B(6) ¦  110.0000¦  110.0000¦  140.0000 ¦

¦B(2) ¦  305.0000¦  320.0000¦  320.0000¦B(7) ¦  120.0000¦  120.0000¦  150.0000 ¦

¦B(3) ¦  195.0000¦  225.0000¦  225.0000¦B(8) ¦   90.0000¦   90.0000¦  105.0000 ¦

¦B(4) ¦    5.0000¦   35.0000¦   35.0000¦B(9) ¦  125.0000¦  125.0000¦+ бесконеч ¦

¦B(5) ¦  215.0000¦  215.0000¦  230.0000¦     ¦          ¦          ¦           ¦

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

2)  Решаем методом потенциалов произвольную задачу о назначениях с матрицей эффективности размером 4x4, рассматривая ее как частный случай ТЗ. Задачу записываем на диск под именем tnznm.

                 1  5    2  10

3  14  1   1    = С_ij  

7  7  16  21

0  8    4    9

n – число поставщиков (1…4)

m – число потребителей (1…4)

C_ij – стоимость (коэффициент затрат) перевозки единицы груза от  i- того поставщика j – му потребителю.

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

Мощность каждого поставщика и каждого потребителя – единичная.

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

 x₁₁+x₁₂+x₁₃+x₁₄=1

 x₂₁+x₂₂+x₂₃+x₂₄=1

 x₃₁+x₃₂+x₃₃+x₃₄=1

 x₄₁+x₄₂+x₄₃+x₄₄=1

Запасы:

x₁₁+x ₂₁+x ₃₁+x ₄₁ =1

x ₁₂+x ₂₂+x ₃₂+x ₄₂ =1

x ₁₃+x ₂₃+x ₃₃+x ₄₃ =1

x ₁₄+x ₂₄+x ₃₄+x ₄₄ =1

x_ij ³ 0, i=1…4, j=1…4

x_ij – целые

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

Z=1x₁₁+5x₁₂+2x₁₃+10x₁₄+3x₂₁+14x₂₂+1x₂₃+1x₂₄+7x₃₁+7x₃₂+16x₃₃+21x₃₄+0x₄₁+8x₄₂+ +4x₄₃+9x₄₄à max

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

  ╔════════╤════════╤════════╤════════╤════════╤════════╤═════════╗

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

  ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

  ║        │ │ 1.000│ │ 5.000│ │ 2.000│ │ 10.00│        │         ║

  ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

  ║S1      │ 1.000  │   0    │        │        │ 1.000  │   0     ║

  ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

  ║        │ │ 3.000│ │ 14.00│ │ 1.000│ │ 1.000│        │         ║

  ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

  ║S2      │        │ 1.000  │   0    │        │ 1.000  │   0     ║

  ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

  ║        │ │ 7.000│ │ 7.000│ │ 16.00│ │ 21.00│        │         ║

  ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

  ║S3      │        │        │ 1.000  │   0    │ 1.000  │   0     ║

  ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

  ║        │ │   0  │ │ 8.000│ │ 4.000│ │ 9.000│        │         ║

  ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

  ║S4      │        │        │        │ 1.000  │ 1.000  │   0     ║

  ╟────────┼────────┼────────┼────────┼────────┼────────┼─────────╢

  ║ПОТРЕБ. │ 1.000  │ 1.000  │ 1.000  │ 1.000  │        │         ║

  ║  V(j)  │   0    │   0    │   0    │   0    │        │         ║

  ╚════════╧════════╧════════╧════════╧════════╧════════╧═════════╝

                      MAX   величина  ЦФ =  40

              КОНЕЧНАЯ таблица (Кол-во итерац. = 3)

 ╔════════╤════════╤════════╤════════╤════════╤════════╤═════════╗

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

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 1.000│ │ 5.000│ │ 2.000│ │ 10.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S1      │ 1.000  │        │        │   0    │ 1.000  │   0     ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 3.000│ │ 14.00│ │ 1.000│ │ 1.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S2      │        │ 1.000  │        │        │ 1.000  │ 5.000   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 7.000│ │ 7.000│ │ 16.00│ │ 21.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S3      │        │        │ 1.000  │        │ 1.000  │ 11.00   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │   0  │ │ 8.000│ │ 4.000│ │ 9.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S4      │        │   0    │   0    │ 1.000  │ 1.000  │-1.000   ║

 ╟────────┼────────┼────────┼────────┼────────┼────────┼─────────╢

 ║ПОТРЕБ. │ 1.000  │ 1.000  │ 1.000  │ 1.000  │        │         ║

 ║  V(j)  │ 1.000  │ 9.000  │ 5.000  │ 10.00  │        │         ║

 ╚════════╧════════╧════════╧════════╧════════╧════════╧═════════╝

         MAX   величина  ЦФ =  40  (возм. мн-во решений )

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