Исследование операций и методы оптимизации.-1

1

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

Федеральное государственное бюджетное образовательное учреждение высшего образования

Томский государственный университет систем управления и радиоэлектроники (ТУСУР)

Факультет систем управления (ФСУ)

Е.Б. Грибанова

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

Методические указания по выполнению лабораторных работ для студентов заочной формы обучения

Томск – 2017

2

В методических указаниях представлены задания по лабораторным работам по дисциплине «Исследование операций и методы оптимизации в экономике». Темы лабораторных работ: «Минимизация функции одной переменно», «Минимизация функции нескольких переменных», «Условная оптимизация». Представлены примеры выполнения лабораторных работ с помощью пакетов Excel, MathCad,

языка программирования Java.

3

СОДЕРЖАНИЕ

Оглавление

Введение.......................................................................................................................................................	4
1. Минимизация функции одной переменной..................................................................................	5
1.1 Методы прямого поиска....................................................................................................................	5
1.1.1. Основные понятия .....................................................................................................................	5
1.1.2. Метод равномерного поиска ....................................................................................................	6
1.1.3. Метод дихотомии .....................................................................................................................	7
1.1.4. Метод золотого сечения ..........................................................................................................	9
1.1.5. Метод Пауэлла ........................................................................................................................	10
1.1.6. Метод Монте-Карло...............................................................................................................	12
1.2 Методы, основанные на использовании производных. ...............................................................	12
1.2.1. Метод Ньютона ......................................................................................................................	12
1.2.2. Метод средней точки (поиск Больцано) ...............................................................................	13
1.3. Простейшие формулы численного дифференцирования ...........................................................	14
1.4. Задание на лабораторную работу №1 ...........................................................................................	14
2. Минимизация функции нескольких переменных ........................................................................	15
2.1. Основные понятия ..........................................................................................................................	15
2.2. Прямые методы...............................................................................................................................	15
2.2.1. Метод Гаусса...........................................................................................................................	16
2.2.2. Метод Хука-Дживса ...............................................................................................................	16
2.2.3. Симплексный метод ................................................................................................................	18
2.3. Градиентные методы ......................................................................................................................	20
2.3.1 Метод градиентного спуска ...................................................................................................	21
2.3.2. Метод Коши.............................................................................................................................	22
2.3.3. Метод Ньютона ......................................................................................................................	22
2.4. Задание.............................................................................................................................................	22
3. Условная оптимизация...................................................................................................................	24
3.1. Задача линейного программирования ..........................................................................................	24
3.1.1. Постановка задачи о диете ................................................................................................	24
3.1.2 Постановка транспортной задачи ........................................................................................	24
3.2. Задание............................................................................................................................................	25
3.2.1. Задача о диете .........................................................................................................................	25
3.2.2. Транспортная задача ..............................................................................................................	27
................................................................................................................................................	28

Литература

Приложение А. Варианты заданий к лабораторной работе №1 «Минимизация функции одной

переменной» ..............................................................................................................................................	29
Приложение Б Варианты заданий к лабораторной работе №2 «Минимизация функции
нескольких переменных» .........................................................................................................................	32

Приложение Г. Примеры отчетов по лабораторным работам по дисциплине «Исследование

операций и методы оптимизации» ......................................................................................................	36
Примеры отчетов по лабораторной работе №1 ..................................................................................	36
Пример отчета по лабораторной работе №2 .......................................................................................	62
Примеры отчетов по лабораторной работе №3 ..................................................................................	75
Приложение Д. Надстройка Excel «Поиск решения» .......................................................................	95
Приложение Ж. Решение оптимизационных задач в MathCAD....................................................	107

4

Введение

Данные методические указания предназначены для выполнения лабораторных работ по дисциплине «Исследование операций и методы оптимизации» и разработаны с учетом требований ФГОС ВО для направления подготовки 09.03.03 «Прикладная информатика».

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

Лабораторные работы выполняются в соответствии с порядком, описанном в методических указаниях.

5

1.Минимизация функции одной переменной

1.1Методы прямого поиска

1.1.1.Основные понятия

Вданной лабораторной работе рассматриваются задачи, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси

f(x) min ; x [a;b] .

Число x* [a;b] называется точкой глобального (абсолютного) минимума,

или просто точкой минимума, функции		f (x) на отрезке [a;b] , если f (x* ) f (x)		для
всех x [a;b] .
Число x* [a;b]	называется точкой локального минимума функции		f (x) на
отрезке [a;b] , если	f (x* ) f (x) для	всех x [a;b] , достаточно близких	к	х*
(рис.1.1).

Рис.1.1 График функции f (x) cos(14,5x 0,3) x(x 0, 2) 0,01

6

Функция f (x) является унимодальной, если с увеличением x слева от х* она монотонно убывает, справа - монотонно возрастает.

Если функция f (x) – выпуклая на [a;b] , то на любом отрезке [x ; x ] [a;b] ее

график расположен не выше хорды, проведенной через точки графика с абсциссами x и x .

Всякая выпуклая непрерывная на отрезке [a;b] функция является унимодальной (обратное неверно).

В данной работе будут рассмотрены методы поиска минимума выпуклой функции.

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

использующие производные.

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

1.метод равномерного поиска;

2.метод дихотомии;

3.метод золотого сечения;

4.Пауэлла;

5.метод Монте-Карло.

Методы первого порядка используют значение или знак производной функции в вычисленных точках:

1.метод Ньютона;

2.метод средней точки.

1.1.2. Метод равномерного поиска

Суть метода: интервал [a 0 ,b0 ] делится на N + 1 равных подинтервалов, в

каждой точке (границах подинтервалов) вычисляется значение функции.

Выбирается точка, в которой значение функции минимально.

7

y

a0 x1 x2 b0 x

Рис.1.2 Метод равномерного поиска. Разбиение интервала на три под интервала

				Алгоритм
Шаг 1. Задать исходные		данные: начальный интервал неопределенности
L0 [a0 ,b0 ], N - количество вычислений функции.
Шаг 2.	Вычислить точки x	a	0	i	(b0 a0 )	,i 1..N , равноотстоящие друг от
	i				N 1
друга.
Шаг 3.	Вычислить значения функции в N найденных точках: f (xi ) , i 1..N .
Шаг 4.	Среди точек xi , i 1..N , найти такую, в которой функция принимает

наименьшее значение: f (xk ) min f (xi ) .

1.1.3.Метод дихотомии

Суть метода: вычисляется середина интервала [a 0 ,b0 ] и две точки по обе

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

значит, функция возрастает на этом промежутке (рис.1.3), и происходит изменение правой границы. Иначе – функция убывает и происходит изменение левой границы.

8

y

a0

y0 z0

b0

x

Рис.1.3 Метод дихотомии. Возрастание функции на интервале [y0;z0], поэтому правая граница b0 будет перемещена в точку z0

					Алгоритм
Шаг 1. Задать исходные данные: начальный интервал неопределенности
L0 [a0 ,b0 ], >0 -малое число, l > 0 – точность ( (0,2l) ).
Шаг 2.	Положить k = 0.
Шаг 3.	Вычислить yk		ak bk		, f ( yk ) , zk		ak bk		, f (zk ) .
		2				2
Шаг 4.	Сравнить f ( yk ) c f (zk ) :
а) если f ( yk ) f (zk ) , положить ak 1						ak ,bk 1		zk и перейти к шагу 5;
б) если f ( yk ) f (zk ) , положить ak 1						yk ,bk 1		bk .
Шаг 5.	Вычислить Lk	| bk 1 ak 1 | и проверить условие окончания:
а) если Lk l ,		процесс		поиска завершается				и в качестве приближенного

решения можно взять середину последнего интервала:

x* ak 1 bk 1 ; 2

б) если Lk l , положить k k 1 и перейти к шагу 3.

9

1.1.4. Метод золотого сечения Суть метода: аналогична методу дихотомии, однако две точки определяются

в пропорции золотого сечения (рис.1.4).

y

a0

y0 z0

b0

x

Рис.1.4 Метод золотого сечения. Возрастание функции на интервале [y0;z0],

поэтому правая граница b0 будет перемещена в точку z0

Алгоритм

Шаг 1. Задать исходные данные: начальный интервал неопределенности

L0 [a0 ,b0 ], точность l >0.

Шаг 2. Положить k =0.

Шаг 3. Вычислить

y		a		3 5		(b a ); z			a b y			.
	0							0			0
		0	2		0		0		0	0
Шаг 4.			Вычислить f ( yk ) ,					f (zk ) .
Шаг 5.			Сравнить f ( yk ) с f (zk ) :
		а) если f ( yk ) f (zk ) , то положить ak 1 ak ,bk 1 zk и
yk 1 ak 1 bk 1 yk , zk 1								yk . Перейти к шагу 6;
		б) если f ( yk ) f (zk ) , положить ak 1 yk ,bk 1 bk и
yk 1 zk , zk 1 ak 1 bk 1 zk .

Шаг 6. Вычислить Lk | bk 1 ak 1 | и проверить условие окончания:

10

а) если Lk l , процесс поиска завершается и в качестве приближенного решения можно взять середину последнего интервала:

x* ak 1 bk 1 ; 2

б) если Lk l , положить k k 1 и перейти к шагу 4.

1.1.5. Метод Пауэлла Суть метода: определить три точки в направлении уменьшения функции и

рассчитать квадратичную аппроксимацию. Сравнить значение функции в наилучшей из трех точек и в точке квадратичной аппроксимации и если условие останова не выполняется, то выбирается наилучшая точка и две точки по обе стороны от неё. Так на рис. 1.5 будет выбрана точка x и две точки по обе стороны

( x1, x2 ) .

y

x1

ˉx x2

x3

x

Рис.1.5 Определение точек методом Пауэлла

Алгоритм

Исходные данные: x1 - начальная точка; x - выбранная величина шага по оси x .

Шаг 1: Вычислить x2 x1 x .

Шаг 2: Вычислить f (x1) и f (x2 ) .