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

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

- yY - совокупность факторов, управляемых противодействующей стороной (Y - множество всех возможных решений ПС) (стратегии ПС).

- zZ - множество факторов, не контролируемых ни оперирующей, ни противодействующей стороной, значения которых заранее не известны. (Z - множество их всех возможных значений).

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

W = W(a, x, y, z)

В зависимости от вида цели, стоящей перед операцией можно различить два вида критериев эффективности: “качественные” и “количественные”.

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

В этом случае результат операции может быть оценен двумя числами:

1 - если цель операции достигнута;

0 - если цель операции не достигнута.

Если все факторы, влияющие на операцию детерминированы, то

0 - если результат достигнут;

W = W(a, x*, y*,) =

1 - если результат не достигнут.

Здесь x*, y* - фиксированные значения управляемых факторов.

Если же на ход операции оказывают влияние случайные факторы Z, то значение показателя W = W(a, x*, y*, z*) также будет случайно и использование его в качестве критерия эффективности в этом случае невозможно.

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

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

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

W = W(a, x*, y*).

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

W = MzR(a, x*, y*, z) = W(a, x*, y*),

При известном законе распределения f(z) случайных факторов Z значение W может быть найдено как

W(a, x*, y*) = R(a, x*, y*, z)f(z)dz

zZ

где f(z) - плотность распределения вероятностей случайных факторов Z.

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

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

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

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

W = PzR(a, x*, y*, z)Rзад

или иначе

W = f(z)dz = W(a, x*, y*).

(zZ: R(a, x*, y*,z)Rзад

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

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

Математические модели операций.

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

x, y W (a, x, y, z)

Z

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

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

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

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

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

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

Изучением таких операций занимается специальный раздел ИО - теория игр.

3. При разработке модель должна отвечать ряду общих требований

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

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

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

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

Разновидность задач ИО.

Все задачи ИО можно условно разбить на две категории: прямые и обратные.

Прямые задачи отвечают на вопрос “что будет, если в заданных условиях будет принято какое-то конкретное решение x*X. В частности - при заданном решении x* и заданных детерминированных значениях неуправляемых факторов а чему будет равен выбранный показатель эффективности операции W(a,x*) или ряд показателей при векторном критерии эффективности

W = W(a, x*).

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

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

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

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

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

При заданном комплексе условий а найти такое решение

x = x (xX),

которое обращает показатель эффективности операции W в максимум

W (x) = мах W(a, x)

xX

(см. Рисунок)

W (a, x) xX

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

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

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

С формальной точки зрения задачи поиска оптимального решения (в случае скалярного показателя W) относятся к классу задач математического программирования. Термин программирование от английского programming - составление плана или программы действий, здесь следует понимать в смысле “поиска наилучших планов”, а не в смысле разработки программного обеспечения для ЭВМ.

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

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

мax U = U(W),

- либо решения (одно из решений), отвечающее условию, что нельзя найти другое решение, позволяющее улучшить любой из показателей Wi (i = 1,к) не ухудшая при этом значения других показателей W (i) (хотя бы одно из них). Такие решения называются эффективными или паретовскими (xпXп ).

U = i Wi i 1 , i = 1 ( i = 1,k)

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

0 i 1 ,

i = 1 ( i = 1, k)

Поиск решения при выбранной функции свертки U(W) аналогичен поиску оптимального решения по скалярному критерию эффективности.

Во втором случае (не свернутый векторный критерий) поиск эффективных (паретовских) решений xпXп может быть осуществлен путем прямого перебора всех возможных решений xX (если оно конечно) с процедурой сравнения показателей

W(x).

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

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

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

Остановимся несколько подробнее на их постановке и методах решения.

4. Постановка и классификация задач математического программирования

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

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

найти значения переменных x1,…xn, доставляющие максимум (минимум) заданной скалярной функции f(x1,…xn; a)

при условиях gi (x1,…xn) ? (?, =) bi , где i=1,…,m.

Здесь a и bi - константы , определяемые из физических условий задачи.

Условия gi(x1,…xn) ограничивают возможность выбора значений переменных x1,…xn из множества всех возможных значений. Множество точек Х= { x1,…xn }, удовлетворяющих системе ограничений gi (i=1,…,m) есть область определения Xпоставленной задачи.

Функция f(x1,…xn; a) называется целевой функцией, которая может достигать экстремальных значений в одной или нескольких точках области X, которые предстоит найти (в конкретных задачах ИО в качестве целевой функции используют критерий эффективности, вычисляемый на основе модели операции).

Обычно вид функций f и g известен, константы?a и bi, вытекающие из параметров исследуемой системы и целей, стоящие перед ней - заданы, число переменных n и ограничений m - определено. Кроме того, при необходимости, специально оговариваются ограничения на не отрицательность и целочисленность переменных xi (i=1,…,n) исходя из их физической природы, которые также входят в систему ограничений на переменные.

Исходя из вышесказанного формальная запись задачи математического программирования имеет вид:

Параметр a входит в вид самой целевой функции и в дальнейшем может быть опущен.

В зависимости от вида целевой функции и ограничений можно выделить следующие классы задач:

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

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

3. Задачи выпуклого программирования. Это такие задачи, когда целевая функция f и множество возможных решений X - выпуклые.

Множество X называется выпуклым, если для любых двух точек x1,x2 X оно содержит в себе весь отрезок, их соединяющий:

Функция f(x) называется выпуклой (выпуклой вниз) на интервале [x1,x2], если для любой точки (внутри этого интервала выполняется условие f() ? .

Здесь

(1)

(2)

(3)

Если

f() ? ,

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

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

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

4. По ограничениям, накладываемым на переменные xi можно выделить задачи с непрерывными и дискретными переменными. Дискретность переменных нарушает выпуклость множества X и приводит, как правило, к необходимости либо полного, либо направленного перебора всех возможных решений xX, что значительно увеличивает трудоемкость решения задачи. При высокой размерности множества X точное решение задачи бывает практически невозможным за приемлемое время.

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

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

Рассмотрим более подробно ряд задач математического программирования и методов их решения.

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

(ЗЛП)

ЗЛП - задача математического программирования с линейной целевой функцией и линейными ограничениями. Является наиболее изученной задачей мат. программирования. Обычно на практике возникает при решении задач, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т.п. ,т.к в этих случаях “расходы” и “доходы” ,как правило линейно(или близко к линейным) связаны с количеством затраченных средств (Напр. Стоимость партии товаров линейно зависит от их количества, оплата перевозок пропорциональна весу перевезенных грузов (или расстоянию и весу) и т.п.

Прим:

Предприятие производит выпуск изделий двух наименований U и U.

На изготовление изделий необходимо сырье 3-х видов - S , S , S , причем на изготовление единицы продукции 1-го вида необходимо соответственно a=1 ,a=2 , a=2 единиц сырья, а на изготовление единицы продукции 2-го вида соответственно a=1 , a=5 , a=2 единиц сырья.

При реализации одного изделия 1-го вида приносит предприятию прибыль c=3 ед. ,а 2-го вида - c=4 ед.

Необходимо так спланировать производство , т.е. определить объем выпуска изделий каждого вида, чтобы в рамках имеющихся ресурсов каждого вида b=8 ед. , b=30 ед. , b=14 ед. соответственно , обеспечить максимальную прибыль (доход).

Формально задачу можно записать следующим образом:

( )

при ограничениях на ресурсы:

a+ ab (+8)

a+ ab (2+530)

a+ ab (2+14)

и на переменные 0 , 0;

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

Как видим в нашем случае целевая функция и ограничения линейны, т.е. мы получим ЗЛП.

В общей постановке ЗЛП состоит в отыскании значений n переменных

,,…, , доставляющих экстремум целевой функции

при ограничениях

и

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

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

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

Это обеспечивает поиск решения за ограниченное число шагов, исключая полный перебор всех крайних точек. (Напр. Симплекс-метод)

Существуют стандартные программы, реализующие методы решения ЗЛП.

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

при ограничениях

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

для введем и получим

и так для каждого неравенства.

Это приводит к увеличению размерности задачи, но позволяет использовать стандартные методы её решения.

(Лит-ра Вагнер Г. ,Основы исследования операций ,М.Мир,197?,т.1

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

Для случаев 2-х переменных ЗЛП удобно решать графически. Так для рассмотренного выше примера при заданных значениях параметров получим:

max

+ 8

2+530

2+14

, 0

c=3 ; c=4

a=1 ;a=1 ; b=8

a=2 ;a=5 ; b=30

a=2 ; a=2 ; b=14

Решение:

=

=

=

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

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

Существуют специальные методы решения целочисленных задач Л.П.

Напр. алгоритм Гомори, которые заключается с след-м:

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

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

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

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

Задачи и методы нелинейного программирования.

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

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

Напр.

Предприятие планирует выпуск изделий двух наименований U1 и U2. Объем выпуска изделий каждого наименования x1 и x2 в условных единицах (напр. в тыс. штук) и ограничивается сверху необходимым ресурсным обеспечением, задаваемыми ограничением:

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

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

При ограничениях:

;

Графически задача может быть представлена в следующем виде на плоскости X10X2

Здесь - область определения X. Линия уровня целевой функции - замкнутые кривые -окружности с центром в т. (2,1). Z(2,1) = 2.5

По мере удаления о т центра R=0 значения функции Z падают.

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

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

при ограничениях на переменные:

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

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

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

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

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

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

Найденные т.о. решения (если их несколько) проверяются на выполнение ограничений и неподходящие отбрасываются.

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

После того, как будут найдены все решения, удовлетворяющие системе ограничений ; они сравниваются между собой и среди них выбирается наилучшее (глобальный ext).

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

Метод множителей Лагранжа может быть распространен и на решение задачи с ограничениями в виде неравенств

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

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

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

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

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ.

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

Центральным вопросом численной оптимизации является вопрос выбора подходящего вычислительного алгоритма и анализа его сходимости.

Алгоритм поиска оптимального решения сходится, если он непосредственно вычисляет значение и соответственно за конечное число шагов, либо представляет его в виде ее предельного значения последовательности точек , , ,…

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

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

Методы возможных направлений.

Идея метода возможных направлений направлений проста: из начальной, допустимой по условиям задачи точки осуществляется переход к новой допустимой точке ,в которой значение целевой функции z лучше, чем в предыдущей. И так до тех пор, пока есть возможность улучшения z. Каждый шаг основан на выборе подходящего направления движения из очередной точки и оценке требуемой «длины шага» таким образом, что позволяет в итоге найти . Выбор очередного (k+1) - го значения производится по формуле:

= +,

где, -величина k-ого шага ; -единичный вектор ,определяющий направление перемещения.

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

Метод крутого восхождения(наискорейшего спуска).

В основе метода крутого восхождения лежат следующие правила:

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

=

2. Величина шага определяется

- либо из условия

,

- либо задается фиксировано;

- либо изменяется по определенному правилу (увеличивается, либо уменьшается)

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

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

В качестве критерия остановки (близости к ) обычно используют : либо величину шага (если , то останов), либо приращение целевой функции

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

5. Метод покоординатного подъема (спуска)

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

,

где -единичный вектор движения по i-ой координате .

Обычно находят решая задачу оптимизации :

Максимизировать по переменной xi целевую функцию f(x1,…,xn), где все

=, о?i, о=1,n. Ограничений на xi не накладывается.

После этого осуществляется движение по следующей переменной xi+1, фиксируя все остальные и так до последней - xn.

Затем происходит возврат к первой переменной x1 и процесс (цикл) повторяется снова.

Метод сходится в случае выпуклой целевой функции.

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

Если <е , то процесс заканчивается и принимается . (см. рис.)

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

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

Методы штрафных функций

Методы основаны на идее преобразования задачи оптимизации с ограничениями к задаче без ограничений.

Пусть необходимо найти максимум целевой функции

при ограничениях на переменные

, j=,

задающие область определения функции Х.

Введем дополнительную функцию

Теперь от задачи оптимизации с ограничениями можно перейти к задаче максимизации без ограничений. Максимизировать

Найденное в результате ее решения значение обязательно будет Х, а значение .

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

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

В методе внутренней точки штрафная функция задается таким образом, чтобы препятствовать выходу за пределы области Х (например ln(xд-х) )

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

(например -N* ln(х-xд)k )

Выбор вида штрафной функции оказывает существенное влияние на эффективность метода.

Метод ветвей и границ

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