Оптималдаштыруу киреше алып келүүчү, чыгашаларды азайтуучу же бизнес процессинин мүчүлүштүктөрүн жараткан параметрди койгон эң жакшы натыйжаны табууга жардам берет.
Бул процесс математикалык программалоо деп да аталат. Ал оптималдаштыруу маселеси жетекчиси тарабынан коюлган максатка жетүү үчүн зарыл болгон чектелген ресурстарды бөлүштүрүүнү аныктоо маселесин чечет. Бардык мүмкүн болгон варианттардын ичинен контролдоочу параметрди, мисалы, пайданы же чыгымды максималдаштырууну (же азайтканды) табуу максатка ылайык. Оптималдаштыруу моделдери ошондой эле көрсөтмөлүү же ченемдик деп аталат, анткени алар бизнес үчүн мүмкүн болгон стратегияны табууга умтулушат.
Өнүгүү таржымалы
Сызыктуу программалоо (LP) бардык чектөөлөр сызыктуу болгон оптималдаштыруу көйгөйлөрүнүн классы менен иштейт.
LP өнүгүүсүнүн кыскача тарыхын көрсөтүү:
- 1762-жылы Лагранж теңдик чектөөлөрү менен жөнөкөй оптималдаштыруу маселелерин чечкен.
- 1820-жылы Гаусс чечкенжок кылууну колдонгон сызыктуу теңдеме системасы.
- 1866-жылы Вильгельм Джордан ылайыктуу критерий катары эң кичине квадраттардын каталарын табуу ыкмасын өркүндөткөн. Бул азыр Гаусс-Джордан ыкмасы деп аталат.
- Санариптик компьютер 1945-жылы пайда болгон.
- Данциг симплекс ыкмаларын 1947-жылы ойлоп тапкан.
- 1968-жылы Fiacco жана McCormick Inside Point ыкмасын киргизишкен.
- 1984-жылы Кармаркар өзүнүн инновациялык анализин кошуп, сызыктуу программаларды чечүү үчүн ички ыкманы колдонгон.
LP реалдуу көйгөйлөрдү моделдөө үчүн да, кеңири колдонулуучу математикалык теория катары да өтө күчтүү курал экенин далилдеди. Бирок, көптөгөн кызыктуу оптималдаштыруу көйгөйлөрү сызыктуу эмес.
Мындай учурда эмне кылуу керек? Мындай маселелерди изилдөө сызыктуу алгебранын, көп өзгөрмөлүү эсептөөлөрдүн, сандык анализдин жана эсептөө ыкмаларынын ар түрдүү аралашмасын камтыйт. Окумуштуулар эсептөө алгоритмдерин, анын ичинде сызыктуу программалоо, геометрия, томпок көптүктөрдү жана функцияларды талдоо жана квадраттык программалоо сыяктуу атайын структураланган маселелерди изилдөө үчүн ички чекит ыкмаларын иштеп чыгууда.
Сызыктуу эмес оптималдаштыруу математикалык анализдин негизги түшүнүгүн камсыз кылат жана инженерия, регрессиялык анализ, ресурстарды башкаруу, геофизикалык чалгындоо жана экономика сыяктуу ар кандай тармактарда кеңири колдонулат.
Оптималдаштыруу көйгөйлөрүнүн классификациясы
Маанилүү кадамОптималдаштыруу процесси – бул моделдердин классификациясы, анткени алардын чечүү алгоритмдери белгилүү бир түргө ылайыкталган.
1. Дискреттик жана үзгүлтүксүз оптималдаштыруу көйгөйлөрү. Кээ бир моделдер өзгөрмөлөр бүтүн сандардын дискреттик топтомунан маанилерди алса гана мааниси бар. Башкалары кандайдыр бир реалдуу мааниге ээ боло турган маалыматтарды камтыйт. Алар, адатта, чечүү үчүн жеңил болот. Алгоритмдердин өркүндөтүлүшү компьютердик технологиянын жетишкендиктери менен айкалышып, сызыктуу программалоону оптималдаштыруу маселесинин көлөмүн жана татаалдыгын кескин жогорулатты.
2. Чексиз жана чектелген оптималдаштыруу. Дагы бир маанилүү айырма өзгөрмөлөр боюнча эч кандай чектөө жок милдеттери болуп саналат. Ал жөнөкөй баалоочулардан тартып, берилиштер ортосундагы татаал мамилелерди моделдөөчү теңдик жана теңсиздик системаларына чейин кеңири таралышы мүмкүн. Мындай оптималдаштыруу маселелерин функциялардын мүнөзүнө жараша дагы классификациялоого болот (сызыктуу жана сызыктуу эмес, томпок жана жылмакай, дифференциалдануучу жана дифференциалданбаган).
3. Техникалык-экономикалык милдеттер. Алардын максаты - оптималдаштыруунун конкреттүү максаты жок эле моделдин чектөөлөрүн канааттандырган өзгөрмө маанилерди табуу.
4. Толуктоочу милдеттер. Алар технологияда жана экономикада кеңири колдонулат. Максат - толуктоо шарттарын канааттандырган чечимди табуу. Практикада бир нече максаттары бар тапшырмалар көбүнчө бир максаттуу болуп кайра түзүлөт.
5. Детерминисттик жана стохастикалык оптималдаштыруу. Детерминисттик оптималдаштыруу маалыматтар үчүн деп болжолдойттапшырмалар толугу менен так. Бирок, көптөгөн актуалдуу маселелер боюнча алар бир нече себептерден улам белгилүү болушу мүмкүн эмес.
Биринчи жөнөкөй өлчөө катасы менен байланыштуу. Экинчи себеби көбүрөөк негиздүү. Бул кээ бир маалыматтар, мисалы, бир продуктка болгон суроо-талап же убакыттын келечектеги баасын, келечек жөнүндө маалыматты билдирет деп жатат. Стохастикалык оптималдаштыруу шарттарында оптималдаштырууда белгисиздик моделге кошулат.
Негизги компоненттер
Максат функциясы - бул кичирейтүү же чоңойтуу. Оптималдаштыруу көйгөйлөрүнүн көпчүлүк түрлөрү бир максаттуу функцияга ээ. Болбосо, алар көп учурда иштеши үчүн кайра түзүлүшү мүмкүн.
Бул эрежеден эки өзгөчөлүк:
1. Максаттуу издөө тапшырмасы. Көпчүлүк бизнес-тиркемелерде менеджер моделдин чектөөлөрүн канааттандыруу менен белгилүү бир максатка жетүүнү каалайт. Колдонуучу өзгөчө бир нерсени оптималдаштырууну каалабайт, ошондуктан объективдүү функцияны аныктоонун мааниси жок. Бул түрү адатта канааттандыруу көйгөйү деп аталат.
2. Көптөгөн объективдүү өзгөчөлүктөр. Көп учурда, колдонуучу бир эле учурда бир нече ар кандай максаттарды оптималдаштырууну каалайт. Алар, адатта, шайкеш келбейт. Бир максат үчүн оптималдаштырган өзгөрмөлөр башкалар үчүн эң жакшы болбошу мүмкүн.
Компоненттин түрлөрү:
- Контролдук киргизүү – бул максаттуу функциянын маанисине таасир этүүчү чечим өзгөрмөлөрүнүн жыйындысы. Өндүрүштүк тапшырмада өзгөрмөлөр ар кандай колдо болгон ресурстардын бөлүштүрүлүшүн же талап кылынган эмгекти камтышы мүмкүнар бир аракет.
- Чектөөлөр - бул чечимдин өзгөрмөлөрү менен параметрлеринин ортосундагы мамилелер. Өндүрүш маселеси үчүн кандайдыр бир ишке көп убакыт коротуунун мааниси жок, андыктан бардык "убактылуу" өзгөрмөлөрдү чектеңиз.
- Мүмкүн жана оптималдуу чечимдер. Бардык чектөөлөр канааттандырылган өзгөрмөлөр үчүн чечимдин мааниси канааттандырарлык деп аталат. Көпчүлүк алгоритмдер адегенде аны таап, андан кийин аны жакшыртууга аракет кылышат. Акыр-аягы, алар бир мүмкүн болгон чечимден экинчисине өтүү үчүн өзгөрмөлөрдү өзгөртүшөт. Бул процесс максат функциясы максималдуу же минимумга жеткенге чейин кайталанат. Бул жыйынтык оптималдуу чечим деп аталат.
Төмөнкү математикалык программалар үчүн иштелип чыккан оптималдаштыруу маселелеринин алгоритмдери кеңири колдонулат:
- Төмөнкү.
- Бөлүнүүчү.
- Квадраттык.
- Геометриялык.
Google сызыктуу чечүүчүлөрү
Сызыктуу оптималдаштыруу же программалоо - бул маселени оптималдуу чечүүнүн эсептөө процессине берилген аталыш. Ал көптөгөн илимий жана инженердик дисциплиналарда пайда болгон сызыктуу мамилелердин жыйындысы катары моделделген.
Google сызыктуу оптималдаштыруу маселелерин чечүүнүн үч жолун сунуштайт:
- Glop ачык булак китепканасы.
- Google Sheets үчүн сызыктуу оптималдаштыруу кошумчасы.
- Google Apps Скриптиндеги сызыктуу оптималдаштыруу кызматы.
Glop Google'га орнотулгансызыктуу чечүүчү. Бул ачык булакта жеткиликтүү. Glop'ту OR-Tools сызыктуу чечүүчү оромосу аркылуу колдоно аласыз, бул Glop үчүн орогуч.
Google Sheets үчүн сызыктуу оптималдаштыруу модулу электрондук жадыбалга маалыматтарды киргизүү менен оптималдаштыруу маселесинин сызыктуу билдирүүсүн аткарууга мүмкүндүк берет.
Квадраттык программалоо
Premium Solver платформасы Simplex ыкмасынын кеңейтилген LP/Quadratic версиясын колдонот, LP жана QP көйгөйлөрүн иштетүү чектери 2000 чечим өзгөрмөсүнө чейин.
SQP Чечимдүү масштабдуу маселелер үчүн квадраттык программалоо (QP) маселелерин чечүү үчүн сейректик менен активдүү топтом ыкмасын заманбап ишке ашырууну колдонот. XPRESS Solver кыймылдаткычы QP көйгөйлөрүн чечүү үчүн "Интерьер чекитинин" табигый кеңейтүүсүн же Newton Barrier ыкмасын колдонот.
MOSEK Solver камтылган "Inside Point" жана авто-кош ыкмаларды колдонот. Бул өзгөчө QP көйгөйлөрү үчүн натыйжалуу. Ал ошондой эле Масштабдык квадраттык чектөө (QCP) жана Экинчи тартиптеги конус программалоо (SOCP) маселелерин чече алат.
Көп операциялык эсептөөлөр
Алар Microsoft Office функцияларын колдонуу менен ийгиликтүү колдонулат, мисалы, Excelде оптималдаштыруу маселелерин чечүүдө.
Жогорудагы таблицада символдор:
- K1 - K6 - товарларды бериши керек болгон кардарлар.
- S1 - S6 бул үчүн курула турган потенциалдуу өндүрүш сайттары. Түзүүгө болот1, 2, 3, 4, 5 же бардык 6 жер.
I тилкеде тизмеленген ар бир объект үчүн туруктуу чыгымдар бар (Оңдоо).
Эгер жайгашкан жер эч нерсени өзгөртпөсө, ал эсептелбейт. Анда эч кандай туруктуу чыгымдар болбойт.
Эң төмөн бааны алуу үчүн потенциалдуу жерлерди аныктаңыз.
Бул шарттарда жайгашкан жер же белгиленет же жок. Бул эки абал: "ЧЫН - ЖАЛГАН" же "1 - 0". Алты жер үчүн алты штат бар, мисалы, 000001 алтынчыга гана коюлган, 111111 бардыгына коюлган.
Экилик санауу системасында 000001 (1)ден 111111ге (63) чейин так 63 түрдүү вариант бар.
L2-L64 эми {=КӨП ОПЕРАЦИЯ (K1)} окушу керек, бул бардык альтернативалуу чечимдердин натыйжалары. Анда минималдуу маани=Мин (L) жана тиешелүү альтернатива - INDEX (K).
CPLEX бүтүн программалоо
Кээде сызыктуу мамиле бизнес көйгөйүнүн өзөгүн түшүнүү үчүн жетишсиз. Бул, өзгөчө, чечимдер дискреттик тандоолорду камтыса, мисалы, белгилүү бир жерде кампа ачуу же ачпоо сыяктуу. Мындай учурларда, бүтүн программалоо колдонулушу керек.
Эгер маселе дискреттик жана үзгүлтүксүз тандоолорду камтыса, бул аралаш бүтүн программа. Анда сызыктуу, томпок квадраттык маселелер жана ошол эле экинчи тартиптеги чектөөлөр болушу мүмкүн.
Бүтүн программалар сызыктуу программаларга караганда алда канча татаал, бирок аларда маанилүү бизнес колдонмолору бар. Программалык камсыздооCPLEX программасы бүтүн сандарды чечүү үчүн татаал математикалык ыкмаларды колдонот. Анын ыкмалары оптималдуу чечимдин мааниси боюнча чектерди эсептөө үчүн сызыктуу же квадраттык программалык релаксацияларды колдонуу менен дискреттик өзгөрмөлөрдүн мүмкүн болгон комбинацияларын системалуу түрдө издөөнү камтыйт.
Алар ошондой эле чектөөлөрдү эсептөө үчүн LP жана башка оптималдаштыруу маселелерин чечүү ыкмаларын колдонушат.
Стандарттуу Microsoft Excel чечүүчү
Бул технология LP көйгөйлөрүн чечүү үчүн негизги Simplex ыкмасын негизги ишке ашырууну колдонот. Ал 200 өзгөрмөлөр менен чектелген. "Премиум чечүүчү" өзгөрмөлөр үчүн эки тараптуу чектери менен жакшыртылган негизги симплекс ыкмасын колдонот. Premium Solver платформасы 2000ге чейин чечим өзгөрмөлөрү менен оптималдаштыруу маселесин чечүү үчүн LP/Quadratic Simplex Solver'тин кеңейтилген версиясын колдонот.
Premium Solver платформасы үчүн чоң масштабдагы LP жөнөкөй жана кош симплекс ыкмасын заманбап ишке ашырууну колдонот, ал убакытты жана эстутумду үнөмдөө үчүн LP моделиндеги сейректикти, жаңыртуунун өркүндөтүлгөн стратегияларын жана рефакторинг матрицалар, көп жана жарым-жартылай баа жана ротациялар, жана деградацияны жеңүү үчүн. Бул кыймылдаткыч үч версияда жеткиликтүү (8 000, 32 000 же чексиз өзгөрмөлөрдү жана чектөөлөрдү иштетүүгө жөндөмдүү).
MOSEK Solver баштапкы жана кош симплексти камтыйт, бул ыкма да сейректиктен пайдаланып, матрицаны жаңыртуу жана "рефакторизация" үчүн өркүндөтүлгөн стратегияларды колдонот. Бул чексиз өлчөмдөгү маселелерди чечет, болгонмиллиондогон чечим өзгөрмөлөрү менен сызыктуу программалоо маселелери боюнча сыналган.
EXCEL'де этап-этабы менен мисал
Excelде оптималдаштыруу маселесинин моделин аныктоо үчүн төмөнкү кадамдарды аткарыңыз:
- Маселе боюнча берилиштерди логикалык түрдө электрондук жадыбалда иреттеңиз.
- Ар бир өзгөрмөнү сактоо үчүн уячаны тандаңыз.
- Оптималдаштыруу маселесинин максаттуу математикалык моделин эсептөө үчүн формуланы клеткада түзүңүз.
- Ар бир чектөөнүн сол тарабын эсептөө үчүн формулаларды түзүңүз.
- Чечүүчүгө чечим өзгөрмөлөрү, максаттар, чектөөлөр жана ал параметрлер боюнча каалаган чектер жөнүндө айтып берүү үчүн Excelдеги диалогдорду колдонуңуз.
- Оптималдуу чечимди табуу үчүн "Чечүүчүнү" иштетиңиз.
- Excel барагын түзүңүз.
- Максат функциясы жана чектөө формуласы эсептелген Excel программасында маселенин берилиштерин уюштуруңуз.
Жогорудагы таблицада B4, C4, D4 жана E4 уячалары X 1, X 2, X 3 жана X 4 чечим өзгөрмөлөрүн көрсөтүү үчүн сакталган. Чечимдин мисалдары:
- Өнүмдүн аралашмасынын модели (ар бир продукт үчүн $450, $1150, $800 жана $400 пайда) тиешелүүлүгүнө жараша B5, C5, D5 жана E5 уячаларына киргизилди. Бул максатты F5=B5B4 + C5C4 + D5D4 + E5E4 же F5 ичинде эсептөөгө мүмкүндүк берет:=SUMPRODUCT (B5: E5, B4: E4).
- B8ге продуктунун ар бир түрүн өндүрүү үчүн зарыл болгон ресурстардын көлөмүн киргизиңиз.
- F8 формуласы:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Муну көчүрүүF9дагы формула. $B$4:$E$4 ичиндеги доллар белгилери бул уяча диапазону туруктуу экенин көрсөтүп турат.
- G8ге оң жактагы чектөөлөрдүн маанилерине туура келген ар бир түрдөгү ресурстардын жеткиликтүү көлөмүн киргизиңиз. Бул аларды төмөнкүдөй билдирүүгө мүмкүндүк берет: F11<=G8: G11.
- Бул төрт чекке барабар F8<=G8, F9 <=G9, F10 <=G10 жана F11=0
Методдун практикалык колдонулуш тармактары
Сызыктуу оптималдаштыруу оптималдаштыруу маселесине мисал катары көптөгөн практикалык колдонмолорго ээ:
Компания белгилүү салым маржасы менен бир нече продукция жасай алат. Ар бир буюмдун бирдигин өндүрүү белгилүү өлчөмдөгү чектелген ресурстарды талап кылат. Милдет - ресурстук чектөөлөрдү бузбастан компаниянын кирешеси максималдуу болушу үчүн ар бир продукциянын канча көлөмүн өндүрүү керек экендигин аныктоо үчүн өндүрүш программасын түзүү.
Аралаштыруу көйгөйлөрү ингредиенттерди акыркы продуктуга айкалыштыруу менен байланышкан оптималдаштыруу маселелерин чечүү. Буга мисал катары 1947-жылы Джордж Данциг тарабынан изилденген диета маселеси болуп саналат. Бир катар сырьёлор, мисалы, сулу, чочконун эти жана күн карама майы, алардын азыктык курамы, мисалы, белок, май, А витамини жана килограммына баа берилет. Маселе – чийки заттан бир же бир нече акыркы продуктуларды мүмкүн болгон эң аз чыгым менен аралаштыруу жана алардын азыктык баалуулугунун минималдуу жана максималдуу чегин сактоо.
Сызыктуу оптималдаштыруу маселесинин классикалык колдонмосу – муктаждыктар үчүн маршрутту аныктоотелекоммуникация же транспорт тармактарындагы трафик. Ошол эле учурда агым өткөрүү жөндөмдүүлүгүнүн шарттарын бузбастан, бардык трафик талаптары аткарылгандай кылып тармак аркылуу өткөрүлүшү керек.
Математикалык теорияда сызыктуу оптималдаштыруу эки адам үчүн нөл суммадагы оюндарда оптималдуу стратегияларды эсептөө үчүн колдонулушу мүмкүн. Бул учурда, ар бир катышуучу үчүн ыктымалдык бөлүштүрүү эсептелет, бул анын стратегияларын кокус аралаштыруу коэффициенти болуп саналат.
Дүйнөдөгү эч бир ийгиликтүү бизнес процесси оптималдаштыруусуз мүмкүн эмес. Көптөгөн оптималдаштыруу алгоритмдери бар. Кээ бир ыкмалар көйгөйлөрдүн айрым түрлөрү үчүн гана ылайыктуу. Алардын өзгөчөлүктөрүн таанып, туура чечүү ыкмасын тандап алуу маанилүү.
