Методы оптимизации систем

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

Факультет информационных технологий

Кафедра управления и информатики в технических системах

 

 

 

 

ОТЧЕТ

по расчетно-графической работе

по курсу «Методы оптимизации систем»

Исследование методов  оптимизации

ОГУ 220201.65.6012.040. О

 

 

 

 

 

 

 

Руководитель

преподаватель

____________Ю.С. Зданевич «__»__________ 2012г.

Исполнитель

студент группы 09УИТС

____________  Д. В. Каравайцев

«__»__________ 2012 г.

 

 

 

Оренбург 2012

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Методы решения задач линейного программирования

1.1 Решение задачи графическим способом

Найти максимум и минимум  целевой функции задачи линейного  программирования с двумя переменными графическим методом:

 

 

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

 

 

Построим полученные прямые на графике, как показано на рисунке 1:

 

 

Рисунок 1 – Построение прямых на графике

 

Построим вектор n с координатами n=(4;-3) и проводим перпендикулярную прямую соответствующую значений функции f=0, рисунок 2:

 

Рисунок 2 – Построение вектора n

 

Так как нас интересуют значение max и min целевой функции, то по графику видно, что первое касание прямой с областью допустимых значений происходит в точке B(1,2;3,3), а последнее в точке D(7;-1,2). Эти точки являются входом(min) и выходом(max) области допустимых значений.

Подставим в целевую функцию  полученные координаты точек:

 

 

 

Ответ:

1.2 Решение задачи симплекс методом

Торговое предприятие  для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b₁, м²), время младшего торгового персонала (общий объем b₂, человеко-часов), время старшего торгового персонала (общий объем b₃, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а₁₁ м², а₂₁ человеко-часов младшего торгового персонала, а₃₁ человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а₁₂, а₂₂,  а₃₂ и а₁₃,  а₂₃, а₃₃. Прибыль от реализации одной партии товаров А, В, С равна с₁, с₂, с₃ соответственно. При каком объеме реализации прибыль будет максимальна?

 

Таблица 1 – Исходные данные

b1	b2	b3	c1	c2	c3	a11	a12	a13	a21	a22	a23	a31	a32	a33
148	370	140	6	3	7	1	0,7	0	0,9	0,1	0,1	0,5	0,6	0,8

 

Решение: данная задача имеет вид:

 

 

Для построения опорного плана, введем дополнительные переменные:

 

 

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

 

 

Составим матрицу коэффициентов по формуле (1.1):

 

.                                                                        (1.1)               

 

                                         

 

Составим первый опорный план, таблица 2:

 

Таблица 2 – Первый опорный план

План	БП	СП	х1	х2	х3	х4	х5	х6	ζ min>0
1	х4	148	1	0,7	0	1	0	0	-
	х5	370	0,9	0,1	0,1	0	1	0	3700
	х6	140	0,5	0,6	0,8	0	0	1	175
	F(x1)	0	-6	-3	-7	0	0	0

 

Первый план не оптимальный, так как в индексной строке есть отрицательные элементы.

Составим второй опорный  план, следую алгоритму:

- просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных переменных) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

- просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке – ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;

- среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится ключевой;

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

- разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.

- строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

- в новой таблице все элементы ключевого столбца = 0, кроме разрешающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

- в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

                                                          (1.2)

 

Таблица 2 – Второй опорный  план

План	БП	СП	x1	x2	x3	x4	x5	x6	ζ min>0
2	x4	148	1	0,7	0	1	0	0	148
	x5	352.5	0.8375	0.025	0	0	1	-0.125	420.9
	x3	175	0.625	0.75	1	0	0	1.25	280
	F(x2)	1225	-1.625	2.25	0	0	0	8.75

 

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

Составим третий опорный  план, следую написанному выше алгоритму.

 

Таблица 3 – Третий опорный  план

План	БП	СП	x1	x2	x3	x4	x5	x6	ζ min>0
3	x1	148	1	0.7	0	1	0	0	148
	x5	228.55	0	-0.555	0	-0.8375	1	-0.125	420.9
	x3	82.5	0	0.31	1	-0.625	0	1.25	280
	F(x3)	1465.5	0	3.38	0	1.625	0	8.75

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

 

 

 

Ответ:

1.3 Решение двойственной  задачи линейного программирования

На основе подраздела 1.2 составим экономико-математическую модель двойственной задачи:

 

 

Прямая:

 

Таблица 3 – Матрица  исходной задачи

	Элементы матрицы						Bj
	0,1	0,9	0,4	1	0	0	108
	0,9	0,8	0,4	0	1	0	413
	0,1	0,2	0,3	0	0	1	129
Ci	4	2	4	0	0	0	max

 

Двойственная:

 

Таблица 4 – Транспонированная  матрица

Транспонированная матрица
0,8	0,9	0,1	4
0,9	0,8	0,2	2
0,4	0,4	0,3	4
1	0	0	0
0	1	0	0
0	0	1	0
108	413	129	min

Выпишем соответствие между  прямой и двойственной задачи:

Таблица 5 – Соответствие

Основные переменные			Дополнительные переменные
x1	x2	x3	x4	x5	x6
z4	z5	z6	z1	z2	z3

 

На основе данного  решения двойственная задача выглядит следующим образом:

 

 

                                                      

                                             

                                         

 

Ответ: .

1.4 Решение транспортной задачи методом потенциалов

Есть три поставщика с запасами a₁, a₂, a₃ и 5 потребителей (их спрос b₁, b₂, b₃, b₄, b₅ соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок.

 

Решение: исходные данные по задаче указаны в таблице 6:

 

Таблица 6 – Таблица тарифов

Пункт	b1	b2	b3	b4	b5	Запас
а1	6	2	1	8	6	65
а2	5	7	2	1	1	50
а3	6	7	2	2	7	20
Потреб	27	13	19	15	11