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

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

Оптималләштереү
Өйрәнеү объекты	оптималлаштәреү мәсьәләһе[d]
Ҡайҙа өйрәнелә	ғәмәли математика[d] һәм математик программалау[d]
Оптималләштереү Викимилектә

Параболоид графы z = f(x, y) = −(x2 + y2) + 4 функцияһы менән тасуирланған . Глобаль максимум от (x, y, z) = (0, 0, 4) күк төҫ менән билдәләнгән

Нельдер-Мид минималь оптималләштереү функцияларын табыу. Симплекслы түбәләр уларҙың мәғәнәһе буйынса тәртипкә килтерелә, шул уҡ ваҡытта 1 түбән (иң яҡшы) әһәмиәткә эйә

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

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

Оптималләштереү мәсьәләһе ҡуйылышы

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

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

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

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

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

Әгәр ҙә минималь функция ҡабарынҡы булмаһа, йыш ҡына локаль минимумдар һәм максимумдар табыу менән сикләшә: $x_{0}$ нөктәләре тирә-яғының ҡайһы берҙәрендә шундайҙар $f(x)\geq f(x_{0})$ минимум һәм $f(x)\leq f(x_{0})$ максимум өсөн.

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

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

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

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

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

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

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

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

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

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

• Оптималләштереү мәсьәләләре, уларҙа $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 тора.

Шулай уҡ ҡарағыҙ

• Күп критерийлы оптималләштереү;
• Математик анализ;
• Скаляр ранжировка

Әҙәбиәт

• Абакаров А. Ш., Сушков Ю. А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.
• Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высшая школа, 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Гирсанов И. В. Лекции по математической теории экстремальных задач. — М.; Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003. — 118 с. — ISBN 5-93972-272-5.
• Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.
• Карманов В. Г. Математическое программирование. — Изд-во физ.-мат. литературы, 2004.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
• Лотов А. В., Поспелова И. И. Конспект лекций по теории и методам многокритериальной оптимизации. 2022 йыл 21 ғинуар архивланған. Архивная копия от 21 января 2022 на Wayback Machine Учеб. пос. М., 2005. 127 с.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
• Плотников А. Д. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4.
• Растригин Л. А. Статистические методы поиска. — М., 1968.
• Сергеев Я. Д., Квасов Д. Е. Диагональные методы глобальной оптимизации Архивная копия от 26 октября 2017 на Wayback Machine. — М.: ФИЗМАТЛИТ, 2008. 341с.
• Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. — 8 изд. — М.: Вильямс, 2007. — С. 912. — ISBN 0-13-032374-8.
• Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981. — 560 с.
• Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. — 2-е изд., перераб. и доп.. — М.: Издательство «Наука», 1967.
• Минаев Ю. Н. Стабильность экономико-математических моделей оптимизации. — М.: Статистика, 1980.
• Моисеев Н. Н. Численные методы в теории оптимальных систем. — М.: Наука, 1971. — 424 с.
• Моисеев Н. Н. Элементы теории оптимальных систем. — М.: Наука, 1975. — 528 с.
• Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. — М.: Наука, 1978. — 352 с.

• Дегтярёв Ю. И. Методы оптимизации. — М.: Советское радио, 1980. — 272 с.
• Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. — М.: Мир, 1986. — 400 с.
• Романовский И. В. Алгоритмы решения экстремальных задач. — М.: Наука, 1977. — 352 с. — 16 000 экз.
• Умнов А. Е., Умнов Е. А. Параметрические задачи в математическом программировании Архивная копия от 9 июля 2021 на Wayback Machine (pdf)
• Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. 2021 йыл 18 ғинуар архивланған. Архивная копия от 18 января 2021 на Wayback Machine Курс лекций. Новосибирск, 2007.
• Хохлюк В. И. Методы дискретной оптимизации. 2021 йыл 18 ғинуар архивланған. Архивная копия от 18 января 2021 на Wayback Machine Учебное пособие. НГУ, 2013. 154 с.

Һылтанмалар

• Поляк Б. П. История математического программирования в СССР: анализ феномена // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения». — 2008. — Т. 1. — С. 2—20.