Ин мақола алгоритми қаблан аз ҷиҳати назариявӣ пешниҳодшудаи interior-point бо ҷустуҷӯи камонӣ барои барномасозии хаттиро ба татбиқи амалии Matlab табдил медиҳад. Барои алгоритм ҳади полиномии O(√nL) зикр шудааст. arcLP масъалаи стандартии \(\min c^Tx\) бо шартҳои \(Ax=b,\;x\ge0\)-ро ҳал карда, пешкоркард, интихоби нуқтаи ибтидоӣ, системаҳои парокандаи Cholesky, кунҷи қадами камонӣ, параметри марказонӣ, коркарди degeneracy, паскоркард ва санҷиши оптималиро якҷо мекунад.

Дар санҷишҳои Netlib барнома бо татбиқи Matlab-и усули Mehrotra predictor-corrector дар шароити якхела муқоиса шудааст. Аз рӯи ҳисоби мустақими 51 масъалаи Ҷадвали 1, arcLP дар 24 ҳолат итератсияи камтар, дар 11 ҳолат баробар ва дар 16 ҳолат итератсияи бештар истифода мекунад. Маҷмӯи итератсияҳо 1084 барои arcLP ва 1099 барои Mehrotra аст. Қимати бақияи constraint дар 34 масъала барои arcLP камтар, дар 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^k\) ва \(s^k\)-ро нигоҳ медорад.

Интихоби нуқтаи ибтидоӣ

\[ \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 истифода мешавад.

Системаи парокандаи Cholesky

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

Ҳалли чунин системаҳо қисми асосии арзиши ҳисоббарории алгоритмро ташкил медиҳад.

Кунҷи камонӣ ва параметри марказонӣ

arcLP ба ҷойи ҳаракати хаттӣ ба самти оптимум аз траекторияи камонӣ истифода мекунад. Кунҷи қадам аналитикӣ ҳисоб шуда метавонад ва \(\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} \]

ҳамчун аломати unbounded ва

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

ҳамчун яке аз аломатҳои infeasible истифода мешавад. Инҳо дар худи мақола ҳамчун эвристикаҳое тавсиф мешаванд, ки дар санҷишҳои ададӣ муайянкунии қобили қабул нишон додаанд.

Меъёри қатъ

\[ \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 solver-и коркунандаи Matlab мебошад ва дар маҷмӯи санҷидашудаи Netlib ҳалли оптималӣ ба даст овардааст. Он аз рӯи итератсия ва бақия бо Mehrotra рақобатпазир аст, аммо дар ҳамаи масъалаҳо бартарӣ надорад.

Аҳамияти эҳтимолӣ барои Тоҷикистон

Тадқиқот бо маълумоти Тоҷикистон анҷом нашудааст. Бо вуҷуди ин, барномасозии хаттӣ дар банақшагирии энергетика, нақлиёт, логистика, истеҳсол, тақсимоти захираҳо ва таҳқиқоти амалиётӣ истифода мешавад. arcLP метавонад барои омӯзиш ва муқоисаи алгоритмҳо дар муассисаҳои илмӣ ва донишгоҳии Тоҷикистон муфид бошад, вале татбиқи амалӣ бояд дар шароити маҳаллии ҳисоббарорӣ ва системаҳои воқеӣ санҷида шавад.

Усул ва Натиҷаҳои Таҳқиқот

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

Мисоли оддӣ

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

Барои \(A=[1\;1]\), \(b=5\), \(c=[1\;0]^T\), arcLP пас аз панҷ итератсия \(x^*=[0\;5]^T\)-ро медиҳад.

Ҷадвали пурраи benchmark

Ёддошт оид ба Манбаъ ва Усул

Муаллиф: Yaguang Yang, Independent Researcher, US.

DOI: 10.5334/jors.674.

Маҷалла: Journal of Open Research Software 14(1):57, Ubiquity Press.

Нашр: 12 августи 2026.

Статус: Software Metapaper-и аз peer review гузашта.

Литсензияи мақола: CC BY 4.0. Литсензияи барнома: BSD 3-Clause.

Версия: 1.0; санаи барнома дар манбаъ “08/02/2026” аст ва бинобар норавшании формат тафсир карда намешавад.

Маблағгузорӣ: маҷалла аз ҳаққи нашр даст кашидааст; гранти алоҳидаи тадқиқотӣ нишон дода нашудааст.

Бархӯрди манфиатҳо: муаллиф набудани онро эълом кардааст.

Маҳдудият: исботи муфассали O(√nL) ва performance profile дар ин мақола дубора оварда нашудаанд.