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

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

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

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

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

¦S3      ¦        ¦ 110.0  ¦ 85.00  ¦        ¦ 30.00  ¦ 225.0  ¦ 4.000   ¦

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

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

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

¦Фикт.   ¦        ¦        ¦ 35.00  ¦        ¦  **    ¦ 35.00  ¦-5.000   ¦

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

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

¦  V(j)  ¦ 4.000  ¦ 4.000  ¦ 5.000  ¦ 5.000  ¦ 6.000  ¦        ¦         ¦

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

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

КОНЕЧНАЯ таблица (Кол-во итерац. = 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      ¦ 215.0  ¦        ¦        ¦ 90.00  ¦ 15.00  ¦ 320.0  ¦ 1.000   ¦

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

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

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

¦S3      ¦        ¦ 110.0  ¦ 115.0  ¦        ¦        ¦ 225.0  ¦ 3.000   ¦

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

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

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

¦Фикт.   ¦        ¦        ¦ 5.000  ¦        ¦ 30.00  ¦ 35.00  ¦-6.000   ¦

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

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

¦  V(j)  ¦ 4.000  ¦ 5.000  ¦ 6.000  ¦ 5.000  ¦ 6.000  ¦        ¦         ¦

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

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

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

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

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

¦ ИЗ    ¦ В     ¦ Поставка ¦ Оценка  ¦ ИЗ    ¦ В     ¦ Поставка ¦ Оценка  ¦

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

¦S1     ¦D1     ¦      0.0 ¦   10.00 ¦S3     ¦D1     ¦      0.0 ¦   12.00 ¦

¦S1     ¦D2     ¦      0.0 ¦   8.000 ¦S3     ¦D2     ¦    110.0 ¦   8.000 ¦

¦S1     ¦D3     ¦      0.0 ¦   12.00 ¦S3     ¦D3     ¦    115.0 ¦   9.000 ¦

¦S1     ¦D4     ¦      0.0 ¦   9.000 ¦S3     ¦D4     ¦      0.0 ¦   12.00 ¦

¦S1     ¦D5     ¦     80.0 ¦   6.000 ¦S3     ¦D5     ¦      0.0 ¦   10.00 ¦

¦S2     ¦D1     ¦    215.0 ¦   5.000 ¦Фикт.  ¦D1     ¦      0.0 ¦     0   ¦

¦S2     ¦D2     ¦      0.0 ¦   7.000 ¦Фикт.  ¦D2     ¦      0.0 ¦     0   ¦

¦S2     ¦D3     ¦      0.0 ¦   11.00 ¦Фикт.  ¦D3     ¦      5.0 ¦     0   ¦

¦S2     ¦D4     ¦     90.0 ¦   6.000 ¦Фикт.  ¦D4     ¦      0.0 ¦     0   ¦

¦S2     ¦D5     ¦     15.0 ¦   7.000 ¦Фикт.  ¦D5     ¦     30.0 ¦     0   ¦

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

¦       MIN   величина  ЦФ =  4115 (возм.неоднозн.)  Итераций   = 1       ¦

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

4)         Сравниваем результаты решения двумя способами.

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

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

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

B1

B2

B3

B4

B5

Запасы

 

A1

10

8

12

9

6

80

80

2

-

-

-

-

-

-

-

A2

5

215

7

11

6

90

7

15

320

1

1

1

-

-

-

-

-

A3

12

8

110

    9

85

12

10

30

225

1

1

1

2

-

-

-

-

A4

0

0

0

35

0

0

35

0

-

-

-

-

-

-

-

Потребности

215

110

120

90

125

660

  

5

7

9

6

7

  

-

7

2

6

7

  

-

-

2

-

7

  

-

-

-

-

10

  

-

-

-

-

-

  

-

-

-

-

-

  

-

-

-

-

-

  

-

-

-

-

-

  
Скачать файл