Информатика и выч. техника \ Прикладные методы оптимизации

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

Число занятых клеток = n + m – 1 = 8 (условие вырожденности).

Стоимость перевозок в начальном опорном плане Z = 4145

β5-α1=6

β5-α2=7

β4-α2=6

β1-α2=5

β5-α3=10

β3-α3=9

β2-α3=8

β3-α4=0

α1=0

Решая систему, получаем:

β1=4,   β2=4,   β3=5,   β4=5,   β5=6; α1=0,   α2= -1,   α3= -4,   α4=5.

Проверяем рентабельность перевозок:

r11= -6 , r12= -4, r13= -7, r14= -4, r22= -3, r23= -5, r31= - 12, r34= -3, r41= -1, r42= -1, r44= 0 , r45=  1.

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

B1

B2

B3

B4

B5

Запасы

A1

10

8

12

9

6

80

80

A2

5

215

7

11

6

90

7

15

320

A3

12

8

110

+  9

85

12

- 10

30

225

A4

0

0

-   0

35

0

+  0

35

Потребности

215

110

120

90

125

660

Получаем новый опорный план:

B1

B2

B3

B4

B5

Запасы

A1

10

8

12

9

6

80

80

A2

5

215

7

11

6

90

7

15

320

A3

12

8

110

9

115

12

10

225

A4

0

0

0

5

0

0

30

35

Потребности

215

110

120

90

125

660

Число занятых клеток = n + m – 1 = 8 (условие вырожденности).

Стоимость перевозок в начальном опорном плане Z = 4115

β5-α1=6

β5-α2=7

β4-α2=6

β1-α2=5

β3-α3=9

β2-α3=8

β4-α4=0

β3-α4=0

α1=0

Решая систему, получаем:

β1=4,   β2=5,   β3=6,   β4=5,   β5=6; α1=0,   α2= -1,   α3= -3,   α4=6.

Проверяем рентабельность перевозок:

r11= -6 , r12= -3, r13= -6, r14= -4, r22= -2, r23= -5, r31= - 5, r34= -4, r35= -1, r41= -2,

r42= -1 , r44=  -1.

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

отрицательные (не рентабельные).

Записываем ТЗ в виде общей задачи линейного программирования и находим ее решение симплекс – методом (режим «Линейное программирование» программного меню ПЭР). Сравниваем полученные результаты. Производим анализ устойчивости решения.

Z= 10x11+8x12+12x13+9x14+6x15+5x21+7x22+11x23+6x24+7x25+12x31+8x32+

+9x33+12x34+10x35 + 0x 41+0x 42+0x 43+0x 44+0x 45 à min

Ограничения:

x11+x12+x 13+x 14+x 15 =80

x 21+x 22+x 23+x 24+x 25 =320

x 31+x 32+x 33+x 34+x 35  =225

x 41+x 42+x 43+x 44+x 45  =35

x11+x 21+x 31+x 41  =215

x 12+x 22+x 32+x 42  =110

x 13+x 23+x 33+x 43  =120

x 14+x 24+x 34+x 44  =90

x 15+x 25+x 35+x 45  = 125

xij>=0, i=1…20

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

¦                 ИТОГОВЫЙ РЕЗУЛЬТАТ ДЛЯ lb2lp     Стр. : 1       ¦

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

¦Переменн.¦          ¦Двойственн.¦Переменн.¦          ¦Двойственн.¦

¦No. Имена¦ РЕШЕНИЕ  ¦   оцен    ¦No. Имена¦ РЕШЕНИЕ  ¦   оцен    ¦

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

¦1   X1   ¦    0.0000¦    6.0000 ¦16  X16  ¦    0.0000¦    2.0000 ¦

¦2   X2   ¦    0.0000¦    3.0000 ¦17  X17  ¦    0.0000¦    1.0000 ¦

¦3   X3   ¦    0.0000¦    6.0000 ¦18  X18  ¦    5.0000¦    0.0000 ¦

¦4   X4   ¦    0.0000¦    4.0000 ¦19  X19  ¦    0.0000¦    1.0000 ¦

¦5   X5   ¦   80.0000¦    0.0000 ¦20  X20  ¦   30.0000¦    0.0000 ¦

¦6   X6   ¦  215.0000¦    0.0000 ¦21  A1   ¦    0.0000¦   -6.0000 ¦

¦7   X7   ¦    0.0000¦    1.0000 ¦22  A2   ¦    0.0000¦   -7.0000 ¦

¦8   X8   ¦    0.0000¦    4.0000 ¦23  A3   ¦    0.0000¦   -9.0000 ¦

¦9   X9   ¦   90.0000¦    0.0000 ¦24  A4   ¦    0.0000¦    0.0000 ¦

¦10  X10  ¦   15.0000¦    0.0000 ¦25  A5   ¦    0.0000¦    2.0000 ¦

¦11  X11  ¦    0.0000¦    5.0000 ¦26  A6   ¦    0.0000¦    1.0000 ¦

¦12  X12  ¦  110.0000¦    0.0000 ¦27  A7   ¦    0.0000¦    0.0000 ¦

¦13  X13  ¦  115.0000¦    0.0000 ¦28  A8   ¦    0.0000¦    1.0000 ¦

¦14  X14  ¦    0.0000¦    4.0000 ¦29  A9   ¦    0.0000¦    0.0000 ¦

¦15  X15  ¦    0.0000¦    1.0000 ¦         ¦          ¦           ¦

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

¦   MIN   величина цел.ф-и = 4115 (множеств. реш.)  Итерац.= 11   ¦

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

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

¦                  АНАЛИЗ УСТОЙЧИВОСТИ КОЭФФ. ЦЕЛЕВОЙ Ф-ЦИИ      Стр. : 1      ¦

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

¦C(j) ¦Min. C(j) ¦ Исходный ¦Max. C(j) ¦C(j) ¦Min. C(j) ¦ Исходный ¦Max. C(j)  ¦

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

¦C(1) ¦    4.0000¦   10.0000¦+ бесконеч¦C(11)¦    7.0000¦   12.0000¦+ бесконеч ¦

¦C(2) ¦    5.0000¦    8.0000¦+ бесконеч¦C(12)¦- бесконеч¦    8.0000¦    9.0000 ¦

¦C(3) ¦    6.0000¦   12.0000¦+ бесконеч¦C(13)¦    8.0000¦    9.0000¦   10.0000 ¦

¦C(4) ¦    5.0000¦    9.0000¦+ бесконеч¦C(14)¦    8.0000¦   12.0000¦+ бесконеч ¦

¦C(5) ¦- бесконеч¦    6.0000¦    9.0000¦C(15)¦    9.0000¦   10.0000¦+ бесконеч ¦

¦C(6) ¦- бесконеч¦    5.0000¦    7.0000¦C(16)¦   -2.0000¦    0.0000¦+ бесконеч ¦

Скачать файл