WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

«Московский международный институт эконометрики, информатики, финансов и права И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ Москва, 2003 УДК 519.6 ББК 22.18 ...»

-- [ Страница 2 ] --

Группе, исследующий рынок, требуется получить данные из n различных мест. В ее распоряжении имеется n дней, и она предполагает провести по одному дню в каждом месте, проведя по аj опросов, j=1,…,n. Вероятность успешного опроса в каждом месте задается матрицей Р. Элемент матрицы рij характеризует вероятность успешного опроса в течении i-го дня в j-м месте, i=1,…,n.

Определить время проведения опросов, при котором общее число опросов максимально.

Решение. Сведем данную задачу к задаче о назначениях.

Введем величину rij=pijaj, показывающую число успешных опросов в в j-м месте в течение i-го дня.

1, если в i-й день опрос проводится в j-м месте;

xij= 0, в противном случае.

Математическая модель задачи имеет следующий вид:

n n F = xij max.

rij i=1 j= n = 1, i = 1,...n;

xij j= n xij = 1, j = 1,...n;

i= xij {0;

1},, i=1,…,n;

, j=1,…,n.

Функция F характеризует суммарное число успешных опросов. Ее нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течении одного дня можно находиться только в одном месте.

Для расчета модели венгерским методом надо перейти к противоположной функции n n F = - xij.

rij i=1 j= и в соответствующей таблице записывать значения rij с противоположным знаком.

Оптимальное использование рабочих агентов.

Торговая фирма продает товары в n различных городах, покупательная способность жителей которых оценивается bj усл. ед., j = 1,…,n. Для реализации товаров фирма располагает n торговыми агентами, каждого из которых она направляет в один из городов.

Профессиональный уровень агентов различен;

доля реализуемых i-м торговым агентом покупательных способностей составляет аi, i = 1,…,n.

Как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров?

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

Введем параметр сij = ai bj, характеризующий величину покупательных способностей, реализуемых i-м торговым агентом в j-м городе.

Управляющие переменные xij, i = 1,…,n;

j = 1,…,n определяются по формуле 1, если i-й агент направлен в j-й город;

xij= 0, в противном случае.

Математическая модель запишется в следующей форме:

n n F = xij max.

cij i=1 j= n xij = 1, i = 1,...n;

j= n xij = 1, j = 1,...n;

i= xij {0;

1}, i =1,…,n;

, j =1,…,n.

Первое и второе ограничения формализуют соответственно условия о том, что в каждый город направляется один торговый агент и один торговый агент не может работать в двух городах. Целевая функция F – это сумма реализованных покупательных способностей всеми торговыми агентами во всех городах. Она должна подлежать максимизации. Для решения задачи венгерским методом надо, как и в предыдущем примере, перейти к противоположной функции.

Домашнее задание 4.3.

1. Рассмотреть следующую задачу распределения четырех рабочих по четырем станкам. Соответствующие коэффициенты стоимости в долларах приведены в таблице. Рабочий 1 не может работать на станке 3, а рабочий 3 — на станке 4. Найти решение.

2. Пусть в задаче 1 введен еще один станок. Соответствующие коэффициенты стоимости (в долларах) для четырех рабочих равны 2, 1, 2 и 8. Этот новый станок может заменять любой из четырех, если такая замена экономически оправдана. Сформулируйте задачу как задачу о назначениях и найдите оптимальное решение. Ответьте на вопрос, оправдана ли экономически замена одного из станков? Если да, то какого?

3. Решить задачу о назначениях.

3 8 2 10 8 7 2 9 6 4 2 7 8 4 2 3 9 10 6 9 4.Решить задачу о назначениях.

3 9 2 3 6 1 5 6 9 4 7 10 2 5 4 2 9 6 2 4 5. Институт получил гранты на выполнение четырех исследовательских проектов. Выходные результаты первого проекта являются входными данными для второго проекта, выходные результаты второго проекта - это входные данные для третьего проекта, результаты третьего проекта используются для работы над четвертым проектом. В качестве научных руководителей проектов рассматриваются кандидатуры четырех ученых, обладающих различным опытом и способностями. Каждый ученый оценил время, необходимое ему для реализации проектов.

Матрица времен - 3 7 5 2 4 4 Т = 4 7 2 9 7 3 В i-ой строке и j-м столбце матрицы стоит время на выполнение i-м ученым j-го проекта. Продолжительность времен задана в месяцах.

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

6. Решить задачу оптимального исследования рынка в четырех городах, если задана матрица успешных опросов 8 12 10 4 7 9 R = 6 5 3 1 3 2 7. Решить задачу оптимального исследования рынка в трех городах, если в каждом из городов предполагается проводить по 10 опросов.

Матрица вероятностей успешных опросов 0,3 0,2 0, Р = 0,1 0,4 0, 0,2 0,5 0, 8. Решить предыдущую задачу при условии, что в первом и втором городах предполагается провести по 5 опросов, а в третьем – 10.

9. Решить задачу оптимального использования трех торговых агентов в трех городах, если задана матрица покупательных способ ностей сij, реализуемых i-м агентом в j-м городе.

200 270 С = 180 240 210 300 10. Решить задачу оптимального использования трех торговых агентов в трех городах, если покупательная способность жителей j-го города, j = 1,2,3, равна 300, 450 и 360 усл. ед., а доли реализуемых i-м торговым агентом i = 1,2,3, покупательных способностей равны 0.5;

0, и 0,3 соответственно.

5. Нелинейные модели.

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

Ранее в задачах линейного программирования полагалось, что себестоимость, цена и др. показатели эффективности на ед. продукции не зависят от изменения объема производства. Однако в общем случае зависимости между переменными в ограничениях и целевой функции не могут быть линейными. Например, себестоимость единицы продукции снижается при увеличении объема производства.

Подобные случаи приводят к нелинейной формулировке ограничений или целевых функций, то есть к задаче нелинейного программирования (ЗНП), которая в общем виде заключается в нахождении максимума (минимума) функции f (x1,…,xn) при ограничениях :

gi (x1,…,xn) 0, i=1,…,m где хотя бы одна из функций или gi есть нелинейная функция своих аргументов.

5.1. Методы одномерной оптимизации.

Постановка задачи Пусть функция f(x) определена на P E1. Задачей одномерной оптимизации будем называть задачу, в которой требуется найти max(min) f (x), x P.

Решением или точкой максимума (минимума) этой задачи назовем * такую точку X P, что f (x*) () f (x) для всех x P. Запишем f (x*) = max(min) f (x) (5.1) xP В дальнейшем будем считать, что максимизируемая функция является унимодальной.

Определение. Функция f(x) называется унимодальной на множестве Р, если существует единственная точка x* ее максимума на Р и для любых x1, x2 P f(x1) f(x2) f(x*), если x1 x2 x*;

f(x*) f(x1) f(x2), если x* x1 x2.

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

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

Поиск отрезка, содержащего точку максимума. Алгоритм Свенна.

Исходные данные. X0 – начальная точка, h – шаг поиска (h>0).

Шаг 1. Вычислить f (x0). f (x0 + h), f (x0 - h), k=1.

Шаг 2. Если f (x0 - h) f (x0) f (x0 + h), то x1=x0+h, перейти к шагу 4.

Шаг 3. Если f (x0 - h) f (x0) f (x0 + h), то x1=x0-h, h=-h, перейти к шагу 4, в противном случае ( f (x0 - h) f (x0 ) f (x0 + h)), a = x0 - h,b = x0 + h, конец.

Шаг 4. xk +1 = xk + 2k h, Вычислить f (xk +1).

Шаг 5. Если f (xk +1) f (xk ), то k=k+1, перейти к шагу 4.

Шаг 6. Если h>0, то a = xk -1,b = xk +1, конец;

в противном случае a = xk +1,b = xk -1, конец.

Заметим, что случай f (x0 - h) f (x0) f (x0 + h) (шаг 3) не рассматривается, так как он противоречит предположению об унимодальности функции f(x).

Пример 5.1.

f (x) = 200x - x2 -10000;

x0 = 30;

h = f (x0) = f (30) = -4900;

f (x0 + h) = f (35) = -4225;

f (x0 - h) = f (25) = - Поскольку f (x0 - h) < f (x0) < f (x0 + h),то x*>30, x1=35.

Далее x2 = x1 + 2 h = 35 +10 = 45.

f (x2) = f (45) = -3025 > f (x1), x* > 35, x3 = x2 + 22 h = 45 + 20 = 65.

f (x3) = f (65) = -1225 > f (x2) x* > 45, x3 = x2 + 22 h = 65 + 40 = 105.

f (x4) = f (105) = -25 > f (x3) x* > 65, x3 = x2 + 22 h = 105 + 80 = 185.

f (x5) = f (185) = -7225 > f (x4) x* < 185,a = 65,b = 185.

Метод золотого сечения. Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Легко показать, что золотое сечение отрезка [a, b] производится двумя точками y и z, симметричными относительно середины отрезка.

(-1) y z b a (-1) Рис. 5. b - a b - y b - a z - a 5 + = = = = = = 1,6180...

b - y y - a z - a b - z Отсюда y = ( -1)a + ( -1)2 b = 0,618 a + 0,382 b z = ( -1)2 a + ( -1)b = 0,382 a + 0,618 b Нетрудно также проверить, что точка y производит золотое сечение отрезка [a, z], а точка z производит золотое сечение отрезка [y, b]. На этом свойстве, позволяющем на каждой итерации вычислять значение функции лишь в одной пробной точке, и основан алгоритм метода золотого сечения.

Исходные данные. [a, b] - отрезок, содержащий точку максимума, - параметр окончания счета.

Шаг 1.

5 + ;

k=1, ak=a;

bk=b;

= y = ( -1)ak + ( -1)2 bk ;

A = f ( y);

z = ( -1)2 ak + ( -1)bk ;

B = f (z).

Шаг 2.

Если A>B, то перейдем к шагу 4.

Шаг 3.

ak +1 = y;

bk +1 = bk ;

y = z;

A = B;

z = ( -1)2 ak +1 + ( -1)bk +1;

B = f (z), перейти к шагу 5.

Шаг 4.

ak +1 = ak ;

bk +1 = z;

z = y;

B = A;

y = ( -1)ak +1 + ( -1)2 bk +1;

A = f ( y ) Шаг 5.

* Если bk +1 - ak +1 <, то X [ak +1,bk +1], конец.

Шаг 6.

k=k+1, перейти к шагу 2.

Пример 5.2.

Найти точку максимума функции f (x ) = sin( x ) на отрезке [1,5;

1,6], = 0,002.

=1,6180;

a1 = 1,5 ;

b1 = 1,6.

y = 0,6180 1,5 + 0,3820 1,6 =1, z = 0,3820 1,5 + 0,6180 1,6 =1, A = sin( y) = 0,99947;

B = sin(z) = 0,99996.

Итерация 1.

Так как A

b2 = b1 = 1,6;

a2 = y = 1,5382;

b2 = b1 = 1,6;

y = z =1,5618;

A = B = 0,99996;

z = 0,3820 1,5382 + 0,6180 1,6 =1, B = sin(z) = 0,999984;

b2 - a2 = 0,0618 >.

Итерация 2.

Так как A

b3 = b2 = 1,6.

y = z =1,5764;

A = B = 0,99998;

z = 0,3820 1,5618 + 0,6180 1,6 = 1,5854 ;

B = sin(z) = 0,99989;

b3 - a3 = 0,0382 >.

Итерация 3.

Так как A>B, то a4 = a3 = 1,5618;

b4 = z = 1,5854.

z = y =1,5764;

B = A = 0,99998;

y = 0,6180 1,5618 + 0,3820 1,5854 =1,5708;

A = 1,00000;

b4 - a4 = 0,0236 >.

Итерация 4.

Так как A>B, то a5 = a4 = 1,5618;

b5 = z =1,57564.

z = y =1,5708;

B = A = 1,00000;

y = 0,6180 1,5618 + 0,3820 1,5764 = 1,5674;

A = sin( y) = 0,99999;

* b5 - a5 = 0,0146 <, следовательно, X [1,5618;

1,5764].

Домашнее задание 5.1.

Методом Свенна найти отрезок, содержащий точку экстремума унимодальной функции f(x), уточнить точку экстремума методом Золотого сечения, = 0,05.

1. f(x)=x2+1min 2. f(x)=3x-x2-1max 3. f(x)=2x-x2-1max 4. f(x)=2x2+3min 5. f(x)=x2+x+1min 6. f(x)=10x2+7x+1min 7. f(x)=15x-2x2+5max 8. f(x)=3+7x-2x2max 9. f(x)=4-3x2max 10. f(x)=5-4x-x2max 5.2. Методы безусловной оптимизации Задачей безусловной оптимизации функции нескольких переменных будем называть задачу, в которой требуется найти min f (x), x En (5.2) при отсутствии ограничений на x, где x = (x1,…,xn)- вектор управляемых переменных, f – скалярная целевая функция.

Определение. Решением, или точкой минимума, задачи безусловной оптимизации будем называть такой вектор x* En, что f (x*) f (x) для всех x En, и писать f (x*) = min f (x), x En (5.3) Определение. Вектор S называется направлением спуска функции f (x)в точке x, если существует такое > 0, что f (x + S ) < f (x), для всех (0;

).

Сущность рассматриваемых в данном разделе методов решения задачи (5.2) состоит в построении последовательности точек x1, x2,...xk,...

принадлежащих En, монотонно уменьшающих значение функции f (x).

Такие методы называют методами спуска.

Алгоритм метода спуска.

Начальный этап. Задать x1 En - начальную точку, > 0- параметр окончания счета;

положить k=1.

Основной этап Шаг 1. В точке xk проверить условие окончания счета;

если оно выполняется, то положить x* = xk и остановиться.

Шаг 2. В точке xk выбрать направление спуска Sk.

r Шаг 3. Положить xk +1 = xk + k Sk, где k - длина шага вдоль направления Sk, положить k=k+1 и перейти к шагу 1.

Различные методы спуска отличаются друг от друга способом выбора направления спуска Sk и шага вдоль этого направления k.

Естественно, что трудоемкость вычисления величины k следует согласовывать с трудоемкости определения направления спуска Sk.

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

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

Градиентные методы, в которых используются значения функции f (x) и ее градиента, т.е. вектора, компонентами которого являются частные производные первого порядка.

Методы второго порядка, в которых используются первые и вторые производные функции f (x), т.е. значения f (x),f (x), H (x), где H (x) - матрица Гессе, элементами которой являются частные производные второго порядка функции f (x).

Методы оптимизации квадратичных функций.

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

Метод скорейшего спуска – метод Коши - метод первого порядка.

Методы безусловной оптимизации, в которых в качестве направления поиска берется градиент функции f (x), называются градиентными. Градиентные методы являются методами первого порядка. Таким образом, последовательность точек генерируется градиентным методом в соответствии с формулой:

xk +1 = xk - kf (xk ) (5.4) где k - параметр, характеризующий величину шага вдоль направления. Величина шага k может выбираться разными способами.

Если значение параметра k вычисляется путем решения задачи одномерной оптимизации, то градиентный метод называется методом скорейшего спуска, или методом Коши.

Алгоритм метода Коши.

Начальный этап. Выбрать x1 - начальную точку, > 0- параметр окончания счета;

положить k=1.

Основной этап.

Шаг 1. Если f (xk ) <, то x* = xk, остановиться.

Шаг2.Положить Sk = -f (xk ), вычислить k = arg min f (xk + Sk ), положить k=k+1 и перейти к шагу 1.

Пример 5.3. Найти минимум функции методом Коши.

2 f (x) = 10x1 +10x1x2 + 3x Начальный этап. Пусть x1 = (-0,6;

1), = 0,1;

k = 1.

f (x) = (20x1 +10x2;

10x1 + 6x2 ) Основной этап.

Шаг 1. Вычислим f (x1) = (-2;

0), так как f (x1) = 2 >, переходим к шагу 2.

Шаг2. Положим S1 = -f (x1) = (2;

0), вычислим 1 = arg min f (x1 + S1) = 0,05, x2 = (-0,5;

1),положим k=2 и перейдем к шагу 1.

Шаг 1. f (x2 ) = (0;

1), т.к. f (x2 ) = 1 >, переходим к шагу 2.

Шаг 2. Положим S2 = -f (x2 ) = (0;

-1), вычислим 2 = arg min f (x2 + S2 ) = 0,167, x3 = (-0,5;

0,167), положим k=3 и перейдем к шагу 1.

Результаты всех вычислений приведены в таблице, из которой следует, что значение функции f (x)становится меньше = 0,1 на 11-й итерации, а значение нормы градиента уменьшается в 5/6 раза каждые две итерации (см. таблицу).

Скорость сходимости метода Коши является довольно низкой, хотя на каждой итерации обеспечивается выполнение неравенства f (xk +1) f (xk ).

Таблица.

f (x) f (xk ) xk xk + 1 k f (xk ) k 11 - 6 1 6/10 (-2;

0) 2 0,05 -0,5;

1) ;

10 1 22 - 5 5/10 (0;

1) 1 1/ ;

- ;

10 2 1 5 5 33 5/12 (-5/3;

0) 5/3 0, - ;

- ;

2 6 12 5 44 25/72 (0;

5/6) 5/6 1/6 - 5 ;

- ;

12 6 12 25 - 25 55 - 5 25 125/432 25/18 0, ;

;

- ;

72 12 36 66 - 25 25 625/259 (0;

25/36) 25/36 1/6 -25 ;

;

72 36 72 77 - 25 125 55 125/108 0, - ;

;

265 ;

72 432 ……………………………………………………………………… ……………………… 11 - 54 59 0 55 ;

269 … 264 Домашнее задание 5.2.

Решить задачу безусловной оптимизации методом Коши с точностью =0,1. Решение сопроводить геометрической интерпретацией 1. –x1 + 6x2 -2x12 – 3x22 + 3x1x2 max 2. 6x1 + 4x2 - x12 - 0,5x22 - x1x2 max 3. 3x1 - 2x2 - 0,5x12 – x22 + x1x2 max 4. –4x1 + 8x2 – x12 –1.5x22 + 2x1x2 max 5. x1 + 4x2 - x12 – 3x22 + 2x1x2 max 6. –2x1 + x2 - 3x12 – 2x22 + x1x2 max 7. x1 - 2x2 - x12 – 3x22 - x1x2 max 8. 3x1 + 6x2 – x12 – 2x22 + 2x1x2 max 9. -3x1 + 2x2 - 2x12 – x22 + 2x1x2 max 10. 4x1 + x2 - 3x12 – x22 + x1x2 max 5.3. Методы условной оптимизации В дальнейшем будем рассматривать следующую задачу:

f ( x ) max (5.5) на множестве P:

P = {x En : gi (x ) 0, i = 1,m, x 0, j = 1,n} (5.6) j где f (x ) и gi (x ) - нелинейные функции.

При решении задач нелинейного программирования ввиду нелинейности функции gi (x ) выпуклость допустимого множества решений P и конечность числа его крайних точек (в отличие от ЗЛП) необязательны. Задача нелинейного программирования не всегда имеет решение. Если задача имеет решение, то максимум функции f (x ) может достигаться в крайней точке допустимой области значений P, в одной из граничных точек или в точке, расположенной внутри допустимой области P.

Определение. Решением или точкой максимума задачи условной * * оптимизации будем называть такой вектор x P E, что f (x ) f (x ) n * для всех x P, т.е. f (x ) = max f (x ).

xP Определение. Будем называть направление S 0 возможным в точке x P, если существует такое действительное число 0 > 0, что (x + S ) P для всех (0, 0 ).

k Определение. Вектор S будем называть возможным k направлением подъема функции f (x ) в точке X P, если существует k такое действительное число 0 > 0, что для всех (0, 0 ):

(x + S ) P и f (x + S ) > f (x ).

k k k k k Методы решения задачи условной оптимизации можно представить как итерационный процесс, в котором исходя из начальной точки x P, получают последовательность точек x P, монотонно увеличивающих k значения функции f (x ). Это так называемые методы подъема.

Элементы этой последовательности точек определяются следующим образом: x = x + k S, k +1 k k где S - возможное направление подъема функции в точке x, а k k k находится при решении задачи одномерной оптимизации:

f (x + S ) max.

k k x Если точка - внутренняя точка множества P, т.е. для k i = 1,m : gi (x ) < 0, то всякое направление в ней является возможным k (пример на рис. 5.2).

x Если точка - граничная точка области P, то возможные k * направления определяются ограничениями gi (x ) = 0 (направление S на k рис. 5.3 возможным не является).

Прежде чем определять направление подъема функции f (x ) в точке x, следует вычислить множество таких возможных направлений, S k k x для которых существовала бы окрестность точки, принадлежащая P.

k Общая схема методов условной оптимизации.

Начальный этап. Задать > 0 и выбрать начальную точку x P.

Основной этап.

S Шаг 1. Выбрать (k-я итерация) - возможное направление k x подъема функции f (x ) в точке. Если такого направления нет, то k x* = x - решение задачи. В противном случае перейти к шагу 2.

k k x = x + S Шаг 2. Положить k+1 k k, где k находим, решая задачу f (x + k S ) max k k > (x + k S ) P k k Шаг 3. Заменить k на k+1 и перейти к шагу 1.

Конкретные методы условной оптимизации различаются способом S x выбора возможного направления подъема функции f (x ) в точке.

k k g1(x ) = g2 (x ) = P S … x k S S S g4 (x ) = g3 (x ) = Рис. 5. g1(x ) = * S x k g2 (x ) = P g4 (x ) = g3 (x ) = Рис 5. Метод Зойтендейка.

Пусть требуется найти максимальное значение вогнутой функции f (x ) :

f (x ) max при условиях Ax b P = (5.7) x Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства.

Предположим также для любой допустимой точки x, что A1 x = b и A2 x < b, где A = (A1, A2 ) и b = (b,b ). Далее приводится алгоритм метода 2 1 Зойтендейка для случая линейных ограничений.

Алгоритм метода Зойтендейка.

Начальный этап. Выбрать начальную точку x P, для которой A= (A1, A2), b =(b,b ), 1 A1 : A1 x = b, A2 : A2 x < b.

0 1 0 Положить k=0.

Основной этап.

k A = (A1k,A2 ) Шаг 1. Для x P предполагаем, что, k k k b = (b,b ), A1 x = b, A2 x < b 1 2 k 1 k 2.

Шаг 2. Определить возможное направление подъема, решая следующую задачу:

(S ) = (f (x ),S ) max k (5.8) при условиях:

Pk ={S : S En,A1S 0, (5.9) -1S 1, j =1,n} j * (S) = (f (x ),S ) = Шаг 3. Если все k k, то x = x - задача решена.

k Шаг 4. Определить k (шаг в направлении S ), решая задачу k одномерной оптимизации:

f (x + S ) max k k * 0.

Шаг 5. Положить x = x + k S, заменить k на k+1 и перейти к k +1 k k шагу 1.

Пример.

f (x) = 4x1 + 6x2 + 2x1x2 - 2x12 - 2x2 2 max x1 + x2 x + 5x2 - x1 - x2 Начальный этап.

Выбираем начальную точку x0 = (0,0), для которой:

-1 0 0 1 1 0 A1 =,b10 = A2 =,b20 =.

0 -1 0, 1 5 f (x) = (4 + 2x2 - 4x1,6 + 2x1 - 4x2 ), положить k=0.

Основной этап.

Итерация 1.

0 Шаг 1. Для x0 = (0,0) заданы A1,b10, A2,b20.

Шаг 2. f (x0 ) = (4,6).

Решаем задачу (S) = (f (x ),S) = 4S1 + 6S2 max при условиях - S1 - S2 -1 S1 -1 S2 При решении этой задачи получаем S0 = (1,1),(S0 ) = 10.

Шаг 3. Так как (S0 ) = 10 0, переходим к шагу 4.

Шаг 4. Решаем одномерную задачу:

f (x + S ) = 10 - 2 max 0 * * Определяем :

2 5 * = min, =, 2 6 т.е. решаем задачу:

10 - 2 max 0 Очевидно, что решением является 0 =.

5 5 Шаг 5. Положить x = x + 0 S = (0,0) + (1,1) = (, ).

1 0 6 6 k=1 и перейти к шагу 1.

Итерация 2.

5 Шаг 1. Для x = (, ) : A1 = (1 5) b = (0).

1 6 7 Шаг 2. f (x ) = (, ). Решаем задачу 3 7 S1 + S max 3 при условиях S1 + 5S -1 S1 -1 S 1 Решение этой ЗЛП - S = (1, - );

(S ) = -.

1 5 Шаг 3. Так как (S ) = - 0, переходим к шагу 4.

Шаг 4. Решаем задачу:

125 22 f (x + S ) = + - max* 1 8 15 * Определяем :

1/ 3 5 / 6 * = min, =, 4 / 5 1/ Таким образом, решая задачу 125 22 + - max, 8 15 0 получим оптимальное значение : 1 =.

Шаг 5. Положить:

35 x = x + 1S = (, ). K=2 и перейти к шагу 1.

2 1 31 Итерация 3.

35 Шаг 1. Для x = (, ) : A1 = (1 5) b = (0).

2 31 32 Шаг 2. f (x ) = (, ) 31 Решаем задачу 32 S1 + S2 max 31 при условиях S1 + 5S2 -1 S1 -1 S2 1.

Решение:

S = (1;

- ). (S ) = 0.

2 * 35 Шаг 3. Так как (S ) = 0, задача решена и x = x = (, ).

2 31 На рис. 5.4 проиллюстрирован процесс решения задачи.

x 1, g2 (x ) = x x g1(x ) = 2, x1 0 x Рис. 5. Домашнее задание 5.3.

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

1. 3x1 - 2x2 - 0.5x12 - x22 + x1x2 max 2x1 + x2 x1 + x2 x1, x2 2. 3x1 - 2x2 - 0.5x12 - x22 + x1x2 max x1 x2 x1, x2 3. -4x1 + 8x2 - x12 – 1.5x22 + 2x1x2 max x1 + x2 x1 - x2 x1, x2 4. - 4x1 + 8x2 - x12 - 1.5x22 + 2x1x2 max -x1 + x2 x1 x1, x2 5. 3x1 - 2x2 - 0.5x12 - x22 + x1x2 max -x1 + 2x2 2 x1 - x2 x1, x2 6. - x1 + 6x2 - x12 - 3x22 - 3x1x2 max x1 - x2 x2 x1, x2 7. 6x1 - x2 - 1.5x22 + 2x1x2 max -x1 + 2x2 x1 x1, x2 8. 6x1 + 4x2 - x12 - 0.5x22 - x1x2 max x1 + 2x2 -2 x1 + x2 x1, x2 9. 6x1 + 4x2 - x12 – 0.5x22 - x1x2 max 2x1 + x2 x2 x1, x2 10. 6x1 + 4x2 - x12 – 0.5x22 - x1x2 max 3x1 + 2x2 3x1 + x2 x1, x2 6. Литература 1. К.А. Багриновский и В.М.Матюшок. Экономико-математические методы и модели, М.: РУДН, 1999.

2. Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании. М.: ФиС, 1999.

3. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб., Лань, 2000.

4. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели в менеджменте. СПб., СПбГТУ, 2000.

5. Дубров А.М., Лагоша Б.А., Хрусталев Е.Ю. Моделирование рисковых ситуаций в экономике и бизнесе. М.: ФиС, 2000.

6. Замков О.О., Толстопятенко А.В., Черемных Ю. Н.

Математические методы в экономике. М.: АО “ДИС”, 1997.

7. Исследование операций в экономике. Под редакцией Н.Ш.Кремера. М., ЮНИТИ, 1997.

8. Курицкий Б.Я. Поиск оптимальных решений средствами EXCEL 7.0. СПб, BHV, 1997.

9. Математическая экономика на персональном компьютере. Под ред. М. Кубонина. М.: ФиС, 10. Орлова И.В. Экономико-математические методы и модели.

Выполнение расчетов в среде EXCEL. М.: ЗАО ‘’Финстатинформ”, 2000.

11. Плис А.И., Сливина Н.А. Mathcad: математический практикум для экономистов и инженеров: учебное пособие. М.: ФиС, 1999.

12. Таха Х. Введение в исследование операций. М.: Мир, 1985.

13. В.М. Трояновский. Математическое моделирование в менеджменте. Русская деловая литература, 1999.

14. Хазанова Л.Е. Математическое моделирование в экономике. М.:

Бек, 1998.

15. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. М.: ЮНИТИ, 2000.

16. Эддоус М., Стэнсфилд Р. Методы принятия решения. М.:

ЮНИТИ, 1997.

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.