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

Тема 3 Математические методы и основные классы задач оптимизации

Общая постановка математической модели задач оптимизации

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

Пусть f(x) - функция, определенная на множестве V, а Ω- некоторое подмножество множества V.

Оптимизационная задача задается тройкой (V, F, Ω). При этом функция f(x) называется целевой функцией, а Ω - допустимым множеством (множеством допустимых значений) оптимизационной задачи.

Оптимизационные задачи бывают двух типов: задачи минимизации и задачи максимизации. Задача минимизации (максимизации) (V, F, Ω) состоит в отыскивании наименьшего (наибольшего) значения целевой функции f(x) на допустимом множестве Ω.

Для того, чтобы решить задачу минимизации (максимизации) (V, F, Ω) достаточно найти её оптимальное решение, т.е. указать x0Ω такое, что f(x0)f(x1…,xn)=f(x) (или f(x0)f(x)) при любом xΩ.

Оптимизационная задача называется неразрешимой, если она не имеет оптимального решения. В частности, задача минимизации (максимизации) (V, F, Ω) будет неразрешимой, если целевая функция f(x) не ограничена снизу (сверху) на допустимом множестве Ω.

Решить оптимизационную задачу - значит либо найти её оптимальное решение, либо установить неразрешимость этой задачи.

Любая задача максимизации (V, F, Ω) сводится к задаче минимизации (V, -F, Ω): эти задачи либо обе неразрешимы, либо имеют одно и тоже оптимальное решение.

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

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

В общем виде математическая постановка задачи оптимизации состоит в определении наибольшего или наименьшего значения целевой функции f(x1…,xn) при условиях gi (x1…,xn)≤ bi (i=1,…,m), где f и gi - заданные функции, а bi - некоторые действительные числа. Если все f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.

Пусть z=f(x1,x2,…,xn). Тогда мы можем записать:

zmax (min)

gi (x1…,xn) bi ,i=1,…,m.

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

z - оптимизационная цель экономической системы;

f(x1,…,xn) - соответствующая ей целевая функция;

x1,x2,…,xn - показатели степени использования средств достижения цели, могут характеризовать выпуск продукции разных видов, загрузку оборудования, использование ресурсов и т.п.

gi (x1…,xn)функция совокупных затрат средств i-й группы, используемых для достижения целей;

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

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

Среди этих предпосылок ключевыми являются следующие:

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

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

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

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

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

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

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

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

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

Очевидно, далеко не все экономические проблемы, для которых выполняются первые три предпосылки, формулируются в условиях выполнения последних трёх предпосылок. Эти дополнительные требования выполняются лишь для хорошо стуктуризованных проблем, не испытывающих существенного влияния неполноты информации. Именно этот класс проблем может быть сведен к задачам математического программирования.

Применительно для общей модели математического программирования функция gi(x) должна быть известна, то есть зависимость расхода или выпуска ресурса i-го вида от переменных должна быть известна. Величина bi есть наличие или возможность получения ресурса i-го вида и должна быть задана. В каждом из ограничений вида gi(x)bi может иметь место в принципе любой из знаков  Ограничение вида gi(x)bi может быть приведено к каноническому (классическому) виду следующем образом: -gi(x)-bi. Различные ограничения могут иметь различные знаки. Соотношение между числом неизвестных n и числом ограничений m может быть любым: m n; m  n; m n. Когда m 0, то ищется максимум или минимум целевой функции без ограничений, т. е. решается задача на нахождение безусловного экстремума.

На переменные могут дополнительно накладываться следующие ограничения:

а) некоторые или все переменные должны быть неотрицательными, то есть xj0 (j 1,2, …, n1), где n1n;

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

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

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

Ранее мы уже выяснили классификацию этих задач на линейные и нелинейные задачи.

Если принять, что f(x1,x2,…,xn)cjxj (3.1)

gi (x1,x2,…,xn) аijxj {  } bi(i=1,…,m) (3.2)

xj (i=1,2,…,n), (3.3)

где аij и cj - заданные величины, то получим общую задачу линейного программирования, которая формулируется следующим образом:

Необходимо найти n неотрицательных переменных xj, максимизирующих (или минимизирующих) линейную целевую функцию (3.1) и удовлетворяющих ограничениям (3.2), (3.3).

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

Все другие задачи, имеющие целевую функцию и ограничения, отличающиеся от (3.1), (3.2) и (3.3), кроме задач, в которых предполагается целочисленность переменных, принято считать нелинейными.

Вычислительные методы разработаны лишь для немногих типов задач нелинейного программирования, а именно для задач так называемого выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции (вида с1x1 с2x2… сnxn d11x12d12x1x2… d1nx1 xn… dnnxn2)

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

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

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

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

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

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

studfiles.net

Математические методы оптимизации ресурсов - страница 2

для второй постановки

Значит, поставить ее можно в одном из двух следующих вариантов:

либо максимизирювать выпуск продукции с заданного

оборудования, либо минимизировать количество оборудования,

используемого при вьшуске заданного объема продукции.

В общем случае математическая модель задачи распределения

ресурсов с числом переменных я и офаничений т имеет

следующий вид:

где Cj — коэффициенты в целевой функции; а^ — норма расхода /-го

ресурса для выпуска единицы у-й продукции; 6, —имеющийся ресурс; dj

и Dj — минимальное и максимальное допустимые значения Xj

Так как в эту модель все переменные входят в первой степени,

т. е. все зависимости являются линейными, то данную модель

называют задачей линейного программирования. С помощью

этих задач можно решать достаточно большой класс задач распределения

ресурсов не только в планировании и управлении

производством и экономическими объектами, но и в проектировании

изделий и технологических процессов.

Если сравнить систему (2.4) с общей постановкой задачи оптимизации

(2.2), то можно утверждать, что задача линейного

программирования представляет собой частный случай задачи

оптимизации в общем виде.

В современных условиях рьшочных отношений при дефиците

материальных и финансовых ресурсов, несбалансированности производственных

планов по номенклатуре, нормам расходов материалов и

сьфья возникают договорные, производственные, финансовые и

прочие нарушения, корректировки планов, приписки и др.

Сбалансированность планов по номенклатуре, заданным показателям

и ресурсам можно оперативно проверить с помощью

моделирования на ЭВМ не спустя какое-то время, когда обнаружатся

ошибки и просчеты и когда изменить что-либо уже

трудно, а сразу же при решении задачи. При этом необходимо

опираться на достоверную нормативную базу, в частности, на

нормы расхода ресурсов на единицу выпускаемой продукции.

Именно математические модели позволяют проанализировать

причины несбалансированности планов и выявлять недостоверность

исходных данных.

Чем же может помочь ЭВМ в анализе несбалансированных задач?

1. Решая задачу распределения ресурсов на ЭВМ, до получения

окончательного результата нам неизвестно, сбалансирована

она или нет. Однако, если существует подозрение, что задача

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

так составить математическую модель, чтобы она учитывала

возможную недостачу ресурсов.

2. Если нам желательно минимизировать дополнительные

ресурсы у,- при получении прибыли от производства и выпуска

продукции, то целевую функцию следует записать с учетом

этого условия

а условие получения прибыли включить в состав ограничений.

Результаты решения подобных задач на ЭВМ позволяют

промоделировать возможные ситуации и определить, сколько и

какие ресурсы требуются и каким станет план, если полностью

изыскать необходимые дополнительные ресурсы. Конечно, ЭВМ

не может заменить недостающие ресурсы, но она позволяет при

составлении полной и корректно сформулированной математической

модели показать, что необходимо осуществить, чтобы

выполнить несбалансированный план. Польза от такого анализа

несомненна в любых ситуациях.

В общем преодолеть несбалансированность производственного

плана можно или увеличением ресурсов при возможности

их изыскания, а при невозможности добавления дополнительных

ресурсов путем уменьшения нижнего предела выпуска продукции,

или сокращения норм расходов каждого ресурса на выпуск

единицы продукции. Если удастся преодолеть несбалансированность

планов за счет увеличения ресурсов или снижения

выпуска продукции и расхода ресурсов, то план производства

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

Определение координат вершин области допустимых решений

(ОДР) в реальных задачах со многими переменными и ограничениями

связано с очень большими объемами вычислений. Поэтому

для аналитического решения задач линейного профамми-

рования разработан специальный алгоритм направленного перебора

вершин, называемый симплекс-методом, с переходом от

одной вершины к другой в направлении, при котором значение

целевой функции от вершины к вершине улучшается. Определе-

йие значения целевой функции и переменных в одной вершине

считается и т е р а ц и е й . Число итераций зависит от числа

искомых переменных и в реальных задачах может измеряться

сотнями. Вручную с помощью симплекс-метода можно решать

задачи, Содержащие не более десяти переменных. В реальных

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

оптимального решения практически невозможен.

Так как оптимальное решение задачи линейного профамми-

рования соответствует вершине ОДР, то можно сформулировать

следующие выводы:

,1) если оптимальным решением являются координаты вершин

ОДР, то сколько вершин имеет ОДР, столько оптимальных

решений может иметь задача;

2) чем больше существует офаничений в модели задачи, тем

больше будет число вершин и, следовательно, число оптимальных

решений;

3) введение дополнительных ограничений никогда не улучшает

оптимального решения (этот вывод особенно важен для

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

функцию, т. е. результат работы, мы должны стремиться к

тому, чтобы иметь как можно меньше ограничений).

www.coolreferat.com

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

Санкт-Петербургский политехнический университет Петра Великого Институт Информационных Технологий и Управления Кафедра компьютерных систем и программных технологий Курсовая работа Дисциплина: Методы оптимизации Тема: Формулировка и решение задачи выбора оптимального решения с использованием различных математических моделей Выполнил студент гр. 53501/3 С.А. Мартынов Руководитель, к.т.н.,доц. А.Г. Сиднев Санкт-Петербург 2015 Содержание 1 Варианты формализации многокритериальной задачи и их решение с использованием Optimization Toolbox системы Matlab. 3 1.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Выделение главного критерия . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Максимизация выручки . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Максимизация прибыли . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Свертка критериев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Максимин или минимакс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Метод последовательных уступок . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Fgoalattain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.7 Задача стохастического программирования . . . . . . . . . . . . . . . . . . . 14 2 Решение задачи оценки показателей эффективности стохастической сети с использованием методики GERT. Выбор и использование математического пакета Matlab для решения сформулированной задачи. 17 2.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Ход работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Поиск оптимальной стратегии принятия решений с использованием марковских моделей. 25 3.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Марковская модель принятия решений . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Метод итерации по стратегиям . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Метод линейного программирования . . . . . . . . . . . . . . . . . . . . . . . 28 4 Поиск оптимальных параметров сети систем массового обслуживания. 32 4.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Алгоритм решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Решение по алгоритму . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 Решение дискретным линейным методом программирования . . . . . . . . . 38 Список используемой литературы 39 2 1 Варианты формализации многокритериальной задачи и их решение с использованием Optimization Toolbox системы Matlab. 1.1 Постановка задачи Мебельная фабрика выпускает столы, стулья, бюро и книжные шкафы. При изготовлении используются два типа досок, причем фабрика имеет в наличии 1500 м досок первого типа и 1000 м досок второго типа. Кроме того, заданы трудовые ресурсы в количестве 800 чел/час. В таблице приводятся нормативы затрат каждого из видов ресурсов на изготовление 1 ед изделия и прибыль от реализации 1 ед изделия. Затраты на 1 ед изделия Ресурсы столы стулья бюро Книжные шкафы Доски первого типа, м 5 1 9 12 Доски второго типа, м 2 3 4 1 Трудовые ресурсы, чел/час 3 2 5 10 Прибыль, руб/шт 12 5 15 10 Таблица 1: Нормативы затрат ресурсов на единицу изделия По этим исходным данным решить задачу определения оптимальный ассортимент, максимизирующий прибыль (разность между выручкой и расходами.) и выручку при следующих ценах изготавливаемую мебель: ∙ стол – 32 руб; ∙ стул – 15 руб; ∙ бюро – 12 руб; ∙ книжный шкаф – 80 руб. В отчёте необходимо описать: 1. Осуществление перехода от многокритериальной задачи к однокритериальной с использованием различных подходов. 2. Решение задачи стохастического программирования для одной из однокритериальных задач, превратив детерминированное ограничение в вероятностное по схеме: 𝑛 ∑︀ 𝑃 ( 𝑎𝑖𝑗 𝑘𝑗 − 𝑏𝑗 ≤ 0) ≥ 𝛼𝑖 𝑗=1 3 Менять 𝛼𝑖 в следующем диапазоне 0.1 ≤ 𝛼𝑖 ≤ 0.9. Считать случайной величиной 𝑏𝑖 или элементы {𝑎𝑖𝑗 } 𝑖-й строки матрицы 𝐴 {𝑎𝑖𝑗 } (по выбору). 1.2 Выделение главного критерия Выбирается один из критериев, например 𝐶𝑖 , который наиболее полно отражает цель принятия решений. Остальные критерии учитываются только с точки зрения возможного указания их нижних границ 𝐶𝑗 (𝑎) ≥ 𝛾𝑖 , 𝑗 ̸= 𝑖. Таким образом, исходная задача многокритериального принятия решений заменяется однокритериальной задачей с критерием 𝐶𝑖 , т.е. 𝑎* = arg max 𝐶𝑖 (𝑎), при ограничениях 𝐶𝑘 (𝑎) ≥ 𝛾𝑖 , 𝑘 ̸= 𝑖. Критерии: ∙ 𝑚𝑎𝑥(12𝑥1 + 5𝑥2 + 15𝑥3 + 10𝑥4 ) (прибыль) ∙ 𝑚𝑎𝑥(32𝑥1 + 15𝑥2 + 12𝑥3 + 80𝑥4 ) (выручка) Ограничения: ∙ 5𝑥1 + 𝑥2 + 9𝑥3 + 12𝑥4 ≤ 1500 (доски первого типа) ∙ 2𝑥1 + 3𝑥2 + 4𝑥3 + 1𝑥4 ≤ 1000 (доски второго типа) ∙ 3𝑥1 + 2𝑥2 + 5𝑥3 + 1𝑥4 ≤ 800 (трудовые ресурсы) 1.2.1 Максимизация выручки Целевая функция: 𝑓 = 𝑚𝑖𝑛(−32𝑥1 − 15𝑥2 − 12𝑥3 − 80𝑥4 ) Начальные условия: ⎛ ⎞ 0 ⎜ ⎟ ⎜0⎟ ⎟ 𝑥0 = ⎜ ⎜0⎟ ⎝ ⎠ 0 Ограничения: 4 ⎛ 5 1 9 12 ⎞ ⎟ ⎜ ⎜2 3 4 1⎟ ⎟ ⎜ ⎟ ⎜ 2 5 1⎟ ⎜3 ⎟ ⎜ 𝐴=⎜ 0 0⎟ ⎟ ⎜−1 0 ⎟ ⎜ ⎜ 0 −1 0 0⎟ ⎟ ⎜ ⎟ ⎜0 0 −1 0 ⎠ ⎝ 0 0 0 −1 ⎛ ⎞ 1500 ⎜ ⎟ ⎜1000⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 800 ⎟ ⎜ ⎟ ⎟ 𝑏=⎜ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎝ ⎠ 0 Листинг 1: Поиск оптимального решения для максимизация выручки 1 x0 = [ 0 ; 2 0; 3 0; 4 0]; 5 6 A=[5 1 9 1 2 ; 7 2 3 4 1; 8 3 2 5 1; 9 −1 0 0 0 ; 10 0 −1 0 0 ; 11 0 0 −1 0 ; 12 0 0 0 −1]; 13 14 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 15 16 [ x2 , f 2 ] = fmincon ( i n l i n e ( ’ −32*x ( 1 ) − 15* x ( 2 ) − 12* x ( 3 ) − 80* x ( 4 ) ’ ) , x0 , A, b ) 17 f 1 = −12*x2 ( 1 ) − 5* x2 ( 2 ) − 15* x2 ( 3 ) − 10* x2 ( 4 ) Результат: ∙ 𝑥1 = −0, 0000 5 ∙ 𝑥2 = 300, 0000 ∙ 𝑥3 = 0 ∙ 𝑥4 = 100, 0000 ∙ 𝑓 1 = −2500 ∙ 𝑓 2 = −12500 1.2.2 Максимизация прибыли Целевая функция: 𝑓 = 𝑚𝑖𝑛(−12𝑥1 − 5𝑥2 − 15𝑥3 − 10𝑥4 ) Начальные условия: ⎛ ⎞ 0 ⎜ ⎟ ⎜0⎟ ⎟ 𝑥0 = ⎜ ⎜0⎟ ⎝ ⎠ 0 Ограничения: ⎞ ⎛ 5 1 9 12 ⎟ ⎜ ⎜ 2 3 4 1 ⎟ ⎟ ⎜ ⎟ ⎜ ⎜ 3 2 5 1 ⎟ ⎟ ⎜ ⎜ −1 0 0 0 ⎟ ⎟ ⎜ 𝐴=⎜ ⎟ ⎟ ⎜ 0 −1 0 0 ⎟ ⎜ ⎟ ⎜ 0 −1 0 ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 0 0 −1 ⎠ ⎝ −32 −15 −12 −80 ⎛ ⎞ 1500 ⎜ ⎟ ⎜ 1000 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 800 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ 𝑏=⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎝ ⎠ −12500 6 Листинг 2: Поиск оптимального решения для максимизация прибыли 1 x0 = [ 0 ; 2 0; 3 0; 4 0]; 5 6 A=[5 1 9 1 2 ; 7 2 3 4 1; 8 3 2 5 1; 9 −1 0 0 0 ; 10 0 −1 0 0 ; 11 0 0 −1 0 ; 12 0 0 0 −1]; 13 14 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 15 16 [ x1 , f 1 ] = fmincon ( i n l i n e ( ’ −12*x ( 1 ) − 5*x ( 2 ) − 15* x ( 3 ) − 10* x ( 4 ) ’ ) , x0 , A, b ) 17 f 2 = −32*x1 ( 1 ) − 15* x1 ( 2 ) − 12* x1 ( 3 ) − 80* x1 ( 4 ) Результат: ∙ 𝑥1 = 261, 2903 ∙ 𝑥2 = 0 ∙ 𝑥3 = 0, 0000 ∙ 𝑥4 = 16, 1290 ∙ 𝑓 1 = −3296, 8 ∙ 𝑓 2 = −9651, 6 1.3 Свертка критериев Максимизируется критерий объединенной операции, получающийся в результате суммирования всех частных критериев: 𝑚 ∑︀ 𝐶(𝑎) = 𝑤𝑖 𝐶𝑖𝑛 (𝑎) 𝑖=1 7 𝐶𝑖𝑛 (𝑎) = 𝐶𝑖 (𝑎) 𝐶𝑖* 𝐶𝑖* - оптимальное решение задачи по каждому критерию в отдельности, 𝑤1 +𝑤2 +· · ·+𝑤𝑚 = 1. Листинг 3: Свертка критериев 1 x0 = [ 0 ; 2 0; 3 0; 4 0]; 5 6 A=[5 1 9 1 2 ; 7 2 3 4 1; 8 3 2 5 1; 9 −1 0 0 0 ; 10 0 −1 0 0 ; 11 0 0 −1 0 ; 12 0 0 0 −1]; 13 14 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 15 16 [ x1 , f 1 ] = fmincon ( i n l i n e ( ’ −12*x ( 1 ) − 5*x ( 2 ) − 15* x ( 3 ) − 10* x ( 4 ) ’ ) , x0 , A, b ) 17 f 2 = −32*x1 ( 1 ) − 15* x1 ( 2 ) − 12* x1 ( 3 ) − 80* x1 ( 4 ) 18 19 [ x2 , f 2 ] = fmincon ( i n l i n e ( ’ −32*x ( 1 ) − 15* x ( 2 ) − 12* x ( 3 ) − 80* x ( 4 ) ’ ) , x0 , A, b ) 20 f 1 = −12*x2 ( 1 ) − 5* x2 ( 2 ) − 15* x2 ( 3 ) − 10* x2 ( 4 ) 21 22 23 % Суммирование [ x3 , F ] = fmincon ( i n l i n e ( ’ −0.5*((12* x ( 1 ) + 5*x ( 2 ) + 15* x ( 3 ) + 10* x ( 4 ) ) / 3296) − 0 . 5 * ( ( 3 2 * x ( 1 ) + 15* x ( 2 ) +12*x ( 3 ) + 80* x ( 4 ) ) / 12 50 0) ’ ) , x0 ,A , b ) В fmincon передается сумма нормированных значений (первый критерий делится на f1, второй на f2), каждое из которых умножено на определенный весовой коэффициент. Результат: ∙ 𝑥1 = 166, 4573 ∙ 𝑥2 = 127, 8185 8 ∙ 𝑥3 = −0, 0000 ∙ 𝑥4 = 44, 9913 ∙ 𝑓 = −0, 9019 (суммарное) 1.4 Максимин или минимакс Максиминную свертку представим в следующем виде: 𝐶𝑖 (𝑎) = min 𝑤𝑖 𝐶𝑖 (𝑎) Решение 𝑎* является наилучшим, если для всех 𝑎 выполняется условие 𝐶(𝑎* ) ≥ 𝐶(𝑎), или 𝑎* = arg max 𝐶(𝑎) = arg max min 𝑤𝑖 𝐶𝑖 (𝑎). Решение задачи представлено как программа в среде Matlab, с использованием функции fminimax: 𝑓1 = ((12𝑥1 + 5𝑥2 + 15𝑥3 + 10𝑥4 )/3214)−1 ; 𝑓2 = ((32𝑥1 + 15𝑥2 + 12𝑥3 + 80𝑥4 )2 /12500)−1 ; Листинг 4: Содержание файла maxmin.m 1 x0 = [ 1 ; 2 1; 3 1; 4 1]; 5 6 A=[5 1 9 1 2 ; 7 2 3 4 1; 8 3 2 5 1; 9 −1 0 0 0 ; 10 0 −1 0 0 ; 11 0 0 −1 0 ; 12 0 0 0 −1]; 13 14 15 16 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 17 18 [ x , f ] = fminimax ( @funminmax , x0 , A, b ) 9 Листинг 5: Содержание файла funminmax.m 1 2 f u n c t i o n f = funminmax ( x ) %Крит ерии 3 f ( 1 ) = 1/ ( ( 12* x ( 1 ) + 5*x ( 2 ) + 15* x ( 3 ) + 10* x ( 4 ) ) / 3214) ; 4 f ( 2 ) = 1 / ( ( 3 2 * x ( 1 ) + 15* x ( 2 ) + 12* x ( 3 ) + 80* x ( 4 ) ) / 12500) ; Так как в среде Matlab реализована только функция fminimax, которая минимизирует наихудшие значения системы функций нескольких переменных, начиная со стартовой оценки (𝑥0 ), то для реализации максиминной свертки необходимо в fminimax передавать функции, возведенные в степень 1"(функция funminmax). Результат: ∙ 𝑥1 = 111, 6707 ∙ 𝑥2 = 201, 6612 ∙ 𝑥3 = −0, 0000 ∙ 𝑥4 = 61, 6654 ∙ 𝑓 1 = 1, 0840 ∙ 𝑓 2 = 1, 0840 1.5 Метод последовательных уступок Для решения данной задачи была выбрана уступка = 10%. Решение задачи представлено как программа в среде Matlab, с использованием функции fmincon. Целевые функции: ∙ 𝑓1 = −(12𝑥1 + 5𝑥2 + 15𝑥3 + 10𝑥4 ) ∙ 𝑓2 = −(32𝑥1 + 15𝑥2 + 12𝑥3 + 80𝑥4 ) Для первого критерия: 10 ⎛ 5 1 9 12 ⎞ ⎟ ⎜ ⎜2 3 4 1⎟ ⎟ ⎜ ⎟ ⎜ 2 5 1⎟ ⎜3 ⎟ ⎜ 𝐴=⎜ 0 0⎟ ⎟ ⎜−1 0 ⎟ ⎜ ⎜ 0 −1 0 0⎟ ⎟ ⎜ ⎟ ⎜0 0 −1 0 ⎠ ⎝ 0 0 0 −1 ⎛ ⎞ 1500 ⎜ ⎟ ⎜1000⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 800 ⎟ ⎜ ⎟ ⎟ 𝑏=⎜ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎝ ⎠ 0 Результат: ∙ 𝑥1 = 261, 29 ∙ 𝑥2 = 0 ∙ 𝑥3 = 0 ∙ 𝑥4 = 16, 13 ∙ 𝑓 1 = 3297 ∙ 𝑓 2 = 9651 3297 – 329,7 = 2967,3 (10%) Для второго критерия: ⎛ ⎞ 5 1 9 12 ⎜ ⎟ ⎜2 ⎟ 3 4 1 ⎜ ⎟ ⎜ ⎟ ⎜3 2 5 1 ⎟ ⎜ ⎟ ⎜−1 0 ⎟ 0 0 ⎜ ⎟ 𝐴=⎜ ⎟ ⎜ 0 −1 0 ⎟ 0 ⎜ ⎟ ⎜ ⎟ 0 −1 0 ⎟ ⎜0 ⎜ ⎟ ⎜0 ⎟ 0 0 −1 ⎝ ⎠ −5 −1 −9 −12 11 ⎞ ⎛ 1500 ⎟ ⎜ ⎜ 1000 ⎟ ⎟ ⎜ ⎟ ⎜ ⎜ 800 ⎟ ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ 𝑏=⎜ ⎟ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 0 ⎠ ⎝ −2967, 3 Результат: ∙ 𝑥1 = 112, 7 ∙ 𝑥2 = 200, 3 ∙ 𝑥3 = 0 ∙ 𝑥4 = 61, 4 ∙ 𝑓 1 = 2967 ∙ 𝑓 2 = 11519 1.6 Fgoalattain fgoalattain решает задачу достижения цели, которая является одной из формулировок задач для векторной оптимизации. x = fgoalattain(fun, 𝑥0 , goal, weight): ∙ fun – целевая функция, ∙ 0 – начальные значения, ∙ goal – целевые значения, ∙ weight – веса. Решение задачи представлено как программа в среде Matlab, с использованием функций fminicon и fgoalattain. Целевые значения: Goal =(15855000 10240038400036 68000000 38080000 4900000) 12 Веса: weight=abs(goal) – для того, чтобы приближение к критериям было одинаково Листинг 6: Содержание файла fgoalattain.m 1 x0 = [ 1 ; 2 1; 3 1; 4 1]; 5 6 A=[5 1 9 1 2 ; 7 2 3 4 1; 8 3 2 5 1; 9 −1 0 0 0 ; 10 0 −1 0 0 ; 11 0 0 −1 0 ; 12 0 0 0 −1]; 13 14 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 15 16 %Первый крит ерий 17 clc 18 clear 19 20 % Ис ходные данные 21 x0 = [ 0 ; 22 0; 23 0; 24 0]; 25 26 A=[5 1 9 1 2 ; 27 2 3 4 1; 28 3 2 5 1; 29 −1 0 0 0 ; 30 0 −1 0 0 ; 31 0 0 −1 0 ; 32 0 0 0 −1]; 33 13 34 b = [1500 , 1000 , 800 , 0 , 0 , 0 , 0 ] ; 35 36 [ x1 , f 1 ] = fmincon ( i n l i n e ( ’ −12*x ( 1 ) −5*x ( 2 ) −15*x ( 3 ) −10*x ( 4 ) ’ ) , x0 , A, b) 37 38 [ x2 , f 2 ] = fmincon ( i n l i n e ( ’ −32*x ( 1 ) −15*x ( 2 ) −12*x ( 3 ) −80*x ( 4 ) ’ ) , x0 , A , b) 39 40 goal = [0 0 ] ; 41 goal (1) = f1 ; 42 goal (2) = f2 ; 43 44 we ig ht = abs ( g o a l ) ; 45 46 [ x , f3 , a t t a i n f a c t o r ] = f g o a l a t t a i n ( @myfun , x0 , g o a l , weight , A, b ) Результат: ∙ 𝑥1 = 207, 81 ∙ 𝑥2 = 72, 08 ∙ 𝑥3 = 0 ∙ 𝑥4 = 32, 4 ∙ 𝑓 1 = 3178 ∙ 𝑓 2 = 10324 ∙ 𝐴𝑡𝑡. = 0, 1741 1.7 Задача стохастического программирования Требуется найти такие 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 для которых выполняться следующие ограничения: ∙ 5𝑥1 + 𝑥2 + 9𝑥3 + 12𝑥4 ≤ 1500 ∙ 2𝑥1 + 3𝑥2 + 4𝑥3 + 1𝑥4 ≤ 1000 ∙ 3𝑥1 + 2𝑥2 + 5𝑥3 + 1𝑥4 ≤ 800 Перейдем от последнего ограничения к вероятностному по схеме: 𝑃 ( 𝑛 ∑︀ 𝑗=1 14 𝑎𝑖𝑗 𝑘𝑗 − 𝑏𝑗 ≤ 0) ≥ 𝛼𝑖 И будем менять 𝛼𝑖 в диапазоне 0.1 ≤ 𝛼𝑖 ≤ 0.9, и возьмём коэффициенты 𝑎𝑖 за случайные величины. 𝑃 (0, 6𝑥1 + 0, 8𝑥2 + 1, 0𝑥3 + 1, 2𝑥4 ≤ 100) ≥ 𝛼𝑖 Пользуясь формулой: 3 ∑︀ 𝑎𝑖𝑗 𝑥𝑗 − 𝑏 + 𝐾𝛼 𝜎𝐴 ≤ 0 𝑗=1 получим вероятностное ограничение для задачи, где a = 0,6, 0,8, 1,0, 1,2, b = 100 – взяты √︀ из первоначального вида ограничения, 𝜎𝐴 = 𝑥 cov(a) 𝑥𝑇 . По таблице функции распределения стандартного нормального закона находим коэффициенты 𝐾𝛼 (0, 5 ≤ 𝛼 ≤ 0, 9): ∙ 𝐾0,5 = 0 ∙ 𝐾0,6 = 0, 253 ∙ 𝐾0,7 = 0, 520 ∙ 𝐾0,8 = 0, 841 ∙ 𝐾0,9 = 1, 282 1 lb = [0 0 0 0 ] ; 2 ub = [ 1 0 0 100 100 1 0 0 ] ; 3 x0 =[0 0 0 0 ] ; 4 5 6 7 o p t i o n s = o p t i m s e t ( ’ Algorithm ’ , ’ i n t e r i o r −p o i n t ’ ) ; % для каждо г о крит ерия по отдельно с ти : [ x , f v a l ] = fmincon ( i n l i n e ( ’ −12*x ( 1 ) −5*x ( 2 ) −15*x ( 3 ) −10*x ( 4 ) ’ ) , x0 , [ ] , [ ] , [ ] , [ ] , lb , ub , @constrStoh , o p t i o n s ) 1 f u n c t i o n [ sigma ] = p r o b a b i l i t y C o n s t r ( x ) 2 covH=x * [ 0 . 6 ; 0 . 8 ; 1 . 0 ; 1 . 2 ] * t r a n s p o s e ( x ) ; 3 sigma = s q r t ( covH ) ; 4 end 1 f u n c t i o n [ c , ceq ] = c o n s t r S t o h ( x ) 2 ceq = 0 ; 3 4 5 6 7 sigma = p r o b a b i l i t y C o n s t r ( x ) ; K= 1 . 2 8 2 ; c = [ % вв еденно е в ероятно с тно е о граничение 15 0 . 6 * x ( 1 ) + 0 . 8 * x ( 2 ) + 1 * x ( 3 ) + 1 . 2 * x ( 4 ) − 100 + K* sigma ; 8 9 10 −0.2*x ( 1 ) − 0 . 3 * x ( 2 ) − 0 . 4 * x ( 3 ) − 0 . 5 * x ( 4 ) + 3 5 ; 11 −0.6*x ( 1 ) − 0 . 4 * x ( 2 ) − 0 . 3 * x ( 3 ) − 0 . 2 * x ( 4 ) + 4 2 ; % у словия из "бывших" крит ерие в 12 −12*x ( 1 ) − 5*x ( 2 ) − 15* x ( 3 ) − 10* x ( 4 ) ] ; 13 14 end K 0 0,253 0,52 0,841 1,282 𝑥1 100 29,2780 27,7214 30,0887 25,4234 𝑥2 0 28,7760 25,8883 26,9406 22,6038 𝑥3 40 28,4840 24,8369 25,4863 21,2327 𝑥4 0 15,4300 12,8728 0,5164 1,1430 𝑓 1800 1076,8 963,4 883,2 748 Таблица 2: Результаты Видно, что задача чувствительна к выбранному ограничению, т.к. для различных K получились разные результаты. Так же следует отметить, что значения функций соответствуют нормальному закону распределения, что соответствует теории. 16 2 Решение задачи оценки показателей эффективности стохастической сети с использованием методики GERT. Выбор и использование математического пакета Matlab для решения сформулированной задачи. 2.1 Постановка задачи Дано: 1. Граф GERT-сети (рисунок 1). 2 0,5 0,1 1 5 0,5 0,2 4 0,6 0,3 0,4 3 6 0,4 Рис. 1: Граф GERT-сети. 2. Каждой дуге-работе (𝑖, 𝑗) поставлены в соответствие следующие данные: (a) Закон распределения времени выполнения работы. Будем считать его нормальным. (b) Параметры закона распределения (математическое ожидание 𝑀 и дисперсия 𝐷). (c) Вероятность 𝑃𝑖𝑗 выполнения работы, показанная на графе. Найти: 1. Вероятность выхода в завершающий узел графа (для всех вариантов узел 6). 17 Начальная вершина Конечная вершина 𝑀 𝐷 1 2 12 9 1 4 28 16 2 5 14 9 3 1 11 4 3 3 33 16 4 2 11 4 4 3 33 25 4 5 45 25 4 6 23 16 5 6 43 25 Таблица 3: Параметры закона распределения для дуг графа 2. Математическое ожидание. 3. Дисперсию времени выхода процесса в завершающий узел графа. Перечислить все петли всех порядков, обнаруженные на графе, выписать уравнение Мейсона, получить решение для 𝑊𝐸 (𝑠) и найти требуемые параметры. Примерно так, как это сделано в примере на стр. 403 – 409 книги Филипса и Гарсиа «Методы анализа сетей» 2.2 Ход работы Решение: Замкнём граф дугой из вершины 6 в вершину 1 (рисунок 2). Петли первого порядка: ∙ 𝑊12 𝑊25 𝑊56 𝑊1𝐸 ∙ 𝑊14 𝑊42 𝑊25 𝑊56 𝑊1𝐸 ∙ 𝑊14 𝑊43 𝑊31 ∙ 𝑊14 𝑊45 𝑊56 𝑊1𝐸 ∙ 𝑊14 𝑊46 𝑊1𝐸 ∙ 𝑊33 Петли второго порядка: 18 2 0,5 0,1 1 5 0,5 0,2 4 0,6 0,3 0,4 1 𝑊𝐸 3 6 0,4 Рис. 2: Замкнутый граф GERT-сети. ∙ 𝑊33 и 𝑊12 𝑊25 𝑊56 𝑊1𝐸 ∙ 𝑊33 и 𝑊14 𝑊42 𝑊25 𝑊56 𝑊1𝐸 ∙ 𝑊33 и 𝑊14 𝑊45 𝑊56 𝑊1𝐸 ∙ 𝑊33 и 𝑊14 𝑊46 𝑊1𝐸 Петель третьего порядка нет. 19 Выпишем уравнение Мейсона: 𝐻 = 1 − 𝑊12 𝑊25 𝑊56 1 𝑊𝐸 − 𝑊14 𝑊42 𝑊25 𝑊56 1 𝑊𝐸 − 𝑊14 𝑊43 𝑊31 − 𝑊14 𝑊45 𝑊56 − 𝑊14 𝑊46 1 𝑊𝐸 1 𝑊𝐸 − 𝑊33 + 𝑊33 𝑊12 𝑊25 𝑊56 1 𝑊𝐸 + 𝑊33 𝑊14 𝑊42 𝑊25 𝑊56 + 𝑊33 𝑊14 𝑊45 𝑊56 + 𝑊33 𝑊14 𝑊46 1 𝑊𝐸 1 𝑊𝐸 1 =0 𝑊𝐸 Отсюда выведем 𝑊𝐸 (𝑆): 1 − 𝑊14 𝑊43 𝑊31 − 𝑊33 = (𝑊12 𝑊25 𝑊56 + 𝑊14 𝑊42 𝑊25 𝑊56 + 𝑊14 𝑊45 𝑊56 + 𝑊14 𝑊46 − 𝑊33 𝑊12 𝑊25 𝑊56 − 𝑊33 𝑊14 𝑊42 𝑊25 𝑊56 − 𝑊33 𝑊14 𝑊45 𝑊56 − 𝑊33 𝑊14 𝑊46 ) 𝑊𝐸 (𝑆) = 1 𝑊𝐸 (𝑊12 𝑊25 𝑊56 + 𝑊14 𝑊42 𝑊25 𝑊56 + 𝑊14 𝑊45 𝑊56 + 𝑊14 𝑊46 − 𝑊33 𝑊12 𝑊25 𝑊56 − 𝑊33 𝑊14 𝑊42 𝑊25 𝑊56 − 𝑊33 𝑊14 𝑊45 𝑊56 − 𝑊33 𝑊14 𝑊46 )/ (1 − 𝑊14 𝑊43 𝑊31 − 𝑊33 ) Далее рассчитаем W-функции дуг. Далее вычислим математическое ожидание и дисперсию: 𝑀𝐸 (𝑠) = 1 при 𝑠 = 0 Поскольку 𝑊𝐸 (𝑠) = 𝑝𝐸 𝑀𝐸 (𝑠), то 𝑝𝐸 = 𝑊𝐸 (0), откуда следует, что 𝑀𝐸 (𝑠) = 𝑊𝐸 (𝑠) 𝑝𝐸 = 𝑊𝐸 (𝑠) 𝑊𝐸 (0) Вычисляя первую и вторую производные по 𝑠 функции 𝑀𝐸 (𝑠), и полагая 𝑠 = 0, находим математическое ожидание: 𝜇1𝐸 = 𝜕𝑀𝐸 (𝑠) |𝑠 𝜕𝑠 =0 и дисперсию: 𝜎 2 = 𝜇2𝐸 − [𝜇1𝐸 ]2 . 20 Начальная вершина Конечная вершина Вес ребра (𝑝𝑖𝑗 ) 𝑀 𝐷 W-функция 1 2 0,5 12 9 0, 5 * 𝑒𝑥𝑝(12𝑠 + 92 𝑠2 ) 1 4 0,5 28 16 0, 5 * 𝑒𝑥𝑝(28𝑠 + 2 5 1 14 9 3 1 0,6 11 4 3 3 0,4 33 16 4 2 0,1 11 4 4 3 0,3 33 25 4 5 0,2 45 25 4 6 0,4 23 16 5 6 1 43 25 16 2 𝑠) 2 𝑒𝑥𝑝(14𝑠 + 29 𝑠2 ) 0, 6 * 𝑒𝑥𝑝(11𝑠 + 42 𝑠2 ) 0, 4 * 𝑒𝑥𝑝(33𝑠 + 16 𝑠2 ) 2 0, 1 * 𝑒𝑥𝑝(11𝑠 + 42 𝑠2 ) 0, 3 * 𝑒𝑥𝑝(33𝑠 + 25 𝑠2 ) 2 0, 2 * 𝑒𝑥𝑝(45𝑠 + 25 𝑠2 ) 2 𝑠2 ) 0, 4 * 𝑒𝑥𝑝(23𝑠 + 16 2 𝑒𝑥𝑝(43𝑠 + 25 𝑠2 ) 2

www.studocu.com

Математические методы оптимизации — Студопедия.Нет

Методы анализа и синтеза структуры сети

Задачи анализа и синтеза структуры сетей

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

Задачи анализа и синтеза структуры сети электросвязи объединяются общностью конечных целей, методологическим подходом и математическим аппаратом. Конечная цель этих задач – построение эффективной инфокоммуникационной системы, которая обеспечивает выполнение установленных функций и способна развиваться. Слово "эффективная" указывает на тот факт, что структура сети близка к оптимальной. Методологический подход к анализу и синтезу структуры сети электросвязи можно считать общим в силу универсальности и неразрывности возникающих задач. Математический аппарат, используемый для решения возникающих задач, идентичен.

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

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

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

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

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

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

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

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

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

Однако для решения практически важных задач необходимы численные оценки – даже весьма приближенные. При этом необходимо понять если не величину ошибки, то хотя бы ее порядок. В ряде случаев допустимы значительные ошибки. Это обусловлено характеристиками используемых технических средств. Например, в начале XX века для организации линии связи между двумя коммутационными станциями использовались многопарные кабели. Было важно точнее оценить число пар, которое, в значительной мере, определяло стоимость проекта. Допустимая ошибка измерялась единицами процентов. В начале XXI века для организации линии связи между двумя коммутационными станциями применяются кабели с оптическими волокнами. Задача состоит в выборе типа системы передачи, величины пропускной способности которых образуют числовой ряд. Каждый член этого ряда предыдущему, умноженному на четыре. Это означает, что допустимая ошибка в расчете необходимого числа каналов измеряется не процентами, а разами.

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

Наиболее известный метод оптимизации для функции одной переменной заключается в нахождении ее производной. Если в точке производная равна нулю, то в этой точке имеет минимум или максимум. Максимум достигается при условии, что . В противном случае (когда ) исследуемая функция имеет минимум. При говорят, что функция при имеет стационарное значение. Точка называется стационарной.

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

максимум при четном и ,
минимум при нечетном и . (13.1)

Выражение (13.1) определяет достаточные условия экстремума.

Для нахождения экстремумов функции в области необходимо сначала найти ее производную:

. (13.2)

Это уравнение имеет корни: . К этим корням надо присоединить граничные точки. В результате получается такой ряд:

. (13.3)

Можно убедиться в следующем: в точке наблюдается граничный минимум, а в точке – граничный максимум. Точка определяет локальный максимум функции , а точка – локальный минимум. Для нулевого значения аргумента . Это означает, что точка определяет место перегиба функции .

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

. (13.4)

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

. (13.5)

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

В подобных ситуациях эффективны методы направленного случайного поиска. Их эффективность возрастает, если функция относится к классу унимодальных, то есть на отрезке имеет либо один минимум, либо один максимум. Такое условие справедливо для большинства задач оптимизации инфокоммуникационной системы, в которых функции стоимости отдельных компонентов сети представлены монотонными функциями. Тогда для локализации экстремума могут быть использованы методы "Деления отрезка пополам", "Золотого сечения" и "Чисел Фибоначчи".

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

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

Рис. 13.1. Три графика функций

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

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

. (13.6)

Функции и можно аппроксимировать непрерывными кривыми. Их анализ свидетельствует, что аппроксимирующие кривые монотонны. Это означает, что на отрезке [ ] будет иметь один минимум. Истинная (ступенчатая) функция , как следует из нижнего графика на рисунке 13.1, может иметь несколько минимумов и максимумов. На нижнем графике указаны соответствующие абсолютные значения. Не исключено, что замена функций и непрерывными кривыми приведет к существенной ошибке в определении минимума исследуемой зависимости.

Для множеств и целесообразно найти наибольшее общее кратное – . Тогда преобразование Лапласа-Стилтьеса для исследуемой функции – может быть представлено суммой:

. (13.7)

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

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

studopedia.net

Математические методы оптимизации:конспект лекций

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

конспект лекций.

Е.Ю. Щетинин

ОГЛАВЛЕНИЕ Глава 1.

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИИ В ОПТИМИЗАЦИИ 5

1.1. Определение границ объекта оптимизации 5

1.2. Выбор управляемых переменных 6

1.3. Определение ограничений на управляемые переменные 6

1.4. Выбор числового критерия оптимизации 7

1.5. Формулировка математической задачи оптимизации 8 Глава 2.

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ 8 2.1. Предварительные сведения 9

2.1.1. Минимум функции одной переменной . 9

2.1.2. Унимодальные функции . 10

2.1.3. Выпуклые функции 11

2.1.4. Условие Липшица 13

2.1.5. Классическая минимизация функции одной переменной 15

2.2. Прямые методы 16

2.2.1. Метод перебора 16

2.2.2. Методы исключения отрезков 18

2.2.3. Метод парабол 26 Глава 3

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 30

3.1. Предварительные сведения 30

3.1.1. Основные понятия линейной алгебры 30

3.1.2. Минимум функции многих переменных 33

3.1.3. Дифференцируемые функции многих переменных 34

3.1.4. Необходимые и достаточные условия минимума дифференцируемой функции 35

Упражнения 36

3.2. Выпуклые множества и выпуклые функции 37

3.2.1. Свойства выпуклых функций 37

3.2.2. Выпуклые квадратичные функции 41

Упражнения 43

3.3. Общие методы n–мерной минимизации 43

Упражнения 47

3.4. Прямые методы безусловной минимизации 47

3.4.1. Минимизация по правильному симплексу 48

3.4.2 Поиск точки минимума по деформируемому симплексу 50

3.4.3. Метод циклического покоординатного спуска 52

3.4.4. Алгоритм Хука– Дживса 54

3.4.5. Методы случайного поиска 55

3.4.6. Метол сопряженных направлений 57

Упражнения 61

3.5. Методы безусловной минимизации, использующие производные функции 62

3.5.1. Метод градиентного спуска 63

3.5.2. Метод наискорейшего спуска 65

3.5.3. Метод сопряженных градиентов 66

3.5.4. Метол Ньютона 69

3.5.5. Квазиньютоновские методы 71

Упражнения 74

Библиографический список 76

Глава 1

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ОПТИМИЗАЦИИ

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

Для того чтобы использовать результаты и вычислительные процедуры теории оптимизации на практике, необходимо, прежде всего, сформулировать рассматриваемую задачу на математическом языке, т.е. построить математическую модель объекта оптимизации. Математическая модель – это более или менее полное математическое описание исследуемого процесса или явления.

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

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

1.1. ОПРЕДЕЛЕНИЕ ГРАНИЦ ОБЪЕКТА ОПТИМИЗАЦИИ

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

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

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

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

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

ВЫБОР УПРАВЛЯЕМЫХ ПЕРЕМЕННЫХ

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

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

1.3. ОПРЕДЕЛЕНИЕ ОГРАНИЧЕНИЙ НА УПРАВЛЯЕМЫЕ ПЕРЕМЕННЫЕ

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

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

1.4. ВЫБОР ЧИСЛОВОГО КРИТЕРИЯ ОПТИМИЗАЦИИ

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

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

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

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

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

1.5. ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ

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

Под минимизацией (максимизацией) функции п переменных f (x)=(x1 ,.., xn) на заданном множестве U n–мерного векторного пространства Еn понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:f (x) min (max),

х U

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

birmaga.ru

Математические методы оптимизации эксперимента

Математика Математические методы оптимизации эксперимента
просмотров - 151

Методы корреляционного и регрессионного анализа

Самая простая зависимость между Х и Y, полученная в эксперименте – линейная. Вследствие случайных отклонений экспериментально полученных величин одному значению Х могут соответствовать различные значения Y. Степень зависимости случайных величин Х, Y характеризуется коэффициентом корреляции (в данном случае, парной корреляции). Коэффициент корреляции характеризует различие между зависимостями Y =f(X) и X = f(Y) и численно равен косинусу угла, который образуют эти функции. В случае если линейная связь между Х и Y отсутствует, то угол равен 90, а соответственно cos = 0.

Проверку значимости коэффициента корреляции проводят либо по таблицам критических значений коэффициентов парной корреляции, либо по критерию Стьюдента. Для проверки по критерию Стьюдента рассчитывают его экспериментальное значение и сравнивают с соответственным табличным. При tэксп>tтабл коэффициент корреляции статистически значим и, следовательно, зависимость между рассматриваемыми переменными имеется.

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

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

Используют для получения максимального объема информации при минимальном объеме эксперимента͵ поиска оптимума процесса или технологии, описания неизвестного процесса математической моделью (полиномиальной формулой), систематизации экспериментального материала.

1. На первом этапе проводят выбор параметров оптимизации (У) и выбор факторов (Х) для зависимости у = f(x).

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

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

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

xi = (x1i - x0i) / Ii,

x1i – натуральное значение фактора на каком-либо уровне,

x0i - натуральное значение фактора на нулевом уровне,

Ii – интервал варьирования фактора (в натуральном виде).

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

К примеру, для учета 15 факторов крайне важно провести 215 опытов, что составит 32768 опытов. И можно взять реплику, в которой число опытов для учета влияния 15 факторов будет равно 16 опытам. Соответственно, для учета 7 факторов – реплику из 8 опытов и т. д. То есть планируют так называемый дробный факторный эксперимент. Факторы варьируют обычно на двух уровнях, при этом кодированные значения факторов равны (-1, 0, +1). Ноль обычно находится в середине значения фактора. Интервалы не должны быть меньше удвоенной среднеквадратичной ошибки. Обычно интервал составляет 10-25% максимального натурального значения фактора.

После проведения опытов рассчитывают коэффициенты полинома – уравнения регрессии. Формула для расчета коэффициентов регрессии:

bj – коэффициент регрессии i-го фактора,

yi – значение параметра оптимизации в i-ом опыте,

xij – кодированное значение j-го фактора в i-ом опыте,

n – количество опытов в матрице.

Ошибку эксперимента находят по результатам опытов, повторенных несколько раз при одних и тех же условиях. Рекомендуется каждый опыт проводить дважды, а если результаты отличаются более чем на 10%, то повторяют опыт еще раз. Одно из трех значений, как случайное, отсеивают по критерию Стьюдента: tрасч ³ tтабличное.

Факторы, незначительно влияющие на параметр оптимизации У, имеют коэффициенты регрессии меньше доверительного интервала. По этому признаку факторы и отсеивают. В случае если факторов отсеялось слишком много, то вполне вероятно, что неправильно определены интервалы варьирования.

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

При использовании метода крутого восхождения вначале проводят дробный факторный эксперимент, определяют коэффициенты уравнения регрессии. В случае если шаги отдельных факторов оказываются малыми (незначимыми), то значения этих факторов стабилизируют. Затем проводят статистический анализ полученных коэффициентов, выбор нового шага (обычно меньшего) и применяют так называемое крутое восхождение по поверхности отклика. Чтобы задать направление вектора, по которому будет происходить возрастание значений Y (при нахождении максимума), вычисляют частные производные по независимым переменным. Численно они равны коэффициентам уравнения регрессии, качественно – значениям переменных Х и являются шагами для крутого восхождения. Результаты некоторых опытов рассчитывают по найденному в дробном эксперименте полиному. Намеченные опыты реализуют до тех пор, пока не будет найден оптимум.