Бул эмгек сызыктуу программалоо үчүн мурда теориялык жактан сунушталган жана полиномдук итерация чеги O(√nL) деп берилген жаа боюнча издөөчү infeasible interior-point алгоритмин Matlab программасына айлантат. arcLP \(Ax=b,\;x\ge0\) шарттарында \(c^Tx\) максат функциясын минималдаштырып, алдын ала иштетүүнү, баштапкы чекитти тандоону, сейрек Cholesky системаларын, жаа бурчун, борборлоштуруу параметрин, дегенерацияны иштетүүнү, постпроцессингди жана акыркы оптималдуулук текшерүүсүн бириктирет.
Netlib benchmark маселелеринде arcLP Mehrotra predictor-corrector Matlab коду менен бирдей баштапкы чекиттерде, бирдей pre/post-process жана бирдей токтотуу критерийлеринде салыштырылган. 51 маселе боюнча таблицаны түз санаганда arcLP 24 учурда аз, 11 учурда тең, 16 учурда көп итерация колдонгон; жалпы сан 1084 жана 1099. Теңдик чектөөлөрүнүн калдыгы arcLP үчүн 34 маселеде төмөн, 1 маселеде тең, 16 маселеде жогору.
Негизги илимий чек: бул 2026-жылдагы программалык метамакала O(√nL) теоремасынын толук далилин кайра чыгарбайт; теориялык жыйынтык мурдагы эмгекке таянат.
Primal жана dual формалар
\[ \min c^Tx,\qquad Ax=b,\quad x\ge0. \tag{1} \]
\[ \max b^T\lambda,\qquad A^T\lambda+s=c,\quad s\ge0. \tag{2} \]
Алгоритм \((x^0,s^0)>0\) ички чекиттен башталып, кийинки итерацияларда да \(x\) жана \(s\) оң бойдон калышын камсыз кылат.
Баштапкы чекит критерийи
\[ \max\left\{ \|Ax^0-b\|, \|A^T\lambda^0+s^0-c\|, \frac{(x^0)^Ts^0}{n} \right\}. \tag{3} \]
Эки талапкердин арасынан ушул өлчөмү кичине болгон баштапкы чекит тандалат.
Матрицанын масштаб диапазону
\[ \frac{\max |A_{i,j}|}{\min\{|A_{k,l}|:A_{k,l}\neq0\}}. \tag{4} \]
Булак жалпы scaling эсептөө натыйжалуулугун туруктуу жакшыртпаганын билдирет. Ошондуктан масштабдоо негизги ишке ашырууга кошулган эмес; бирок бул катыш pre-processing эрежесин тандоодо колдонулат. `calRatioCondition(A)` функциясынын алгачкы сүрөттөлүшү менен кийинки scaling бөлүгүнүн ортосундагы айырма булакта өзү бар.
Сейрек Cholesky системасы
\[ AD^2A^Tu=L\Lambda L^Tu=v. \tag{5} \]
Мына ушул типтеги системаларды чечүү негизги эсептөө чыгымын түзөт.
Жаа бурчу жана борборлоштуруу
arcLP түз сызык боюнча эмес, оптимумга карай жаа боюнча жылат. \(\alpha_k\) кадам бурчу аналитикалык эсептелет, ал эми \(\sigma_k\) борборлоштуруу параметри атайын Golden Section издөөсү менен тандалат.
\[ \alpha_k=\min\{0.9999\alpha_k,\;0.99\pi/2\}<0.99\pi/2. \]
Infeasible жана unbounded учурларды аныктоо
\[ \max_i|x_i|>10^{10}, \qquad \max_i|\lambda_i|>10^{10}. \]
Биринчи шарт чексиздикти, экинчиси мүмкүн болбогон LP абалын аныктоочу эвристикалык белгилердин бири болуп саналат. Автор бул механизмдерди сандык тесттерде “reasonable detection” берген ыкмалар катары сүрөттөйт.
Токтотуу критерийи
\[ \frac{\|r_b^k\|}{\max\{1,\|b\|\}}+ \frac{\|r_c^k\|}{\max\{1,\|c\|\}}+ \frac{\mu_k}{\max\{1,|c^Tx^k|,|b^T\lambda^k|\}} <10^{-8}, \]
\[ r_b^k=Ax^k-b,\qquad r_c^k=A^T\lambda^k+s^k-c. \]
Изилдөө эмнени далилдейт?
arcLP иштеген Matlab solver экенин, берилген Netlib тесттеринде оптималдуу чечим тапканын жана Mehrotra коду менен эсептөө жагынан атаандаша аларын көрсөтөт. Бирок бардык LP маселелеринде дайыма тезирээк же такыраак экенин далилдебейт.
Кыргызстан үчүн мүмкүн болгон мааниси
Изилдөө Кыргызстанда жүргүзүлгөн эмес. Ошентсе да сызыктуу программалоо энергетика, транспорт, логистика, өндүрүш, ресурстарды бөлүштүрүү жана пландаштырууда колдонулат. Matlabдагы ачык алгоритм Кыргызстандын университеттеринде оптималдаштыруу ыкмаларын үйрөтүү жана салыштыруу үчүн пайдалуу болушу мүмкүн. Өндүрүштүк колдонуу жергиликтүү эсептөө инфраструктурасы жана конкреттүү маселелер менен өзүнчө текшерилиши керек.
Изилдөөнүн Ыкмасы жана Жыйынтыктары
[x,obj,kk,infe,lambda,s,exflag]=arcLP(A,b,c,d,tol,iter)
| exflag | Мааниси |
|---|---|
| 0 | Ийгиликтүү аяктоо |
| 1 | Булак API боюнча infeasible instance |
| 2 | Булак API боюнча unbounded instance |
| 3 | Primal жана dual маселелердин экөө тең infeasible |
| 4 | A, b же c кирүү маалыматтары толук эмес |
Жөнөкөй мисал
\[ \min x_1,\qquad x_1+x_2=5,\quad x_1,x_2\ge0. \]
arcLP булактагы мисалда беш итерациядан кийин \(x^*=[0\;5]^T\) чечимин табат.
Netlib benchmark таблицасы
| Маселе | Mehrotra ит. | arcLP ит. | Mehrotra максат | arcLP максат | Mehrotra калдык | arcLP калдык |
|---|---|---|---|---|---|---|
| Adlittle | 15 | 16 | 2.2549e+05 | 2.2549e+05 | 3.4e–08 | 3.0e–11 |
| Afiro | 9 | 9 | –464.7531 | –464.7531 | 8.0e–12 | 6.2e–13 |
| Agg | 22 | 20 | –3.5992e+07 | –3.5992e+07 | 5.2e–05 | 3.7e–06 |
| Agg2 | 20 | 21 | –2.0239e+07 | –2.0239e+07 | 5.2e–07 | 3.1e–08 |
| Agg3 | 18 | 20 | 1.0312e+07 | 1.0312e+07 | 8.8e–09 | 1.5e–08 |
| Bandm | 22 | 20 | –158.6280 | –158.6280 | 8.3e–10 | 3.6e–11 |
| Beaconfd | 11 | 11 | 3.3592e+04 | 3.3592e+04 | 1.4e–10 | 1.8e–12 |
| Blend | 14 | 14 | –30.8122 | –30.8122 | 4.9e–11 | 1.6e–12 |
| Bnl1 | 35 | 34 | 1.9776e+03 | 1.9776e+03 | 3.4e–09 | 2.9e–09 |
| Bnl2+ | 38 | 35 | 1.8112e+03 | 1.8112e+03 | 9.3e–07 | 3.5e–06 |
| Brandy | 19 | 24 | 1.5185e+03 | 1.5185e+03 | 6.2e–08 | 2.4e–06 |
| Degen2+ | 17 | 19 | –1.4352e+03 | –1.4352e+03 | 2.0e–10 | 5.9e–10 |
| Degen3* | 22 | 35 | –9.8729e+02 | –9.8729e+02 | 1.2e–09 | 8.6e–08 |
| fffff800 | 31 | 28 | 5.5568e+05 | 5.5568e+05 | 7.7e–04 | 3.7e–09 |
| Israel | 29 | 27 | –8.9665e+05 | –8.9664e+05 | 1.8e–08 | 3.4e–08 |
| Lotfi | 18 | 16 | –25.2647 | –25.2646 | 2.7e–07 | 7.8e–09 |
| Maros_r7 | 21 | 20 | 1.4972e+06 | 1.4972e+06 | 6.4e–09 | 1.7e–09 |
| Osa_07+ | 35 | 32 | 5.3578e+05 | 5.3578e+05 | 1.5e–07 | 8.4e–10 |
| Osa_14 | 37 | 42 | 1.1065e+06 | 1.1065e+06 | 3.0e–08 | 5.2e–09 |
| Osa_30 | 36 | 42 | 2.1421e+06 | 2.1421e+06 | 1.3e–08 | 1.3e–08 |
| Qap12 | 24 | 23 | 5.2289e+02 | 5.2289e+02 | 6.2e–09 | 2.9e–10 |
| Qap15+ | 44 | 28 | 1.0410e+03 | 1.0410e+03 | 1.5e–05 | 8.4e–08 |
| Qap8+ | 13 | 12 | 2.0350e+02 | 2.0350e+02 | 7.1e–09 | 6.2e–11 |
| Sc105 | 11 | 11 | –52.2021 | –52.2021 | 9.8e–11 | 2.2e–12 |
| Sc205 | 12 | 12 | –52.2021 | –52.2021 | 8.8e–11 | 4.4e–11 |
| Sc50a | 9 | 10 | –64.5751 | –64.5751 | 8.3e–08 | 8.5e–13 |
| Sc50b | 8 | 10 | –70.0000 | –70.0000 | 9.1e–07 | 3.6e–12 |
| Scagr25 | 18 | 19 | –1.4753e+07 | –1.4753e+07 | 4.6e–09 | 1.7e–08 |
| Scagr7 | 17 | 17 | –2.3314e+06 | –2.3314e+06 | 1.1e–07 | 7.0e–10 |
| Scfxm1+ | 22 | 21 | 1.8417e+04 | 1.8417e+04 | 1.6e–08 | 3.3e–05 |
| Scfxm2 | 26 | 24 | 3.6660e+04 | 3.6660e+04 | 2.6e–08 | 4.8e–05 |
| Scfxm3+ | 23 | 23 | 5.4901e+04 | 5.4901e+04 | 9.8e–08 | 1.2e–04 |
| Scrs8 | 30 | 28 | 9.0430e+02 | 9.0430e+02 | 1.8e–10 | 1.0e–10 |
| Scsd1 | 13 | 11 | 8.6666 | 8.6666 | 8.7e–14 | 3.3e–15 |
| Scsd6 | 16 | 16 | 50.5000 | 50.5000 | 8.6e–15 | 2.6e–13 |
| Scsd8 | 14 | 15 | 9.0500e+02 | 9.0500e+02 | 1.3e–10 | 2.6e–13 |
| Sctap1 | 27 | 20 | 1.4123e+03 | 1.4123e+03 | 0.0031 | 1.4e–11 |
| Sctap2 | 21 | 22 | 1.7248e+03 | 1.7248e+03 | 4.4e–07 | 1.4e–12 |
| Sctap3 | 22 | 21 | 1.4240e+03 | 1.4240e+03 | 5.9e–07 | 1.9e–12 |
| Share1b | 25 | 26 | –7.6589e+04 | –7.6589e+04 | 1.5e–06 | 1.9e–07 |
| Share2b | 15 | 15 | –4.1573e+02 | –4.1573e+02 | 7.9e–10 | 1.4e–10 |
| Ship04l | 18 | 19 | 1.7933e+06 | 1.7933e+06 | 2.9e–11 | 1.3e–10 |
| Ship04s | 20 | 19 | 1.7987e+06 | 1.7987e+06 | 4.5e–09 | 3.1e–10 |
| Ship08l | 22 | 20 | 1.9091e+06 | 1.9090e+06 | 1.0e–10 | 1.8e–11 |
| Ship08s | 20 | 19 | 1.9201e+06 | 1.9201e+06 | 4.5e–12 | 1.7e–09 |
| Ship12l | 21 | 21 | 1.4702e+06 | 1.4702e+06 | 1.0e–08 | 3.0e–10 |
| Ship12s | 19 | 21 | 1.4892e+06 | 1.4892e+06 | 2.1e–13 | 5.0e–11 |
| Stocfor1+ | 14 | 13 | –4.1132e+04 | –4.1132e+04 | 1.1e–10 | 8.6890e–11 |
| Stocfor2 | 22 | 22 | –3.9024e+04 | –3.9024e+04 | 1.6e–09 | 4.3e–09 |
| Stocfor3 | 38 | 37 | –3.9976e+04 | –3.9977e+04 | 6.4e–08 | 7.7e–08 |
| Truss | 26 | 24 | 4.5882e+05 | 4.5882e+05 | 9.5e–06 | 5.2e–07 |
Жыйынтыктар аралаш мүнөздө: arcLP көп саптарда азыраак калдык же азыраак итерация берет, бирок Degen3*, Scfxm1+, Scfxm2, Scfxm3+ сыяктуу учурларда Mehrotra айрым метрикалар боюнча жакшыраак. Бул ар дайымкы үстөмдүктү эмес, атаандаштыкка жөндөмдүүлүктү көрсөтөт.
Verianla Live: arcLP иш агымы
Бул агым булакта берилген негизги программалык архитектураны көрсөтөт.
| Этап | Түшүндүрмө | Source |
|---|---|---|
| 1. Киргизүү | A, b, c жана параметрлер алынат. | Main function |
| 2. Pre-process | Алдын ала иштетүү жана эрте статус текшерүүсү. | Pre-process |
| 3. Баштапкы чекит | Деңгээл (3) боюнча жакшы талапкер тандалат. | Equation 3 |
| 4. Arc-search | Оң x жана s менен жаа боюнча итерациялар. | Arc-search |
| 5. Сейрек система | Cholesky системасы чечилет. | Equation 5 |
| 6. Токтотуу | Калдыктар, μ, кадам жана статус критерийлери текшерилет. | Termination criteria |
| 7. Post-process | Акыркы текшерүү жана жыйынтыктарды кайтаруу. | Main function |
Булак жана Ыкма Жөнүндө Эскертүү
Автор: Yaguang Yang, Independent Researcher, US.
DOI: 10.5334/jors.674.
Журнал: Journal of Open Research Software, 14(1):57, Ubiquity Press.
Жарыяланган күнү: 12 август 2026.
Статус: рецензияланган Software Metapaper.
Макала лицензиясы: CC BY 4.0. Код лицензиясы: BSD 3-Clause.
Версия: 1.0. Код үчүн булакта “08/02/2026” датасы жазылган, формат так эмес болгондуктан кайра чечмеленбейт.
Каржылоо: JORS жарыялоо акысын алып салган; өзүнчө илимий грант көрсөтүлгөн эмес.
Кызыкчылыктардын кагылышы: жок деп жарыяланган.
Чектөө: O(√nL) далилинин толук чыгарылышы жана performance profile ушул макалада кайра берилген эмес.P
Пикир калтырыңыз
E-mail дарегиңиз жарыяланбайт. Милдеттүү талаалар * менен белгиленген