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

Группа:

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


___________________________________________________________________________________



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









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

	Погрузчик              Тележка (часы/ед.)              (часы/ед.)	Общ. мощ. (часы)
Мет. обраб. Сварка Сборка	6                                4 2                                3 9                                3	2400 1500 2700

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

Решение.


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

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

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

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

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

4)       (ограничение на неотрицательность переменных) .
Итак,  получили  следующую  математическую  модель  данной  задачи:
   



   

   

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

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

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  соответственно. Таким  образом,  .
3.     
Геометрически  решить  задачу  линейного  программирования:
                                          ,

                                 
        

Решение.

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

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

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

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

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

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

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

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

2. Вектор  градиента  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) =   - 
 -
 

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

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

 = 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 единиц.