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

Страницы работы

15 страниц (Word-файл)

Содержание работы

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Кафедра экономической информатики

Отчет

по лабораторной работе №2

«Транспортная задача»

Вариант – 4

Факультет: бизнеса

Группа: ФБИ-23

Студентки:

Преподаватель: Наумов А.А.

Новосибирск

2004


ЦЕЛЬ РАБОТЫ

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

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

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

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

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

 


10   8   12   9    6

 5    7   11   6    7      = Сij  

12   8    9   12  10

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

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

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

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

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

 x11+x21+x31=215

 x12+x22+x32=110

 x13+x23+x33=120

 x14+x24+x34=90

 x15+x25+x35=125

Запасы:

x11+x12+x13+x14+x15=80

x21+x22+x23+x24+x25=320

x31+x32+x33+x34+x35=225

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

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

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

+9x33+12x34+10x35à 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  ¦        ¦         ¦

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

Похожие материалы

Информация о работе