Этапы решения задач исследования операций

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

1. Исследование операций, этапы решения задач исследования операций (ИО)

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

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

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

Основными этапами в ИО являются:

Построение модели

Выбор критериев и их формулировка

Нахождение оптимального решения

Для ИО характерно:

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

Руководитель (ЛПР или др. лицо) получает научно обоснованное решение.

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

Особенности задач в исследовании операций. Многокритериальность задач ИО при выборе альтернатив.

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

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

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

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

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

Оптимум - наилучшее условие или совокупность наиболее благоприятных условий.

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

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

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

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

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

Число управлений - число степеней свободы объекта.

К управлениям относят различные параметры: оптимизация качества управления объекта в САР - настройки регулятора; закон регулирования.

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

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

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

Классификация переменных (технологических параметров) ХТП как объекта оптимизации.

- вектор переменных, значения которых известны (заданы) в задаче или они поступают с объекта как измеренные, но изменять их мы не можем;

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

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

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

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

5. Задачи на условный и безусловный экстремумы, геометрическое представление задач оптимизации, формы записи задач оптимизации.

Задачи без ограничений - задачи на безусловный экстремум или задачами безусловной оптимизации.

,

Спроецируем линии постоянных критериев на поверхности R на плоскость X1X2. Тогда на плоскости увидим точку М. Значение в точке М называется безусловным экстремумом. Задача оптимизации заключается в определении координат точки М.

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

Пусть заданы ограничения в форме неравенств.



(1)

(2)

(3)

Задачи с ограничениями вида (1), (2), (3) - задачи на условный экстремум.

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

з

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

Формы записи задач оптимизации:

,



,

Классификация ХТП. Оптимизационные задачи в сфере химических производств (управление, проектирование, исследование).

К основным химико-технологическим процессам относятся:

Химические превращения (реакторные системы)

Массообменные (ректификация, абсорбция, адсорбция, сушка)

Механические

Гидравлические (перемещение жидкости по трубе)

Криогенные

В зависимости от организации материальных потоков в аппарате различают процессы:

Периодического действия

Непрерывного действия (вещества поступают и выходят непрерывно)

Полунепрерывные (часть участников поступают и выходят непрерывно, а часть находятся постоянно)

Дискретные (короткое время обработки)

Дискретно-непрерывные (процессы могут производиться непрерывно, смешиваясь дискретизуются )

По структуре потоков :

Аппараты идеального смешения

Аппараты идеального вытеснения

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

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

Задачи:

1) Управление (оптимизация)

2) Проектирование

3) Оптимальное планирование эксперимента

В управлении ТП существует также класс задач оптимального управления динамическим режимом ТП. К таким относятся:

1) Пуск технологической установки

2) Переход с режима на режим

3) Планирование эксперимента

Оптима - означает наилучшее условие.

Оптимизация - процесс достижения оптимума. Применяемо к ТП - определение наилучших условий проведения процесса.

При постановке задач оптимизации, и в ХТ необходима количественная оценка качества работы оптимизируемого объекта(системы): “Критерий оптимальности” или “Целевая функция”. При этом оптимальное условие соответствия наилучшему значению критерия оптимальности(max, min).

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

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

Критерии эффективности ХТП (ХТС), обобщенный критерий оптимальности и его составляющие (экономические).

2. Критерий оптимальности - показатели эффективности ХТП

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

Экономическая эффективность оценивается по:

1) В - производительность готовой продукции. Количество единиц продукции в единицу времени.

2) Ф - объем капитальных вложений.

3) Э - эксплуатационные расходы осущ. Производства.

4) К - показатели качества выпускаемой продукции. Определяет её цену на рынке.

R = R(В, Ф, Э, К)

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

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

3. Себестоимость выпускаемой продукции, составляющие себестоимости

Себестоимость выпуск. продукта (Sпр)- полные затраты на единицу выпускаемой продукции.

Производственная С/С и объема выпуска продукции представляют полные затраты на производство:

Sпр*В= Sс+ Sт+ Sп



Sс- стоимость сырья на полный выпуск

Sт- текущие расходы, связанные с процессом производства.

Sп-постоянные расходы, независящие от объема выпуска продукции.

S=B*Sс

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

Sт=В*sт

sт- текущие расходы на единицу продукции. Входят затраты на электроэнергию, пар, воду, вспомогательные материалы, з/п операт. Персонала.

Sп=SА+Sp

Sп-постоянные расходы

SА-амортизационные отчисления

Sp-часть расходов, определяемая затратами на профессиональный ремонт +з/п персонала и затраты на реализацию готовой продукции

SА=НА*Ф

НА-норма амортизации

НА=(Ф+Р-Л)/(Ф*Т)

Ф- стоимость основных фондов

Р-затраты на ремонт оборудования

Л- ликвидационная стоимость фондов

Т-срок службы ОПФ

Т и Р также зависят от условий проведения пресса, т.е. определяется режим работы ТО.

Используя приведенные соотношения можно записать соотношение для себестоимости единицы продукции.

Sп= Sс+ Sт+(Ф+Р-Л)/(B*T)+ Sp/B

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

Прибыль получаемая при реализации:

П=Ф*(Sц- Sпр)

Sц - цена ед. продукции

4. Прибыль как критерий оптимальности, норма прибыли. Показатель приведенных затрат

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

Прибыль, получаемая при реализации, может быть рассчитана:

д.е/ ед.вр. (предполагается, что вся продукция реализуется)

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

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

,

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

Учитываются как затраты непосредственно связанные с себестоимостью производства, так и затраты связанные с аппаратным оформлением производства.

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

Критерий оптимальности в виде алгебраического выражения:

,

Критерий оптимальности в виде аддитивной функции частных критериев оптимальности.

Такой критерии характерен для многостадийных процессов.

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

Критерии оптимальности в виде линейной функции от управления.

R=C0+C1U1+…+CnUn=УCiUi,

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

Критерий в таком виде характерен для задач ЛП

Критерии оптимальности в виде функционала.

Функционал - это математический оператор, переводящий функцию в число; например скалярное произведение двух векторов и

, где

Критерий оптимальности в виде функционала.

Функционал - это математический оператор, переводящий функцию в число; например скалярное произведение двух векторов и

, где ,

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

Такой критерии характерен для многостадийных процессов.

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

-мультипликативный

,

,

5. Критерием всего процесса является степень превращения

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

13. Критерий оптимальности и ограничения в виде линейных функций от управлений. Линейное программирование (ЛП), постановка задачи ЛП.

R=C0+C1U1+…+CnUn=УCiUi,

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

Критерий в таком виде характерен для задач ЛП

Постановка задачи

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

с1 и с2 - цена единицы продукции 1 и 2 видов. Тогда общая стоимость произведенной продукции:

,

Пусть b1 и b2 - количество сырья 1 и 2 вида, имеющегося на складах. Известно, что aij - число единиц i - го вида сырья, необходимого для производства единицы j-го вида продукции.

Тогда (2),

Неравенство (2) является ограничением.

Относительно переменных xj в линейном программировании принято, что они больше нуля.

(3)

Ограничение (3) по умолчанию.

Метод решения этих задач называется линейным программированием. Разработан в 30х годах советским ученым Конторовичем.

14. Математическая формулировка задач ЛП.

Пусть задача линейная формула

R= = (1)

Требуется среди всех неотрицательных решений системы (2) найти такое, при котором лин форма R(1) принимает max/min значение.

Утверждения 1:

Ограничение задачи(2) в виде неравенств системы (2) можно представить в виде диф. Уравнений. Покажем это:

Пусть ограничение задано неравенством

, (3)

Введен в левую часть 3 доп переменных

,

,



,

Введенные переменные наз-ся дополнительными. Их введение позволяет перейти от неравенств к равенствам.

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

15. Переход в задаче ЛП от системы равенств к неравенствам.

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

,

,

Рассматривается случай, когда система совместа, т.е ранг матрицы системы и ранг расширенной матрицы одинаковы.

rang A =rang B = r

Можно выразить любое r через переменные n-Z, свободные. Выразим базисные переменные:



,

(1)

Из условий ЛП

(2)

Система (2) вместе с линейной формой (1) позволяет эффективно сформулировать задачу ЛП с ограничениями в виде неравенств.

Геометрическая интерпретация задачи ЛП.

Любое неотрицательное решение системы ограничений называется допустимым. Допустимое решение, доставляющее min/max в линейной форме R называется оптимальным. Совместность всех допустимых решений системы ограничений называется ОДР (область допустимых решений).

(1)

Предположим, что существует решение системы (1), т.е. система совместна:

rangA = n=

Система (1) имеет единственное решение. В этом случае задача оптимизации исчезает. Ранг матрицы А равен числу неизвестных решений

rangA < n, где n =

Система (1) имеет бесчисленное множество решений, и задача оптимизации заключается в нахождении таких решений, которые доставляют min/max значение критерию R.

,

R=C1>C2>C3>C4

,

R=C5<C4<C3<C2<C1

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

А) В ЛП область ограничений является выпуклой.

Б) Критерий оптимельности R есть облать ограничений, имеющая конкретное значение.

В) Все переменные должны быть положительными

17. ЛП Решение задач ЛП симплекс-методом Данцига, базисные и свободные переменные.

Симплексом в n-мерном пространстве называют выпуклый многогранник, имеющий (n+1) вершин и (n+1) граней в гиперпространстве n-переменных.

Пусть ограничения заданы в виде равенств:

(1)

,

Выразим r базисных переменных, начиная с 1ой через оставшуюся (n-1) переменную, которые будут являться свободными.

Система имеет бесчисленное множество решений.

(2)

Так как свободным переменным можно придавать любые положительные значения, то свободные члены должны быть положительными, так как в противном случае (bj<0) получим xi<0

Положив в системе (2) все свободные переменные равными 0, получим



(3)

(4)

Вектор (4) является допустимым, так как все свободные переменные нулевые, а базисные больше 0. Подставим в линейную форму R вместо базисных переменных их выражения из системы (2) через свободные переменные

(5)

(6)

Получив 1 б.р. переходим к следующему. Переход осуществляется следующим образом: одна из базисных переменных в системе (2) заменяется одной из свободных переменных с учетом определенных правил. Находится 2б.р. т.д. до тех пор, пока происходит улучшение линейной формы R.

Последовательность решения задачи ЛП симплекс-методом (на примере)

(7) xr , r=1;2;….

R=3>min (8)

Система (7) является совместной

(9)

Предположим, что и , с учетом системы (9) получим X1 X2 X3 X4 X5 1б.р. : col(2; 7; 2; 0; 0) R(1б.р.)=3

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

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

Из анализа системы (9) видим, что можно увеличивать до=? 4?2 , таким образом переходим к следующему б.р. X1 X2 X3 X4 X5 2б.р. : col(0; 3; 4; 2; 0) R(2б.р.)=3-2+0=1

Выразим новые б.п. через новые свободные переменные

,

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

Таким образом уравнение (10) является искомым и 2б.р. оптимальным.

ЛП. Первое базисное решение, метод искусственного базиса (случай 1).

Пусть ограничения имеют вид неравенств вида:

(1)

,



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

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

ЛП. Первое базисное решение, метод искусственного базиса (случай 2)

Ограничения имеют вид неравенств вида:

,

Введем доп. Переменные в каждое ограничение

(4)

В этом случае ед. подматрица состоит из отрицательных элементов. По условию задач ЛП необходимо чтобы эти элементы были положительными . Для этого из сист (4) выбираем одно, у которого . Остальные(m-1) ур-ия системы умножаем на (-1). Сложим выбранное ур-ие с каждым оставшемся ур-ем системы. Тогда получим новую сист (m-1) ур-ий, эквивалентную исходной, но с положительными коэфф. Ед. подматрицы.

Пусть max (5)

(6)



(7)

Новая сист(6) имеет ед. подматрицу с положит. Элементом порядок которой (m-1). Для того, чтобы дополнить подматрицу до матрицы порядка m, введем в у ур-ие сист(4) искусств переменную

(8)

Тогда переменные (i=n+1, n+2, (m-1)+n) совместно с образует ед. подматрицу с положит. эл-ми, по которой определяется 1 б.р, но при этом при достижении оптимума обязательно должно вып-ся условие:

,

Для этого можно восп-ся приемом: ввести переменную (9) в выражение для критерия в след виде:

R= (10) - ф-ия штрафов)

большое положительное число если ищем max и отрицательное если ищем max

Метод искусственного базиса (случай 3).

М - большое положительное число, если ищем max и отрицательное, если ищем min

Ограничение имеет вид:



,

Этот случай представляет собой простую комбинацию случаев 1 и 2. Поэтому для неравенств 1-го вида поступают как в случае 1. Т.е. вводят положительную дополнительную переменную для неравенств 2-го вида как в случае 2

Лин форму для критерия записанном в виде R=

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

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

Вид продукции	Вид сырья и побочных продуктов в у. е.
	A	B	C	D
I	2	1	-1	4
II	2	4	2	-1
III	-1	-1	-1	1
Запасы
	8	4	1	8

Наряду с расходом обр-ся побочные компон,которые яв-ся продуктами для других процессов

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

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

	Прибыль на ед .пр.	цена	С/c
I	7 у. д. е	72	65
II	3 у. д. е	93	90
III	2 у. д. е	51	49

Прибыль=B(Ц-с/c)

Обозначим: x1, x2, x3 - объемы выпуска каждого вида продукции в у. е.

max (1)

(2)

Формально в задаче ЛП нужно определить значения x1 x2 x3 удовлетворяющие ограничениям (2) и довстовляющие max в линейную форму (1).

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

(3)

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

(4)



Присвоим свободным переменным 0.

Получим первое базисное решение

1 б.р.:

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

Функция многих переменных R(x1,x2,....xn) имеет в точках (x1,x2,....xn) экстремумы, если существует такая достаточно малая окрестность этой точки, взятая из области определения этой функции, что для всех точек этой окрестности справедливо одно из условий:

1) R(x1,x2,....xn)< R(x1(0), x2(0),.... xn(0),) => max R()

2) R(x1,x2,....xn)< R(x1(0), x2(0),.... xn(0),) => min R()

R()=R((0))

Необходимым условием существования экстремума многих переменных является равенство нулю частных производных первого порядка по всем переменным. (система производных)



(;

(;

(;

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

А R() | = 0 (0)

dR(x1,x2,....xn)= dx1 + dx2 +......+ dxn = dxi

Если () = 0 , то dR() = 0 (0)

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

Разложим ф-ию в ряд Тейлора в окрестности точки по степеням , r=

= R-(+,…, +,…,+)=R(

,

,

=0.1;

; =0.1*0.1=0.001



)= Ш

(*)

Если (*) сохраняет знак при любых и [1,n], то extr( есть

Обозначим (*) через aij ; ;

,

Z(2)

,

,

,

Z(2)

) Z(2) =

Необходимо и достаточно:

,

,

a11= ; a21= (**)

(**) - условие Сильвестра

Таким образом:

Если квадратичная форма положительна,т.е. все определители Сильвестра положительны, то в точке

Если определители Сильвестра нечетного порядка отрицательны, а четного порядка положительны, то в точке

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

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

1) Найти аналитически положение экстремума целевых функций.

Необходимое условие: существование экстрем. многих переменных

R(x)

Имеет в точке x0 экстремум если существует такая окрестность этой точки, взятая из ос-ти опр.функции(не понятно), что для всех точек этой окрестности справедливы следующие неравенства:

R() < R()

R() > R()

Необходимым условием существования экстремума функции многих переменных является равенство 0 частных производных первого порядка по всем переменным

Достаточное условие экстремума функций многих переменных:

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

и, удовлетворяющие системе ограничений

где - переменные;

- заданные функции n переменных;

- заданные числа.

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

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

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

Задачи нелинейного программирования возникают на практике, например, 1) когда затраты изменяются не пропорционально количеству закупленных или произведенных товаров,

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

Задача ставится следующий образом:



,

,

,

Теорема Куна-Таккера, необходимые условия существования условного экстремума с ограничениями в виде равенств и неравенств, целевая функция (Куна-Таккера) для условного экстремума.

Теорема К-Т:

Если функция при наличии функций типа равенств и неравенств достигает условного экстремума в т с, принадлежащей допустимой области, то существуют такие числам W0, W2, W3…

Мю u1,u2,u3… из которых хотя бы оно отлично от 0, такие что u1>0,u2>0 для которых выполняется соотношение

+

если соотношение 1 ужножить на пост число то смысл его не меняется поэтому вместо условия W0>0 можно воспользоваться W0=1

если ищем мин то w0<0 u1<0, u2<0…

все остальное остается в силе

первая и вторая прозводные

,



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

Задача на условный экстремум

При определении условного экстремума функции, когда требуется определить максимум (или минимум) функции F(х) при ограничивающих условиях:

gi(x) = bi, i = 1, ..., m,

т. е.

f(x)=max;

gi(x)=bi;

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

(3.6.2)

где лi - неопределенные множители Лагранжа.

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

,



Если ввести в рассмотрение векторы

соотношения (17-8) и (17-9) перепишутся как

grad Ц = grad F - л grad ц = 0; (3.6.6)

b - ц = 0,

где равенство нулю векторов понимается покомпонентно.

Рисунок 3.6.1 - Пояснение к задаче на условный экстремум

В случае n = 2 и m = 1 геометрическая задача об отыскании условного экстремума сводится (рис. 17-6) к отысканию точки касания А кривой ц = b к одной из кривых постоянного уровня f = const.

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



Формула Лагранжа:

Необходимые условия существования условного экстремума:

,

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

Выразим л из 1 и из 2



Оптимальное распределение материального потока на параллельно работающие аппараты.

А-продукт

ri(Vi)=XA XA=

CA=CA0

CA=0

XA C [0;1] Условием оптимального распределения сырья на параллельные аппараты будет яв-ся равенство частных производных или приращений.

Нужно распределить потоки сырья оптимальным способом

,

,

,

,

,

,

ц(X)=0 >



Составляем функцию Лагранжа:

Ц()=

; i=

,

,

,

,

,

Нелинейное программирование (НЛП), постановка задачи оптимизации, нормирование переменных.

Нормирование переменных:

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

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

Постановка задачи оптимизации

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=( ), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств , i=1,2,…,m (1) а переменные , т.е. компоненты вектора х, неотрицательны:

(2) Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если , то , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например , то их можно представить в виде пары неравенств , , сохранив тем самым типовую формулировку задачи.

6. НЛП. Классификация поисковых методов, глобальный оптимум, седловая точка

Методы нелинейного программирования:

1)Методы случайного поиска

2)Методы детерминированного поиска:

безградиентные (не требуют вычисления Ц.Ф.)

градиентные ( требуют вычесленияЦ.Ф.)

К безградиентному можно отнести методы:

Сканирования(`+': простота, глобальность; `-`: большое количество вычисления)

Поочередного изменения переменных (Гаусса - Зейделя)

Симплексный

К градиентным можно отнести методы:

Градиента

Релаксации

Наискорейшего спуска/подъема по целевой функции

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

Глобальный оптимум:

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

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

Седловые точки:

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

НЛП. Метод сканирования.

Метод сканирования заключается в последовательном просмотре значений R(x) в точках, принадлежащих допустимой области изменения переменных и нахождения среди них точек такой, в которой критерий оптимальности имеет наилучшее значение (max или min).

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

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

Достоинства метода:

Прост для программной реализации

Метод глобальный

Недостатки:

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

Существует множество модификаций данного метода. Алгоритмы отличаются методом локализации экстремума на одной из осей.



НЛП. Метод поочередного изменения переменных, описание алгоритма, критерий останова.

Движение к оптимуму происходит по каждой из осей до нахождения частного экстремума .

х (0) -стартовая точка.

На каждом шаге вычисляется значения R.

Если R>extr , значит шаг не удачен и возвращаемся в предыдущую точку .

Если R<extr , то двигаемся дальше.

Находим область extr?.

Первая ось , по которой осуществляется поиск extr , выбирается произвольно.

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

НЛП. Симплексный метод оптимизации.

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

Симплекс в n-мерном пространстве- выпуклый многогранник , имеющий (n+1) вершину и (n+1) грань.

n=dim x

Полезное св-во:

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

Рассмотрим качественно иллюстрацию алгоритма симплексного метода на примере ф-ии двух переменных.

R(S10)> R(S20)> R(S30)

R(S11)> R(S30)> R(S20)

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

Размеры симплекса уменьшают до тех пор, пока размеры симплекса не станут меньше или равны заданному ?(lij<=?) i?j

35. НЛП. Алгоритм симплексного метода (деформация симплекса).

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

Алгоритм: 1. Построение начального симплекса (задается начальная) точка, формируется вершина симплекса)

2. Определяется направление улучшения решения

3.Строится новый симплекс

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

36. НЛП. Критерий останова симплекса. Вычисление длины ребер симплекса

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

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

,

37. Ориентация исходного симплекса в пространстве переменных.

Для быстрой сходимости симплексметода необходимо соответствующим образом сориентировать симплекс в пространстве кодированных координат. Пусть кодирование координат заключается в области [-1;1].



Центр симплекса располагают в исходной точке поиска. Остальные вершины располагаются симметрично относительно координат оси .

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

x- кодированные координаты в диапазоне [-1;1]



В качестве начального симплекса в кодированных координатах следует исп-ть правильный симплекс, вершины и грани которого соответственно одинаково удалены от центра симплекса. В качестве критерия основана метода можно взять достижение длины всех ребер симплекса заданной точности локализации extr?. Размеры симплекса можно вычислить исходя из того, что в проекции направленного отрезка U, соединяющего S(i) -Sj, будет равен U=X(i)-X(j) в векторном виде.

38. НЛП. Метод случайного поиска, случайный вектор, выбор случайной точки в заданной области пространства переменных.

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

Введем понятие случайного вектора

Такой вектор (можно получить из последовательности случайных чисел (i=1,n) равномерно распределенных в диапазоне [-b; b], например, программой с использованием генератора случайных чисел.

Выразим компоненты следующим соотношением

,

=1

Дадим понятие выбора случайной точки в области n- мерного пространства.

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

,

Пусть тогда

39. НЛП. Метод случайных направлений. Алгоритм метода

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

Координаты новой точки рассчитываются в соответствии с алгоритмом:



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

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

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

Если при этом, после выполнения серии из S шагов, (S=2n) h=hmin, то поиск прекращается и найденная точка будет считаться оптимальной.

41. НЛП. Градиентные методы оптимизации. Понятие производной по направления, понятие градиента функции, идея градиентных методов.



,

Свойством , используемом при решении задач оптимизации , является то, что вектор-градиент направлен для нормали к линиям уровня R(x), что позволяет при движении по градиенту минимизировать расстояние от стартовой точки поиска до точки экстремума.

Графическая идея метода:

Если шаг неудачен, то следует уменьшить длину шага.

Точность локализации экстремума можно взять одинаковой по всем координатным осям

,

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

,

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

42. Метод градиента

Поиск оптимума осущ-ся последовательными шагами в направлении градиента, вычисляемого на каждом шаге.

Алгоритм поиска:

|=,

|=

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

Шаг регулируется, т.е яв-ся настроенным параметром и может зависеть от самой производной .

При различны: |

Если различны: |

Если ищем min то движение к оптимуму идет по направлению антиградиента. Частные производные имеют знак «-».

Если движение к max, то частные производные имеют знак «+».

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

Для max

Для min

Вблизи оптимума (extr):

- max

Иногда алгоритм поиска может быть модифицирован к виду:

=

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

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

Метод позволяет найти ext при минимальном объеме вычислений. Его целесообразно использовать, когда вектор R(x) меняется не резко. Вблизи экстремумов метод выражается в метод градиентов, т.к. шаг может быть уменьшен до заданной точности локализации

НЛП. Метод «штрафов»

Теорема Куна-Таккера:



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

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

При поиске условного минимума к функции добавляется некоторое положительное число - «штраф», а при поиске максимума «штраф» вычитается.

Формально шрафование происходит следующим образом:

Образуется некоторая функция

а - постоянная (настроечный параметр алгоритма)

С использованием функции образуется новая функция

- функция штрафов

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

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

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

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

Метод оврагов, алгоритм метода.

Ставится задача найти минимум для овражной функции.

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

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

Размещено на Allbest.ru

...