Реализация транспортной задачи в матричной постановке. Вариант № 8

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

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

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

МО и ПО РФ

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

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

Расчетно-графическая работа №2

по курсу

«Теория оптимального управления

в экономических системах»

ТРАНСПОРТНАЯ ЗАДАЧА

Вариант 8

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

Группа:

Студенты:

Преподаватель: Кириллов Ю.В.

Новосибирск

2003

Цели  задания:

1. понимать смысл, различать, осознанно использовать следующие понятия: транспортная задача (ТЗ) в матричной постановке; открытая и закрытая модели ТЗ; транспортная таблица, допустимый, опорный, оптимальный планы ТЗ; поставки, перераспределение поставок, потен­циалы строк и столбцов транспортной таблицы как двойственные оцен­ки; характеристики клеток транспортной таблицы, цикл пересчета; альтернативные решения ТЗ;

2. получить навыки, уметь: строить математическую модель ТЗ; переходить от открытой модели ТЗ к закрытой; использовать различ­ные методы для построения опорных планов ТЗ; решать ТЗ методом потенциалов; анализировать полученное решение и находить альтерна­тивные варианты; интерпретировать полученное решение в терминах

поставленной задачи.

   Условие задачи: транспортная фирма обслуживает n поставщиков однородного груза и m потребителей этого груза. В течение дня из каждого пункта пос­тавки фирма должна вывезти соответственно a1, А2,,.. , Аn тонн гру­за, а в каждый пункт потребления доставить соответственно Вi, В2,..., Вm тонн. Себестоимость перевозки 1 тонны груза от i-го поставщика j-му потребителю составляет Сij тыс. руб.

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

 Задание:записать математическую модель задачи. Построить опорные планы методом северо-западного угла, методом минимального элемента и ме­тодом Фогеля. Сравнить результаты. Опираясь на любой из полученных планов, решить задачу методом потенциалов. Решить задачу на ПЭВМ с помощью ПЭР и сравнить результаты с полученными ручным способом.

            Исходные данные для 8 варианта:        n=3,m=5;A1=400,A2=265,A3=515;                 B1=220,B2=230,B3=250,B4=220,B5=310;

                                                                           

Чтобы решить данную задачу необходимо и достаточно, чтобы суммарная мощность всех поставщиков равнялась суммарной мощности всех потребителей, т.е. , а т.к. у нас < , то есть запасов товара на складе меньше, чем потребности покупателей, то необходимо ввести дополнительного (фиктивного) поставщика А5 = .

 Построим начальный опорный план (НОП) задачи 3 способами: методом северо-западного угла, методом Фогеля и методом минимального элемента. После каждой заполненной таблицы будем поверять условие ее невырожденности: ЧЗК = m + n –1. Если оно не выполняется, выбираем любую свободную клетку и заносим в нее 0, считая занятой, так, чтобы не образовалось цикла из занятых клеток.

1.  НОП, построенный методом северо-западного угла.

      Используя данный метод, мы должны начинать заполнять таблицу с верхнего левого угла (это следует из названия метода). Т.о. мы выбираем клетку А1В1 и заполняем ее числом  220, т.к. именно столько у нас потребностей покупателей для данного вида товара (следовательно, больше мы первый столбец не учитываем). Аналогично заполняем следующие клетки, начиная всегда с верхнего левого угла.

            В

из

В1

В2

В3

В4

В5

Запасы

А1

         15

220

         17   

   180

         14    

         12

      15

400

А2

         17

         11

    50

         13

   215

         11

      10

  265

         А3

         12

         13

         16

   35

         18

220

      17

  260

  515

      А4

      (фиктивная)

          0

          0

          0

          0

       0

  50

  50

Потребности

   220

   230

   250

   220

  310

                                                   X =  

Z = 220*15 + 180*17 + 50*11 + 215*13 + 35*16 + 220*18 + 260*17 + 50*0 = 18645 тыс.руб.

2.  НОП, построенный методом Фогеля.

    В

из

В1

В2

В3

В4

В5

Запасы

Δ

Δ

Δ

Δ

Δ

Δ

 

А1

  15    

  17   

   14       

135

   12    220

 15

45

400

2

2

2

1

1

1

 

А2

  17

  11 

   13

   11   

 10   

265

  265

1

1

-

-

-

-

 

А3

  12

220 

  13 

230

   16     

65

   18  

 17

  515

1

1

1

1

4

1

 

А4

(фикт.)

   0 

   0     

   0     

50

    0  

 0

  50

0

-

-

    -

-

-

 

Потр.

   220

   230

   250

   220

  310

Δ

12

11

13

11

10

Δ

3

2

1

1

5

Δ

3

4

2

6

2

Δ

3

4

2

-

2

Δ

3

-

2

   -

2

Δ

-

-

2

   -

2

     Чтобы построить начальную таблицу методом Фогеля, необходимо сначала найти разность между двумя наименьшими тарифами для каждой строки и столбца (соответственно: Δ и Δ) После чего из полученных результатов находим наибольшее значение [в нашем случае -  это число 13] и начинаем заполнение таблицы именно с этой строки\столбца [у нас - столбец В3]. В найденной строке/столбце находим наименьший тариф и заполняем данную клетку [А4В3]. Затем аналогичным способом  заполняем следующие клетки, при условии, что если потребности покупателя удовлетворены полностью или запасы на складе полностью использованы,  мы больше не учитываем соответствующий столбец/строку при расчете Δ. Полученная таблица выглядит следующим образом:

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

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