Оңтайландыру табыс әкелетін, шығындарды азайтатын немесе бизнес үдерісінің сәтсіздігін тудыратын параметрді орнататын ең жақсы нәтижені табуға көмектеседі.
Бұл процесс математикалық бағдарламалау деп те аталады. Ол оңтайландыру мәселесінің басшысы алға қойған мақсатқа жету үшін қажетті шектеулі ресурстарды бөлуді анықтау мәселесін шешеді. Барлық ықтимал нұсқалардың ішінен бақылаушы параметрді, мысалы, пайданы немесе шығынды барынша арттыратын (немесе азайтатын) нұсқаны тапқан жөн. Оңтайландыру үлгілері сондай-ақ нұсқаушы немесе нормативтік деп аталады, себебі олар бизнес үшін мүмкін болатын стратегияны табуға тырысады.
Даму тарихы
Сызықтық бағдарламалау (LP) барлық шектеулер сызықтық болатын оңтайландыру есептерінің класымен жұмыс істейді.
ЛП дамуының қысқаша тарихын ұсыну:
- 1762 жылы Лагранж теңдік шектеулері бар қарапайым оңтайландыру мәселелерін шешті.
- 1820 жылы Гаусс шешім қабылдадыжоюды қолданатын сызықтық теңдеулер жүйесі.
- 1866 жылы Вильгельм Джордан сәйкестік критерийі ретінде ең кіші квадрат қателерін табу әдісін жетілдірді. Бұл енді Гаусс-Джордан әдісі деп аталады.
- Сандық компьютер 1945 жылы пайда болды.
- Данциг 1947 жылы симплекс әдістерін ойлап тапты.
- 1968 жылы Фиакко мен МакКормик Inside Point әдісін енгізді.
- 1984 жылы Қармарқар өзінің инновациялық талдауын қосып, сызықтық бағдарламаларды шешу үшін ішкі әдісті қолданды.
LP шынайы мәселелерді модельдеу үшін де, кеңінен қолданылатын математикалық теория ретінде де өте қуатты құрал екенін дәлелдеді. Дегенмен, көптеген қызықты оңтайландыру мәселелері сызықты емес.
Бұл жағдайда не істеу керек? Мұндай есептерді зерттеу сызықтық алгебраның, көп өлшемді есептеулердің, сандық талдаудың және есептеу әдістерінің әртүрлі қоспасын қамтиды. Ғалымдар есептеу алгоритмдерін, соның ішінде сызықтық бағдарламалаудың ішкі нүктелік әдістерін, геометрияны, дөңес жиындар мен функцияларды талдауды және квадраттық бағдарламалау сияқты арнайы құрылымдық есептерді зерттеуді жасауда.
Сызықты емес оңтайландыру математикалық талдаудың іргелі түсінігін береді және инженерия, регрессиялық талдау, ресурстарды басқару, геофизикалық барлау және экономика сияқты әртүрлі салаларда кеңінен қолданылады.
Оңтайландыру мәселелерінің классификациясы
Маңызды қадамОңтайландыру процесі модельдерді жіктеу болып табылады, өйткені олардың шешу алгоритмдері белгілі бір түрге бейімделген.
1. Дискретті және үздіксіз оңтайландыру мәселелері. Кейбір үлгілер айнымалылар бүтін сандардың дискретті ішкі жиынынан мән алған жағдайда ғана мағыналы болады. Басқаларында кез келген нақты мәнді қабылдай алатын деректер бар. Оларды шешу әдетте оңайырақ. Алгоритмдердің жетілдірілуі компьютерлік технологияның жетістіктерімен үйлескенде сызықтық бағдарламалауды оңтайландыру мәселесінің көлемі мен күрделілігін күрт арттырды.
2. Шексіз және шектеулі оңтайландыру. Тағы бір маңызды айырмашылық - айнымалыларға ешқандай шектеулер жоқ тапсырмалар. Ол қарапайым бағалаушылардан деректер арасындағы күрделі қатынастарды модельдейтін теңдіктер мен теңсіздіктер жүйелеріне дейін кең ауқымды болуы мүмкін. Мұндай оңтайландыру есептерін функциялардың сипатына қарай қосымша жіктеуге болады (сызықтық және сызықтық емес, дөңес және тегіс, дифференциалданатын және дифференциалданбайтын).
3. Техникалық-экономикалық міндеттер. Олардың мақсаты - арнайы оңтайландыру мақсатынсыз модель шектеулерін қанағаттандыратын айнымалы мәндерді табу.
4. Қосымша тапсырмалар. Олар технология мен экономикада кеңінен қолданылады. Мақсат - толықтыру шарттарын қанағаттандыратын шешім табу. Тәжірибеде бірнеше мақсаты бар тапсырмалар көбінесе бір мақсатқа қайта тұжырымдалады.
5. Детерминистік және стохастикалық оңтайландыру. Детерминистік оңтайландыру деректерге арналған деп болжайдытапсырмалар толығымен дәл. Дегенмен, көптеген өзекті мәселелер бойынша олар бірқатар себептерге байланысты белгілі болмайды.
Біріншісі қарапайым өлшеу қателігімен байланысты. Екінші себеп неғұрлым іргелі. Бұл кейбір деректер болашақ туралы ақпаратты, мысалы, өнімге сұранысты немесе болашақ уақыт кезеңіндегі бағаны білдіретіндігінде жатыр. Стохастикалық оңтайландыру шарттарында оңтайландыру кезінде модельге белгісіздік кіреді.
Негізгі компоненттер
Мақсат функциясы - кішірейту немесе көбейту. Оңтайландыру есептерінің көптеген түрлерінің бір мақсаттық функциясы бар. Әйтпесе, оларды жұмыс істеу үшін жиі қайта құруға болады.
Осы ережеден екі ерекшелік:
1. Мақсатты іздеу тапсырмасы. Іскерлік қолданбалардың көпшілігінде менеджер модель шектеулерін қанағаттандыра отырып, белгілі бір мақсатқа қол жеткізгісі келеді. Пайдаланушы ерекше бір нәрсені оңтайландыруды қаламайды, сондықтан мақсаттық функцияны анықтаудың мағынасы жоқ. Бұл түрі әдетте қанағаттану мәселесі деп аталады.
2. Көптеген объективті қасиеттер. Көбінесе пайдаланушы бір уақытта бірнеше түрлі мақсаттарды оңтайландырғысы келеді. Олар әдетте сәйкес келмейді. Бір мақсат үшін оңтайландырылған айнымалылар басқалары үшін ең жақсысы болмауы мүмкін.
Компонент түрлері:
- Бақыланатын кіріс – мақсат функциясының мәніне әсер ететін шешім айнымалыларының жиынтығы. Өндірістік тапсырмада айнымалылар әртүрлі қолжетімді ресурстарды немесе қажетті жұмыс күшін бөлуді қамтуы мүмкінәрбір әрекет.
- Шектеулер – шешім қабылдау айнымалылары мен параметрлер арасындағы қатынастар. Өндіріс мәселесі үшін кез келген әрекетке көп уақыт жұмсаудың мағынасы жоқ, сондықтан барлық "уақытша" айнымалыларды шектеңіз.
- Мүмкін және оңтайлы шешімдер. Барлық шектеулер орындалатын айнымалылар үшін шешімнің мәні қанағаттандырылатын деп аталады. Көптеген алгоритмдер алдымен оны табады, содан кейін оны жақсартуға тырысады. Соңында, олар бір мүмкін болатын шешімнен екіншісіне өту үшін айнымалы мәндерді өзгертеді. Бұл процесс мақсат функциясы максималды немесе минимумға жеткенше қайталанады. Бұл нәтиже оңтайлы шешім деп аталады.
Келесі математикалық бағдарламалар үшін әзірленген оңтайландыру есептерінің алгоритмдері кеңінен қолданылады:
- Дөңес.
- Бөлінетін.
- Квадрат.
- Геометриялық.
Google сызықтық шешушілер
Сызықтық оңтайландыру немесе бағдарламалау – мәселені оңтайлы шешудің есептеу процесіне берілген атау. Ол көптеген ғылыми және инженерлік пәндерде пайда болатын сызықтық қатынастар жиынтығы ретінде модельденген.
Google сызықтық оңтайландыру мәселелерін шешудің үш әдісін ұсынады:
- Glop ашық бастапқы кітапханасы.
- Google Sheets үшін сызықтық оңтайландыру қондырмасы.
- Google Apps сценарийіндегі сызықтық оңтайландыру қызметі.
Glop Google жүйесіне енгізілгенсызықтық шешуші. Ол ашық көзде қол жетімді. Glop қолданбасына Glop үшін қаптама болып табылатын OR-Tools сызықтық шешуші орауыш арқылы қол жеткізе аласыз.
Google Sheets үшін сызықтық оңтайландыру модулі электрондық кестеге деректерді енгізу арқылы оңтайландыру мәселесінің сызықтық мәлімдемесін орындауға мүмкіндік береді.
Квадраттық бағдарламалау
Premium Solver платформасы 2000 шешім айнымалысына дейін LP және QP мәселелерін өңдеу шектеулері бар Simplex әдісінің кеңейтілген LP/Quadratic нұсқасын пайдаланады.
SQP ауқымды есептерге арналған шешуші квадраттық бағдарламалау (QP) есептерін шешу үшін сиректеу белсенді жиын әдісінің заманауи іске асырылуын пайдаланады. XPRESS Solver қозғалтқышы QP мәселелерін шешу үшін "Интерьер нүктесі" немесе Ньютон кедергісі әдісінің табиғи кеңейтімін пайдаланады.
MOSEK шешушісі ендірілген «Ішкі нүкте» және автоматты қосарлы әдістерді қолданады. Бұл әсіресе еркін байланысқан 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 шешушісі негізгі және қосарлы симплексті қамтиды, ол сонымен қатар сиректікті пайдаланатын және матрицаны жаңарту мен "рефакторизация" үшін кеңейтілген стратегияларды қолданатын әдіс. Ол шексіз көлемдегі мәселелерді шешеді, болдымиллиондаған шешім айнымалылары бар сызықтық бағдарламалау есептері бойынша сыналған.
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:=СУMPRODUCT (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 жылы Джордж Данциг зерттеген диета мәселесін келтіруге болады. Сұлы, шошқа еті, күнбағыс майы сияқты бірқатар шикізаттар ақуыз, май, А дәрумені сияқты қоректік заттармен және олардың килограмм бағасымен бірге беріледі. Мәселе шикізаттан бір немесе бірнеше түпкілікті өнімді олардың тағамдық құндылығының минималды және максималды шектеулерін сақтай отырып, ең аз шығынмен араластыру болып табылады.
Сызықтық оңтайландыру мәселесінің классикалық қолданбасы қажеттіліктер үшін маршруттауды анықтау болып табыладытелекоммуникациялар немесе көлік желілеріндегі трафик. Бұл ретте ағындар өткізу қабілеттілігі шарттарын бұзбай, барлық трафик талаптары орындалатындай етіп желі арқылы бағытталуы керек.
Математикалық теорияда сызықтық оңтайландыруды екі адамға арналған нөлдік қосынды ойындарында оңтайлы стратегияларды есептеу үшін пайдалануға болады. Бұл жағдайда әрбір қатысушы үшін ықтималдық үлестірімі есептеледі, бұл оның стратегияларының кездейсоқ араласу коэффициенті болып табылады.
Оңтайландырусыз әлемде сәтті бизнес-процесс мүмкін емес. Көптеген оңтайландыру алгоритмдері бар. Кейбір әдістер проблемалардың белгілі бір түрлеріне ғана жарамды. Олардың сипаттамаларын тани білу және сәйкес шешім әдісін таңдау маңызды.
