ოპტიმიზაცია გეხმარებათ იპოვოთ საუკეთესო შედეგი, რომელიც მოაქვს მოგებას, ამცირებს ხარჯებს ან ადგენს პარამეტრს, რომელიც იწვევს ბიზნეს პროცესის წარუმატებლობას.
ამ პროცესს მათემატიკური პროგრამირებასაც უწოდებენ. ის წყვეტს ოპტიმიზაციის პრობლემის ხელმძღვანელის მიერ დასახული მიზნის მისაღწევად საჭირო შეზღუდული რესურსების განაწილების განსაზღვრის პრობლემას. ყველა შესაძლო ვარიანტიდან სასურველია იპოვოთ ის, რომელიც მაქსიმალურად გაზრდის (ან ამცირებს) საკონტროლო პარამეტრს, მაგალითად, მოგებას ან ღირებულებას. ოპტიმიზაციის მოდელებს ასევე უწოდებენ ინსტრუქციულ ან ნორმატიულს, რადგან ისინი ცდილობენ იპოვონ ბიზნესისთვის ხელმისაწვდომი სტრატეგია.
განვითარების ისტორია
წრფივი პროგრამირება (LP) მუშაობს ოპტიმიზაციის პრობლემების კლასით, სადაც ყველა შეზღუდვა წრფივია.
წარმოგიდგენთ LP-ის განვითარების მოკლე ისტორიას:
- 1762 წელს ლაგრანჟმა გადაჭრა მარტივი ოპტიმიზაციის პრობლემები თანასწორობის შეზღუდვებით.
- 1820 წელს გაუსმა გადაწყვიტაგანტოლებათა წრფივი სისტემა ელიმინაციის გამოყენებით.
- 1866 წელს ვილჰელმ ჯორდანმა დაასრულა უმცირესი კვადრატების შეცდომების პოვნის მეთოდი, როგორც შესაბამისი კრიტერიუმი. ახლა ამას გაუს-იორდანიის მეთოდს უწოდებენ.
- ციფრული კომპიუტერი გამოჩნდა 1945 წელს.
- დანციგმა გამოიგონა სიმპლექსის მეთოდები 1947 წელს.
- 1968 წელს ფიაკომ და მაკკორმიკმა შემოიღეს Inside Point მეთოდი.
- 1984 წელს კარმარკარმა გამოიყენა ინტერიერის მეთოდი ხაზოვანი პროგრამების გადასაჭრელად და დაამატა თავისი ინოვაციური ანალიზი.
LP დადასტურდა, რომ არის უაღრესად ძლიერი ინსტრუმენტი, როგორც რეალური პრობლემების მოდელირებისთვის, ასევე, როგორც ფართოდ გამოყენებული მათემატიკური თეორია. თუმცა, ბევრი საინტერესო ოპტიმიზაციის პრობლემა არაწრფივია.
რა უნდა გავაკეთოთ ამ შემთხვევაში? ასეთი პრობლემების შესწავლა მოიცავს წრფივი ალგებრის, მრავალვარიანტული გამოთვლების, რიცხვითი ანალიზისა და გამოთვლითი მეთოდების მრავალფეროვან ნარევს. მეცნიერები ავითარებენ გამოთვლით ალგორითმებს, მათ შორის წრფივი პროგრამირების შიდა წერტილის მეთოდებს, გეომეტრიას, ამოზნექილი სიმრავლეების და ფუნქციების ანალიზს და სპეციალურად სტრუქტურირებული ამოცანების შესწავლას, როგორიცაა კვადრატული პროგრამირება..
არაწრფივი ოპტიმიზაცია უზრუნველყოფს მათემატიკური ანალიზის ფუნდამენტურ გაგებას და ფართოდ გამოიყენება სხვადასხვა სფეროში, როგორიცაა ინჟინერია, რეგრესიული ანალიზი, რესურსების მართვა, გეოფიზიკური კვლევა და ეკონომიკა.
ოპტიმიზაციის პრობლემების კლასიფიკაცია
მნიშვნელოვანი ნაბიჯიოპტიმიზაციის პროცესი არის მოდელების კლასიფიკაცია, რადგან მათი გადაწყვეტის ალგორითმები ადაპტირებულია კონკრეტულ ტიპზე.
1. დისკრეტული და უწყვეტი ოპტიმიზაციის პრობლემები. ზოგიერთ მოდელს აქვს აზრი მხოლოდ იმ შემთხვევაში, თუ ცვლადები იღებენ მნიშვნელობებს მთელი რიცხვების დისკრეტული ქვეჯგუფიდან. სხვები შეიცავს მონაცემებს, რომლებსაც შეუძლიათ მიიღონ ნებისმიერი რეალური მნიშვნელობა. როგორც წესი, მათი გადაჭრა უფრო ადვილია. ალგორითმების გაუმჯობესებამ, კომპიუტერული ტექნოლოგიების მიღწევებთან ერთად, მკვეთრად გაზარდა ხაზოვანი პროგრამირების ოპტიმიზაციის პრობლემის ზომა და სირთულე.
2. შეუზღუდავი და შეზღუდული ოპტიმიზაცია. კიდევ ერთი მნიშვნელოვანი განსხვავება არის ამოცანები, სადაც არ არის შეზღუდვა ცვლადებზე. ის შეიძლება ფართოდ განსხვავდებოდეს მარტივი შემფასებელიდან დაწყებული თანასწორობისა და უთანასწორობის სისტემებამდე, რომელიც აყალიბებს მონაცემებს შორის კომპლექსურ ურთიერთობებს. ოპტიმიზაციის ასეთი ამოცანები შეიძლება შემდგომ კლასიფიცირდეს ფუნქციების ბუნების მიხედვით (წრფივი და არაწრფივი, ამოზნექილი და გლუვი, დიფერენცირებადი და არადიფერენცირებადი).
3. მიზანშეწონილობის ამოცანები. მათი მიზანია იპოვონ ცვლადი მნიშვნელობები, რომლებიც აკმაყოფილებს მოდელის შეზღუდვებს რაიმე კონკრეტული ოპტიმიზაციის მიზნის გარეშე.
4. კომპლემენტარობის ამოცანები. ისინი ფართოდ გამოიყენება ტექნოლოგიასა და ეკონომიკაში. მიზანია იპოვოთ გამოსავალი, რომელიც დააკმაყოფილებს კომპლემენტარობის პირობებს. პრაქტიკაში, რამდენიმე მიზნის მქონე ამოცანები ხშირად გადაფორმებულია ერთ მიზნად.
5. დეტერმინისტული სტოქასტური ოპტიმიზაციის წინააღმდეგ. დეტერმინისტული ოპტიმიზაცია ვარაუდობს, რომ მონაცემებიდავალებები სრულიად ზუსტია. თუმცა, ბევრ აქტუალურ საკითხზე მათი ცნობილი არაერთი მიზეზის გამო შეუძლებელია.
პირველი დაკავშირებულია გაზომვის მარტივ შეცდომასთან. მეორე მიზეზი უფრო ფუნდამენტურია. ის მდგომარეობს იმაში, რომ ზოგიერთი მონაცემი წარმოადგენს ინფორმაციას მომავლის შესახებ, მაგალითად, მოთხოვნა პროდუქტზე ან ფასი მომავალი პერიოდისთვის. სტოქასტური ოპტიმიზაციის პირობებში ოპტიმიზაციისას, გაურკვევლობა შედის მოდელში.
მთავარი კომპონენტები
მიზნობრივი ფუნქცია არის ის, რომელიც უნდა იყოს მინიმუმამდე ან მაქსიმუმამდე. ოპტიმიზაციის პრობლემების უმეტესობას აქვს ერთი ობიექტური ფუნქცია. თუ არა, ხშირად შესაძლებელია მათი ხელახალი ფორმულირება იმისთვის, რომ იმუშაოს.
ორი გამონაკლისი ამ წესიდან:
1. სამიზნე საძიებო დავალება. უმეტეს ბიზნეს აპლიკაციებში, მენეჯერს სურს მიაღწიოს კონკრეტულ მიზანს მოდელის შეზღუდვების დაკმაყოფილების დროს. მომხმარებელს არ სურს რაიმეს ოპტიმიზაცია, ამიტომ აზრი არ აქვს ობიექტური ფუნქციის განსაზღვრას. ამ ტიპს ჩვეულებრივ მოიხსენიებენ, როგორც დაკმაყოფილების პრობლემას.
2. ბევრი ობიექტური თვისება. ხშირად, მომხმარებელს სურს ერთდროულად რამდენიმე განსხვავებული მიზნის ოპტიმიზაცია. ისინი, როგორც წესი, შეუთავსებელია. ცვლადები, რომლებიც ოპტიმიზებულია ერთი მიზნისთვის, შეიძლება არ იყოს საუკეთესო სხვებისთვის.
კომპონენტის ტიპები:
- კონტროლირებადი შეყვანა არის გადაწყვეტილების ცვლადების ნაკრები, რომლებიც გავლენას ახდენენ ობიექტური ფუნქციის მნიშვნელობაზე. წარმოების ამოცანაში ცვლადები შეიძლება მოიცავდეს სხვადასხვა ხელმისაწვდომი რესურსების განაწილებას ან საჭირო შრომასთითოეული მოქმედება.
- შეზღუდვები არის ურთიერთობა გადაწყვეტილების ცვლადებსა და პარამეტრებს შორის. წარმოების პრობლემის შემთხვევაში, აზრი არ აქვს დიდი დროის დახარჯვას რაიმე აქტივობაზე, ამიტომ შეზღუდეთ ყველა „დროებითი“ცვლადი.
- შესაძლო და ოპტიმალური გადაწყვეტილებები. ცვლადების გადაწყვეტილების მნიშვნელობა, რომლის მიხედვითაც დაკმაყოფილებულია ყველა შეზღუდვა, ეწოდება დამაკმაყოფილებელი. ალგორითმების უმეტესობა ჯერ პოულობს მას, შემდეგ კი ცდილობს გააუმჯობესოს. საბოლოოდ, ისინი ცვლიან ცვლადებს, რათა გადავიდნენ ერთი შესაძლებელი გადაწყვეტილებიდან მეორეზე. ეს პროცესი მეორდება მანამ, სანამ ობიექტური ფუნქცია არ მიაღწევს მაქსიმუმს ან მინიმუმს. ამ შედეგს ეწოდება ოპტიმალური გადაწყვეტა.
ფართოდ გამოიყენება შემდეგი მათემატიკური პროგრამებისთვის შემუშავებული ოპტიმიზაციის ამოცანების ალგორითმები:
- ამოზნექილი.
- გამყოფი.
- კვადრატული.
- გეომეტრიული.
Google Linear Solvers
წრფივი ოპტიმიზაცია ან პროგრამირება არის პრობლემის ოპტიმალურად გადაჭრის გამოთვლითი პროცესის სახელი. ის მოდელირებულია, როგორც წრფივი ურთიერთობების ერთობლიობა, რომელიც წარმოიქმნება მრავალ სამეცნიერო და საინჟინრო დისციპლინაში.
Google გთავაზობთ სამ გზას წრფივი ოპტიმიზაციის პრობლემების გადასაჭრელად:
- Glop ღია კოდის ბიბლიოთეკა.
- ხაზოვანი ოპტიმიზაციის დანამატი Google Sheets-ისთვის.
- ხაზოვანი ოპტიმიზაციის სერვისი Google Apps Script-ში.
Glop ჩაშენებულია Google-შიხაზოვანი ამომხსნელი. ის ხელმისაწვდომია ღია კოდით. Glop-ზე წვდომა შეგიძლიათ OR-Tools წრფივი ამოხსნის შეფუთვით, რომელიც არის Glop-ის შეფუთვა.
წრფივი ოპტიმიზაციის მოდული Google Sheets-ისთვის გაძლევთ საშუალებას შეასრულოთ ოპტიმიზაციის პრობლემის ხაზოვანი განცხადება ელცხრილში მონაცემების შეყვანით.
კვადრატული პროგრამირება
Premium Solver პლატფორმა იყენებს Simplex მეთოდის გაფართოებულ LP/კვადრატულ ვერსიას LP და QP პრობლემების დამუშავების ლიმიტებით 2000-მდე გადაწყვეტილების ცვლადი.
SQP ამომხსნელი ფართომასშტაბიანი პრობლემებისთვის იყენებს აქტიური კომპლექტის მეთოდის თანამედროვე დანერგვას სპარსელობით კვადრატული პროგრამირების (QP) ამოცანების გადასაჭრელად. XPRESS Solver ძრავა იყენებს "შიდა წერტილის" ან ნიუტონის ბარიერის მეთოდის ბუნებრივ გაფართოებას QP პრობლემების გადასაჭრელად.
MOSEK Solver იყენებს ჩაშენებულ "Inside Point" და ავტომატურ ორმაგ მეთოდებს. ეს განსაკუთრებით ეფექტურია თავისუფლად დაწყვილებული QP პრობლემებისთვის. მას ასევე შეუძლია გადაჭრას მასშტაბის კვადრატული შეზღუდვა (QCP) და მეორე რიგის კონუსური პროგრამირების (SOCP) პრობლემები.
მრავალოპერაციული გამოთვლები
ისინი საკმაოდ წარმატებით გამოიყენება Microsoft Office-ის ფუნქციების გამოყენებით, მაგალითად, Excel-ში ოპტიმიზაციის პრობლემების გადაჭრა.
ზემოთ ცხრილში სიმბოლოებია:
- K1 - K6 - მომხმარებლები, რომლებსაც სჭირდებათ საქონლის მიწოდება.
- S1 - S6 არის პოტენციური საწარმოო ადგილები, რომლებიც შეიძლება აშენდეს ამისათვის. შეიძლება შეიქმნას1, 2, 3, 4, 5 ან ექვსივე მდებარეობა.
არის ფიქსირებული ხარჯები თითოეული ობიექტისთვის, რომელიც ჩამოთვლილია I სვეტში (შესწორება).
თუ მდებარეობა არაფერს ცვლის, ის არ ჩაითვლება. მაშინ არ იქნება ფიქსირებული ხარჯები.
იდენტიფიცირება პოტენციური მდებარეობების მისაღებად ყველაზე დაბალი ფასის მისაღებად.
ამ პირობებში მდებარეობა ან დადგენილია ან არა. ეს ორი მდგომარეობაა: "მართალი - მცდარი" ან "1 - 0". ექვსი მდებარეობისთვის არის ექვსი მდგომარეობა, მაგალითად, 000001 დაყენებულია მხოლოდ მეექვსეზე, 111111 დაყენებულია ყველასთვის.
ორობითი რიცხვების სისტემაში არის ზუსტად 63 განსხვავებული ვარიანტი 000001-დან 111111-მდე (63).
L2-L64 ახლა უნდა წაიკითხოს {=MULTIPLE OPERATION (K1)}, ეს არის ყველა ალტერნატიული გადაწყვეტის შედეგები. მაშინ მინიმალური მნიშვნელობა არის=Min (L) და შესაბამისი ალტერნატივა არის INDEX (K).
CPLEX მთელი რიცხვის პროგრამირება
ზოგჯერ წრფივი ურთიერთობა არ არის საკმარისი იმისათვის, რომ საქმის პრობლემის არსს მივაღწიოთ. ეს განსაკუთრებით ეხება, როდესაც გადაწყვეტილებები მოიცავს დისკრეტულ არჩევანს, როგორიცაა საწყობის გახსნა თუ არა გარკვეულ ადგილას. ამ სიტუაციებში უნდა იქნას გამოყენებული მთელი რიცხვების პროგრამირება.
თუ პრობლემა მოიცავს როგორც დისკრეტულ, ასევე უწყვეტ არჩევანს, ეს არის შერეული მთელი პროგრამა. მას შეიძლება ჰქონდეს წრფივი, ამოზნექილი კვადრატული ამოცანები და იგივე მეორე რიგის შეზღუდვები.
მთლიანი პროგრამები ბევრად უფრო რთულია, ვიდრე ხაზოვანი პროგრამები, მაგრამ მათ აქვთ მნიშვნელოვანი ბიზნეს აპლიკაციები. პროგრამული უზრუნველყოფაCPLEX პროგრამული უზრუნველყოფა იყენებს კომპლექსურ მათემატიკურ მეთოდებს მთელი რიცხვების ამოცანების გადასაჭრელად. მისი მეთოდები მოიცავს დისკრეტული ცვლადების შესაძლო კომბინაციების სისტემატურ ძიებას წრფივი ან კვადრატული პროგრამული რელაქსაციის გამოყენებით ოპტიმალური ამოხსნის მნიშვნელობის საზღვრების გამოსათვლელად.
ისინი ასევე იყენებენ LP და სხვა ოპტიმიზაციის პრობლემის გადაჭრის მეთოდებს შეზღუდვების გამოსათვლელად.
სტანდარტული Microsoft Excel გადამხსნელი
ეს ტექნოლოგია იყენებს ძირითადი Simplex მეთოდის ძირითად განხორციელებას LP პრობლემების გადასაჭრელად. ის შემოიფარგლება 200 ცვლადით. "Premium Solver" იყენებს გაუმჯობესებულ პირველადი სიმპლექსის მეთოდს ცვლადების ორმხრივი საზღვრებით. Premium Solver პლატფორმა იყენებს LP/Quadratic Simplex Solver-ის გაფართოებულ ვერსიას ოპტიმიზაციის პრობლემის გადასაჭრელად 2000-მდე გადაწყვეტილების ცვლადით.
მსხვილმასშტაბიანი LP Premium Solver პლატფორმისთვის იყენებს უახლესი ტექნოლოგიის დანერგვას მარტივი და ორმაგი სიმპლექსის მეთოდით, რომელიც იყენებს LP მოდელში სიმცირეს დროისა და მეხსიერების დაზოგვის მიზნით, განახლების მოწინავე სტრატეგიებს და მატრიცების რეფაქტორირება, მრავალჯერადი და ნაწილობრივი ფასი და როტაცია და გადაგვარების დასაძლევად. ეს ძრავა ხელმისაწვდომია სამ ვერსიაში (შეუძლია 8000-მდე, 32000-მდე ან შეუზღუდავი ცვლადები და ლიმიტები).
MOSEK Solver მოიცავს პირველად და ორმაგ სიმპლექსს, მეთოდს, რომელიც ასევე იყენებს სიმცირეს და იყენებს მოწინავე სტრატეგიებს მატრიცის განახლებისა და "რეფაქტორიზაციისთვის". ის წყვეტს შეუზღუდავი ზომის პრობლემებს, იყოტესტირება წრფივი პროგრამირების ამოცანებზე მილიონობით გადაწყვეტილების ცვლადით.
ნაბიჯ-ნაბიჯ მაგალითი EXCEL-ში
Excel-ში ოპტიმიზაციის პრობლემის მოდელის დასადგენად, შეასრულეთ შემდეგი ნაბიჯები:
- პრობლემის მონაცემების ორგანიზება ელცხრილში ლოგიკური ფორმით.
- აირჩიეთ უჯრედი თითოეული ცვლადის შესანახად.
- შექმენით უჯრედში ფორმულა ოპტიმიზაციის პრობლემის სამიზნე მათემატიკური მოდელის გამოსათვლელად.
- შექმენით ფორმულები თითოეული შეზღუდვის მარცხენა მხარის გამოსათვლელად.
- გამოიყენეთ დიალოგები Excel-ში, რათა უთხრათ Solver-ს გადაწყვეტილების ცვლადების, მიზნების, შეზღუდვების და სასურველი საზღვრების შესახებ ამ პარამეტრებზე.
- გაუშვით "Solver" ოპტიმალური გადაწყვეტის მოსაძებნად.
- შექმენით 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 წელს შესწავლილი დიეტის პრობლემა. მოცემულია რამდენიმე ნედლეული, როგორიცაა შვრია, ღორის და მზესუმზირის ზეთი, მათ საკვებ შემცველობასთან ერთად, როგორიცაა ცილა, ცხიმი, ვიტამინი A და მათი ფასი კილოგრამზე. გამოწვევაა ნედლეულიდან ერთი ან მეტი საბოლოო პროდუქტის შერევა ყველაზე დაბალ ფასად, მათი კვებითი ღირებულების მინიმალური და მაქსიმალური ლიმიტების დაცვით.
წრფივი ოპტიმიზაციის პრობლემის კლასიკური გამოყენება არის საჭიროებებისთვის მარშრუტის განსაზღვრამოძრაობა სატელეკომუნიკაციო ან სატრანსპორტო ქსელებში. ამავდროულად, ნაკადები უნდა გადაიტანოს ქსელში ისე, რომ ტრაფიკის ყველა მოთხოვნა დაკმაყოფილდეს გამტარუნარიანობის პირობების დარღვევის გარეშე.
მათემატიკურ თეორიაში, წრფივი ოპტიმიზაცია შეიძლება გამოყენებულ იქნას ოპტიმალური სტრატეგიების გამოსათვლელად ნულოვანი ჯამის თამაშებში ორი ადამიანისთვის. ამ შემთხვევაში, თითოეული მონაწილისთვის გამოითვლება ალბათობის განაწილება, რომელიც არის მისი სტრატეგიების შემთხვევითი შერევის კოეფიციენტი.
მსოფლიოში წარმატებული ბიზნეს პროცესი შეუძლებელია ოპტიმიზაციის გარეშე. არსებობს მრავალი ოპტიმიზაციის ალგორითმი ხელმისაწვდომი. ზოგიერთი მეთოდი შესაფერისია მხოლოდ გარკვეული ტიპის პრობლემებისთვის. მნიშვნელოვანია მათი მახასიათებლების ამოცნობა და შესაბამისი გადაწყვეტის მეთოდის შერჩევა.
