«И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ Москва, 2003 УДК 519.6 ББК 22.18 М 327 И.Н. Мастяева, Г.Я. Горбовцов, О.Н. Семенихина. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ: Учебное пособие / ...»

9. Решить задачу из примера 4.6 при условии, что стоимость хранения единицы изделий уменьшается от месяца к месяцу на одну и ту же величину, равную 0,1 доллара.

10. Решить задачу из примера 4.6 при условии, что стоимость хранения единицы изделий меняется от месяца к месяцу и составляет 0,4; 0,3 и 0,7 долларов для первого, второго и третьего месяцев соответственно.

Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i=1,...,m), выполняемая на станке j (j=1,...,n), связана с затратами cij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1, т.е. a i = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т.е. b j = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна cij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость cij берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:

Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = Пусть x ij = 0, если j-я работа не выполняется на i-м станке, = 1, если j-я работа выполняется на i-м станке.

Таким образом, решение задачи может быть записано в виде двумерного массива X = x ij. Допустимое решение называется назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы X = x ij и ровно одного элемента в каждом столбце этой матрицы. Для заданного значения n существует n!

допустимых решений.

Теперь задача будет формулироваться следующим образом:

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

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

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

Приведенное замечание показывает, что если можно построить новую матрицу C с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным.

Оптимальное назначение:

x11 = 1, x23 = 1, x32 = 1, остальные x ij = 0, К сожалению, не всегда удается определить решение так просто.

Шаг 1. (Редукция строк и столбцов).

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

Шаг 2. (Определение назначений).

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

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

в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов. Если построенное назначение полное, то оно является оптимальным.

Если некоторые нули остались невычеркнутыми, то можно попытаться найти полное назначение.

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

Шаг 3. (Модификация редуцированной матрицы).

Для редуцированной матрицы стоимостей:

а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

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

2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.

Пример 4.7. Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей:

Итерация Шаг 1. Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

Шаг 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

а) Строки 1, 2 и 4 содержат по одному невычеркнутому нулю.

Рассматривая эти строки в порядке возрастания их номеров, произведем вначале назначение, соответствующее элементу (1,1), и вычеркнем нулевой элемент (4,1). Затем произведем назначение, соответствующее элементу (2,2). Строка 4 не может быть использована, поскольку нулевой элемент (4,1) был вычеркнут.

б) Столбцы 3 и 4 содержат по одному невычеркнутому нулю.

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

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

Шаг 3. Модификация редуцированной матрицы.

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно.

Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией.

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

г) Значение минимального невычеркнутого элемента равно 2.

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

Итерация 2.

Выполняя вновь процедуру построения допустимого решения нулевой стоимости, получаем следующее оптимальное решение:

Оптимальное назначение:

x13 = 1, x22 = 1, x34 = 1, x41 = 1, остальные x ij = 0, Пример 4.8: (Задача размещения производства) Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции – по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции.

1. Издержки производства единицы продукции (руб.):

2. Издержки сбыта единицы продукции (руб.):

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

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

Умножая прибыль, приходящуюся на единицу продукции, на годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции – предприятие. Данные величины (в тыс. руб.) приведены в следующей таблице:

Если прибыль рассматривать как отрицательные затраты, то исходная задача максимизации может быть сведена к минимизационной задаче о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с числом 5760 и введем два вида фиктивной продукции (4 и 5), которой соответствует нулевая прибыль. В результате будет получена следующая матрица:

Итерация Итерация 2:

Шаг 2. Воспользуемся замечанием 1. Тогда получим:

Оптимальное решение данной задачи следующее: производство первого вида продукции назначается предприятию 4, второго вида – предприятию 1, третьего вида – предприятию 3, четвертого вида – предприятию 2, пятого вида – предприятию 5. Очевидно, что последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна1050 + 5600 + = 7892 тыс. руб.

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

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

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

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

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

xij {0;1},, i=1,…,n;, j=1,…,n.

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

Для расчета модели венгерским методом надо перейти к противоположной функции и в соответствующей таблице записывать значения 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-й город;

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

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

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

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

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

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

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

В i-ой строке и j-м столбце матрицы стоит время на выполнение i-м ученым j-го проекта. Продолжительность времен задана в месяцах.

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

6. Решить задачу оптимального исследования рынка в четырех городах, если задана матрица успешных опросов 7. Решить задачу оптимального исследования рынка в трех городах, если в каждом из городов предполагается проводить по 10 опросов.

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

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

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

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

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

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

где хотя бы одна из функций или gi есть нелинейная функция своих аргументов.

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

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

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

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

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

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

шагу 4, в противном случае Шаг 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(x).

Пример 5.1.

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

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

Нетрудно также проверить, что точка y производит золотое сечение отрезка [a, z], а точка z производит золотое сечение отрезка [y, b]. На этом свойстве, позволяющем на каждой итерации вычислять значение функции лишь в одной пробной точке, и основан алгоритм метода золотого сечения.

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

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

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

Пример 5.2.

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

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.

Итерация 2.

Итерация 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;

Итерация 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 ].

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

Задачей безусловной оптимизации функции нескольких переменных будем называть задачу, в которой требуется найти при отсутствии ограничений на x, где x = (x1,…,xn)- вектор управляемых переменных, f – скалярная целевая функция.

Определение. Решением, или точкой минимума, задачи безусловной оптимизации будем называть такой вектор x * E n, что Определение. Вектор S называется направлением спуска функции f (x ) в точке x, если существует такое > 0, что f ( x + S ) < f ( x ), для всех Сущность рассматриваемых в данном разделе методов решения задачи (5.2) состоит в построении последовательности точек x1, x 2,...x k,...

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

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

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

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

Шаг 1. В точке x k проверить условие окончания счета; если оно выполняется, то положить x * = x k и остановиться.

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

направления S k, положить k=k+1 и перейти к шагу 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

положить k=k+1 и перейти к шагу 1.

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

Начальный этап. Пусть x1 = (0,6;1), = 0,1; k = 1.

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

Шаг 1. Вычислим f ( x1 ) = (2;0), так как f ( x1 ) = 2 >, переходим к шагу 2.

Шаг2. Положим S1 = f ( x1 ) = (2;0), вычислим 1 = arg min f ( x1 + S1 ) = 0,05, x 2 = (0,5;1),положим k=2 и перейдем к шагу 1.

2 = arg min f ( x 2 + S 2 ) = 0,167, x3 = (0,5;0,167), положим k=3 и перейдем к шагу 1.

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

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

на множестве P:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Начальный этап. Выбрать начальную точку x 0 P, для которой Положить k=0.

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

Шаг 1. Для x k P предполагаем, что A = ( A1k, A2k ), Шаг 2. Определить возможное направление подъема, решая следующую задачу:

при условиях:

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

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

Пример.

Начальный этап.

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

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

Итерация 1.

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

Решаем задачу при условиях При решении этой задачи получаем S 0 = (1,1), ( S 0 ) = 10.

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

т.е. решаем задачу:

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

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

Итерация 2.

Шаг 2. f ( x 1 ) = (, ). Решаем задачу при условиях Шаг 4. Решаем задачу:

Определяем Таким образом, решая задачу Шаг 5. Положить:

Итерация 3.

Решаем задачу при условиях Решение:

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

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

5. 3x1 - 2x2 - 0.5x12 - x22 + x1x2 max 6. - x1 + 6x2 - x12 - 3x22 - 3x1x2 max 7. 6x1 - x2 - 1.5x22 + 2x1x2 max 10. 6x1 + 4x2 - x12 – 0.5x22 - x1x2 max 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.