Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 

Сетевое моделирование при планировании. Задача о коммивояжере...

Работа из раздела: «Экономико-математическое моделирование»
Московский городской институт управления Правительства Москвы



                             Лабораторные работы



                                по дисциплине



                 «Экономико-математические методы и модели»



                              Подготовила студентка V курса Евдокимова Е. Д.

                                              Преподаватель – Новикова Г. М.



                                   Москва

                                    2004

                                 Содержание



      Задание №1……………………………………………………………….3

      Задание №2……………………………………………………………….8
      Задание №3……………………………………………………………...11
      Задание №4……………………………………………………………...14
      Задание №5……………………………………………………………...16
      Задание №6……………………………………………………………...20



                                 Задание №1



                Тема: Сетевое моделирование при планировании

        Задача: Разработка, анализ и оптимизация сетевого графика при
                      календарном планировании проекта
       Компания «АВС» реализует проекты серийного производства различных
видов продукции. Каждый проект обеспечивает получение в неделю 100 тыс. $
дополнительной прибыли. Перечень работ и их характеристики представлены в
таблице 1.1.
                                                                 Таблица 1.1

                     Перечень работ и их характеристики

|Работы|Непосредственн|Продолжительность     |Стоимость   |Коэффициент|
|      |о             |работы, недель        |работы, тыс.|затрат на  |
|      |предшествующие|                      |$ при       |ускорение  |
|      |работы        |                      |t(i,j)=tHB(I|работы     |
|      |              |                      |,j)         |           |
|      |              |tmin       |tmax      |            |           |
|A     |-             |4          |6         |110         |22         |
|B     |-             |7          |9         |130         |28         |
|C     |-             |8          |11        |160         |18         |
|D     |A             |9          |12        |190         |35         |
|E     |C             |5          |8         |150         |28         |
|F     |B, E          |4          |6         |130         |25         |
|G     |C             |11         |15        |260         |55         |
|H     |F, G          |4          |6         |90          |15         |

                                  Задание:
          1. Изобразить проект с помощью сетевой модели.
          2. Определить наиболее вероятную продолжительность каждой работы.
          3. Найти все полные пути сетевого графика, определить критический
             путь, ожидаемую продолжительность выполнения проекта и полную
             стоимость всех работ.
          4. Разработать математическую модель оптимизации процесса
             реализации проекта.


                               Сетевой график


                                         D

                 A
    H
                        B                         F

                  C                          E
                                         G


                 Наиболее вероятная продолжительность работ

                           tНВ = (2tmin + 3tmax)/5
      tНВ A = (2*4 + 3*6)/5 = 5,2
      tНВ B= (2*7 + 3*9)/5 = 8,2
      tНВ C= (2*8 + 3*11)/5 = 9,8
      tНВ D= (2*9 + 3*12)/5 = 10,8
      tНВ E= (2*5 + 3*8)/5 = 6,8
      tНВ F= (2*4 + 3*6)/5 = 5,2
      tНВ G= (2*11 + 3*15)/5 = 13,4
      tНВ H= (2*4 + 3*6)/5 = 5,2

                            Возможные полные пути

        I. 1 – 2 – 5. Длина: tНВ A + tНВ D =5,2 + 10,8 = 16
       II. 1 – 3 – 6 – 5. Длина: tНВ B + tНВ F + tНВ H = 8,2 + 5,2 +5,2 =
           18,6
      III. 1 – 4 – 6 – 5. Длина: tНВ C + tНВ G + tНВ H = 9,8 + 13,4 + 5,2 =
           28,4
       IV. 1 – 4 – 3 – 6 – 5. Длина: tНВ C + tНВ E + tНВ F + tНВ H = 9,8 +
           6,8 + 5,2 + 5,2= = 27
      Максимальная длина пути, равная 28,4 недели соответствует пути III, на
котором лежат работы C, G, H. Следовательно, он является критическим.

                            Математическая модель

      Примем за x1,  x2 , …, x8 продолжительность работ A, B,…, H
соответственно.
      x1 ( 4 (1)
      x2 ( 7 (2)
      x3 ( 8 (3)
      x4 ( 9 (4)
      x5 ( 5 (5)
      x6 ( 4 (6)
      x7 ( 11 (7)
      x8 ( 4 (8)
      x1 ( 6 (9)
      x2 ( 9 (10)
      x3 ( 11 (11)
      x4 ( 12 (12)
      x5 ( 8 (13)
      x6 ( 6 (14)
      x7 ( 15 (15)
      x8 ( 6 (16)
      x1 + x4 + x9 ( 28,4 (17)
      x2 + x6 + x8 + x9 ( 28,4 (18)
      x3 + x7 + x8 + x9 ( 28,4 (19)
      x3 + x5 + x6 + x8 + x9 ( 28,4 (20)
      Функция цели: 22x1 + 28x2 + 18x3 + 35x4 + 28x5+ 25x6 + 55x7 + 15x8 +
100x9          max

                              Исходная матрица


                                                                 Таблица 1.2

|A       |6       |5,2     |-0,8    |22      |-17,6   |110      |92,4    |
|B       |9       |8,2     |-0,8    |28      |-22,4   |130      |107,6   |
|C       |8       |9,8     |1,8     |18      |32,4    |160      |192,4   |
|D       |12      |10,8    |-1,2    |35      |-42     |190      |148     |
|E       |7       |6,8     |-0,2    |28      |-5,6    |150      |144,4   |
|F       |4       |5,2     |1,2     |25      |30      |130      |160     |
|G       |11      |13,4    |2,4     |55      |132     |260      |392     |
|H       |4       |5,2     |1,2     |15      |18      |90       |108     |
|Всего   |        |        |        |        |124,8   |1220     |1344,8  |
|затрат  |        |        |        |        |        |         |        |

      Таким образом, время выполнения работ A, B, D, E увеличилось по
сравнению с наиболее вероятным; продолжительность остальных работ
уменьшилась. Затраты на реализацию проекта возросли на 124,8 тыс. $.
Увеличение затрат произошло, в основном, из-за работы G, по которой
наблюдается наибольшее сокращение времени в сочетании с наивысшим
коэффициентом затрат на выполнение работы.
      Из-за сокращения критического пути проект будет введен в эксплуатацию
на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за
этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $.
      В результате дополнительная прибыль с учетом возрастания затрат на
проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $



                                 Задание №2
                                 Тема: Графы
                            Задача о коммивояжере
      Имеется 4 пункта. Время переезда из пункта I в пункт j представлено в
таблице 2.1.
                                                                 Таблица 2.1

                               Исходные данные

|Из пункта i  |В пункт j                                                 |
|             |1            |2            |3            |4            |
|1            |0            |8            |8            |6            |
|2            |4            |0            |6            |12           |
|3            |10           |12           |0            |18           |
|4            |8            |10           |4            |0            |

      График представлен на рисунке.



      Требуется найти оптимальный маршрут, вычеркнув из таблицы
отсутствующие маршруты.

                            Математическая модель

      Обозначим за x маршруты, приведенные в таблице 2.2.
                                                                 Таблица 2.2

                                 Обозначения

|xi           |Пункт        |Пункт        |Время        |
|             |отправления  |назначения   |переезда     |
|x1           |1            |2            |8            |
|x2           |1            |3            |8            |
|Продолжение                                               |
|x3           |1            |4            |6            |
|x4           |2            |1            |4            |
|x5           |2            |3            |6            |
|x6           |2            |4            |12           |
|x7           |3            |1            |10           |
|x8           |3            |2            |12           |
|x9           |3            |4            |18           |
|x10          |4            |1            |8            |
|x11          |4            |2            |10           |
|x12          |4            |3            |4            |

      Сумма входящих и исходящих маршрутов в каждом пункте равна 1.
Следовательно, система условий-ограничений выглядит следующим образом:
      x1 + x2 + x3 = 1 (1)
      x4 + x5 + x6 = 1 (2)
      x7 + x8 + x9 = 1 (3)
      x10 + x11 + x12 = 1 (4)
      x4 + x7 + x10 = 1 (5)
      x1 + x8 + x11 = 1 (6)
      x2 + x5 + x12 = 1 (7)
      x3 + x6 + x9 = 1 (8)
      Функция цели: 8x1 + 8x2 + 6x3 + 4x4 + 6x5 + 12x6 + 10x7 + 12x8 + 18x9
+ 8x10   + 10x11 + 4x12          min
      Исходная матрица условий задачи представлена в таблице 2.3.

                                                                 Таблица 2.3

|(12     |(13     |(21     |(32     |(34     |(45     |(53     |(54     |
|3       |2       |1       |3       |2       |2       |3       |1       |

                            Математическая модель
      Примем за х1, х2, …, х5 предельные вероятности состояний в
стационарном режиме пунктов S1, S2, …, S5 соответственно. Произведение
вероятности состояния на интенсивность исходящих из этого пункта потоков
равна произведению интенсивностей входящих потоков на вероятность состояния
в стационарном режиме пунктов их отправления. Система уравнений Колмогорова
для данной задачи в общем виде выглядит следующим образом:
      ((13 + (12 )* х1 = (21 * х2 (1)
      (21 * х2 = (12 * х1+ (32 * х3 (2)
      ((32 + (34 )* х3 = (13 * х1 + (53 * х5 (3)
      (45 * х4 = (34 * х3+ (54 * х5 (4)
       ((54 + (53 )* х5 = (45 * х4 (5)
      Кроме того, сумма всех вероятностей равна 1. При подстановке данных
таблицы 4.1 и добавлении переменной х6 получаем:
      5 х1 - х2 + х6 = 0 (1)
      х2 - 3х1 - 3х3 + х6 = 0 (2)
      5 х3 - 2х1 - 3х5 + х6 = 0 (3)
      2 х4 - 2х3 – х3 + х6 = 0 (4)
      4 х5 - 2х4 + х6 = 0 (5)
      х1 + х2 + х3 + х4 + х5 + х6 = 1 (6)
      Функция цели: М х6         max
                                                                Таблица 4.2.

                              Исходная матрица

|№      |х1     |х2     |х3     |х4     |х5     |х6     |Св.чл. |Знак   |
|1      |5      |-1     |0      |0      |0      |1      |0      |=      |
|2      |-3     |1      |-3     |0      |0      |1      |0      |=      |
|3      |-2     |0      |5      |0      |-3     |1      |0      |=      |
|4      |0      |0      |-2     |2      |-1     |1      |0      |=      |
|5      |0      |0      |0      |-2     |4      |1      |0      |=      |
|6      |1      |1      |1      |1      |1      |1      |1      |=      |
|Ф.ц.   |0      |0      |0      |0      |0      |М      |max    |       |

                                   Решение
      Функционал = -500
      х1 = 0,125
      х2 = 0,625
      х3 = 0,083
      х4 = 0,111
      х5 = 0,055
      Сумма данных вероятностей составляет 0,999, т. е. погрешность,
полученная при расчетах, крайне незначительна.
                                 Задание №5
                      Тема: Имитационное моделирование
      Задача: Расчет и анализ графика запуска-выпуска продукции в цехе
                         мелкосерийного производства
      В таблице 5.1 представлены технологические маршруты изготовления
различных видов продукции, а также директивное время исполнения заказов (в
условных единицах) и нормы затрат времени на обработку одной партии
продукции на каждом из типов оборудования.
      Общая масса заказа по каждому виду продукции разбивается на N партий
так, что для каждого вида продукции выполняется условие:
      Общая масса заказа = (масса партий)*(число партий)
      Нормы затрат времени в каждом эксперименте имитационного моделирования
обратно пропорциональны числу партий.
      Требуется определить оптимальный маршрут изготовления продукции.

                                                                 Таблица 5.1


               Технологические маршруты изготовления продукции

|      Продукция|Эксперимент №1    |Эксперимент №2     |Эксперимент №3       |
|               |                  |                   |                     |
|               |                  |                   |                     |
|Оборудование   |                  |                   |                     |
|Изделие 1 |1      |6      |0      |0      |0      |1      |4      |26     |
|Изделие 2 |1      |0      |0      |0      |0      |2      |4      |14     |
|Изделие 3 |1      |0      |6      |0      |0      |0      |4      |25     |
|Изделие 4 |1      |0      |0      |0      |0      |3      |4      |12     |
|Изделие 5 |1      |0      |0      |3      |0      |0      |4      |25     |
|Изделие 6 |1      |0      |0      |0      |2      |0      |4      |24     |

      В итоге получился следующий график запуска-выпуска продукции.
                                                                Таблица 5.3.

                      График запуска-выпуска продукции

|             |№1           |№2           |№3           |             |
|№1           |0,15         |0,10         |0,30         |100          |
|№2           |0,25         |0,15         |0,25         |280          |
|№3           |0,30         |0,25         |0            |320          |


                            Математическая модель

      х1 = 0,15х1 + 0,1х2 + 0,3х3 + 100
      х2 = 0,25х1 + 0,15х2 + 0,25х3 + 280
      х3 = 0,3х1 + 0,25х2 + 0х3 + 320
      Отсюда, умножив уравнения на –1, получаем следующую систему уравнений
ограничений:
      0,85х1 - 0,1х2 - 0,3х3 - х4 = 100 (1)
      -0,25х1 + 0,85х2 - 0,25х3 - х4 = 280 (2)
      -0,3х1 + 0,25х2 + х3 - х4 = +320 (3)
      Функция цели: -Мх4        max
      Исходная матрица условий задачи представлена в таблице 6.2.

                                                                Таблица 6.2.

                              Исходная матрица

|№        |х1       |х2       |х3       |х4       |Знак     |Св. чл.  |
|1        |0,85     |-0,1     |-0,3     |-1       |=        |100      |
|2        |-0,25    |0,85     |-0,25    |-1       |=        |280      |
|3        |-0,3     |-0,25    |1        |-1       |=        |320      |
|Ф. ц.    |0        |0        |0        |-М       |max      |         |



                                   Решение

      Функционал = 0
      х1 = 401,292
      х2 = 622,756
      х3 = 596,077
      Умножив полученные значения валового продукта на коэффициенты прямых
затрат, получим решение, представленное в таблице 6.3.
                                                                Таблица 6.3.

                                   Решение

|Производящие цехи   |Потребляющие цехи              |Конечный  |Валовой  |
|                    |                               |продукт   |продукт  |
|                    |1        |2        |3        |          |         |
|1                   |60,15    |40,1     |120,3    |100       |401      |
|2                   |155,75   |93,45    |155,75   |280       |623      |
|3                   |178,8    |149,0    |0        |320       |596      |
|Итого               |         |         |         |          |         |

      В таблице показаны затраты на производство продукции в количественном
выражении.
-----------------------
1

2

3

4

5

6

1

2

3

4

1

2

3

4

1

2

3

4

5

S1

S4


S3


S2


S5

1

3

5

2

4



ref.by 2006—2022
contextus@mail.ru