Оптималләштереү (математика)

**Оптималләштереү** (математикала, информатикала һәм тикшереү операцияларында) — һыҙыҡлы һәм / йәки һыҙыҡһыҙ тигеҙлектәр һәм/йәки тигеҙһеҙлектәр йыйылмаһы менән сикләнгән сикле үлсәмле векторлы арауыҡтың ҡайһы бер өлкәһендә маҡсатлы функцияның экстремумын (минимум йәки максимум) табыу мәсьәләһе.

Оптималләштереү мәсьәләләре теорияһын һәм ысулдарын ***математик программалау*** өйрәнә:

**Математик программалау** — математика өлкәһе, сикләүҙәр менән күп үлсәмле мәсьәләләр сисеүҙә һанлы ысулдар теорияһын эшләй.

## Оптималләштереү мәсьәләһе ҡуйылышы
Проектлау процесында, ғәҙәттә, объекттар параметрҙарының иң яҡшыларын, структураһын йәки ҡиммәттәрен билдәләү мәсьәләһе ҡуйыла. Бындай мәсьәләне оптималләштереү тип атайҙар. Әгәр оптималләштереү объекттың теге йәки был структураһы өсөн оптималь параметр ҡиммәттәрен хисаплау менән бәйле булһа, ул параметрик оптимизация тип атала. Оптималь структураны һайлау мәсьәләһе — структураны оптималләштереү булып тора.

Математик оптималләштереүҙең стандарт мәьәләһе ошо рәүешле билдәләнә. Χ күмәклеген формалаштырыусы χ элементтары араһында, бирелгән f (χ*) функцияһының минималь ҡиммәтен биреүсе χ* элементын табыу. Шуның өсөн, оптималләштереү мәсьәләләрен дөрөҫ ҡуйыу өсөн, биреү кәрәк.:

# Бирелгән күмәклек — \mathbb{X}=\{\vec{x}|\;g_i(\vec{x})\leq 0,\;i=1,\ldots,m\} \subset \mathbb{R}^n күмәклек;
# *Маҡсатлы функция* — f:\;\mathbb{X}\to\mathbb{R} сағылыш;
# *Эҙләү критерийҙары* (йәки max min).

Ул саҡта мәсьәлә сиселә f(x)\to \min_{\vec{x}\in\mathrm{X}} береһе тигәнде аңлата:

# Күрһәтергә, \mathbb{X}=\varnothing белдерә.
# Күрһәтергә, f(\vec{x}) маҡсатлы функция аҫтан сикләнгән түгел.
# Табыу \vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x}).
# Әгәр \nexists \vec{x}^*  , ул саҡта \inf_{\vec{x}\in\mathbb{X}}f(\vec{x}) табырға.

Әгәр ҙә минималь функция ҡабарынҡы булмаһа, йыш ҡына локаль минимумдар һәм максимумдар табыу менән сикләшә: x_0 нөктәләре тирә-яғының ҡайһы берҙәрендә шундайҙар f(x)\ge f(x_0) минимум һәм f(x)\le f(x_0) максимум өсөн.

Әгәр бирелгән күмәклек \mathbb{X}=\mathbb{R}^n икән, бындай мәсьәлә, *шартһыҙ оптималләштереү* , кире осраҡта — *шартлы оптималләштереү мәсьәлә тип атала.*

## ''Оптималләштереү'' ысулдарының классификацияһы
Оптималләштереүҙең дөйөм яҙмаһы улар класының күп төрлөлөгөн бирә. Ысулды һайлап алыу мәсьәлә класына (уны сисеү һөҙөмтәлелегенә) бәйле.

Мәсьәләләрҙе классификациялауҙы билдәләй: маҡсатлы функция һәм бирелгән өлкә (тигеҙһеҙлек һәм тигеҙлек системаһы йә ҡатмарлыраҡ алгоритм менән билдәләнә).

Оптималләштереү ысулдары оптималләштереү мәсьәләләренә ярашлы классификациялана:

* Локаль ысулдар: маҡсатлы функцияның ниндәйҙер локаль экстремумына ҡушыла. Унимодаль маҡсатлы функция осрағында, был экстремум берҙән-бер, һәм глобаль максимум/минимум буласаҡ.
* Глобаль ысулдар: күп экстремаль маҡсатлы функциялар менән эш итеүгә эйә. Глобаль эҙләнеүҙәрҙә төп бурыс булып маҡсатлы функцияның глобаль тәртибе тенденцияларын асыҡлау тора.

Хәҙерге эҙләү ысулдары өс ҙур төркөмгә бүленә:

# билдәләүсе (детерминированные);
# осраҡлы (стохастик);
# ҡатнаш (комбинированные).

Бирелгән күмәклек үлсәмлелеге критерийы буйынса оптималләштереү ысулдары оптималләштереүҙең бер үлсәмле ысулдарын һәм күп үлсәмле оптималләштереү ысулдарына бүленә.

Маҡсатлы функция төрөнә һәм бирелгән күмәклеккә ярашлы оптималләштереү мәсьәләләрен һәм уларҙы сисеү ысулдары түбәндәге кластарға бүленә:

* Оптималләштереү мәсьәләләре, уларҙа f(\vec{x}) маҡсатлы функция һәм g_i(\vec{x}),\; i=1,\ldots,m сикләүҙәр һыҙыҡлы функциялар булып тора, программалауҙың һыҙыҡлы ысулдары менән сиселә.
* Кире осраҡта һыҙыҡһыҙ прогаммалау мәсьәләһе һәм методтары ҡулланырға тура килә. Үҙ сиратында уларҙан ике айырым мәсьәлә сығарыла:
** әгәр f(\vec{x}) һәм g_i(\vec{x}),\;i=1,\ldots,m — ҡабарынҡы функциялар икән, бындай мәсьәлә *ҡабарынҡы программалау тип атала*;
** әгәр \mathbb{X}\subset \mathbb{Z} икән, *бөтөн һандар (дискрет) программалау мәсьәләһе менән эш ителә*.

Шымалыҡ талаптарына һәм маҡсатлы функцияла өлөшләтә сығарылмаларҙың булыуына ҡарап, уларҙы түбәндәгеләргә бүлергә мөмкин:

* Яҡынлашыу нөктәһендә маҡсатлы функцияны иҫәпләүҙе генә талап иткән туранан-тура ысулдар;
* беренсе тәртип ысулдары: функцияның беренсе өлөшләтә сығарылмаларын иҫәпләүҙе талап итә;
* икенсе тәртип ысулдары: икенсе өлөшләтә сығарылмаларҙы иҫәпләүҙе талап итә, йәғни маҡсатлы функцияның гессианы.

* аналитик метод (мәҫәлән,, Лагранждың ҡабатлашыусылар ысулы һәм Каруша — Кун — Таккер шарттары);
* һанлы ысулдар;
* график ысулдар.

X күмәклеге характерына ҡарап, программалауҙың математик мәсьәләләре түбәндәгесә классификациялана:

* дискрет программалау мәсьәләләре (йәки комбинаторлы оптимизациялау) — әгәр **X** сикһеҙ йәки иҫәпле күмәклек;
* бөтөн һандарҙы программалау мәсьәләләре— әгәр **X** бөтөн һандар күмәклектең аҫкүмәклеге булып торһа;
* һыҙыҡһыҙ программалау мәсьәләре — әгәр сикләү йәки маҡсатлы функция һыҙыҡһыҙ функцияларҙы алһа һәм **X** сикле үлсәмле вектор арауығы аҫкүмәклеге булып торһа.
* Әгәр ҙә бөтә сикләү һәм маҡсатлы функция һыҙыҡлы функцияны ғына алһа, был — һыҙыҡлы программалау мәсьәләһе.

Бынан тыш, математик программалау бүлектәренә параметрик программалау, программалау динамикаһы һәм стохастик программалау инә.

Математик программалау операцияларҙы тикшереүҙә оптималләштереү мәсьәләләрен сисеүҙә ҡулланыла.

Экстремумды табыу ысулы тулыһынса мәсьәлә класы менән билдәләнә. Ләкин математик модель алыр алдынан моделләштереүҙең 4 этабын башҡарырға кәрәк:

* Оптимизация системаһы сиктәрен билдәләү
** Оптималләштереү объектының тышҡы донъя менән оптималләштереү һөҙөмтәһенә ҙур йоғонто яһай алмаған бәйләнештәрен, йәки, дөрөҫөрәге, уларһыҙ сиселеше ябайлашҡандарын төшөрөп ҡалдырыла.
* Идара ителеүсе үҙгәреүсәндәрҙе һайлау
** Ҡайһы бер үҙгәреүсәндәрҙең (идара ителмәгән үҙгәреүсәндәрҙең) ҡиммәттәре «туңдырыла». Башҡалары ғәмәлдәге сиселештәр даирәһенән (идара ителеүсе үҙгәреүсәндәр) ниндәй ҙә булһа ҡиммәттәрҙе ҡабул итергә китә..
* Идара ителеүсе үҙгәреүсәндәрҙә сикләүҙәрҙе билдәләү
** … (тигеҙлек һәм/йәки тигеҙһеҙлек)
* Оптималләштереү һанлы һайлау критерийҙары (мәҫәлән,, һөҙөмтәлелек күрһәткесе)
** Маҡсатлы функцияһы төҙөлә

## Тарихы
Һыҙыҡлы программалау мәсьәләләре тигеҙһеҙлек кеүек сикләүҙәр булғанда функцияларҙың экстремумын табыу өсөн ентекләп өйрәнелгән тәүге мәсьәләләр була. 1820 йылда Фурье, ә һуңынан 1947 йылда Джордж Данциг маҡсатлы функцияны арттырыу йүнәлешендә күрше вертикаларҙы йүнәлешле эҙләү ысулын тәҡдим итә .

«Программалау» терминының булыуы беренсе тикшеренеүҙәр һәм һыҙыҡлы оптималләштереү проблемаларын ҡулланыу иҡтисад өлкәһендә булыуы менән аңлатыла, сөнки инглиз телендә «programming» һүҙе планлаштырыу, пландар йәки программалар төҙөүҙе аңлата. Терминология мәсьәләнең математик формулировкаһы менән уның иҡтисади интерпретацияһы (оптималь иҡтисади программаны өйрәнеү) араһындағы тығыҙ бәйләнеште сағылдырыуы тәбиғи. «Һыҙыҡлы программалау» термины Дж. Данциг 1949 йылда һыҙыҡлы сикләүҙәрҙә һыҙыҡлы функцияларҙы оптималләштереү менән бәйле теоретик һәм алгоритмик мәсьәләләрҙе өйрәнеү өсөн тәҡдим итә.

Шуға күрә «математик программалау» атамаһы мәсьәләләрҙе сисеүҙең маҡсаты оптималь эш итеү программаһын һайлау менән бәйле.

Һыҙыҡлы сикләүҙәр биргән күмәклек һыҙыҡлы функционаллеге менән билдәләнгән экстремаль мәсьәләләрен класын бүлеү 1930-се йылдарға тура килә, Һыҙыҡлы программалауҙың мәсьәләләрен тәүгеләрҙән булып дөйөм формала өйрәнәләр: Джон фон Нейман — математик һәм физик, матрица уйындарының төп теоремаһын иҫбатлаған һәм уның исемен йөрөткән иҡтисади моделде өйрәнеүсе, һәм Л. В. Канторович — совет академигы, Нобель премияһы лауреаты (1975),һыҙыҡлы программалауҙың бер нисә мәсьәләһен уйлап таба һәм 1939 йылда уларҙы сисеү ысулын тәҡдим итә.

1931 йылда венгр математигы Б. Эгервари математик ҡуйылышты ҡарай һәм һыҙыҡлы программалау мәсьәләһен сисә, уны — «һайлау проблемаһы» тип, ә сисеү ысулын — «венгр ысулы» тип атайҙар.

Л. В. Канторович, В. С. Немчинов, В. В. Новожилов, А. Л. Лури, А. Л. Брюдно, А. Г. Ганбегян, Д. Б. Юдин, Э. Г. Гольштейн һәм башҡа математиктар һәм иҡтисадсылар, һыҙыҡлы һәм һыҙыҡһыҙ программалауҙың математик теорияһын һәм уның төрлө иҡтисади мәсьәләләрен өйрәнеү ысулдарын артабан үҫешенә ҙур өлөш индерә.

Сит ил ғалимдарының күп кенә эштәре һыҙыҡлы программалау ысулдарына арналған. 1941 йылда Ф. Л. Хичкок транспорт мәсьәләһен ҡуя. Һыҙыҡлы программалау мәсьәләләрен сисеүҙең төп ысулы — симплекс-ысулы — 1949 йылдарҙа Дж. Данциг тарафынан нәшер ителә. Һыҙыҡлы һәм һыҙыҡһыҙ программалау ысулдары артабан Г. Кун, А. Таккер, Гасс (Gass Saul I), Чарнес (A. Charnes), Било (E. Beale M.) һ. б. эштәрендә үҫеш ала.

Һыҙыҡлы программалау менән бер үк ваҡытта һыҙыҡһыҙ прогаммалау мәсьәләләренә ҙур иғтибар бүленә. 1951 йылда Г. Кун һәм А. Таккерҙың эше баҫылып сыға, унда һыҙыҡлы булмаған программалау мәсьәләләрен сисеү өсөн кәрәкле һәм етерлек шарттар бирелә. Был эш артабанғы тикшеренеүҙәр өсөн нигеҙ булып хеҙмәт итә.

1955 йылдан квадрат программалауға арналған эштәр баҫыла. Ж. Б. Деннис, Ж. Б. Розен һәм Г. Зонтендейк һыҙыҡһыҙ программалау мәсьәләләрен сисеү өсөн градиент ысулдарын эшләй.

Хәҙерге ваҡытта компьютерҙарҙа математик программалау һәм мәсьәләлрен сисеү ысулдарын һөҙөмтәле ҡулланыу өсөн алгебраик моделләштереү телдәре эшләнгән, уларҙың вәкилдәре булып AMPL һәм LINGO тора.

## Шулай уҡ ҡарағыҙ
* Күп критерийлы оптималләштереү;
* Математик анализ;
* Скаляр ранжировка

## Иҫкәрмәләр

## Әҙәбиәт
* 
* 
* 
* 
* 
* 
* 
* 
* *Лотов&amp;nbsp;А.&amp;nbsp;В., Поспелова И. И.* Конспект лекций по теории и методам многокритериальной оптимизации.  Архивная копия от 21 января 2022 на Wayback Machine Учеб. пос. М., 2005. 127 с.
* 
* 
* 
* 
* *Сергеев Я. Д., Квасов Д. Е.* Диагональные методы глобальной оптимизации  Архивная копия от 26 октября 2017 на Wayback Machine. — М.: ФИЗМАТЛИТ, 2008. 341с.
* 
* 
* 
* 
* 
* 
* 

* 
* 
* 
* *Умнов А. Е., Умнов Е. А.* Параметрические задачи в математическом программировании Архивная копия от 9 июля 2021 на Wayback Machine (pdf)
* *Хохлюк&amp;nbsp;В.&amp;nbsp;И.* Параллельные алгоритмы целочисленной оптимизации.  Архивная копия от 18 января 2021 на Wayback Machine Курс лекций. Новосибирск, 2007.
* *Хохлюк В. И.* Методы дискретной оптимизации.  Архивная копия от 18 января 2021 на Wayback Machine Учебное пособие. НГУ, 2013. 154 с.

## Һылтанмалар
*