Ushbu ish avval nazariy jihatdan ishlab chiqilgan, polinom iteratsiya chegarasi O(√nL) deb berilgan yoy bo‘ylab qidiruvchi infeasible interior-point algoritmini ishlaydigan Matlab yechimiga aylantiradi. arcLP standart chiziqli dasturlash masalasini, ya’ni \(Ax=b,\;x\ge0\) shartlari ostida \(c^Tx\) ni minimallashtirishni yechadi. Dastur oldindan ishlov berish, boshlang‘ich nuqtani tanlash, siyrak Cholesky tizimlari, yoy qadam burchagi, markazlash parametri, degeneratsiyani boshqarish, yakuniy ishlov va optimallik tekshiruvini birlashtiradi.

Netlib benchmark masalalarida arcLP Mehrotra predictor-corrector Matlab implementatsiyasi bilan bir xil boshlang‘ich nuqta, bir xil pre/post-process va bir xil to‘xtash mezonlarida solishtirilgan. 51 qatordan iborat 1-jadvalni Verianla hisoblaganda arcLP 24 masalada kamroq, 11 masalada teng, 16 masalada ko‘proq iteratsiya ishlatadi; jami 1084 iteratsiya, Mehrotra variantida esa 1099. Tenglik cheklovi qoldig‘i arcLP uchun 34 masalada kichikroq, 1 ta masalada teng va 16 ta masalada kattaroq.

Muhim ilmiy chegara: 2026-yilgi ushbu Software Metapaper O(√nL) yaqinlashuv isbotini qaytadan keltirmaydi. Nazariy natija oldingi maqolaga tayanadi; bu ishning bevosita vazifasi dastur arxitekturasi va sonli sinovlarni hujjatlashtirishdir.

Standart primal va dual masala

\[ \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} \]

Bu yerda \(A\in\mathbb{R}^{m\times n}\), \(b\in\mathbb{R}^m\), \(c,x,s\in\mathbb{R}^n\), \(\lambda\in\mathbb{R}^m\). Algoritm \((x^0,s^0)>0\) ichki nuqtadan boshlanadi va iteratsiyalarda musbatlikni saqlaydi.

Boshlang‘ich nuqta mezoni

\[ \max\left\{ \|Ax^0-b\|, \|A^T\lambda^0+s^0-c\|, \frac{(x^0)^Ts^0}{n} \right\}. \tag{3} \]

Ikki nomzod orasidan ushbu qiymati kichik bo‘lgan nuqta tanlanadi.

Matritsadagi nol bo‘lmagan qiymatlar diapazoni

\[ \frac{\max |A_{i,j}|} {\min\{|A_{k,l}|:A_{k,l}\neq0\}}. \tag{4} \]

Maqola umumiy scaling hisoblash samaradorligini doimo yaxshilamasligini va shu sababli asosiy implementatsiyaga kiritilmaganini aytadi. Biroq nisbat pre-processing qoidalaridan birini ishga tushirish zaruratini aniqlashda ishlatiladi. `calRatioCondition(A)` haqidagi oldingi tavsif bilan scaling bo‘limi orasidagi ifoda farqi manbada mavjud.

Siyrak Cholesky algebra

\[ AD^2A^Tu=L\Lambda L^Tu=v. \tag{5} \]

Bu tizimlarni yechish asosiy hisoblash xarajatini tashkil etadi. \(D\) va \(\Lambda\) diagonal, \(L\) quyi uchburchak matritsadir.

Yoy burchagi va σ_k

arcLP to‘g‘ri chiziq bo‘ylab emas, yoy bo‘ylab optimallikka qarab siljiydi. Qadam burchagi analitik aniqlanishi mumkin. Markazlash parametri \(\sigma_k\) maxsus Golden Section qidiruvi bilan tanlanadi. Manbada klassik qidiruv intervalni taxminan 0.618 ga, qo‘llanilgan maxsus qidiruv esa har bosqichda 0.5 ga qisqartirishi aytilgan.

\[ \alpha_k=\min\{0.9999\alpha_k,\;0.99\pi/2\}<0.99\pi/2. \]

Infeasible va unbounded holatlar

\[ \max_i|x_i|>10^{10} \]

unbounded holat,

\[ \max_i|\lambda_i|>10^{10} \]

esa infeasible holat uchun ishlatiladigan heuristik ko‘rsatkichlardan biridir. Algoritm musbat \(x,s\) ni saqlab duality gap-ni kamaytiradigan qadam topa olmasa ham infeasibility signali yuzaga kelishi mumkin. Bu mexanizmlar manbada sonli heuristikalar sifatida baholanadi.

To‘xtash mezoni

\[ \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. \]

Tadqiqot nimani tasdiqlaydi?

arcLP ishlaydigan Matlab LP solveri ekanini, Netlib sinovlarida optimal yechim topganini va Mehrotra implementatsiyasi bilan hisoblash jihatidan raqobat qila olishini ko‘rsatadi. Ammo har bir LP, har bir platforma va har bir tijoriy solverga nisbatan mutlaq ustunlik isbotlanmagan.

O‘zbekiston uchun mumkin bo‘lgan ahamiyati

Tadqiqot O‘zbekiston ma’lumotlariga asoslanmagan. Biroq chiziqli dasturlash energetika, ishlab chiqarish, logistika, transport, resurslarni taqsimlash va muhandislik rejalashtirishida keng qo‘llanadi. Ochiq kodli Matlab yechimi O‘zbekistondagi universitet va ilmiy guruhlarda optimallashtirish algoritmlarini o‘qitish va solishtirish uchun foydali bo‘lishi mumkin. Mahalliy sanoatga tatbiq etish alohida muammolar, hisoblash muhiti va integratsiya talablarida tekshirilishi kerak.

Tadqiqot Usuli va Natijalari

[x,obj,kk,infe,lambda,s,exflag]=arcLP(A,b,c,d,tol,iter)

Oddiy misol

\[ \min x_1,\qquad x_1+x_2=5,\quad x_1,x_2\ge0. \]

Manbaga ko‘ra \(A=[1\;1]\), \(b=5\), \(c=[1\;0]^T\) uchun arcLP besh iteratsiyada \(x^*=[0\;5]^T\) ni topadi.

51 ta Netlib benchmark natijasi

Jadvalga ko‘ra natijalar bir xil yo‘nalishda emas: arcLP ko‘p masalalarda juda kichik qoldiq beradi, ammo Degen3*, Scfxm1+, Scfxm2, Scfxm3+ va ayrim boshqa satrlarda Mehrotra qoldig‘i yaxshiroq. Shu sababli “raqobatbardosh” xulosasi “har doim ustun” degani emas.

Manba va Usul Bo‘yicha Izoh

Muallif: Yaguang Yang, Independent Researcher, US.

DOI: 10.5334/jors.674.

Nashr: Journal of Open Research Software 14(1):57, Ubiquity Press, 12-avgust 2026.

Turi: ekspert baholashidan o‘tgan Software Metapaper.

Maqola litsenziyasi: CC BY 4.0. Dastur litsenziyasi: BSD 3-Clause.

Dastur versiyasi: 1.0. Manbadagi “08/02/2026” sana formati sharhlanmasdan saqlanishi lozim.

Moliyalashtirish: JORS nashr to‘lovidan voz kechgan; alohida tadqiqot granti ko‘rsatilmagan.

Manfaatlar to‘qnashuvi: muallif yo‘qligini bildirgan.

Cheklov: O(√nL) isbotining to‘liq matematik tafsiloti va performance profile ushbu yetti sahifali maqolada qayta berilmagan.