по Математическому моделированию

СПЕЦИАЛЬНОСТЬ: 

	Группа: 

	Дисциплина: Исследование операций

	___________________________________________________________________________________

	

	ФИО студента:________________________________________









Набор  задач  №34.



Построить  математическую  модель  следующей  задачи  оптимального  планирования  объемов  производства.



 Компания  производит  погрузчики  и  тележки. От одного  погрузчика  компания  получает  доход  в  размере  $80  и  от  одной  тележки  в  размере  $40 . Имеется  три  обрабатывающих  центра, на  которых  выполняются  операции  металлообработки, сварки  и  сборки, необходимые  для  производства  любого  из продуктов. Для  интервала  планирования, равного  месяцу, задана  предельная  производственная  мощность каждого  обрабатывающего  центра  в  часах, а также  количество  часов, необходимое  на  этом  центре  для  производства  одного  погрузчика  и  одной  тележки. Эта  информация  задана  в  таблице.





  Погрузчик              Тележка

(часы/ед.)              (часы/ед.)

Общ. мощ.

(часы)



Мет. обраб.

Сварка

Сборка





6                                4

	2                        	3

	9	3



2400

1500

2700



Требуется  составить  допустимый  план  работ  на  месяц  с  максимальным  доходом.





 

Решение.



Пусть   —  количество  производимых  погрузчиков;

              — количество  производимых  тележек.

              



Тогда  целевая  функция, обозначающая   общую  сумму  дохода по  всем видам производимой  продукции ( погрузчики  и  тележки ),  равна







Задача  состоит  в  нахождении  допустимых  значений  переменных  и , максимизирующих   J(x). При этом, в  силу  условия  задачи, должны выполняться следующие ограничения  на  переменные:



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



  часов  в  месяц ( для  центра  металлообработки)   ;

 часов  в  месяц ( для  центра  сварки) ;

 часов  в  месяц ( для  центра  сборки);

 (ограничение на неотрицательность переменных) . 



Итак,  получили  следующую  математическую  модель  данной  задачи:



    



    

    

    

     





Найти  множество  Парето  следующей  двухкритериальной  задачи.



,  ,

при  условии  . Значения  функций       заданы  таблицей



x

1

2

3

4

5

6

7



-2

-4

-6

-4

-6

-8

-6



12

12

12

10

10

10

6  

							







   





 Решение.





Решим  вопрос  нахождения  множества  Парето  данной  задачи  геометрически. Для  этого  изобразим   на  графике  множество, состоящее  из  точек  



=   

 







С  помощью  графика найдем  все  точки  с  максимальным  значением  координаты . В данном  случае это одна  точка, имеющая координаты  (-2,12). Она  войдет  во  множество  оптимальных  по Парето исходов. Далее исключим  из  рассмотрения  все точки, координаты   которых не  превосходят, а координаты   больше  или равны  координатам  найденной  точки (-2,12) ( это  (-4,12) и (-6,12) ). Снова из оставшихся точек выберем все с  наибольшим значением  . Это точка с координатами  (-4,10). Из оставшихся  две точки  (-6,10)  и  (-8,10)  нам  не  подходят, поскольку  их  координаты    меньше  первой  координаты выбранной точки  (-4,10), а координаты   равны второй координате этой точки. Значит, соответствующие им  стратегии  являются  доминируемыми. Что  же  касается  точки  (-6, 6), то  она  войдет  во  множество оптимальных  по Парето  точек. Окончательно  получили, что  множество  Парето  данной задачи  состоит  из трех точек - (-2,12), (-4,10), (-6, 6). Они  отвечают  стратегиям  под  номерами  1, 4   и 7  соответственно. Таким  образом,  .

















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



                                          ,

                                  



         

Решение.





Строим область  допустимых  решений, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения  данной  ЗЛП. Каждое из неравенств  системы ограничений нашей задачи геометрически в системе  координат  (,)   определяет полуплоскость соответственно с граничными прямыми.

Первому ограничению соответствует прямая, пересекающая координатные оси в точках  с координатами  ( 0, 6 )  и  ( 6, 0 ).

Второму ограничению соответствует прямая, пересекающая координатные оси в точках с координатами  ( 0, -1 ) и ( 1, 0 ).

Третьему ограничению соответствует прямая, пересекающая координатные оси в точке с координатами  ( 1, 0 ) и проходящая  параллельно  оси .

Четвертому  ограничению соответствует прямая, пересекающая координатные оси в точках с координатами  ( 0, 6 ) и ( 3, 0 ).

Пятому  ограничению соответствует прямая, пересекающая координатные оси в точках с координатами  ( 0, 4 ) и ( -8, 0 ).

Шестому ограничению соответствует прямая, пересекающая координатные оси в точке с координатами  ( 0, 1 ) и проходящая  параллельно  оси .



Области, в которых выполняются соответствующие ограничения в виде неравенств, указаны  на  рисунке стрелками, направленными в сторону допустимых значений переменных.

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



Вектор  градиента  v  определяется  координатами  ( 0.5, 2 ).  Он  перпендикулярен  линиям  уровня  и  указывает направление возрастания  целевой функции. На  рисунке  красным  цветом  изображены линии уровня , заданные  уравнениями   и , т. е.  когда  целевая функция  принимает  значение  0  и 10  соответственно.

 



 

3. По  графику  видно, что касание линии  уровня ( ее  уравнение  ), перед выходом из области допустимых решений, произойдет в точке пересечения  прямых  и . Нетрудно  подсчитать, что  эта  точка  имеет  координаты   .

  

4.  В этой точке  значение  целевой  функции будет наибольшим, т.е.

  .

 



4. Перейти  к  задаче   с  ограничениями  :



                   

                  



Решение.

	

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

	 

	      

	    

	 

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

	

	



 



Подставив  эти  значения  вместо  переменных  ,  и    в  исходную  задачу, для  целевой  функции  получим:





 

Итак,  преобразовав полученные  неравенства  и целевую  функцию, имеем  задачу, эквивалентную  исходной с ограничениями   « = » , но  уже с  ограничениями   «  »:



  min,

	

	



 



              





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









Решение.



Перед  применением  симплекс-метода необходимо преобразовать систему линейных ограничений  и  рассматриваемую  нами  функцию к  каноническому  виду.

Все свободные члены системы ограничений неотрицательны, значит, выполнено одно из необходимых условий применения симплекс-метода. Осталось  все условия системы представить в  виде  уравнений. Для  этого к левой части 1-го  неравенства  системы ограничений прибавляем неотрицательную переменную  ,  к  левой части 2-го  неравенства  прибавляем неотрицательную переменную   , а  к  левой части 3-го -  неотрицательную переменную  , тем самым мы преобразуем неравенства  в равенства:



Определимся с начальным опорным решением. Наличие единичного базиса в системе ограничений позволяет легко найти  его.

Переменная  входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом 0, т.е.   - базисная переменная. Аналогично переменные   и  являются базисными. Остальные  переменные являются свободными. Приравняв свободные переменные к  0  в  системе ограничений, получаем  опорное решение:



 = ( 0 , 0 , 1 , 3 , 2 ).



Теперь  непосредственно  составим  таблицу:





Базисные

переменные











Свободные

переменные

Отношение



2

-1

1

0

0

1

-



1

3

0

1

0

3

1



1

-2

0

0

1

2

-

J(x)

-2

-3

0

0

0

0

-



В  качестве  ведущего выступает 2-ой столбец, поскольку -3 - наименьший элемент в строке J(x).  За ведущую строку  принимаем строку 2, т. к. отношение свободного члена к соответствующему элементу выбранного столбца для 2-ой строки является наименьшим из неотрицательных.  Разделим элементы 2-ой  строки  на 3, чтобы  получить в качестве  ведущего элемента 1:



Базисные

переменные











Свободные

переменные

Отношение



2

-1

1

0

0

1

-





1

0



0

1

1



1

-2

0

0

1

2

-

J(x)

-2

-3

0

0

0

0

-

 



Взяв  за  ведущий  выделенный  элемент, проведем соответствующие  преобразования. 

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на -1.

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на -2.

От элементов строки J(x) отнимаем соответствующие элементы строки 2, умноженные на  -3. В результате   имеем:





Базисные

переменные











Свободные

переменные

Отношение





0

1



0

2







1

0



0

1

3





0

0



1

4



J(x)

-

0

0

1

0

3

-

 



За ведущий столбец выберем столбец 1 ( по тому же правилу) , а за ведущую строку - строку 1.  Разделим элементы 1-ой  строки   на :





Базисные

переменные











Свободные

переменные

Отношение



1

0





0









1

0



0

1

3





0

0



1

4



J(x)

-1

0

0

1

0

3

-





Взяв  за  ведущий  выделенный  элемент, проведем соответствующие  преобразования. 

От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 

От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на .

От элементов строки J(x)  отнимаем соответствующие элементы строки 1, умноженные на -1.  В результате   имеем:



Базисные

переменные











Свободные

члены

Отношение



1

0





0



-



0

1

-



0



-



0

0

-



1



-

J(x)

0

0





0



-



Мы  получили строку J(x), состоящую только  из неотрицательных элементов. Значит,   оптимальное  решение  найдено,  = ( ,  , 0 , 0 ,  ).

J(x) =   -   -  

Поскольку  и  по условию неотрицательны, наибольшее значение функции равно свободному члену, т. е. .





6. Решить  транспортную  задачу.

            Транспортная  таблица  имеет  вид:













Запасы  



20

13

8

11

70



15

9

17

18

70



21

19

15

13

110

Заявки     

70

90

70

60





     

 Решение.



Найдём общую сумму запасов:  = 70 + 70 + 110 = 250.

Найдём общую сумму заявок:  =70 + 90 + 70 + 60 = 290.

В нашем случае запасы поставщиков ( 250 единиц продукции ) меньше, чем потребность потребителей ( 290 единиц продукции )  на 40 единиц. Введем в рассмотрение фиктивного поставщика  с запасом продукции,  равным 40. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.













Запасы  



20

13

8

11

70



15

9

17

18

70



21

19

15

13

110



0

0

0

0

40

Заявки     

70

90

70

60



 

Решение транспортной задачи начнем с построения допустимого базисного плана, для  этого  воспользуемся  методом северо-западного угла. 



Рассмотрим ячейку  таблицы. Запасы поставщика  составляют 70 единиц продукции, заявки   потребителя  составляет 70. Разместим в ячейку  значение , равное  min { 70 , 70 } = 70, т.е. мы полностью израсходoвали запасы поставщика . Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения. В  то же  время  мы полностью удовлетворили потребность потребителя , но будем считать, что потребность данного потребителя составляют 0 единиц продукции (не будем одновременно вычеркивать строку и столбец). 



Рассмотрим ячейку .Запасы поставщика  составляют 70 единиц продукции. Потребность потребителя  составляет 0. Разместим в ячейку  значение,  равное  min { 70 , 0 } = 0 ,т.е. мы полностью удовлетворили потребность потребителя . Поэтому  исключаем  1ый  столбец  таблицы  из дальнейшего рассмотрения.



Рассмотрим ячейку .Запасы поставщика  составляют 70 единиц продукции. Потребность потребителя  составляет 90. Разместим в ячейку  значение,  равное  min { 70 , 90 } = 70 ,т.е. мы полностью   израсходoвали запасы поставщика . Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения. 



Рассмотрим ячейку .Запасы поставщика  составляют 110  единиц продукции. Потребность потребителя  составляет 90 – 70 = 20 . Разместим в ячейку  значение,  равное  min { 110 , 20 } = 20 ,т.е. мы полностью   удовлетворили запросы потребителя . Поэтому   исключаем  2ой столбец  таблицы из дальнейшего рассмотрения.



Рассмотрим ячейку .Запасы поставщика  составляют 110 – 20 = 90 единиц продукции. Потребность потребителя  составляет 70. Разместим в ячейку  значение,  равное  min { 90 , 70 } = 70 , т.е. мы полностью удовлетворили запросы потребителя . Поэтому   исключаем  3ий столбец  таблицы из дальнейшего рассмотрения.



Рассмотрим ячейку . Запасы поставщика  составляют 90 – 70 = 20 единиц продукции. Потребность потребителя  составляет 60 . Разместим в ячейку  значение,  равное  min { 20 , 60 } = 20 ,т.е. мы полностью израсходoвали запасы поставщика . Поэтому  исключаем 3ью  строку  таблицы  из дальнейшего рассмотрения.



Рассмотрим ячейку . Запасы поставщика  составляют 40 единиц продукции. Потребность потребителя  составляет 60 – 20 = 40 . Разместим в ячейку  значение,  равное  min { 40 , 40 } = 40 ,т.е. мы полностью израсходoвали запасы поставщика . Поэтому  исключаем 4ую  строку  таблицы  из дальнейшего рассмотрения. В то  же  время мы  полностью удовлетворили запросы потребителя .



Мы нашли начальное опорное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все заявки потребителей. Занесем  полученные  значения  в  таблицу:





 









Запасы  



             20

70    

            13



                8

               11

70



             15

0

                 9

70

                 17



                  18



70



             21

            19

20

              15

70

                  13

20

110



                 0

                 0

                   0

                    0

40

40

Заявки     

70

90

70

60







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

 = 2070 + 15 0 + 9 70 + 19 20 + 15 70 + 13 20 + 0 40 = 3720 единиц.



Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 0 - 13 = -13

=  -  = 9 - 19 = -10

=  -  = 15 – ( -10 ) = 25

=  -  = 20 - 25 = -5













Запасы  

Потенциалы  



             20

70    

            13



                8

               11

70

-5



             15

0

                 9

70

                 17



                  18



70

-10



             21

            19

20

              15

70

                  13

20

110

0



                 0

                 0

                   0

                    0

40

40

-13

Заявки     

70

90

70

60





Потенциалы     

25

19

15

13







 Найдем оценки свободных ячеек следующим образом :



 =  - ( +  ) = 13 - ( -5 + 19 ) = -1

 =  - ( +  ) = 8 - ( -5 + 15 ) = -2

 =  - ( +  ) = 11 - ( -5 + 13 ) = 3

 =  - ( +  ) = 17 - ( -10 + 15 ) = 12

 =  - ( +  ) = 18 - ( -10 + 13 ) = 15

 =  - ( +  ) = 21 - ( 0 + 25 ) = -4

 =  - ( +  ) = 0 - ( -13 + 25 ) = -12

 =  - ( +  ) = 0 - ( -13 + 19 ) = -6

 =  - ( +  ) = 0 - ( -13 + 15 ) = -2



 Среди оценок есть отрицательные, следовательно, решение не оптимальное.

Из отрицательных оценок выбираем минимальную, она соответствует  ячейке , ее оценка  = -2.

Ячейки  ,  , , , ,  образуют цикл для свободной ячейки . Цикл начинается в этой свободной ячейке. Пусть ячейка  имеет порядковый номер 1.

 Среди ячеек цикла  , , , номера которых четные , выберем ячейку , как обладающую наименьшим значением 70. От ячеек цикла с четными номерами, мы отнимаем 70. К ячейкам с нечетными номерами мы прибавляем 70.   Ячейка  выйдет из базиса, ячейка  станет базисной.















Запасы  



             20

    

            13



                8

70

               11

70



             15

70

                 9



                 17



                  18



70



             21

            19

90

              15



                  13

20

110



                 0

                 0

                   0

                    0

40

40

Заявки     

70

90

70

60



 



Общие затраты на доставку всей продукции, для данного решения , составляют

 = 870 + 15 70 + 19 90 + 13 20 + 0 40  = 3580 единиц.



Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 0 - 13 = -13

=  -  = 8 - 15 = -7

=  -  = 9 - 19 = -10

=  -  = 15 – ( -10 ) = 25













Запасы  

Потенциалы  



             20

    

            13



                8

70

               11

70

-7



             15

70

                 9



                 17



                  18



70

-10



             21

            19

90

              15



                  13

20

110

0



                 0

                 0

                   0

                    0

40

40

-13

Заявки     

70

90

70

60





Потенциалы     

25

19

15

13











Найдем оценки свободных ячеек следующим образом :

 =  - ( +  ) = 20 - ( -7 + 25 ) = 2

 =  - ( +  ) = 13 - ( -7 + 19 ) = 1

 =  - ( +  ) = 11 - ( -7 + 13 ) = 5

 =  - ( +  ) = 17 - ( -10 + 15 ) = 12

 =  - ( +  ) = 18 - ( -10 + 13 ) = 15

 =  - ( +  ) = 21 - ( 0 + 25 ) = -4

 =  - ( +  ) = 0 - ( -13 + 25 ) = -12

 =  - ( +  ) = 0 - ( -13 + 19 ) = -6

 

Среди оценок есть отрицательные, следовательно, решение не оптимальное.

Из отрицательных оценок выбираем минимальную, она соответствует  ячейке , ее оценка  = -12.

Ячейки , ,  ,  ,,  образуют цикл для свободной ячейки . Цикл начинается в этой свободной ячейке. Пусть ячейка  имеет порядковый номер 1.

 Среди ячеек цикла  ,  , , номера которых четные , выберем ячейку , как обладающую наименьшим значением 40. От ячеек цикла с четными номерами, мы отнимаем 40. К ячейкам с нечетными номерами мы прибавляем 40.   Ячейка  выйдет из базиса, ячейка  станет базисной.













Запасы  



             20

    

            13



                8

70

               11

70



             15

30

                 9

40

                 17



                  18



70



             21

            19

50

              15



                  13

60

110



                 0

40

                 0

                   0

                    0



40

Заявки     

70

90

70

60







  



Общие затраты на доставку всей продукции, для данного решения , составляют

 = 870 + 15 30 + 9 40 + 19 50 + 13 60 + 0 40 = 3100 единиц.

 

Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 8 - 15 = -7

=  -  = 9 - 19 = -10

=  -  = 15 – ( -10 ) = 25

=  -  = 0 - 25 = -25















Запасы  

Потенциалы  



             20

    

            13



                8

70

               11

70

-7



             15

30

                 9

40

                 17



                  18



70

-10



             21

            19

50

              15



                  13

60

110

0



                 0

40

                 0

                   0

                    0

40

40

-25

Заявки     

70

90

70

60





Потенциалы     

25

19

15

13







Найдем оценки свободных ячеек следующим образом :

 =  - ( +  ) = 20 - ( -7 + 25 ) = 2

 =  - ( +  ) = 13 - ( -7 + 19 ) = 1

 =  - ( +  ) = 11 - ( -7 + 13 ) = 5

 =  - ( +  ) = 17 - ( -10 + 15 ) = 12

 =  - ( +  ) = 18 - ( -10 + 13 ) = 15

 =  - ( +  ) = 21 - ( 0 + 25 ) = -4

 =  - ( +  ) = 0 - ( -25 + 19 ) = 6

 =  - ( +  ) = 0 - ( -25 + 15 ) = 10

 =  - ( +  ) = 0 - ( -25 + 13 ) = 12





Среди оценок есть отрицательные, следовательно, решение не оптимальное.

Из отрицательных оценок выбираем минимальную, она соответствует  ячейке , ее оценка  = -4. Ячейки , , ,   образуют цикл для свободной ячейки . Цикл начинается в этой свободной ячейке. Пусть ячейка  имеет порядковый номер 1. 

Среди ячеек цикла  ,  ,номера которых четные , выберем ячейку , как обладающую наименьшим значением 30. От ячеек цикла с четными номерами, мы отнимаем 30. К ячейкам с нечетными номерами мы прибавляем 30.  Ячейка  выйдет из базиса, ячейка  станет базисной.













Запасы  



             20

    

            13



                8

70

               11

70



             15



                 9

70

                 17



                  18



70



             21

30

            19

20

              15



                  13

60

110



                 0

40

                 0

                   0

                    0



40

Заявки     

70

90

70

60







  Общие затраты на доставку всей продукции, для данного решения , составляют

 = 870 + 9 70 + 21 30 + 19 20 + 13 60 + 0 40 = 2980 единиц.

 

Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 21 – 0  = 21

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 0 - 21 = -21

=  -  = 8 - 15 = -7

=  -  = 9 - 19 = -10

 











Запасы  

Потенциалы  



             20

    

            13



                8

70

               11

70

-7



             15



                 9

70

                 17



                  18



70

-10



             21

30

            19

20

              15



                  13

60

110

0



                 0

40

                 0

                   0

                    0

40

40

-21

Заявки     

70

90

70

60





Потенциалы     

21

19

15

13











Найдем оценки свободных ячеек следующим образом :

Найдем оценки свободных ячеек следующим образом :

 =  - ( +  ) = 20 - ( -7 + 21 ) = 6

 =  - ( +  ) = 13 - ( -7 + 19 ) = 1

 =  - ( +  ) = 11 - ( -7 + 13 ) = 5

 =  - ( +  ) = 15 - ( -10 + 21 ) = 4

 =  - ( +  ) = 17 - ( -10 + 15 ) = 12

 =  - ( +  ) = 18 - ( -10 + 13 ) = 15

 =  - ( +  ) = 0 - ( -21 + 19 ) = 2

 =  - ( +  ) = 0 - ( -21 + 15 ) = 6

 =  - ( +  ) = 0 - ( -21 + 13 ) = 8



Все оценки свободных  ячеек положительные, следовательно, найдено оптимальное решение.



 

 = 870 + 9 70 + 21 30 + 19 20 + 13 60 + 0 40 = 2980 , т.е. общие затраты на доставку всей продукции, для оптимального решения составляют 2980 единиц.