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

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

Группа:

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

___________________________________________________________________________________

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

Набор задач №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	1	-
	1	3	1	3	1
	1	-2	1	2	-
J (x )	-2	-3	-

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

Базисные переменные						Свободные переменные	Отношение
	2	-1	1	1	-
		1		1	1
	1	-2	1	2	-
J (x )	-2	-3	-

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

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

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

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

Базисные переменные						Свободные переменные	Отношение
		1		2
		1		1	3
			1	4
J (x )	-	1	3	-

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

Базисные переменные						Свободные переменные	Отношение
	1
		1		1	3
			1	4
J (x )	-1	1	3	-

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

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

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

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

Базисные переменные						Свободные члены	Отношение
	1				-
	1	-			-
	-		1		-
J (x )				-

Мы получили строку 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
	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	9 70	17	18	70
	21	19 20	15 70	13 20	110
	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	9 70	17	18	70	-10
	21	19 20	15 70	13 20	110
	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
	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
	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
	40	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
	40	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. Ячейка выйдет из базиса, ячейка станет базисной.