افحص التغييرات الفردية
تسمح لك هذه الصفحة بفحص المتغيرات التي تم إنشاؤها بواسطة عامل تصفية إساءة الاستخدام لإجراء تغيير فردي.
المتغيرات المولدة لهذا التغيير
| متغير | قيمة |
|---|---|
عدد التعديلات للمستخدم (user_editcount) | 78 |
اسم حساب المستخدم (user_name) | 'Alanouddd' |
عمر حساب المستخدم (user_age) | 2068204 |
المجموعات (متضمنة غير المباشرة) التي المستخدم فيها (user_groups) | [
0 => '*',
1 => 'user',
2 => 'autoconfirmed'
] |
المجموعات العامة التي ينتمي إليها الحساب (global_user_groups) | [] |
ما إذا كان المستخدم يعدل من تطبيق المحمول (user_app) | false |
ما إذا كان المستخدم يعدل عبر واجهة المحمول (user_mobile) | false |
user_wpzero | false |
هوية الصفحة (page_id) | 6484774 |
نطاق الصفحة (page_namespace) | 0 |
عنوان الصفحة (بدون نطاق) (page_title) | 'خوارزمية كارماركر' |
عنوان الصفحة الكامل (page_prefixedtitle) | 'خوارزمية كارماركر' |
آخر عشرة مساهمين في الصفحة (page_recent_contributors) | [
0 => 'Alanouddd'
] |
فعل (action) | 'edit' |
ملخص التعديل/السبب (summary) | 'تعديل صيغ رياضية' |
نموذج المحتوى القديم (old_content_model) | 'wikitext' |
نموذج المحتوى الجديد (new_content_model) | 'wikitext' |
نص الويكي القديم للصفحة، قبل التعديل (old_wikitext) | ''''خوارزمية كارماركر''' هي [[خوارزمية]] قدمها ناريندرا كارماركر في عام 1984 لحل مسائل [[برمجة خطية|البرمجة الخطية]] . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في [[تعقيد الوقت|زمن متعدد الحدود]] . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.
بجعل <math>n</math>تدل على عدد المتغيرات و <math>L</math> على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج الى <math>O(n^{3.5} L)</math>عملية على خانات <math>O(L)</math>, في المقابل تحتاج الى <math>O(n^6 L)</math>عمليات بخوارزمية الاهليجي.
بالتالي زمن تشغيل خوارزمية كارماركر هو:
: <math>O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)</math>
باستخدام الضرب القائم على FFT (انظر [[رمز O الكبير]] ).
تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في [[طريقة التبسيط (برمجة)|طريقة simplex]] ، لكنه يتحرك بداخل المنطقة الممكنة ، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار ، والوصول إلى الحل الأمثل مع البيانات المنطقية. <ref name="Strang">{{Cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=Karmarkar's algorithm and its place in applied mathematics|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|issue=2|DOI=10.1007/BF03025891|mr=883185|ref=harv}}</ref>
== الخوارزمية ==
بالنظر في مشكلة البرمجة الخطية في شكل المصفوفة:
{|
| colspan="2" | تعظيم {{Math|''c''<sup>T</sup>''x''}}
|-
| تخضع الى
| {{Math|''Ax'' ≤ ''b''}} .
|-
|}
تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل {{Math|0 < γ ≤ 1}}.<ref>http://dl.acm.org/citation.cfm?id=808695</ref><ref>{{Cite journal|DOI=10.1007/BF02579150|volume=4|issue=4|title=A new polynomial-time algorithm for linear programming|journal=Combinatorica|pages=373–395|last=Karmarkar|first=N.|year=1984}}</ref><ref>{{Cite journal|DOI=10.1002/j.1538-7305.1989.tb00316.x|volume=68|issue=3|title=Power Series Variants of Karmarkar-Type Algorithms|journal=AT&T Technical Journal|pages=20–36|last=Karmarkar|first=Narendra K.|year=1989}}</ref><ref>Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).</ref>
وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>{{algorithm-begin|name=Affine-Scaling}}
Since the actual algorithm is rather complicated, researchers looked for a more intuitive version of it, and in 1985 developed [[affine scaling]], a version of Karmarkar's algorithm that uses [[affine transformation]]s where Karmarkar used [[projective geometry|projective]] ones, only to realize four years later that they had rediscovered an algorithm published by [[Soviet Union|Soviet]] mathematician I. I. Dikin in 1967.<ref>{{cite conference
| last1 = Vanderbei | first1 = R. J.
| last2 = Lagarias | first2 = J. C.
| contribution = I. I. Dikin's convergence result for the affine-scaling algorithm
| doi = 10.1090/conm/114/1097868
| mr = 1097868
| pages = 109–119
| publisher = American Mathematical Society | location = Providence, RI
| series = Contemporary Mathematics
| title = Mathematical developments arising from linear programming (Brunswick, ME, 1988)
| volume = 114
| year = 1990}}</ref> The affine-scaling method can be described succinctly as follows.<ref>{{cite journal
| doi = 10.1007/BF01840454
| author = Robert J. Vanderbei |author2=Meketon, Marc |author3=Freedman, Barry
| year = 1986
| title = A Modification of Karmarkar's Linear Programming Algorithm
| journal = Algorithmica
| volume = 1
| issue = 1–4 | pages = 395–407 |url=https://www.princeton.edu/~rvdb/tex/myPapers/VanderbeiMeketonFreedman.pdf
| author-link = Robert J. Vanderbei }}</ref> The affine-scaling algorithm, while applicable to small scale problems, is not a polynomial time algorithm.{{بحاجة لمصدر}}
{{بدون لف|Input: A, b, c, <math>x^0</math>,}} ''stopping criterion'', {{Mvar|γ}}.
{{بدون لف|<math> k \leftarrow 0 </math>}}
{{بدون لف|'''do while''' ''stopping criterion'' '''not satisfied'''}}
{{بدون لف|<math>v^k \leftarrow b-Ax^k</math>}}
{{بدون لف|<math>D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)</math>}}
{{بدون لف|<math>h_x\leftarrow (A^TD_v^{-2}A)^{-1}c</math>}}
{{بدون لف|<math>h_v\leftarrow -Ah_x</math>}}
{{بدون لف|'''if''' <math>h_v \ge 0</math> '''then'''}}
'''return''' unbounded
'''end if'''
{{بدون لف|<math>\alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}</math>}}
{{بدون لف|<math>x^{k+1}\leftarrow x^k + \alpha h_x</math>}}
{{بدون لف|<math>k\leftarrow k+1</math>}}
'''end do'''
{{algorithm-end}}
== مثال ==
[[ملف:Karmarkar.svg|يسار|تصغير|200x200بك| مثال الحل ]]
بالنظر في البرنامج الخطي
: <math> \begin{array}{lrclr}
\text{maximize}
&
x_1
+
x_2
\\
\text{subject to}
&
2p x_1
+
x_2
& \leq & p^2+1, & p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0.
\end{array}
</math>
حيث يوجد متغيرين <math>x_1, x_2</math> و 11 قيود مرتبطة باختلاف قيم <math>p</math> . يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء. وتظهر القيود كخطوط زرقاء.
== جدل براءات الاختراع ==
في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
== المراجع ==
* {{Cite journal|last=Adler|first=Ilan|last2=Karmarkar|first2=Narendra|last3=Resende|first3=Mauricio G.C.|last4=Veiga|first4=Geraldo|year=1989|title=An Implementation of Karmarkar's Algorithm for Linear Programming|url=|journal=Mathematical Programming|volume=44|issue=1–3|pages=297–335|DOI=10.1007/bf01587095}}
* ناريندرا كارماركار (1984). " [https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية] " ، ''Combinatorica'' ، المجلد '''4''' ، العدد. 4 ، ص. 373 – 395.
{{مراجع|30em}}
[[تصنيف:برمجة خطية]]
[[تصنيف:مقالات ذات عبارات بحاجة لمصادر منذ فبراير 2016]]
[[تصنيف:جميع المقالات التي بها عبارات بحاجة لمصادر]]' |
نص الويكي الجديد للصفحة، بعد التعديل (new_wikitext) | ''''خوارزمية كارماركر''' هي [[خوارزمية]] قدمها ناريندرا كارماركر في عام 1984 لحل مسائل [[برمجة خطية|البرمجة الخطية]] . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في [[تعقيد الوقت|زمن متعدد الحدود]] . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.
بجعل <math>n</math>تدل على عدد المتغيرات و <math>L</math> على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج الى <math>O(n^{3.5} L)</math>عملية على خانات <math>O(L)</math>, في المقابل تحتاج الى <math>O(n^6 L)</math>عمليات بخوارزمية الاهليجي.
بالتالي زمن تشغيل خوارزمية كارماركر هو:
: <math>O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)</math>
باستخدام الضرب القائم على FFT (انظر [[رمز O الكبير]] ).
تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في [[طريقة التبسيط (برمجة)|طريقة simplex]] ، لكنه يتحرك بداخل المنطقة الممكنة ، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار ، والوصول إلى الحل الأمثل مع البيانات المنطقية. <ref name="Strang">{{Cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=Karmarkar's algorithm and its place in applied mathematics|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|issue=2|DOI=10.1007/BF03025891|mr=883185|ref=harv}}</ref>
== الخوارزمية ==
بالنظر في مشكلة البرمجة الخطية في شكل المصفوفة:
{|
| colspan="2" | تعظيم {{Math|''c''<sup>T</sup>''x''}}
|-
| تخضع الى
| {{Math|''Ax'' ≤ ''b''}} .
|-
|}
تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل {{Math|0 < γ ≤ 1}}.<ref>http://dl.acm.org/citation.cfm?id=808695</ref><ref>{{Cite journal|DOI=10.1007/BF02579150|volume=4|issue=4|title=A new polynomial-time algorithm for linear programming|journal=Combinatorica|pages=373–395|last=Karmarkar|first=N.|year=1984}}</ref><ref>{{Cite journal|DOI=10.1002/j.1538-7305.1989.tb00316.x|volume=68|issue=3|title=Power Series Variants of Karmarkar-Type Algorithms|journal=AT&T Technical Journal|pages=20–36|last=Karmarkar|first=Narendra K.|year=1989}}</ref><ref>Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).</ref>
وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>
<br />
== مثال ==
[[ملف:Karmarkar.svg|يسار|تصغير|200x200بك| مثال الحل ]]
بالنظر في البرنامج الخطي
: <math> \begin{array}{lrclr}
\text{maximize}
&
x_1
+
x_2
\\
\text{subject to}
&
2p x_1
+
x_2
& \leq & p^2+1, & p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0.
\end{array}
</math>
حيث يوجد متغيرين <math>x_1, x_2</math> و 11 قيود مرتبطة باختلاف قيم <math>p</math> . يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء. وتظهر القيود كخطوط زرقاء.
== جدل براءات الاختراع ==
في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
== المراجع ==
* {{Cite journal|last=Adler|first=Ilan|last2=Karmarkar|first2=Narendra|last3=Resende|first3=Mauricio G.C.|last4=Veiga|first4=Geraldo|year=1989|title=An Implementation of Karmarkar's Algorithm for Linear Programming|url=|journal=Mathematical Programming|volume=44|issue=1–3|pages=297–335|DOI=10.1007/bf01587095}}
* ناريندرا كارماركار (1984). " [https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية] " ، ''Combinatorica'' ، المجلد '''4''' ، العدد. 4 ، ص. 373 – 395.
{{مراجع|30em}}
[[تصنيف:برمجة خطية]]
[[تصنيف:مقالات ذات عبارات بحاجة لمصادر منذ فبراير 2016]]
[[تصنيف:جميع المقالات التي بها عبارات بحاجة لمصادر]]' |
فرق موحد للتغييرات المصنوعة بواسطة التعديل (edit_diff) | '@@ -22,42 +22,7 @@
تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل {{Math|0 < γ ≤ 1}}.<ref>http://dl.acm.org/citation.cfm?id=808695</ref><ref>{{Cite journal|DOI=10.1007/BF02579150|volume=4|issue=4|title=A new polynomial-time algorithm for linear programming|journal=Combinatorica|pages=373–395|last=Karmarkar|first=N.|year=1984}}</ref><ref>{{Cite journal|DOI=10.1002/j.1538-7305.1989.tb00316.x|volume=68|issue=3|title=Power Series Variants of Karmarkar-Type Algorithms|journal=AT&T Technical Journal|pages=20–36|last=Karmarkar|first=Narendra K.|year=1989}}</ref><ref>Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).</ref>
-وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>{{algorithm-begin|name=Affine-Scaling}}
+وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>
-Since the actual algorithm is rather complicated, researchers looked for a more intuitive version of it, and in 1985 developed [[affine scaling]], a version of Karmarkar's algorithm that uses [[affine transformation]]s where Karmarkar used [[projective geometry|projective]] ones, only to realize four years later that they had rediscovered an algorithm published by [[Soviet Union|Soviet]] mathematician I. I. Dikin in 1967.<ref>{{cite conference
- | last1 = Vanderbei | first1 = R. J.
- | last2 = Lagarias | first2 = J. C.
- | contribution = I. I. Dikin's convergence result for the affine-scaling algorithm
- | doi = 10.1090/conm/114/1097868
- | mr = 1097868
- | pages = 109–119
- | publisher = American Mathematical Society | location = Providence, RI
- | series = Contemporary Mathematics
- | title = Mathematical developments arising from linear programming (Brunswick, ME, 1988)
- | volume = 114
- | year = 1990}}</ref> The affine-scaling method can be described succinctly as follows.<ref>{{cite journal
- | doi = 10.1007/BF01840454
- | author = Robert J. Vanderbei |author2=Meketon, Marc |author3=Freedman, Barry
- | year = 1986
- | title = A Modification of Karmarkar's Linear Programming Algorithm
- | journal = Algorithmica
- | volume = 1
- | issue = 1–4 | pages = 395–407 |url=https://www.princeton.edu/~rvdb/tex/myPapers/VanderbeiMeketonFreedman.pdf
-| author-link = Robert J. Vanderbei }}</ref> The affine-scaling algorithm, while applicable to small scale problems, is not a polynomial time algorithm.{{بحاجة لمصدر}}
- {{بدون لف|Input: A, b, c, <math>x^0</math>,}} ''stopping criterion'', {{Mvar|γ}}.
-
- {{بدون لف|<math> k \leftarrow 0 </math>}}
- {{بدون لف|'''do while''' ''stopping criterion'' '''not satisfied'''}}
- {{بدون لف|<math>v^k \leftarrow b-Ax^k</math>}}
- {{بدون لف|<math>D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)</math>}}
- {{بدون لف|<math>h_x\leftarrow (A^TD_v^{-2}A)^{-1}c</math>}}
- {{بدون لف|<math>h_v\leftarrow -Ah_x</math>}}
- {{بدون لف|'''if''' <math>h_v \ge 0</math> '''then'''}}
- '''return''' unbounded
- '''end if'''
- {{بدون لف|<math>\alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}</math>}}
- {{بدون لف|<math>x^{k+1}\leftarrow x^k + \alpha h_x</math>}}
- {{بدون لف|<math>k\leftarrow k+1</math>}}
- '''end do'''
-{{algorithm-end}}
+<br />
== مثال ==
@@ -84,5 +49,5 @@
== جدل براءات الاختراع ==
-في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
+في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
== المراجع ==
' |
حجم الصفحة الجديد (new_size) | 7293 |
حجم الصفحة القديم (old_size) | 9775 |
الحجم المتغير في التعديل (edit_delta) | -2482 |
السطور المضافة في التعديل (added_lines) | [
0 => 'وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>',
1 => '<br />',
2 => 'في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.'
] |
السطور المزالة في التعديل (removed_lines) | [
0 => 'وسع كامارك الطريقة <ref>Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</ref><ref>Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</ref><ref>26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</ref><ref>27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</ref> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<ref>Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</ref>{{algorithm-begin|name=Affine-Scaling}}',
1 => 'Since the actual algorithm is rather complicated, researchers looked for a more intuitive version of it, and in 1985 developed [[affine scaling]], a version of Karmarkar's algorithm that uses [[affine transformation]]s where Karmarkar used [[projective geometry|projective]] ones, only to realize four years later that they had rediscovered an algorithm published by [[Soviet Union|Soviet]] mathematician I. I. Dikin in 1967.<ref>{{cite conference',
2 => ' | last1 = Vanderbei | first1 = R. J.',
3 => ' | last2 = Lagarias | first2 = J. C.',
4 => ' | contribution = I. I. Dikin's convergence result for the affine-scaling algorithm',
5 => ' | doi = 10.1090/conm/114/1097868',
6 => ' | mr = 1097868',
7 => ' | pages = 109–119',
8 => ' | publisher = American Mathematical Society | location = Providence, RI',
9 => ' | series = Contemporary Mathematics',
10 => ' | title = Mathematical developments arising from linear programming (Brunswick, ME, 1988)',
11 => ' | volume = 114',
12 => ' | year = 1990}}</ref> The affine-scaling method can be described succinctly as follows.<ref>{{cite journal',
13 => ' | doi = 10.1007/BF01840454',
14 => ' | author = Robert J. Vanderbei |author2=Meketon, Marc |author3=Freedman, Barry',
15 => ' | year = 1986',
16 => ' | title = A Modification of Karmarkar's Linear Programming Algorithm ',
17 => ' | journal = Algorithmica',
18 => ' | volume = 1',
19 => ' | issue = 1–4 | pages = 395–407 |url=https://www.princeton.edu/~rvdb/tex/myPapers/VanderbeiMeketonFreedman.pdf',
20 => '| author-link = Robert J. Vanderbei }}</ref> The affine-scaling algorithm, while applicable to small scale problems, is not a polynomial time algorithm.{{بحاجة لمصدر}} ',
21 => ' {{بدون لف|Input: A, b, c, <math>x^0</math>,}} ''stopping criterion'', {{Mvar|γ}}.',
22 => false,
23 => ' {{بدون لف|<math> k \leftarrow 0 </math>}}',
24 => ' {{بدون لف|'''do while''' ''stopping criterion'' '''not satisfied'''}}',
25 => ' {{بدون لف|<math>v^k \leftarrow b-Ax^k</math>}}',
26 => ' {{بدون لف|<math>D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)</math>}}',
27 => ' {{بدون لف|<math>h_x\leftarrow (A^TD_v^{-2}A)^{-1}c</math>}}',
28 => ' {{بدون لف|<math>h_v\leftarrow -Ah_x</math>}}',
29 => ' {{بدون لف|'''if''' <math>h_v \ge 0</math> '''then'''}}',
30 => ' '''return''' unbounded',
31 => ' '''end if'''',
32 => ' {{بدون لف|<math>\alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i < 0,\, i=1,\ldots,m\}</math>}}',
33 => ' {{بدون لف|<math>x^{k+1}\leftarrow x^k + \alpha h_x</math>}}',
34 => ' {{بدون لف|<math>k\leftarrow k+1</math>}}',
35 => ' '''end do'''',
36 => '{{algorithm-end}}',
37 => 'في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة [[آي بي إم]] كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في [[جامعة ستانفورد]] لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في [[إيه تي آند تي]] وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<nowiki/>[[مختبرات بل|مختبرات بيل]] لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <ref>Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</ref> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر. '
] |
نص الصفحة الجديد، مجردا من أية تهيئة (new_text) | 'خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.
بجعل
n
{\displaystyle n}
تدل على عدد المتغيرات و
L
{\displaystyle L}
على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج الى
O
(
n
3.5
L
)
{\displaystyle O(n^{3.5}L)}
عملية على خانات
O
(
L
)
{\displaystyle O(L)}
, في المقابل تحتاج الى
O
(
n
6
L
)
{\displaystyle O(n^{6}L)}
عمليات بخوارزمية الاهليجي.
بالتالي زمن تشغيل خوارزمية كارماركر هو:
O
(
n
3.5
L
2
⋅
log
⁡
L
⋅
log
⁡
log
⁡
L
)
{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}
باستخدام الضرب القائم على FFT (انظر رمز O الكبير ).
تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة ، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار ، والوصول إلى الحل الأمثل مع البيانات المنطقية. [1]
محتويات
1 الخوارزمية
2 مثال
3 جدل براءات الاختراع
4 المراجع
الخوارزمية[عدل]
بالنظر في مشكلة البرمجة الخطية في شكل المصفوفة:
تعظيم cTx
تخضع الى
Ax ≤ b .
تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل 0 < γ ≤ 1.[2][3][4][5]
وسع كامارك الطريقة [6][7][8][9] ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.[10]
مثال[عدل]
مثال الحل
بالنظر في البرنامج الخطي
maximize
x
1
+
x
2
subject to
2
p
x
1
+
x
2
≤
p
2
+
1
,
p
=
0.0
,
0.1
,
0.2
,
…
,
0.9
,
1.0.
{\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}
حيث يوجد متغيرين
x
1
,
x
2
{\displaystyle x_{1},x_{2}}
و 11 قيود مرتبطة باختلاف قيم
p
{\displaystyle p}
. يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء. وتظهر القيود كخطوط زرقاء.
جدل براءات الاختراع[عدل]
في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة آي بي إم كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في جامعة ستانفورد لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في إيه تي آند تي وقدم مقالته إلى <a href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه لمختبرات بيل لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، [11] أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
المراجع[عدل]
Adler، Ilan؛ Karmarkar، Narendra؛ Resende، Mauricio G.C.؛ Veiga، Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming. 44 (1–3): 297–335. doi:10.1007/bf01587095. .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
ناريندرا كارماركار (1984). " خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية " ، Combinatorica ، المجلد 4 ، العدد. 4 ، ص.   373 – 395.
^ Strang، Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. ISSN 0343-6993. MR 883185. doi:10.1007/BF03025891. 
^ http://dl.acm.org/citation.cfm?id=808695
^ Karmarkar، N. (1984). "A new polynomial-time algorithm for linear programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. 
^ Karmarkar، Narendra K. (1989). "Power Series Variants of Karmarkar-Type Algorithms". AT&T Technical Journal. 68 (3): 20–36. doi:10.1002/j.1538-7305.1989.tb00316.x. 
^ Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
^ Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)
^ Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).
^ 26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).
^ 27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).
^ Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010
^ Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).
' |
مصدر HTML المعروض للمراجعة الجديدة (new_html) | '<div class="mw-parser-output"><p><b>خوارزمية كارماركر</b> هي <a href="/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9" title="خوارزمية">خوارزمية</a> قدمها ناريندرا كارماركر في عام 1984 لحل مسائل <a href="/wiki/%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%AE%D8%B7%D9%8A%D8%A9" title="برمجة خطية">البرمجة الخطية</a> . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في <a href="/wiki/%D8%AA%D8%B9%D9%82%D9%8A%D8%AF_%D8%A7%D9%84%D9%88%D9%82%D8%AA" title="تعقيد الوقت">زمن متعدد الحدود</a> . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.
</p><p>بجعل <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="n"/></span>تدل على عدد المتغيرات و <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>L</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle L}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="L"/></span> على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج الى <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3.5}L)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3.5</mn>
</mrow>
</msup>
<mi>L</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{3.5}L)}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75bfa3b481f545e25ae3d8d60ef6ca14d51050ef" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:8.894ex; height:3.176ex;" alt="{\displaystyle O(n^{3.5}L)}"/></span>عملية على خانات <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(L)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mi>L</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(L)}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2686f0d98bdf16092324c5519a1497c1f7a3e2fc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:5.165ex; height:2.843ex;" alt="{\displaystyle O(L)}"/></span>, في المقابل تحتاج الى <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{6}L)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msup>
<mi>L</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{6}L)}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b415f36ac1c25ad1609e767279717826fc236fa" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.614ex; height:3.176ex;" alt="{\displaystyle O(n^{6}L)}"/></span>عمليات بخوارزمية الاهليجي.
</p><p>بالتالي زمن تشغيل خوارزمية كارماركر هو:
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3.5</mn>
</mrow>
</msup>
<msup>
<mi>L</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo>⋅<!-- ⋅ --></mo>
<mi>log</mi>
<mo>⁡<!-- --></mo>
<mi>L</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>log</mi>
<mo>⁡<!-- --></mo>
<mi>log</mi>
<mo>⁡<!-- --></mo>
<mi>L</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54eb1454236e7cb0c252068d56917c419304abea" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:26.548ex; height:3.176ex;" alt="{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}"/></span></dd></dl>
<p>باستخدام الضرب القائم على FFT (انظر <a href="/wiki/%D8%B1%D9%85%D8%B2_O_%D8%A7%D9%84%D9%83%D8%A8%D9%8A%D8%B1" title="رمز O الكبير">رمز O الكبير</a> ).
</p><p>تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في <a href="/wiki/%D8%B7%D8%B1%D9%8A%D9%82%D8%A9_%D8%A7%D9%84%D8%AA%D8%A8%D8%B3%D9%8A%D8%B7_(%D8%A8%D8%B1%D9%85%D8%AC%D8%A9)" title="طريقة التبسيط (برمجة)">طريقة simplex</a> ، لكنه يتحرك بداخل المنطقة الممكنة ، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار ، والوصول إلى الحل الأمثل مع البيانات المنطقية. <sup id="cite_ref-Strang_1-0" class="reference"><a href="#cite_note-Strang-1">[1]</a></sup>
</p>
<div id="toc" class="toc"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="ar" dir="rtl"><h2>محتويات</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#الخوارزمية"><span class="tocnumber">1</span> <span class="toctext">الخوارزمية</span></a></li>
<li class="toclevel-1 tocsection-2"><a href="#مثال"><span class="tocnumber">2</span> <span class="toctext">مثال</span></a></li>
<li class="toclevel-1 tocsection-3"><a href="#جدل_براءات_الاختراع"><span class="tocnumber">3</span> <span class="toctext">جدل براءات الاختراع</span></a></li>
<li class="toclevel-1 tocsection-4"><a href="#المراجع"><span class="tocnumber">4</span> <span class="toctext">المراجع</span></a></li>
</ul>
</div>
<h2><span id=".D8.A7.D9.84.D8.AE.D9.88.D8.A7.D8.B1.D8.B2.D9.85.D9.8A.D8.A9"></span><span class="mw-headline" id="الخوارزمية">الخوارزمية</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&action=edit&section=1" title="عدل القسم: الخوارزمية">عدل</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>بالنظر في مشكلة البرمجة الخطية في شكل المصفوفة:
</p>
<table>
<tbody><tr>
<td colspan="2">تعظيم <span class="texhtml" dir="ltr" style="white-space: nowrap;"><i>c</i><sup>T</sup><i>x</i></span>
</td></tr>
<tr>
<td>تخضع الى
</td>
<td><span class="texhtml" dir="ltr" style="white-space: nowrap;"><i>Ax</i> ≤ <i>b</i></span> .
</td></tr>
</tbody></table>
<p>تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل <span class="texhtml" dir="ltr" style="white-space: nowrap;">0 < γ ≤ 1</span>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2">[2]</a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3">[3]</a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4">[4]</a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5">[5]</a></sup>
</p><p>وسع كامارك الطريقة <sup id="cite_ref-6" class="reference"><a href="#cite_note-6">[6]</a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7">[7]</a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8">[8]</a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9">[9]</a></sup> ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10">[10]</a></sup>
</p><p><br />
</p>
<h2><span id=".D9.85.D8.AB.D8.A7.D9.84"></span><span class="mw-headline" id="مثال">مثال</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&action=edit&section=2" title="عدل القسم: مثال">عدل</a><span class="mw-editsection-bracket">]</span></span></h2>
<div class="thumb tleft"><div class="thumbinner" style="width:202px;"><a href="/wiki/%D9%85%D9%84%D9%81:Karmarkar.svg" class="image"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Karmarkar.svg/200px-Karmarkar.svg.png" decoding="async" width="200" height="150" class="thumbimage" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Karmarkar.svg/300px-Karmarkar.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Karmarkar.svg/400px-Karmarkar.svg.png 2x" data-file-width="720" data-file-height="540" /></a> <div class="thumbcaption"><div class="magnify"><a href="/wiki/%D9%85%D9%84%D9%81:Karmarkar.svg" class="internal" title="كبّر"></a></div>مثال الحل</div></div></div>
<p>بالنظر في البرنامج الخطي
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="left right center left right" rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mtext>maximize</mtext>
</mrow>
</mtd>
<mtd>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mtext>subject to</mtext>
</mrow>
</mtd>
<mtd>
<mn>2</mn>
<mi>p</mi>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mo>≤<!-- ≤ --></mo>
</mtd>
<mtd>
<msup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo>+</mo>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mi>p</mi>
<mo>=</mo>
<mn>0.0</mn>
<mo>,</mo>
<mn>0.1</mn>
<mo>,</mo>
<mn>0.2</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mn>0.9</mn>
<mo>,</mo>
<mn>1.0.</mn>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e4cbde9d0991b0c33c6205d2cd8751b152ca612f" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -2.505ex; width:66.547ex; height:6.176ex;" alt="{\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}"/></span></dd></dl>
<p>حيث يوجد متغيرين <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},x_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x_{1},x_{2}}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/188263943645114e27e316cc1be787861e5b67be" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:5.802ex; height:2.009ex;" alt="{\displaystyle x_{1},x_{2}}"/></span> و 11 قيود مرتبطة باختلاف قيم <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="p"/></span> . يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء. وتظهر القيود كخطوط زرقاء.
</p>
<h2><span id=".D8.AC.D8.AF.D9.84_.D8.A8.D8.B1.D8.A7.D8.A1.D8.A7.D8.AA_.D8.A7.D9.84.D8.A7.D8.AE.D8.AA.D8.B1.D8.A7.D8.B9"></span><span class="mw-headline" id="جدل_براءات_الاختراع">جدل براءات الاختراع</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&action=edit&section=3" title="عدل القسم: جدل براءات الاختراع">عدل</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>في الوقت الذي ابتكر فيه الخوارزمية ، توظف كامارك بواسطة <a href="/wiki/%D8%A2%D9%8A_%D8%A8%D9%8A_%D8%A5%D9%85" title="آي بي إم">آي بي إم</a> كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في <a href="/wiki/%D8%AC%D8%A7%D9%85%D8%B9%D8%A9_%D8%B3%D8%AA%D8%A7%D9%86%D9%81%D9%88%D8%B1%D8%AF" title="جامعة ستانفورد">جامعة ستانفورد</a> لشرح الخوارزمية ، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في <a href="/wiki/%D8%A5%D9%8A%D9%87_%D8%AA%D9%8A_%D8%A2%D9%86%D8%AF_%D8%AA%D9%8A" title="إيه تي آند تي">إيه تي آند تي</a> وقدم مقالته إلى <a href="<a class="external free" href="https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing">https://en.wikipedia.org/wiki/Symposium_on_Theory_of_Computing</a>" rel="mw:ExtLink" data-linkid="42" class="cx-link" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه ل<a href="/wiki/%D9%85%D8%AE%D8%AA%D8%A8%D8%B1%D8%A7%D8%AA_%D8%A8%D9%84" title="مختبرات بل">مختبرات بيل</a> لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، <sup id="cite_ref-11" class="reference"><a href="#cite_note-11">[11]</a></sup> أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.
</p>
<h2><span id=".D8.A7.D9.84.D9.85.D8.B1.D8.A7.D8.AC.D8.B9"></span><span class="mw-headline" id="المراجع">المراجع</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&action=edit&section=4" title="عدل القسم: المراجع">عدل</a><span class="mw-editsection-bracket">]</span></span></h2>
<ul><li><span class="citation journal">Adler، Ilan؛ Karmarkar، Narendra؛ Resende، Mauricio G.C.؛ Veiga، Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". <i>Mathematical Programming</i>. <b>44</b> (1–3): 297–335. <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%A7%D8%B4%D9%8A%D8%A7%D8%A1_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9" class="mw-redirect" title="معرف الاشياء الرقمية">doi</a>:<a rel="nofollow" class="external text" href="//doi.org/10.1007%2Fbf01587095">10.1007/bf01587095</a>.</span><span title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&rft.atitle=An+Implementation+of+Karmarkar%27s+Algorithm+for+Linear+Programming&rft.au=Karmarkar%2C+Narendra&rft.au=Resende%2C+Mauricio+G.C.&rft.au=Veiga%2C+Geraldo&rft.aufirst=Ilan&rft.aulast=Adler&rft.date=1989&rft.genre=article&rft.issue=1%933&rft.jtitle=Mathematical+Programming&rft.pages=297-335&rft.volume=44&rft_id=info%3Adoi%2F10.1007%2Fbf01587095&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal" class="Z3988"><span style="display:none;"> </span></span><style data-mw-deduplicate="TemplateStyles:r32919374">.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}</style></li>
<li>ناريندرا كارماركار (1984). " <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf">خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية</a> " ، <i>Combinatorica</i> ، المجلد <b>4</b> ، العدد. 4 ، ص.   373 – 395.</li></ul>
<div class="reflist reflist-cols reflist-cols30em"><ol class="references">
<li id="cite_note-Strang-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Strang_1-0">^</a></b></span> <span class="reference-text"><span id="CITEREFStrang1987" class="citation journal"><a href="/w/index.php?title=Gilbert_Strang&action=edit&redlink=1" class="new" title="Gilbert Strang (الصفحة غير موجودة)">Strang، Gilbert</a> (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". <i><a href="/w/index.php?title=The_Mathematical_Intelligencer&action=edit&redlink=1" class="new" title="The Mathematical Intelligencer (الصفحة غير موجودة)">The Mathematical Intelligencer</a></i>. <b>9</b> (2): 4–10. <a href="/wiki/%D8%B1%D9%82%D9%85_%D8%AF%D9%88%D9%84%D9%8A_%D9%85%D8%B9%D9%8A%D8%A7%D8%B1%D9%8A_%D9%84%D9%84%D8%AF%D9%88%D8%B1%D9%8A%D8%A7%D8%AA" title="رقم دولي معياري للدوريات">ISSN</a> <a rel="nofollow" class="external text" href="//www.worldcat.org/issn/0343-6993">0343-6993</a>. <a href="/wiki/%D9%85%D8%A7%D8%AB%D9%85%D8%A7%D8%AA%D9%8A%D9%83%D9%84_%D8%B1%D9%8A%D9%81%D9%8A%D9%88%D8%B2" title="ماثماتيكل ريفيوز">MR</a> <a rel="nofollow" class="external text" href="//www.ams.org/mathscinet-getitem?mr=883185">883185</a>. <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%A7%D8%B4%D9%8A%D8%A7%D8%A1_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9" class="mw-redirect" title="معرف الاشياء الرقمية">doi</a>:<a rel="nofollow" class="external text" href="//doi.org/10.1007%2FBF03025891">10.1007/BF03025891</a>.</span><span title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&rft.atitle=Karmarkar%27s+algorithm+and+its+place+in+applied+mathematics&rft.aufirst=Gilbert&rft.aulast=Strang&rft.date=1987-06-01&rft.genre=article&rft.issn=0343-6993&rft.issue=2&rft.jtitle=The+Mathematical+Intelligencer&rft.pages=4-10&rft.volume=9&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D883185&rft_id=info%3Adoi%2F10.1007%2FBF03025891&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal" class="Z3988"><span style="display:none;"> </span></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r32919374"/></span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external free" href="http://dl.acm.org/citation.cfm?id=808695">http://dl.acm.org/citation.cfm?id=808695</a></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><span class="citation journal">Karmarkar، N. (1984). "A new polynomial-time algorithm for linear programming". <i>Combinatorica</i>. <b>4</b> (4): 373–395. <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%A7%D8%B4%D9%8A%D8%A7%D8%A1_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9" class="mw-redirect" title="معرف الاشياء الرقمية">doi</a>:<a rel="nofollow" class="external text" href="//doi.org/10.1007%2FBF02579150">10.1007/BF02579150</a>.</span><span title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&rft.atitle=A+new+polynomial-time+algorithm+for+linear+programming&rft.aufirst=N.&rft.aulast=Karmarkar&rft.date=1984&rft.genre=article&rft.issue=4&rft.jtitle=Combinatorica&rft.pages=373-395&rft.volume=4&rft_id=info%3Adoi%2F10.1007%2FBF02579150&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal" class="Z3988"><span style="display:none;"> </span></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r32919374"/></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><span class="citation journal">Karmarkar، Narendra K. (1989). "Power Series Variants of Karmarkar-Type Algorithms". <i>AT&T Technical Journal</i>. <b>68</b> (3): 20–36. <a href="/wiki/%D9%85%D8%B9%D8%B1%D9%81_%D8%A7%D9%84%D8%A7%D8%B4%D9%8A%D8%A7%D8%A1_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9" class="mw-redirect" title="معرف الاشياء الرقمية">doi</a>:<a rel="nofollow" class="external text" href="//doi.org/10.1002%2Fj.1538-7305.1989.tb00316.x">10.1002/j.1538-7305.1989.tb00316.x</a>.</span><span title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Far.wikipedia.org%3A%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9+%D9%83%D8%A7%D8%B1%D9%85%D8%A7%D8%B1%D9%83%D8%B1&rft.atitle=Power+Series+Variants+of+Karmarkar-Type+Algorithms&rft.aufirst=Narendra+K.&rft.aulast=Karmarkar&rft.date=1989&rft.genre=article&rft.issue=3&rft.jtitle=AT%26T+Technical+Journal&rft.pages=20-36&rft.volume=68&rft_id=info%3Adoi%2F10.1002%2Fj.1538-7305.1989.tb00316.x&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal" class="Z3988"><span style="display:none;"> </span></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r32919374"/></span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).</span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)</span>
</li>
<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).</span>
</li>
<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).</span>
</li>
<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).</span>
</li>
<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010</span>
</li>
<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).</span>
</li>
</ol></div>
<!--
NewPP limit report
Parsed by mw1339
Cached time: 20190903131611
Cache expiry: 2592000
Dynamic content: false
Complications: [vary‐revision‐sha1]
CPU time usage: 0.188 seconds
Real time usage: 0.309 seconds
Preprocessor visited node count: 408/1000000
Preprocessor generated node count: 0/1500000
Post‐expand include size: 12413/2097152 bytes
Template argument size: 58/2097152 bytes
Highest expansion depth: 4/40
Expensive parser function count: 0/500
Unstrip recursion depth: 1/20
Unstrip post‐expand size: 14975/5000000 bytes
Number of Wikibase entities loaded: 0/400
Lua time usage: 0.108/10.000 seconds
Lua memory usage: 2.74 MB/50 MB
-->
<!--
Transclusion expansion time report (%,ms,calls,template)
100.00% 177.254 1 -total
86.76% 153.786 4 قالب:Cite_journal
18.07% 32.024 1 قالب:مراجع
2.08% 3.692 3 قالب:Math
-->
</div>' |
ما إذا كان التعديل قد تم عمله من خلال عقدة خروج تور (tor_exit_node) | false |
طابع زمن التغيير ليونكس (timestamp) | 1567516589 |