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

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

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


Группа:


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


___________________________________________________________________________________


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


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


,



Решение.


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

Первому ограничению соответствует прямая, пересекающая координатные оси в точках с координатами ( 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
d>
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 единиц.

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:4275
Символов:36363
Размер:71.02 Кб.