Оновчилол нь ашиг авчрах, зардлыг бууруулах эсвэл бизнесийн үйл явцын доголдол үүсгэдэг параметрийг тохируулах хамгийн сайн үр дүнг олоход тусална.
Энэ процессыг мөн математик програмчлал гэж нэрлэдэг. Энэ нь оновчтой болгох асуудлын тэргүүний тавьсан зорилгод хүрэхэд шаардлагатай хязгаарлагдмал нөөцийн хуваарилалтыг тодорхойлох асуудлыг шийддэг. Бүх боломжит сонголтуудаас ашиг, өртөг гэх мэт хяналтын параметрийг нэмэгдүүлэх (эсвэл багасгах) сонголтыг олох нь зүйтэй юм. Оновчлолын загварууд нь бизнест хэрэгжих боломжтой стратегийг олохыг эрэлхийлдэг тул заавар эсвэл норматив гэж нэрлэдэг.
Хөгжлийн түүх
Шугаман програмчлал (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 Script дээрх шугаман оновчлолын үйлчилгээ.
Glop нь Google-д суурилагдсаншугаман шийдэгч. Энэ нь нээлттэй эх сурвалж дээр байдаг. Та Glop-д зориулсан OR-Tools шугаман уусгагч боолтоор дамжуулан хандах боломжтой.
Google Sheets-д зориулсан шугаман оновчлолын модуль нь танд хүснэгтэд өгөгдөл оруулах замаар оновчлолын асуудлын шугаман мэдэгдлийг гүйцэтгэх боломжийг олгоно.
Квадрат програмчлал
Premium Solver платформ нь 2000 хүртэлх шийдвэрийн хувьсагчийн LP болон QP асуудлыг боловсруулах хязгаартай Simplex аргын өргөтгөсөн LP/Quadratic хувилбарыг ашигладаг.
SQP Том хэмжээний бодлого шийдэгч нь квадрат програмчлалын (QP) асуудлыг шийдвэрлэхэд сийрэг, идэвхтэй багц аргын орчин үеийн хэрэгжилтийг ашигладаг. XPRESS Solver хөдөлгүүр нь QP-ийн асуудлыг шийдвэрлэхийн тулд "Дотоод цэг" буюу Ньютон саадын аргын байгалийн өргөтгөлийг ашигладаг.
MOSEK solver нь суулгагдсан "Дотоод цэг" болон автомат хос аргыг ашигладаг. Энэ нь ялангуяа сул холболттой QP асуудлуудад үр дүнтэй байдаг. Энэ нь мөн Scale Quadratic Constraint (QCP) болон Second Order Cone Programming (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)} гэж унших ёстой, эдгээр нь бүх өөр шийдлүүдийн үр дүн юм. Дараа нь хамгийн бага утга нь=Min (L) ба тохирох хувилбар нь INDEX (K).
CPLEX бүхэл тоон програмчлал
Заримдаа шугаман харилцаа бизнесийн асуудлын голыг ойлгоход хангалтгүй байдаг. Энэ нь ялангуяа тодорхой байршилд агуулах нээх эсэх гэх мэт салангид сонголттой холбоотой шийдвэр гаргахад үнэн юм. Эдгээр тохиолдолд бүхэл тоон програмчлалыг ашиглах ёстой.
Хэрэв асуудал нь салангид болон тасралтгүй сонголттой холбоотой бол энэ нь холимог бүхэл тооны програм юм. Энэ нь шугаман, гүдгэр квадрат бодлого, хоёр дахь эрэмбийн хязгаарлалттай байж болно.
Бүтэн тоон программууд нь шугаман программуудаас хавьгүй илүү төвөгтэй боловч бизнесийн чухал хэрэглээтэй. Програм хангамжCPLEX программ хангамж нь бүхэл тооны бодлогуудыг шийдвэрлэхийн тулд математикийн нарийн төвөгтэй аргуудыг ашигладаг. Түүний аргууд нь оновчтой шийдлийн утгын хязгаарыг тооцоолохын тулд шугаман эсвэл квадрат програм хангамжийн сулралуудыг ашиглан салангид хувьсагчдын боломжит хослолыг системтэйгээр хайж олох явдал юм.
Тэд мөн хязгаарлалтыг тооцоолохдоо LP болон бусад оновчлолын асуудлыг шийдвэрлэх аргуудыг ашигладаг.
Стандарт Microsoft Excel шийдэл
Энэ технологи нь LP асуудлыг шийдвэрлэх үндсэн Simplex аргын үндсэн хэрэгжилтийг ашигладаг. Энэ нь 200 хувьсагчаар хязгаарлагддаг. "Premium Solver" нь хувьсагчдын хувьд хоёр талт хязгаар бүхий сайжруулсан үндсэн симплекс аргыг ашигладаг. 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-ийг төлөөлөхийн тулд нөөцөлсөн. Шийдвэрийн жишээ:
- Бүтээгдэхүүний холимог загварыг B5, C5, D5, E5 нүдэнд тус тус оруулсан (450, 1150, 800, 400 долларын ашиг тус). Энэ нь зорилтот утгыг F5=B5B4 + C5C4 + D5D4 + E5E4 эсвэл F5:=ДҮГНЭЛТ (B5: E5, B4: E4) дээр тооцоолох боломжийг олгодог.
- В8-д төрөл бүрийг үйлдвэрлэхэд шаардагдах нөөцийн хэмжээг оруулна.
- 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 онд Жорж Данцигийн судалсан хоолны дэглэмийн асуудал юм. Овъёос, гахайн мах, наранцэцгийн тос зэрэг хэд хэдэн түүхий эдийг уураг, өөх тос, А аминдэм гэх мэт тэжээллэг чанар, килограмм тутамд нь үнээр нь өгдөг. Түүхий эдээс нэг буюу хэд хэдэн эцсийн бүтээгдэхүүнийг аль болох бага зардлаар холихын зэрэгцээ тэдгээрийн тэжээллэг чанарын хамгийн бага ба дээд хязгаарыг дагаж мөрдөх нь тулгамдсан асуудал юм.
Шугаман оновчлолын асуудлын сонгодог хэрэглээ бол хэрэгцээнд тохирсон чиглүүлэлт тодорхойлох явдал юмхарилцаа холбоо, тээврийн сүлжээн дэх урсгал. Үүний зэрэгцээ урсгалыг сүлжээгээр дамжуулж, зурвасын өргөнийг зөрчихгүйгээр замын хөдөлгөөний бүх шаардлагыг хангасан байх ёстой.
Математикийн онолд шугаман оновчлолыг хоёр хүний 0 нийлбэртэй тоглоомд оновчтой стратегийг тооцоолоход ашиглаж болно. Энэ тохиолдолд оролцогч бүрийн магадлалын тархалтыг тооцдог бөгөөд энэ нь түүний стратегийг санамсаргүй холих коэффициент юм.
Дэлхий дээрх ямар ч амжилттай бизнесийн үйл явцыг оновчтой болгохгүйгээр хийх боломжгүй. Олон тооны оновчлолын алгоритмууд байдаг. Зарим аргууд нь зөвхөн тодорхой төрлийн асуудалд тохиромжтой. Тэдний шинж чанарыг таньж мэдэх, тохирох шийдлийн аргыг сонгох нь чухал.
