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

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

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

Решение:

Решим неравенство графическим способом. Введем на плоскости прямоугольную систему координат , в которой точки с координатами находятся  в первом  квадранте этой координатной плоскости.

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

Графическое решение нашей системы приведено на рисунке 1. Здесь прямая (1), соответствует уравнению . Построена она по двум точкам ( ) и    ( . Точка О(0,0), удовлетворяющая нашему первому неравенству , определяет в качестве решения полуплоскость, лежащую ниже прямой (1). Аналогично строим другие прямые и находим соответствующие неравенствам полуплоскости. Решением же системы является отрезок ВС – часть прямой

Найдем координаты точек B и C.

ВС образует область допустимых решений или допустимых планов нашей задачи, в которой мы и будем искать оптимальное решение L= . Для этого построим вектор , который укажет направление наибольшего возрастания целевой функции.

Линии, перпендикулярные этому вектору - , которые называются линиями уровня, задают одно из возможных значений целевой функции. На графике одно из этих уравнений, например , задает прямую, которой соответствует значение L=0. Максимальное же значение целевой функции будет соответствовать, такой линии уровня, которая будет получена путем параллельного переноса одной из линий уровня, проходящей через область допустимых планов, в пограничную область в направлении вектора   =(-2,5)=grad L. В нашем случае максимум целевой функции достигается в точке B.

 и 

Будем параллельно перемещать ее в направлении вектора (-2,5) до границы области допустимых планов в противоположном направлении. Минимум – в точке С(8;0).

 

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

Для изготовления различных видов продукции 1, 2, 3 и 4 предприятие использует три вида сырья А, В и С. Нормы расхода сырья на производство единицы продукции каждого вида, цена одного изделия, а также запас каждого вида ресурса известны и приведены в таблице 1.1.

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

 

Таблица 1.1 – Нормативы затрат ресурсов на единицу продукции каждого вида

(общие для всех вариантов)

РЕСУРС	ВИДЫ ПРОДУКЦИИ				ЗАПАС  РЕСУРСА
	1	2	3	4
А	6	8	4	7	3960
В	0,75	0,64	0,5	0,8	540
С	8	12	10	14	6600
ЭКОНОМИЧЕСКИЙ ЭФФЕКТ	6	7	5	8	МАХ

 

План решения задачи:

• выбрать из таблиц исходные данные своего варианта;
• обозначить неизвестные задачи;
• сформировать систему ограничений и целевую функцию задачи;
• привести систему ограничений к каноническому виду, обозначив и введя дополнительные переменные;
• вычертить симплексную таблицу и заполнить еѐ первоначальным опорным планом;
• пользуясь алгоритмом симплексного метода, найти оптимальное решение задачи;
• выписать оптимальное решение и провести его экономический анализ.

Решение

Обозначим через - количества продукции 1-го, 2-го, 3-го, 4-го видов.

Система ограничений по ресурсам:

Целевая функция:

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

Целевая функция:

 

Составим симплексную таблицу и заполним еѐ первоначальным опорным планом

Базис
	6	8	4	7	1	0	0	3960
	0,75	0,64	0,5	0,8	0	1	0	540
	8	12	10	14	0	0	1	6600
-Z	6	7	5	8	0	0	0	0

 

 

Решим симплекс-методом

Базис
	6	8	4	7	1	0	0	39600	565,7
	0,75	0,64	0,5	0,8	0	1	0	540	675
	8	12	10	14	0	0	1	6600	471,4
-Z	6	7	5	8	0	0	0	0
	2	2	-1	0	1	0	-0,5	660	330
	0,293	-0,046	-0,071	0	0	1	-0,057	162,9	556,1
	0,571	0,857	0,714	1	0	0	0,071	471,4	825
-Z	1,429	0,143	-0,714	0	0	0	-0,571	3771
	1	1	-0,5	0	0,5	0	-0,25	330
	0	-0,339	0,075	0	-0,146	1	0,016	66,21
	0	0,286	1	1	-0,286	0	0,214	282,9
-Z	0	-1,290	0	0	-0,714	0	-0,214	4243

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

Оптимальное решение: . Продукцию 1 вида нужно выпустить в объеме 330, 4-го –282,9. Продукцию 2-го и третьего вида не надо выпускать. Прибыль составляет 4243.

Задание 3. Решить открытую транспортную задачу методом потенциалов.

На оптовых складах А1, А2, А3, А4 имеются запасы некоторого продукта в известных количествах, который необходимо доставить в магазины В1, В2, В3, В4, В5. Известны также тарифы на перевозку единицы продукта из каждого склада в каждый магазин. Найти такой вариант прикрепления магазинов к складам, при котором сумма затрат на перевозку была бы минимальной.

Оптовые склады	Магазины					Запасы
	B1	B2	B3	B4	B5
A1	5	4	10	7	8	740
A2	7	6	7	10	6	600
A3	2	9	5	3	4	560
A4	6	11	4	12	5	600
Потребности	640	660	470	250	980

 

Решение

Общее число запасов на складах :

2500

; Общая потребность :

3000

Для отыскания первого опорного плана применим метод минимального элемента.

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

	B1		B2		B3		B4		B5		Запасы	Ui
A1		5		4		10		7		8	740	8
			660						80
A2		7		6		7		10		6	600	6
									600
A3		2		9		5		3		4	560	4
	140						250		170
A4		6		11		4		12		5	600	5
					470				130
A5		0		0		0		0		0	500	2
	500
Потребности	640		660		470		250		980
Vj	-2		-4		-1		-1		0

 

	B1		B2		B3		B4		B5		Запасы	Ui
A1		5		4		10		7		8	740	5
	80		660
A2		7		6		7		10		6	600	6
									600
A3		2		9		5		3		4	560	2
	310						250
A4		6		11		4		12		5	600	5
					470				130
A5		0		0		0		0		0	500	0
	250
Потребности	640		660		470		250		980
Vj	0		-1		-1		1		0