Контрольная работа по "Методы принятия оптимальных решений"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ФГБОУ ВПО «Уральский государственный экономический университет»

 

Центр дистанционного образования

 

 

 

 

 

 

 

 

Контрольная работа

по дисциплине: "Методы принятия оптимальных решений"

Вариант № 6

 

 

 

 

 

Исполнитель: студентка

Направление: Управление качеством

Профиль: Управление качеством в производственно-технологических системах

Группа: УКу-12КТ

Никонова Татьяна Юрьевна

Преподаватель: Кандоба Игорь Николаевич  

 

 

 

 

Краснотурьинск

2014

СОДЕРЖАНИЕ

Задача 1 3

Задача 2 5

Задача 3 11

Задача 4 15

Задача 5 17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1. Решить графически.

min F = 2x1 – 6x2;

 

 

Решение: Построим в осях Х1ОХ2 граничные прямые, соответствующие исходным неравенствам. Каждая из этих прямых делит плоскость на две части, одна из которых удовлетворяет неравенству. Подставив в неравенство координаты любой точки, например (0;0), находим эту полуплоскость (отмечено стрелками). В результате получена область ОДР, ограничивающая часть плоскости, удовлетворяющую всем ограничениям – это область допустимых решений – ОДР (заштриховано). Следует отметить, что ОДР не ограничена в сторону бесконечно больших значений х1 и х2.

Целевая функция в виде нулевой линии уровня F0 проходит через начало координат. Если перемещать эту линию в направлении вектора – вниз, скользя началом линии по оси х1, то значения целевой функции будут возрастать от нуля до бесконечности при х2 = 0. Если её перемещать в противоположном направлении, скользя началом линии по прямой   -х1 + х2 = 1, то значения целевой функции будут уменьшаться от нуля до  бесконечности при х1 ≥  x2 – 1.

Т.к. условием задано найти минимум, то получим решение задачи в виде:

Если бы ограничения в условии были записаны так:

то ОДР превратилась бы в четырёхугольник ОАВС, минимум функции был бы в точке В с координатами х1 = 1; х2 = 1,5 и целевая функция приобрела бы значение:

Fmin = 2x1 – 6x2 = 2∙1 – 6∙1,5 = -7;

Соответственно максимум функции оказался бы в точке С (2; 0).

Fmax = 2x1 – 6x2 = 2∙2 – 6∙0 = 4;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2. Для производства 4-х видов продукции используется 3 вида сырья. Нормы расхода сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	Изделие 1	Изделие 2	Изделие 3	Изделие 4
Ресурс 1	3	7	1	1	50
Ресурс 2	1	4	2	5	40
Ресурс 3	4	7	12	10	100
Ценность	6	7	9,5	7

Решение: Обозначим х1 – выпуск изделия 1; х2 – выпуск изделия 2; х3 – выпуск изделия 3; х4 – выпуск изделия 4.

Т.к. затраты ресурсов не могут превосходить их запасы сi, то математическая модель задачи предстанет в виде:

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

Z = αх1 + βх2 + γх3 + δх4 = 6х1 + 7х2 + 9,5х3 + 7х4 → max;

Преобразуем систему неравенств в систему уравнений, введя дополнительные переменные х5; х6; х7, которые дают начальный базис:

Для решения этой системы уравнений составим исходную симплекс-таблицу №1. Здесь по строкам записаны коэффициенты при неизвестных в уравнениях. В верхней строке записаны коэффициенты при целевой функции, а в нижней – оценочной – те же коэффициенты с обратным знаком. Базисные переменные х4, х5, х6 имеют нулевые коэффициенты Сi в целевой функции. Столбец В – свободные члены уравнений.

Сi Базис хi	Сi	В	6	7	9,5	7	0	0	0
			x1	x2	х3	х4	х5	х6	х7
х5	0	50	3	7	1	4	1	0	0	50
х6	0	40	1	4	2	5	0	1	0	20
х7	0	100	4	7	12	10	0	0	1	8,333
Z ≥ 0		0	-6	-7	-9,5	-7	0	0	0	№1

Т.к. наиболее отрицательная оценка (–9,5) в столбце х3, то этот столбец выберем в качестве разрешающего столбца.

Отношения свободных членов В к элементам разрешающего столбца Вi/xi записаны в правом столбце – здесь минимум в строке х7 – эта строка разрешающая.

На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент 12 (выделен). Значение целевой функции Z0 = 0, т.к. все базисные переменные фиктивны и коэффициенты при них в целевой функции равны нулю.

Вводим в базис переменную х3 со своей оценкой вместо переменной х5.

Строку х7 – там разрешающий элемент – делим на него, т.е. на 12. В столбце х3 все нули кроме разрешающего элемента. Остальные элементы пересчитаем по правилу прямоугольника:

где аik; а′ik – старое и новое значение в углу прямоугольника, диагонального разрешающему элементу, аqp – разрешающий элемент; аqk; aip – другие углы, смежные с разрешающим элементом. Получили таблицу №2.

Сi Базис хi	Сi	В	6	7	9,5	7	0	0	0
			x1	x2	х3	х4	х5	х6	х7
х5	0	41,667	2,6667	6,4167	0	3,1667	1	0	-0,0833	15,625
х6	0	23,3333	0,3333	2,8333	0	3,3333	0	1	-0,1667	70
х3	9,5	8,333	0,3333	0,5833	1	0,8333	0	0	0,0833	25
Z1		79,1667	-2,833	-1,4583	0	0,9167	0	0	0,7917	№2

Здесь значение целевой функции Z1 = 79,167, но т.к. в строке Z есть отрицательные оценки, это решение не оптимально и значение Z может быть увеличено.

Выбрав разрешающий элемент  – это 2,6667 в столбце х1 и введя переменную х1 в базис вместо х5 получили третью таблицу, в оценочной строке которой нет отрицательных оценок, т.е. план оптимален.

 

 

 

Сi Базис хi	Сi	В	6	7	9,5	7	0	0	0
			x1	x2	х3	х4	х5	х6	х7
х1	6	15,625	1,000	2,406	0,000	1,188	0,375	0,000	-0,031
х6	0	18,125	0,000	2,031	0,000	2,938	-0,125	1,000	-0,156
х3	9,5	3,125	0,000	-0,219	1,000	0,438	-0,125	0,000	0,094
Z ≥ 0		123,4375	0,000	5,359	0,000	4,281	1,0625	0,000	0,70313	№3

Т.о. х1 = 15,625; х2 = х4 = 0; х3 = 3,125; Zmax = 123,4375.

Значение х6 = 18,125 указывает величину неиспользованного второго ресурса.

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

Т.о. для получения максимальной прибыли следует производить изделия 1 и 3, отказавшись от производства изделий 2 и 4.

Это же решение может быть получено в MS Excel применением инструмента "поиск решения". Лист Excel с результатами решения представлен ниже:

 

 

 

 

 

 

 

 

		ПЕРЕМЕННЫЕ
	Х1	Х2	Х3	Х4
Значения	15,625	0,0000	3,125	0	ЦФ
Коэф. в ЦФ	6	7	9,5	7	123,4375
		ОГРАНИЧЕНИЯ
					Лев.часть.	Знак	Прав.часть.
Ресурс 1	3	7	1	4	50,0000	<=	50
Ресурс 2	1	4	2	5	21,8750	<=	40
Ресурс 3	4	7	12	10	100,0000	<=	100

Здесь показано, что максимум целевой функции ЦФмакс = 123,4375 при оптимальном решении Х(15,625; 0; 3,125; 0). Ресурс 1 и ресурс 3 использованы полностью (левая и правая части равны между собой), а из ресурса 3 использовано лишь 21,875 ед., т.е. остаток 40 – 21,875 = 18,125 ед.