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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

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

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

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

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

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

ОТЧЕТ

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

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

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

ОГУ 220201.65.6012.043. О

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

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

Ю.С. Зданевич

Исполнитель

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

Д.А. Кузнецов

Оренбург 2012

Содержание

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

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

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

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

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

2. Решение задач линейного программирования с помощью MS Excel 13

2.1 Решение задачи симплекс методом с помощью надстройки MS Excel «Поиск решения» 13

2.2 Решение двойственной задачи и анализ полученных данных 15

2.3 Решение задачи в предположении целочисленности переменных 17

2.4 Решение транспортной задачи с помощью надстройки MS Excel «Поиск решения» 18

Выводы 21

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

функция задача программирование оптимизация

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

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

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

(1.1)

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

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

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

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

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

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

(1.2)

(1.3)

Ответ:

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

Торговое предприятие для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b1, м2), время младшего торгового персонала (общий объем b2, человеко-часов), время старшего торгового персонала (общий объем b3, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а11 м2, а21 человеко-часов младшего торгового персонала, а31 человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а12, а22, а32 и а13, а23, а33. Прибыль от реализации одной партии товаров А, В, С равна с1, с2, с3 соответственно. При каком объеме реализации прибыль будет максимальна?

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

b1	b2	b3	c1	c2	c3	a11	a12	a13	a21	a22	a23	a31	a32	a33
151	436	195	4	10	1	0,8	0,1	0	0,4	0,4	0,5	0,9	0,8	0,3

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

(1.4)

(1.5)

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

 (1.6)

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

(1.7)

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

. (1.8)

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

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

План	БП	СП	х1	х2	х3	х4	х5	х6	ж min>0
1	х4	151	0,8	0,1	1	1	0	0	1510
	х5	436	0,4	0,4	0,5	0	1	0	1090
	х6	195	0,9	0,8	0,3	0	0	1	243,75
	F(x1)	0	-4	-10	-1	0	0	0

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

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

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

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

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

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

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

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

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

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

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

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

(1.9)

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

План	БП	СП	х1	х2	х3	х4	х5	х6	ж min>0
2	х4	126,6	0,688	0	0,963	1	0	-0,13
	х5	338,5	-0,05	0	0,35	0	1	-0,5
	х2	243,8	1,125	1	0,375	0	0	1,25
	F(x2)	2438	7,25	0	2,75	0	0	12,5

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

Ответ:

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

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

Прямая:

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

	Элементы матрицы	Bj
	0,8	0,1	1	1	0	0	151
	0,4	0,4	0,5	0	1	0	436
	0,9	0,8	0,3	0	0	1	195
Ci	4	10	1	0	0	0	max

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

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

Транспонированная матрица
0,8	0,4	0,9	4
0,1	0,4	0,8	10
1	0,5	0,3	1
1	0	0	0
0	1	0	0
0	0	1	0
151	436	195	min

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

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

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

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

(1.10)

Ответ:

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

Есть три поставщика с запасами a1, a2, a3 и 5 потребителей (их спрос b1, b2, b3, b4, b5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок.

Таблица 6 - Исходные данные

a1	a2	a3	b1	b2	b3	b4	b5	c11	c12	c13	c14	c15	c21	c22	c23	c24	c25
20	32	28	20	15	30	25	45	9	2	6	2	6	3	6	8	3	7

Решение: данную задачу можно представить в виде таблицы:

Таблица 7 - Таблица тарифов

	B1	B2	B3	B4	B5	Запасы
A1	9	2	6	2	6	20
A2	3	6	8	3	7	32
A3	6	2	1	8	6	28
Потребности	20	15	30	25	45

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

Таблица 8 - Метод min стоимости

Поставщик	Потребитель	Запасы
	B1	B2	B3	B4	B5
A1	-	15	-	5	-	20
A2	20	-	-	12	-	32
A3	-	-	28	-	-	28
A4	-	-	2	8	45	55
Потребности	20	15	30	25	45

Составим целевую функцию:

(1.11)

Проверим полученный опорный план на невырожденность:

(1.12)

Определим потенциалы поставщиков и потребителя из формулы (1.18):

(1.13)

Проверим опорный план на оптимальность, вычислив оценки свободных ячеек из формулы (1.20):

(1.14)

Все оценки свободных ячеек не отрицательны, найдено оптимальное решение.

Ответ: Общие затраты на доставку все продукции составляют 164 ден.

ед.

2. Решение задач линейного программирования с помощью MS Excel

2.1 Решение задачи симплекс методом с помощью надстройки MS Excel «Поиск решения»

Торговое предприятие для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b1, м2), время младшего торгового персонала (общий объем b2, человеко-часов), время старшего торгового персонала (общий объем b3, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а11 м2, а21 человеко-часов младшего торгового персонала, а31 человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а12, а22, а32 и а13, а23, а33. Прибыль от реализации одной партии товаров А, В, С равна с1, с2, с3 соответственно. При каком объеме реализации прибыль будет максимальна?

Исходные данные задачи представлены на рисунке (2.1):

Рисунок 2.1 - Исходные данные

В ячейку E6, значение целевой функции, введем формулу (2.1):

(2.1)

В ячейки Е10:Е12, количество материалов, введем формулы (2.2):

(2.2)

Результат ввода формул (2.1) и (2.2) показан на рисунке (2.2):

Рисунок 2.2 - Результат ввода формул (2.1) и (2.2)

Выбираем команду «Поиск решения» и заполняем диалоговое окно «Поиск решения» как показано на рисунке (2.3):

Рисунок 2.3 - Диалоговое окно команды «Поиск решения» для задачи оптимизационного типа

Рисунок 2.4 - Результат расчета задачи оптимизационного типа

Прибыль будет максимальна при объеме реализации 2437,5.

Ответ:

2.2 Решение двойственной задачи и анализ полученных данных

К имеющимся данным задачи подраздела 2.1 добавим следующее: двойственные оценки (z) - H10:H13, в ячейку Н15 введем формулу (2.1) целевой функции:

(2.1)

Рисунок 2.5 - Ввод формулы (2.1) целевой ячейки

В ячейку диапазона B14:D14 введем формулы (2.2) определяющие левые части ограничений двойственной задачи:

(2.2)

Рисунок 2.6 - Ввод формулы (2.2) ограничения двойственной задачи

Выбираем команду «Поиск решения» и заполним диалоговое окно как показано на рисунке (2.7):

Рисунок 2.7 - Диалоговое окно команды «Поиск решения» для двойственной задачи

Затраты будут минимальны при объеме реализации равной 2437,5.

Ответ:

2.3 Решение задачи в предположении целочисленности переменных

На основе задачи подраздела 2.1, при помощи команды «Поиск решения», добавим следующее ограничение целочисленности рисунок (2.8):

Рисунок 2.8 - Диалоговое окно команды «Поиск решения»

Рисунок 2.9 - Результат целочисленного решения задачи симплекс методом с помощью надстройки MS Excel «Поиск решения»

2.4 Решение транспортной задачи с помощью надстройки MS Excel «Поиск решения»

Есть три поставщика с запасами a1, a2, a3 и 5 потребителей (их спрос b1, b2, b3, b4, b5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок. Исходные данные представлены на рисунке (10).

Рисунок 2.10 - Исходные данные

Исходная задача является открытой моделью, так как сумма потребностей больше суммы поставщика. Добавим фиктивного поставщика с нулевыми тарифами и запасами, рассчитанными по формуле (2.10):

(2.10)

Введем в ячейку G12 формулу (2.11) целевой функции:

(2.11)

В ячейки B12:F12 введем формулы (2.12):

(2.12)

В ячейки G8:G11 введем формулы (2.13):

(2.13)

При помощи команды «Поиск решений» добавим следующие ограничения и значение целевой функции рисунок (2.12):

Рисунок 2.12 - Диалоговое окно команды «Поиск решений»

Рисунок 2.13 - Результат расчета транспортной задачи

Минимальные затраты на поставку всей продукции составляют 164 ден.ед.

Ответ:

Выводы

В данной расчетно-графической работе было рассмотрено решение задач линейного программирования различными методами. Графическим метом был произведен расчет и найдено min(max) значение целевой функции. Симплекс методом был рассчитан оптимальный план реализации продукции для получения max прибыли. Так же решение задачи транспортным методом, найден оптимальный план перевозки продукции при min расходах. Для проверки решения данные задачи были рассчитаны при помощи программы MS Excel, полученные значения целевых функций совпали.

Размещено на www.allbest.

...