البرمجة الخطية

الموسوعة الحرة
تمثيل بياني لبرنامج خطي بسيط بمتغيرين وستة متباينات. مجموعة الحلول الممكنة ممثلة باللون الأصفر وتشكل مضلعًا ثنائي الأبعاد . تقع القيمة المثلى لدالة التكلفة الخطية عند نقطة تقاطع الخط الأحمر مع المضلع. يمثل الخط الأحمر مستوى دالة التكلفة، ويشير السهم إلى اتجاه التحسين.
المنطقة المغلقة الممكنة لمسألة ذات ثلاثة متغيرات هي متعدد السطوح المحدب . أما الأسطح التي تعطي قيمة ثابتة لدالة الهدف فهي مستويات (غير موضحة). وتتمثل مسألة البرمجة الخطية في إيجاد نقطة على متعدد السطوح تقع على المستوى ذي أعلى قيمة ممكنة.

البرمجة الخطية ( LP )، وتُسمى أيضاً التحسين الخطي ، هي طريقة لتحقيق أفضل النتائج (مثل أقصى ربح أو أقل تكلفة) في نموذج رياضي تُمثل متطلباته وأهدافه بعلاقات خطية . وتُعد البرمجة الخطية حالة خاصة من البرمجة الرياضية (المعروفة أيضاً بالتحسين الرياضي ).

بصورة أدق، البرمجة الخطية هي أسلوب لتحسين دالة هدف خطية ، تخضع لقيود المساواة والمتباينة الخطية . تُعرف منطقة الحلول الممكنة بمضلع محدب ، وهو مجموعة تُعرَّف بأنها تقاطع عدد محدود من أنصاف الفضاءات ، يُعرَّف كل منها بمتباينة خطية . دالة الهدف هي دالة خطية حقيقية القيم مُعرَّفة على هذا المضلع. تجد خوارزمية البرمجة الخطية نقطة في المضلع حيث تكون لهذه الدالة أكبر (أو أصغر) قيمة، إن وُجدت.

البرامج الخطية هي مسائل يمكن التعبير عنها بالشكل القياسي كما يلي:

ابحث عن متجهxالذي يحقق أقصى قدرجتيxرهناً بـأx≤بوx≥0.{\displaystyle {\begin{aligned}&{\text{ابحث عن ناقل}}&&\mathbf {x} \\&{\text{الذي يزيد}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{محاذاة}}}

هنا مكوناتx{\displaystyle \mathbf {x} }هي المتغيرات التي يجب تحديدها،ج{\displaystyle \mathbf {c} }وب{\displaystyle \mathbf {b} }يتم إعطاء متجهات ، وأ{\displaystyle A}هي مصفوفة معطاة . الدالة التي يُراد تعظيم قيمتها (x↦جتيx{\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} }(في هذه الحالة) تسمى دالة الهدف . القيودأx≤ب{\displaystyle A\mathbf {x} \leq \mathbf {b} }وx≥0{\displaystyle \mathbf {x} \geq \mathbf {0} }حدد متعدد السطوح المحدب الذي سيتم تحسين دالة الهدف عليه.

يمكن تطبيق البرمجة الخطية في مجالات دراسية متنوعة. فهي تُستخدم على نطاق واسع في الرياضيات، وبدرجة أقل في إدارة الأعمال والاقتصاد وبعض المسائل الهندسية. ثمة ارتباط وثيق بين البرامج الخطية، والمعادلات الذاتية، ونموذج التوازن العام لجون فون نيومان ، ونماذج التوازن الهيكلي (انظر البرنامج الخطي المزدوج لمزيد من التفاصيل). [ 1 ] [ 2 ] [ 3 ] تشمل الصناعات التي تستخدم نماذج البرمجة الخطية النقل والطاقة والاتصالات والتصنيع. وقد أثبتت جدواها في نمذجة أنواع مختلفة من المشكلات في التخطيط والتوجيه والجدولة والتخصيص والتصميم .

تاريخ

ليونيد كانتوروفيتش
جون فون نيومان

يعود تاريخ مشكلة حل نظام من المتباينات الخطية إلى ما لا يقل عن تاريخ فورييه ، الذي نشر في عام 1827 طريقة لحلها، [ 4 ] والتي سميت طريقة حذف فورييه-موتزكين باسمه.

في أواخر ثلاثينيات القرن العشرين، انكبّ عالم الرياضيات السوفيتي ليونيد كانتوروفيتش والاقتصادي الأمريكي فاسيلي ليونتيف، كلٌ على حدة، على دراسة التطبيقات العملية للبرمجة الخطية. ركّز كانتوروفيتش على جداول الإنتاج، بينما استكشف ليونتيف التطبيقات الاقتصادية. وقد ظلّ عملهما الرائد مهملاً إلى حد كبير لعقود.

كانت نقطة التحول خلال الحرب العالمية الثانية عندما برزت البرمجة الخطية كأداة حيوية. وقد استُخدمت على نطاق واسع في معالجة تحديات الحرب المعقدة، بما في ذلك الخدمات اللوجستية للنقل، وجدولة العمليات، وتخصيص الموارد. وأثبتت البرمجة الخطية جدواها في تحسين هذه العمليات مع مراعاة القيود الحاسمة مثل التكاليف وتوافر الموارد.

على الرغم من غموضها الأولي، إلا أن نجاحات الحرب العالمية الثانية دفعت البرمجة الخطية إلى دائرة الضوء. بعد الحرب، حظيت هذه الطريقة باعتراف واسع النطاق وأصبحت حجر الزاوية في مجالات متنوعة، من بحوث العمليات إلى الاقتصاد. أصبحت إسهامات كانتوروفيتش وليونتيف، التي لم تحظَ بالاهتمام الكافي في أواخر ثلاثينيات القرن العشرين، أساسيةً في نهاية المطاف لقبول البرمجة الخطية واستخدامها على نطاق أوسع في تحسين عمليات صنع القرار. [ 5 ]

في البداية ، أُهمل عمل كانتوروفيتش في الاتحاد السوفيتي . [ 6 ] وفي نفس الفترة تقريبًا، صاغ الاقتصادي الهولندي الأمريكي تي سي كوبمانز مسائل اقتصادية كلاسيكية كبرامج خطية. وتقاسم كانتوروفيتش وكوبمانز لاحقًا جائزة نوبل التذكارية في العلوم الاقتصادية عام 1975. [ 4 ] وفي عام 1941، صاغ فرانك لورين هيتشكوك أيضًا مسائل النقل كبرامج خطية، وقدم حلًا مشابهًا جدًا لطريقة سيمبلكس اللاحقة . [ 7 ] توفي هيتشكوك عام 1957، وجائزة نوبل التذكارية لا تُمنح بعد الوفاة.

بين عامي 1946 و1947، طوّر جورج ب. دانتزيغ بشكل مستقل صياغة عامة للبرمجة الخطية لاستخدامها في مسائل التخطيط في سلاح الجو الأمريكي. [ 8 ] وفي عام 1947، ابتكر دانتزيغ أيضًا طريقة السمبلكس التي عالجت، ولأول مرة بكفاءة، مسألة البرمجة الخطية في معظم الحالات. [ 8 ] عندما رتب دانتزيغ اجتماعًا مع جون فون نيومان لمناقشة طريقة السمبلكس، استنتج فون نيومان على الفور نظرية الازدواجية بإدراكه أن المسألة التي كان يعمل عليها في نظرية الألعاب مكافئة لها. [ 8 ] قدّم دانتزيغ برهانًا رسميًا في تقرير غير منشور بعنوان "نظرية في المتباينات الخطية" في 5 يناير 1948. [ 6 ] أُتيح عمل دانتزيغ للجمهور في عام 1951. وفي سنوات ما بعد الحرب، طبّقته العديد من الصناعات في تخطيطها اليومي.

كان مثال دانتزيغ الأصلي هو إيجاد أفضل توزيع لـ 70 شخصًا على 70 وظيفة. تتطلب القدرة الحاسوبية اللازمة لاختبار جميع الاحتمالات لاختيار أفضل توزيع قدرًا هائلاً من الموارد؛ إذ يتجاوز عدد التكوينات الممكنة عدد الجسيمات في الكون المرئي . مع ذلك، لا يستغرق الأمر سوى لحظة لإيجاد الحل الأمثل من خلال صياغة المشكلة كبرنامج خطي وتطبيق خوارزمية سيمبلكس . تقلل النظرية الكامنة وراء البرمجة الخطية بشكل كبير عدد الحلول الممكنة التي يجب فحصها.

أثبت ليونيد خاتشيان لأول مرة إمكانية حل مسألة البرمجة الخطية في وقت متعدد الحدود عام 1979، [ 9 ] ولكن حدث تقدم نظري وعملي أكبر في هذا المجال عام 1984 عندما قدم ناريندرا كارماركار طريقة جديدة للنقطة الداخلية لحل مسائل البرمجة الخطية. [ 10 ]

الاستخدامات

يُعدّ البرمجة الخطية مجالًا واسع الانتشار في علم التحسين لعدة أسباب. إذ يُمكن التعبير عن العديد من المشكلات العملية في بحوث العمليات على شكل مسائل برمجة خطية. [ 6 ] وتُعتبر بعض الحالات الخاصة للبرمجة الخطية، مثل مسائل تدفق الشبكات ومسائل تدفق السلع المتعددة ، ذات أهمية بالغة، ما استدعى إجراء العديد من الأبحاث حول خوارزميات متخصصة. كما تعمل العديد من الخوارزميات لأنواع أخرى من مسائل التحسين من خلال حلّ مسائل البرمجة الخطية كمسائل فرعية. تاريخيًا، ألهمت أفكار البرمجة الخطية العديد من المفاهيم الأساسية لنظرية التحسين، مثل الازدواجية والتفكيك وأهمية التحدب وتعميماته. وبالمثل، استُخدمت البرمجة الخطية بكثافة في المراحل الأولى لنشأة الاقتصاد الجزئي ، ولا تزال تُستخدم حاليًا في إدارة الشركات، مثل التخطيط والإنتاج والنقل والتكنولوجيا. ورغم أن قضايا الإدارة الحديثة دائمة التغير، فإن معظم الشركات تسعى إلى تعظيم الأرباح وتقليل التكاليف في ظل موارد محدودة. كما تستخدم جوجل البرمجة الخطية لتحسين استقرار مقاطع الفيديو على يوتيوب. [ 11 ]

النموذج القياسي

الصيغة القياسية هي الصيغة المعتادة والأكثر سهولة لوصف مسألة البرمجة الخطية. وهي تتكون من الأجزاء الثلاثة التالية:

  • دالة خطية (أو خطية تآلفية) يُراد تعظيمها
مثالو(x1،x2)=ج1x1+ج2x2{\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}
  • قيود المشكلة بالشكل التالي
مثال
أ11x1+أ12x2≤ب1أ21x1+أ22x2≤ب2أ31x1+أ32x2≤ب3{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}
  • المتغيرات غير السالبة
مثال
x1≥0x2≥0{\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}

تُصاغ المسألة عادةً في شكل مصفوفة ، ثم تصبح:

الأعلى{جتيx|x∈Rن∧أx≤ب∧x≥0}{\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}

يمكن دائمًا إعادة كتابة الأشكال الأخرى، مثل مسائل التصغير، والمسائل ذات القيود على الأشكال البديلة، والمسائل التي تتضمن متغيرات سالبة ، إلى مسألة مكافئة في شكل قياسي.

مثال

الحل البياني لمثال المزارع - بعد تظليل المناطق التي تنتهك الشروط، فإن رأس المنطقة غير المظللة مع الخط المتقطع الأبعد عن الأصل يعطي التركيبة المثلى (وقوعه على خطوط الأرض والمبيدات يعني أن الإيرادات محدودة بالأرض والمبيدات، وليس بالأسمدة).

لنفترض أن مزارعًا يمتلك قطعة أرض زراعية، ولتكن مساحتها L هكتارًا ، ينوي زراعتها إما بالقمح أو الشعير أو مزيج منهما. يمتلك المزارع F كيلوغرامًا من السماد و P كيلوغرامًا من المبيدات. يحتاج كل هكتار من القمح إلى F1 كيلوغرامًا من السماد و P1 كيلوغرامًا من المبيدات، بينما يحتاج كل هكتار من الشعير إلى F2 كيلوغرامًا من السماد و P2 كيلوغرامًا من المبيدات. لنفترض أن S1 هو سعر بيع القمح وS2 هو سعر بيع الشعير للهكتار الواحد. إذا رمزنا لمساحة الأرض المزروعة بالقمح والشعير بـ x1 و x2 على التوالي ، فإنه يمكن تعظيم الربح باختيار القيم المثلى لـ x1 و x2 . يمكن التعبير عن هذه المسألة بصيغة البرمجة الخطية القياسية التالية :

تحقيق أقصى استفادة:S1⋅x1+S2⋅x2{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}(تعظيم الإيرادات (إجمالي مبيعات القمح بالإضافة إلى إجمالي مبيعات الشعير) - الإيرادات هي "دالة الهدف").
رهناً بـ:x1+x2≤ل{\displaystyle x_{1}+x_{2}\leq L}(الحد الأقصى للمساحة الإجمالية)
F1⋅x1+F2⋅x2≤F{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}(الحد الأقصى للأسمدة)
P1⋅x1+P2⋅x2≤P{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}(الحد الأقصى للمبيدات الحشرية)
x1≥0،x2≥0{\displaystyle x_{1}\geq 0,x_{2}\geq 0}(لا يمكن زراعة منطقة سلبية).

يصبح هذا في شكل مصفوفة:

أقصى[S1S2][x1x2]{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}
رهناً بـ[11F1F2P1P2][x1x2]≤[لFP]،[x1x2]≥[00].{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}

الصيغة المعززة (الصيغة المبسطة)

يمكن تحويل مسائل البرمجة الخطية إلى صيغة مُوسّعة لتطبيق الصيغة الشائعة لخوارزمية السمبلكس . تُدخل هذه الصيغة متغيرات ركود غير سالبة لاستبدال المتباينات بمعادلات في القيود. ويمكن كتابة المسائل بعد ذلك في صيغة المصفوفة الكتلية التالية :

تحقيق أقصى استفادةz{\displaystyle z}:
[1-جتي0تي0أأنا][zxs]=[0ب]{\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&\mathbf {0} ^{\mathsf {T}}\\\mathbf {0} &\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}
x≥0،s≥0{\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {s} \geq \mathbf {0} }

أينs{\displaystyle \mathbf {s} }هي متغيرات الركود المُستحدثة،x{\displaystyle \mathbf {x} }هي متغيرات القرار، وz{\displaystyle z}المتغير الذي يجب تعظيمه.

مثال

يتم تحويل المثال أعلاه إلى الشكل الموسع التالي:

تحقيق أقصى استفادة:S1⋅x1+S2⋅x2{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}(دالة الهدف)
رهناً بما يلي:x1+x2+x3=ل{\displaystyle x_{1}+x_{2}+x_{3}=L}(قيد مُعزز)
F1⋅x1+F2⋅x2+x4=F{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}(قيد مُعزز)
P1⋅x1+P2⋅x2+x5=P{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P}(قيد مُعزز)
x1،x2،x3،x4،x5≥0.{\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}

أينx3،x4،x5{\displaystyle x_{3},x_{4},x_{5}}هي متغيرات ركود (غير سالبة)، تمثل في هذا المثال المساحة غير المستخدمة، وكمية الأسمدة غير المستخدمة، وكمية المبيدات غير المستخدمة.

يصبح هذا في شكل مصفوفة:

تحقيق أقصى استفادةz{\displaystyle z}:
[1-S1-S20000111000F1F20100P1P2001][zx1x2x3x4x5]=[0لFP]،[x1x2x3x4x5]≥0.{\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}

الازدواجية

يمكن تحويل كل مسألة برمجة خطية، والتي تُسمى المسألة الأصلية ، إلى مسألة ثنائية ، تُقدم حدًا أعلى للقيمة المثلى للمسألة الأصلية. ويمكننا التعبير عن المسألة الأصلية في شكل مصفوفة كما يلي:

قم بتعظيم c T x بشرط A x ≤ b ، x ≥ 0؛
مع المسألة الثنائية المتناظرة المقابلة ،
تقليل b T y بشرط A T y ≥ c ، y ≥ 0.

الصيغة الأولية البديلة هي:

قم بتعظيم c T x بشرط A x ≤ b ؛
مع المسألة الثنائية غير المتناظرة المقابلة ،
تقليل b T y بشرط A T y = c ، y ≥ 0.

تتمثل الفكرة الأساسية لنظرية الازدواجية في حقيقة أن (بالنسبة للثنائي المتناظر) ثنائي البرنامج الخطي المزدوج هو البرنامج الخطي الأولي الأصلي.

المتغيرات المزدوجةy{\displaystyle \mathbf {y} }يمكن فهم هذه المعاملات على أنها معاملات في توليفة خطية من المتباينات المستمدة من المسألة الأصلية، والتي تُصاغ على أمل الحصول على حدٍّ لدالة الهدف. يجب أن تكون هذه المعاملات غير سالبة، وإلا ستنعكس المتباينات، ومن ثمّ نطلبy≥0{\displaystyle \mathbf {y} \geq \mathbf {0} }إذا بالإضافة إلى ذلكج⊤≤y⊤أ{\displaystyle \mathbf {c} ^{\top }\leq \mathbf {y} ^{\top }\!A}وبناءً على ذلك ج⊤x≤y⊤أx≤y⊤ب=ب⊤y،{\displaystyle \mathbf {c} ^{\top }\mathbf {x} \leq \mathbf {y} ^{\top }\!A\mathbf {x} \leq \mathbf {y} ^{\top }\mathbf {b} =\mathbf {b} ^{\top }\mathbf {y} {\text{,}}} أي قيمة دالة الهدف المزدوجةب⊤y{\displaystyle \mathbf {b} ^{\top }\mathbf {y} }عند أي نقطة مزدوجة ممكنةy{\displaystyle \mathbf {y} }يمثل حدًا أعلى لقيمة دالة الهدف الأوليةج⊤x{\displaystyle \mathbf {c} ^{\top }\mathbf {x} }في أي نقطة أولية ممكنةx{\displaystyle \mathbf {x} }هذا هو مبدأ الازدواجية الضعيفة . تنص نظرية الازدواجية القوية على أن هذا الحد في الواقع دقيق: إذا كان للمسألة الأصلية حل أمثل، x * ، فإن المسألة المزدوجة لها أيضًا حل أمثل، y * ، و c T x * = b T y * .

قد يكون البرنامج الخطي غير محدود أو غير قابل للتنفيذ. تنص نظرية الازدواجية على أنه إذا كان البرنامج الأصلي غير محدود، فإن البرنامج الثنائي يكون غير قابل للتنفيذ وفقًا لنظرية الازدواجية الضعيفة. وبالمثل، إذا كان البرنامج الثنائي غير محدود، فلا بد أن يكون البرنامج الأصلي غير قابل للتنفيذ. مع ذلك، من الممكن أن يكون كل من البرنامج الثنائي والبرنامج الأصلي غير قابلين للتنفيذ. راجع البرنامج الخطي الثنائي لمزيد من التفاصيل والأمثلة.

ازدواجية التغطية/التعبئة

البرنامج الخطي المغطي هو برنامج خطي على الشكل التالي:

تقليل: b T y ,
مع مراعاة الشروط التالية: A T y ≥ c ، y ≥ 0 ،

بحيث تكون المصفوفة A والمتجهان b و c غير سالبين.

البرنامج الخطي المزدوج للتغطية هو برنامج خطي للتعبئة ، وهو برنامج خطي على الشكل التالي:

تعظيم: c T x ,
مع مراعاة الشروط التالية: A x ≤ b ، x ≥ 0 ،

بحيث تكون المصفوفة A والمتجهان b و c غير سالبين.

أمثلة

تُعدّ مسائل البرمجة الخطية للتغطية والتعبئة شائعةً كتقريبٍ لمسألةٍ توافقية، وهي مهمةٌ في دراسة خوارزميات التقريب . [ 12 ] على سبيل المثال، تُعتبر مسائل البرمجة الخطية المُصغّرة لمسألة تعبئة المجموعات ، ومسألة المجموعات المستقلة ، ومسألة المطابقة، مسائل برمجة خطية للتعبئة. كما تُعتبر مسائل البرمجة الخطية المُصغّرة لمسألة تغطية المجموعات ، ومسألة تغطية الرؤوس ، ومسألة المجموعة المهيمنة ، مسائل برمجة خطية للتغطية.

يُعدّ إيجاد تلوين جزئي للرسم البياني مثالاً آخر على البرمجة الخطية التغطية. في هذه الحالة، يوجد قيد واحد لكل رأس من رؤوس الرسم البياني ومتغير واحد لكل مجموعة مستقلة من رؤوس الرسم البياني.

التراخي التكميلي

يمكن الحصول على حل أمثل للمسألة الثنائية عندما يكون الحل الأمثل للمسألة الأصلية فقط معروفًا، وذلك باستخدام نظرية التراخي التكميلي. وتنص النظرية على ما يلي:

لنفترض أن x  =  ( x₁ , x₂ , ... , xₙ ) حل أولي ممكن ، وأن y = ( y₁ , y₂ , ... , yₘ ) حل ثنائي ممكن. ولنرمز إلى متغيرات الركود الأولية المقابلة بـ (w₁, w₂, ..., wₘ)، ولنرمز إلى متغيرات الركود الثنائية المقابلة بـ ( z₁ , z₂ , ... , zₙ ) . عندئذٍ ، يكون x و y مثاليين لمسألتيهما إذا وفقط إذا                 

  • x j z j  =  0، من أجل j  =  1،  2،  ...  ، n ، و 
  • w i y i  =  0، لـ i  =  1،  2،  ...  ، m . 

إذا كان المتغير الراكد رقم i في المسألة الأصلية لا يساوي صفرًا، فإن المتغير رقم i في المسألة الثنائية يساوي صفرًا. وبالمثل، إذا كان المتغير الراكد رقم j في المسألة الثنائية لا يساوي صفرًا، فإن المتغير رقم j في المسألة الأصلية يساوي صفرًا.

يُجسّد هذا الشرط الضروري للأمثلية مبدأً اقتصاديًا بسيطًا نسبيًا. ففي الصيغة القياسية (عند تحقيق أقصى قيمة)، إذا كان هناك فائض في مورد أساسي محدود (أي، توجد كميات فائضة)، فإن الكميات الإضافية من هذا المورد لا قيمة لها. وبالمثل، إذا كان هناك فائض في شرط عدم سلبية السعر (الظلي)، أي أن السعر ليس صفرًا، فلا بد من وجود إمدادات نادرة (لا توجد كميات فائضة).

نظرية

وجود الحلول المثلى

هندسياً، تحدد القيود الخطية المنطقة الممكنة ، وهي متعددة سطوح محدبة . الدالة الخطية دالة محدبة ، مما يعني أن كل قيمة صغرى محلية هي قيمة صغرى مطلقة ؛ وبالمثل، الدالة الخطية دالة مقعرة ، مما يعني أن كل قيمة عظمى محلية هي قيمة عظمى مطلقة .

ليس بالضرورة وجود حل أمثل، وذلك لسببين. أولاً، إذا كانت القيود غير متسقة، فلن يوجد حل ممكن: على سبيل المثال، لا يمكن تحقيق القيدين x  ≥  2 و x  ≤ 1 معًا؛ في هذه الحالة، نقول إن برنامج البرمجة الخطية غير قابل للتنفيذ . ثانيًا، عندما يكون متعدد السطوح غير محدود في اتجاه تدرج دالة الهدف (حيث يكون تدرج دالة الهدف هو متجه معاملات دالة الهدف)، فلن يتم الوصول إلى قيمة مثلى لأنه من الممكن دائمًا تحقيق قيمة أفضل من أي قيمة محدودة لدالة الهدف. 

الرؤوس (والأشعة) المثلى للمجسمات متعددة الأوجه

بخلاف ذلك، إذا وُجد حل ممكن وكانت مجموعة القيود محدودة، فإن القيمة المثلى تُحقق دائمًا على حدود مجموعة القيود، وذلك وفقًا لمبدأ القيمة القصوى للدوال المحدبة (أو مبدأ القيمة الدنيا للدوال المقعرة )، لأن الدوال الخطية محدبة ومقعرة في آنٍ واحد. مع ذلك، توجد حلول مثلى مختلفة لبعض المسائل؛ على سبيل المثال، تُعد مسألة إيجاد حل ممكن لنظام من المتباينات الخطية مسألة برمجة خطية تكون فيها دالة الهدف هي الدالة الصفرية (أي الدالة الثابتة التي تأخذ القيمة صفر في كل مكان). في هذه المسألة المتعلقة بإمكانية الحل، إذا وُجد حلان مختلفان، فإن كل توليفة محدبة من الحلول تُعد حلاً.

تُسمى رؤوس متعدد السطوح أيضًا بالحلول الممكنة الأساسية . والسبب وراء هذا الاسم هو كما يلي: لنفترض أن d يُمثل عدد المتغيرات. عندئذٍ، تنص النظرية الأساسية للمتباينات الخطية (بالنسبة للمسائل الممكنة) على أنه لكل رأس x * في منطقة الحلول الممكنة للبرمجة الخطية، توجد مجموعة من d (أو أقل) من قيود المتباينات من البرمجة الخطية، بحيث يكون الحل الوحيد هو x * عند التعامل مع هذه القيود d كمعادلات . وبالتالي، يمكننا دراسة هذه الرؤوس من خلال النظر إلى مجموعات فرعية معينة من مجموعة جميع القيود (مجموعة منفصلة)، بدلاً من سلسلة حلول البرمجة الخطية المتصلة. هذا المبدأ هو أساس خوارزمية السمبلكس لحل البرامج الخطية.

الخوارزميات

في مسائل البرمجة الخطية، تُنتج سلسلة من القيود الخطية منطقة محدبة من القيم الممكنة لتلك المتغيرات. في حالة المتغيرين، تكون هذه المنطقة على شكل مضلع بسيط محدب .

خوارزميات تبادل الأساس

خوارزمية سيمبلكس لدانتزيج

تُحل خوارزمية السمبلكس ، التي طورها جورج دانتزيج عام 1947، مسائل البرمجة الخطية عن طريق بناء حل ممكن عند رأس من رؤوس متعدد السطوح ، ثم السير على طول مسار على حواف متعدد السطوح إلى رؤوس ذات قيم غير متناقصة لدالة الهدف حتى الوصول إلى الحل الأمثل بشكل مؤكد. في العديد من المسائل العملية، يحدث " توقف ": حيث يتم إجراء العديد من عمليات التمحور دون زيادة في دالة الهدف. [ 13 ] [ 14 ] في مسائل عملية نادرة، قد "تدور" الإصدارات المعتادة من خوارزمية السمبلكس. [ 14 ] لتجنب هذه الدورات، طور الباحثون قواعد جديدة للتمحور. [ 15 ]

عمليًا، تُعدّ خوارزمية سيمبلكس فعّالة للغاية، ويمكن ضمان إيجاد الحل الأمثل الشامل باتخاذ بعض الاحتياطات لتجنب التكرار . وقد ثبت أن خوارزمية سيمبلكس تحلّ المسائل "العشوائية" بكفاءة، أي في عدد مكعب من الخطوات، [ 16 ] وهو ما يُشابه سلوكها في المسائل العملية. [ 13 ] [ 17 ]

مع ذلك، يُظهر خوارزمية السمبلكس أداءً سيئًا في أسوأ الحالات: فقد صمّم كلي ومينتي مجموعة من مسائل البرمجة الخطية التي تتطلب فيها طريقة السمبلكس عددًا من الخطوات يتناسب أُسّيًا مع حجم المسألة. [ 13 ] [ 18 ] [ 19 ] في الواقع، لم يكن معروفًا لفترة من الزمن ما إذا كانت مسألة البرمجة الخطية قابلة للحل في وقت متعدد الحدود ، أي من فئة التعقيد P.

خوارزمية التقاطع

على غرار خوارزمية سيمبلكس لدانتزيج، تُعد خوارزمية التبادل المتقاطع خوارزمية تبادل أساسات تنتقل بين قواعد مختلفة. مع ذلك، لا يُشترط في خوارزمية التبادل المتقاطع الحفاظ على إمكانية الحل، بل يمكنها الانتقال من أساس ممكن إلى أساس غير ممكن. لا تتمتع خوارزمية التبادل المتقاطع بتعقيد زمني متعدد الحدود في البرمجة الخطية. في أسوأ الحالات، تزور كلتا الخوارزميتين جميع زوايا مكعب  (مُشوَّه) ثنائي الأبعاد في بُعد D ، وهو مكعب كلي-مينتي . [ 15 ] [ 20 ] 

خوارزمية القطع الناقص، بعد خاشيان

هذه أول خوارزمية تعمل في أسوأ الحالات بزمن متعدد الحدود تم التوصل إليها على الإطلاق للبرمجة الخطية. لحل مشكلة تحتوي على n متغيرًا ويمكن ترميزها في L بت من المدخلات، تعمل هذه الخوارزمية فييا(ن6ل){\displaystyle O(n^{6}L)}[ 9 ] حلّ ليونيد خاشيان مشكلة التعقيد هذه التي طال أمدها في عام 1979 من خلال تقديم طريقة القطع الناقص . ولتحليل التقارب سوابق (في الأعداد الحقيقية)، ولا سيما الطرق التكرارية التي طورها نعوم ز. شور وخوارزميات التقريب التي وضعها أركادي نيميروفسكي ود. يودين .

المشكلة التي يتم حلها بشكل أصلي بواسطة طريقة القطع الناقص ليست برنامجًا خطيًا "لتحقيق أقصى قيمة".ج⊤x{\displaystyle \mathbf {c} ^{\top }\mathbf {x} }منحأx≤ب،x≥0{\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} }بل إن مشكلة الجدوى هي التي تحدد ما إذا كان متعدد السطوحأx≤ب{\displaystyle A\mathbf {x} \leq \mathbf {b} }غير فارغة. لحل البرامج الخطية باستخدام اختبارات الجدوى، يتم أولاً التحقق مما إذا كانت المشكلة الأصليةأx≤ب،x≥0{\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} }ممكن (وإلا فلا يوجد حل)، وثانيًا يتم التحقق مما إذا كانت المشكلة المزدوجةأ⊤y≥ج،y≥0{\displaystyle A^{\top }\mathbf {y} \geq \mathbf {c} ,\mathbf {y} \geq \mathbf {0} }ممكن (وإلا فإن المسألة الأصلية غير محدودة، ولا يوجد حد أقصى). وأخيرًا، يتم الحصول على الحل الأمثل المطلوب من المسألة الأصلية الثنائية.x≥0،y≥0،أx≤ب،أ⊤y≥ج،ج⊤x=ب⊤y{\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {y} \geq \mathbf {0} ,A\mathbf {x} \leq \mathbf {b} ,A^{\top }\mathbf {y} \geq \mathbf {c} ,\mathbf {c} ^{\top }\mathbf {x} =\mathbf {b} ^{\top }\mathbf {y} }; يتم استخدام المزيد من اختبارات الجدوى لإزالة أو تحويل جميع المتباينات في ذلك النظام إلى معادلات، وبعد ذلك يتم إيجاد الحل عن طريق حل نظام المعادلات الخطية.

تعتمد فكرة طريقة القطع الناقص على حصر المنطقة الممكنة في سلسلة من القطع الناقصة ذات الأحجام المتناقصة. في كل خطوة تكرارية، يتم اختبار نقطة منتصف القطع الناقص للتأكد من كونها ممكنة؛ إذا كانت كذلك، تكون الإجابة "نعم". وإلا، نكتشف أن المنطقة الممكنة تقع ضمن نصف محدد من القطع الناقص، فنبحث عن قطع ناقص أصغر يحصر هذا النصف فقط، ونكرر العملية. في خوارزمية خاشيان، يوجد حد أدنى معروف لحجم المنطقة الممكنة غير الفارغة ، وهو ما يُترجم إلى حد أعلى متعدد الحدود لعدد التكرارات المطلوبة قبل التأكد من أن الإجابة "لا". لا تتداخل القطع الناقصة، بل تتناقص أحجامها فقط.

نقطة داخلية

كان لخوارزمية خاشيان أهمية بالغة في إثبات إمكانية حل البرامج الخطية في زمن متعدد الحدود. لم تُشكّل الخوارزمية طفرة حسابية، إذ تُعدّ طريقة السمبلكس أكثر كفاءة لجميع أنواع البرامج الخطية باستثناء عائلات مُصممة خصيصًا. مع ذلك، ألهمت خوارزمية خاشيان مسارات بحثية جديدة في البرمجة الخطية.

على عكس خوارزمية سيمبلكس، التي تجد الحل الأمثل من خلال اجتياز الحواف بين الرؤوس على مجموعة متعددة السطوح، تتحرك طرق النقطة الداخلية عبر الجزء الداخلي من المنطقة الممكنة.

خوارزمية كارماركار الإسقاطية

في عام 1984، اقترح ن. كارماركار طريقة إسقاطية للبرمجة الخطية. وقد حسّنت خوارزمية كارماركار [ 10 ] من الحد متعدد الحدود في أسوأ الحالات الذي وضعه خاشيان [ 9 ] (مما يعطييا(ن3.5ل){\displaystyle O(n^{3.5}L)}ادعى كارماركار أن خوارزميته أسرع بكثير في البرمجة الخطية العملية من طريقة سيمبلكس، وهو ادعاء أثار اهتمامًا كبيرًا بطرق النقاط الداخلية. [ 21 ] منذ اكتشاف كارماركار، تم اقتراح وتحليل العديد من طرق النقاط الداخلية.

خوارزمية فايديا رقم 87

في عام 1987، اقترح فايديا خوارزمية تعمل فييا(ن3){\displaystyle O(n^{3})}الوقت. [ 22 ]

خوارزمية فايديا رقم 89

في عام 1989، طور فايديا خوارزمية تعمل فييا(ن2.5){\displaystyle O(n^{2.5})}[ 23 ] من الناحية الرسمية، تستغرق الخوارزمية وقتًا أطول باستخدام خوارزميات ضرب المصفوفات السريعة . [23]يا((ن+د)1.5نل){\displaystyle O((n+d)^{1.5}nL)}العمليات الحسابية في أسوأ الحالات، حيثد{\displaystyle d}يمثل عدد القيود،ن{\displaystyle n}يمثل عدد المتغيرات، ول{\displaystyle L}هو عدد البتات.

خوارزميات زمن تباعد المدخلات

في عام 2015، أظهر لي وسيدفورد أنه يمكن حل البرمجة الخطية فييا~((ننz(أ)+د2)دل){\displaystyle {\tilde {O}}{\bigl (}(\mathrm {nnz} (A)+d^{2}){\sqrt {d}}L{\bigr )}}الوقت، [ 24 ] حيثيا~{\displaystyle {\tilde {O}}}يرمز إلى ترميز O الناعم ، وننz(أ){\displaystyle \mathrm {nnz} (A)}يمثل عدد العناصر غير الصفرية، ويظل يأخذيا(ن2.5ل){\displaystyle O(n^{2.5}L)}في أسوأ الأحوال.

خوارزمية وقت ضرب المصفوفة الحالية

في عام 2019، قام كوهين ولي وسونغ بتحسين مدة التشغيل إلىيا~((نω+ن2.5-α/2+ن2+1/6)ل){\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}وقت،ω{\displaystyle \omega }هو أس ضرب المصفوفات وα{\displaystyle \alpha }هو الأس المزدوج لضرب المصفوفات. [ 25 ]α{\displaystyle \alpha }يُعرَّف (تقريبًا) بأنه أكبر عدد يمكن ضربه فين×ن{\displaystyle n\times n}مصفوفة بواسطة أن×نα{\displaystyle n\times n^{\alpha }}المصفوفة فييا(ن2){\displaystyle O(n^{2})}في دراسة لاحقة أجراها لي وسونغ وتشانغ، توصلوا إلى النتيجة نفسها باستخدام طريقة مختلفة. [ 26 ] وظلت هاتان الخوارزميتان قائمتين .يا~(ن2+1/6ل){\displaystyle {\tilde {O}}(n^{2+1/6}L)}متىω=2{\displaystyle \omega =2}وα=1{\displaystyle \alpha =1}وقد تحسنت النتيجة بفضل جهود جيانغ، وسونغ، ووينشتاين، وتشانغ.يا~(ن2+1/6ل){\displaystyle {\tilde {O}}(n^{2+1/6}L)}ليا~(ن2+1/18ل){\displaystyle {\tilde {O}}(n^{2+1/18}L)}[ 27 ]​

مقارنة بين طرق النقطة الداخلية وخوارزميات سيمبلكس

الرأي السائد حاليًا هو أن كفاءة التطبيقات الجيدة لطرق السمبلكس وطرق النقاط الداخلية متقاربة في التطبيقات الروتينية للبرمجة الخطية. مع ذلك، بالنسبة لأنواع محددة من مسائل البرمجة الخطية، قد يكون أحد نوعي الحلول أفضل من الآخر (وأحيانًا أفضل بكثير)، وقد يختلف هيكل الحلول الناتجة عن طرق النقاط الداخلية اختلافًا كبيرًا عن تلك الناتجة عن طرق السمبلكس، حيث تكون مجموعة المتغيرات النشطة عادةً أصغر في الأخيرة. [ 28 ]

المشكلات المفتوحة والأعمال الحديثة

مشكلة لم تُحل في علوم الحاسوب
هل تسمح البرمجة الخطية بخوارزمية ذات وقت متعدد الحدود قوي؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

توجد العديد من المشكلات المفتوحة في نظرية البرمجة الخطية، والتي من شأنها أن تمثل اختراقات أساسية في الرياضيات وتقدماً كبيراً محتملاً في قدرتنا على حل البرامج الخطية واسعة النطاق.

  • هل تقبل البرمجة الخطية خوارزمية ذات زمن متعدد الحدود قوي ؟
  • هل تسمح البرمجة الخطية بخوارزمية ذات وقت متعدد الحدود لإيجاد حل تكميلي تمامًا؟
  • هل تسمح البرمجة الخطية بخوارزمية ذات وقت متعدد الحدود في نموذج الحساب ذي الأعداد الحقيقية (تكلفة الوحدة)؟

أشار ستيفن سميل إلى هذه المجموعة المترابطة من المسائل باعتبارها من بين أعظم 18 مسألة لم تُحل في القرن الحادي والعشرين. ووفقًا لسميل، فإن النسخة الثالثة من المسألة "هي المسألة الرئيسية التي لم تُحل في نظرية البرمجة الخطية". ورغم وجود خوارزميات لحل البرمجة الخطية في زمن متعدد الحدود ضعيف ، مثل طرق القطع الناقص وتقنيات النقطة الداخلية ، إلا أنه لم يتم التوصل بعد إلى خوارزميات تُتيح أداءً في زمن متعدد الحدود قوي بالنسبة لعدد القيود وعدد المتغيرات. وسيكون لتطوير مثل هذه الخوارزميات أهمية نظرية كبيرة، وربما يُتيح أيضًا مكاسب عملية في حل مسائل البرمجة الخطية الكبيرة.

على الرغم من أن فرضية هيرش قد تم دحضها مؤخراً بالنسبة للأبعاد الأعلى، إلا أنها لا تزال تترك الأسئلة التالية مفتوحة.

  • هل توجد قواعد محورية تؤدي إلى متغيرات سيمبلكس ذات وقت متعدد الحدود؟
  • هل جميع الرسوم البيانية متعددة الأوجه لها قطر محدود متعدد الحدود؟

تتعلق هذه الأسئلة بتحليل أداء وتطوير طرق مشابهة لخوارزمية سيمبلكس. تشير الكفاءة العالية لخوارزمية سيمبلكس عمليًا، على الرغم من أدائها النظري الذي يتطلب وقتًا أُسّيًا، إلى إمكانية وجود صيغ مختلفة منها تعمل في وقت متعدد الحدود أو حتى وقت متعدد الحدود بشكل كبير. سيكون من الأهمية العملية والنظرية البالغة معرفة ما إذا كانت هناك أي من هذه الصيغ، لا سيما كنهج لتحديد إمكانية حل مسائل البرمجة الخطية في وقت متعدد الحدود بشكل كبير.

تندرج خوارزمية سيمبلكس ومتغيراتها ضمن عائلة خوارزميات تتبع الحواف، التي سُميت بهذا الاسم لأنها تحل مسائل البرمجة الخطية بالانتقال من رأس إلى آخر على طول حواف متعدد السطوح. هذا يعني أن أداءها النظري محدود بالحد الأقصى لعدد الحواف بين أي رأسين على متعدد السطوح في البرمجة الخطية. ونتيجة لذلك، نهتم بمعرفة القطر النظري الأقصى لمتعددات السطوح . وقد ثبت أن جميع متعددات السطوح لها قطر شبه أسي. ويُعد دحض حدسية هيرش مؤخرًا الخطوة الأولى لإثبات ما إذا كان لأي متعدد سطوح قطر فائق كثير الحدود. إذا وُجدت أي متعددات سطوح من هذا النوع، فلن تتمكن أي من متغيرات تتبع الحواف من العمل في وقت كثير الحدود. وتُعد مسائل قطر متعدد السطوح ذات أهمية رياضية مستقلة.

تحافظ طرق المحور البسيط على إمكانية الحل الأولي (أو الثنائي). في المقابل، لا تحافظ طرق المحور المتقاطع على إمكانية الحل الأولي (أو الثنائي) ، إذ يمكنها زيارة قواعد ذات حلول أولية ممكنة، أو قواعد ذات حلول ثنائية ممكنة، أو قواعد ذات حلول أولية وثنائية غير ممكنة بأي ترتيب. وقد دُرست طرق المحور من هذا النوع منذ سبعينيات القرن الماضي. [ 29 ] وتسعى هذه الطرق أساسًا إلى إيجاد أقصر مسار محوري على متعدد السطوح الترتيبي في ظل مسألة البرمجة الخطية. وعلى عكس الرسوم البيانية متعددة السطوح، من المعروف أن رسوم متعددات السطوح الترتيبية تتميز بقطر صغير، مما يسمح بإمكانية استخدام خوارزمية المحور المتقاطع ذات الوقت متعدد الحدود القوي دون الحاجة إلى حل مسائل تتعلق بقطر متعددات السطوح العامة. [ 15 ] 

أعداد صحيحة مجهولة

إذا اشترطت جميع المتغيرات المجهولة أن تكون أعدادًا صحيحة، تُسمى المسألة حينها مسألة برمجة عددية صحيحة (IP) أو برمجة خطية عددية صحيحة (ILP). وعلى عكس البرمجة الخطية، التي يمكن حلها بكفاءة في أسوأ الحالات، فإن مسائل البرمجة العددية الصحيحة تُصنف في كثير من الحالات العملية (تلك التي تكون فيها المتغيرات محدودة) ضمن فئة NP-hard . تُعد البرمجة العددية الصحيحة الثنائية ( BIP) حالة خاصة من البرمجة العددية الصحيحة حيث يُشترط أن تكون قيم المتغيرات إما 0 أو 1 (بدلاً من أي عدد صحيح). تُصنف هذه المسألة أيضًا ضمن فئة NP-hard، وفي الواقع، كانت نسخة القرار منها إحدى مسائل كارب الـ 21 المصنفة ضمن فئة NP-complete .

إذا اقتصرت المسألة على بعض المتغيرات المجهولة التي تتطلب أن تكون أعدادًا صحيحة، فإنها تُسمى مسألة برمجة خطية مختلطة (MIP أو MILP). وتُصنف هذه المسائل عمومًا ضمن المسائل الصعبة من نوع NP، لأنها أكثر عمومية من مسائل البرمجة الخطية الصحيحة (ILP).

ومع ذلك، هناك بعض الفئات الفرعية المهمة من مشاكل البرمجة الخطية والبرمجة الخطية المختلطة التي يمكن حلها بكفاءة، وأبرزها المشاكل التي تكون فيها مصفوفة القيود أحادية المعيار تمامًا والجوانب اليمنى للقيود هي أعداد صحيحة أو - بشكل أكثر عمومية - حيث يكون للنظام خاصية التكامل الثنائي الكلي (TDI).

تتضمن الخوارزميات المتقدمة لحل البرامج الخطية الصحيحة ما يلي:

تمت مناقشة خوارزميات البرمجة العددية هذه بواسطة بادبيرج وفي بيزلي.

البرامج الخطية التكاملية

يُقال إن البرنامج الخطي في المتغيرات الحقيقية متكامل إذا كان له حل أمثل واحد على الأقل متكامل، أي يتكون من قيم صحيحة فقط ( لا ينبغي الخلط بينه وبين التكاملات ). وبالمثل، فإن متعدد السطوحP={x|أx≥0}{\displaystyle P=\{x\mid Ax\geq 0\}}يُقال إنها متكاملة إذا كان البرنامج الخطي لجميع دوال الهدف المحدودة والممكنة c{الأعلىجx|x∈P}{\displaystyle \{\max cx\mid x\in P\}}يتمتع بمستوى مثاليx*{\displaystyle x^{*}}بإحداثيات صحيحة. وكما لاحظ إدموندز وجايلز في عام 1977، يمكن القول بشكل مكافئ أن متعدد السطوحP{\displaystyle P}تكون الدالة صحيحة إذا كانت القيمة المثلى للبرنامج الخطي لكل دالة هدف صحيحة محدودة وممكنة c{الأعلىجx|x∈P}{\displaystyle \{\max cx\mid x\in P\}}هو عدد صحيح.

تُعدّ البرامج الخطية التكاملية ذات أهمية محورية في الجانب متعدد الأوجه من التحسين التوافقي ، إذ تُقدّم توصيفًا بديلًا للمسألة. تحديدًا، لأي مسألة، يكون الغلاف المحدب للحلول متعدد الأوجه تكامليًا؛ إذا كان لهذا متعدد الأوجه وصفٌ دقيق/موجز، فيمكننا إيجاد الحل الأمثل الممكن بكفاءة تحت أي هدف خطي. في المقابل، إذا استطعنا إثبات أن استرخاء البرمجة الخطية تكاملي، فإنه يُمثّل الوصف المطلوب للغلاف المحدب للحلول الممكنة (التكاملية).

لا تتسم المصطلحات بالاتساق في جميع المراجع، لذا ينبغي توخي الحذر عند التمييز بين المفهومين التاليين،

  • في برنامج خطي للأعداد الصحيحة، الموصوف في القسم السابق، يتم تقييد المتغيرات قسراً لتكون أعداداً صحيحة، وهذه المشكلة هي مشكلة صعبة من نوع NP بشكل عام.
  • في برنامج خطي متكامل، كما هو موضح في هذا القسم، لا تقتصر المتغيرات على كونها أعدادًا صحيحة، بل يتم إثبات بطريقة ما أن المشكلة المستمرة لها دائمًا قيمة مثلى متكاملة (بافتراض أن c عدد صحيح)، ويمكن إيجاد هذه القيمة المثلى بكفاءة نظرًا لأنه يمكن حل جميع البرامج الخطية ذات الحجم متعدد الحدود في وقت متعدد الحدود.

إحدى الطرق الشائعة لإثبات أن متعدد السطوح متكامل هي إظهار أنه أحادي المعامل تمامًا . توجد طرق عامة أخرى، منها خاصية التفكيك إلى أعداد صحيحة والتكامل الثنائي الكلي . ومن بين مسائل البرمجة الخطية التكاملية المعروفة الأخرى: متعدد السطوح المطابق، ومتعددات السطوح الشبكية، ومتعددات السطوح التدفقية شبه المعاملية ، وتقاطع متعددات السطوح المعممة/ متعددات السطوح المعممة- g (انظر على سبيل المثال Schrijver 2003).

برامج حل المشكلات ولغات البرمجة النصية

التراخيص المسموحة :

اسمرخصةمعلومات موجزة
جيكورخصة MITمكتبة مفتوحة المصدر لحل مسائل التحسين واسعة النطاق في البرمجة الخطية، والبرمجة التربيعية ، والبرمجة التربيعية المقترنة ، والبرمجة غير الخطية ، والبرمجة الخطية المختلطة.
غلوبأباتشي الإصدار الثانيبرنامج جوجل لحل البرمجة الخطية مفتوح المصدر
قفزةرخصة MPLلغة نمذجة مفتوحة المصدر مزودة بأدوات حل لمشاكل التحسين واسعة النطاق في البرمجة الخطية، والبرمجة التربيعية ، والبرمجة التربيعية المقيدة ، والبرمجة شبه المحددة ، والبرمجة التربيعية المتسلسلة ، والبرمجة غير الخطية ، والبرمجة الخطية المختلطة.
ojAlgoرخصة MIToj! Algorithms - ojAlgo - هو كود جافا مفتوح المصدر يتعلق بالرياضيات والجبر الخطي والتحسين.
بيوموبي إس ديلغة نمذجة مفتوحة المصدر مكتوبة بلغة بايثون، تُستخدم في عمليات التحسين الخطي، والتحسين المختلط، والتحسين غير الخطي على نطاق واسع.
SCIPأباتشي الإصدار الثانيبرنامج عام لحل مسائل البرمجة الخطية المقيدة مع التركيز على البرمجة الخطية المختلطة. متوافق مع لغة نمذجة Zimpl.
سوانشوأباتشي الإصدار الثانيمجموعة مفتوحة المصدر من خوارزميات التحسين لحل مسائل البرمجة الخطية، والبرمجة التربيعية ، والبرمجة التربيعية المخروطية ، والبرمجة شبه المحددة ، والبرمجة التربيعية المحددة في لغة جافا

تراخيص حقوق النشر المتبادلة :

اسمرخصةمعلومات موجزة
ALGLIBرخصة جنو العمومية 2+برنامج لحل المعادلات الخطية من مشروع ALGLIB ( C++ ، C# ، Python )
حلّ قيود طائر الكاسواريإل جي بي إلمجموعة أدوات لحل القيود التدريجية التي تحل بكفاءة أنظمة المعادلات والمتباينات الخطية.
CLPرخصة القيادة التجاريةبرنامج لحل المعادلات الخطية من شركة COIN-OR
glpkرخصة جنو العموميةمجموعة أدوات البرمجة الخطية GNU، وهي أداة لحل مسائل البرمجة الخطية/البرمجة الخطية المختلطة، مزودة بواجهة برمجة تطبيقات C أصلية ، بالإضافة إلى 15 غلافًا برمجيًا من جهات خارجية للغات أخرى. توفر دعمًا متخصصًا لشبكات التدفق . تتضمن المجموعة لغة النمذجة والمترجم GNU MathProg الشبيهة بلغة AMPL .
حل البرمجة الخطيةرخصة LGPL الإصدار 2.1برنامج لحل مسائل البرمجة الخطية والبرمجة الخطية المختلطة ، يدعم صيغة MPS وصيغته الخاصة "lp"، بالإضافة إلى صيغ مخصصة عبر واجهة اللغة الخارجية (XLI). [ 30 ] [ 31 ] كما يُمكن ترجمة صيغ النماذج المختلفة. [ 32 ]
كوكارخصة جنو العموميةمكتبة لحل أنظمة المعادلات الخطية بشكل تدريجي باستخدام دوال هدف متنوعة
مشروع Rرخصة جنو العموميةلغة برمجة وبيئة برمجية للحوسبة الإحصائية والرسومات

MINTO (Mixed Integer Optimizer، وهو برنامج لحل البرمجة العددية الصحيحة يستخدم خوارزمية التفرع والتقييد) لديه شفرة مصدرية متاحة للجمهور [ 33 ] ولكنه ليس مفتوح المصدر.

التراخيص الخاصة :

اسممعلومات موجزة
أهدافلغة نمذجة تسمح بنمذجة نماذج التحسين الخطية، والتحسين المختلط، والتحسين غير الخطي. كما توفر أداة لبرمجة القيود. ويمكن أيضًا تطبيق الخوارزميات، سواءً كانت استدلالية أو دقيقة، مثل خوارزمية التفرع والقطع أو توليد الأعمدة. تستدعي الأداة برنامج حل مناسبًا، مثل CPLEX أو ما شابه، لحل مسألة التحسين المطروحة. التراخيص الأكاديمية مجانية.
ALGLIBنسخة تجارية من المكتبة المرخصة بموجب حقوق النشر المفتوحة. لغات البرمجة: C++، C#، Python.
AMPLلغة نمذجة شائعة للتحسين الخطي، والتحسين المختلط للأعداد الصحيحة، والتحسين غير الخطي على نطاق واسع مع إصدار محدود مجاني متاح للطلاب (500 متغير و500 قيد).
أناليتيكالغة نمذجة عامة وبيئة تطوير تفاعلية. تُمكّن مخططات التأثير المستخدمين من صياغة المشكلات كرسوم بيانية تتضمن عقدًا لمتغيرات القرار والأهداف والقيود. يتضمن إصدار Analytica Optimizer حلولًا خطية ومختلطة وغير خطية، ويختار الحل الأنسب للمشكلة. كما يدعم محركات أخرى كإضافات، بما في ذلك XPRESS وGurobi و Artelys Knitro و MOSEK .
APMonitorواجهة برمجة تطبيقات (API) لبرامج MATLAB و Python. حل مسائل البرمجة الخطية (LP) باستخدام MATLAB أو Python أو واجهة ويب.
مجمعبرنامج حل مسائل شائع مزود بواجهة برمجة تطبيقات (API) للعديد من لغات البرمجة، كما أنه يحتوي على لغة نمذجة ويعمل مع AIMMS وAMPL و GAMS وMPL وOpenOpt وOPL Development Studio و TOMLAB . مجاني للاستخدام الأكاديمي.
دالة حل المشكلات في برنامج Excelبرنامج لحل المعادلات غير الخطية مُعدّل خصيصًا لجداول البيانات التي تعتمد فيها عمليات تقييم الدوال على إعادة حساب الخلايا. يتوفر الإصدار الأساسي كإضافة قياسية لبرنامج Excel.
FortMP
GAMS
مُحسِّن Gurobi
المكتبات الرقمية IMSLمجموعات من الخوارزميات الرياضية والإحصائية متوفرة بلغات C/C++ و Fortran و Java و C#/ .NET . تتضمن إجراءات التحسين في مكتبات IMSL عمليات تقليل غير مقيدة، ومقيدة خطيًا وغير خطيًا، وخوارزميات البرمجة الخطية.
ليندوبرنامج حل مزود بواجهة برمجة تطبيقات (API) لتحسين البرامج الخطية، والخطية الصحيحة، والتربيعية، والمخروطية، والبرامج غير الخطية العامة على نطاق واسع، مع امتدادات البرمجة العشوائية. يوفر البرنامج إجراءً للتحسين الشامل لإيجاد الحل الأمثل المضمون عالميًا للبرامج غير الخطية العامة ذات المتغيرات المستمرة والمتقطعة. كما يحتوي على واجهة برمجة تطبيقات لأخذ العينات الإحصائية لدمج محاكاة مونت كارلو في إطار عمل التحسين. يتضمن البرنامج لغة نمذجة جبرية ( LINGO ) ويتيح النمذجة داخل جدول بيانات ( What'sBest ).
خشب القيقبلغة برمجة عامة الأغراض للحوسبة الرمزية والرقمية.
MATLABلغة برمجة عامة الأغراض وموجهة نحو المصفوفات للحوسبة العددية. تتطلب البرمجة الخطية في MATLAB حزمة أدوات التحسين بالإضافة إلى منتج MATLAB الأساسي؛ وتشمل الإجراءات المتاحة INTLINPROG وLINPROG.
ماثكادمحرر رياضيات WYSIWYG ("whizzy-wig") . يحتوي على وظائف لحل مسائل التحسين الخطي وغير الخطي.
ماثيماتيكالغة برمجة عامة الأغراض للرياضيات، بما في ذلك القدرات الرمزية والرقمية.
موسكبرنامج لحل مسائل التحسين واسعة النطاق مع واجهة برمجة تطبيقات للعديد من اللغات (C++، Java، .NET، Matlab، Python).
مكتبة NAG الرقميةمجموعة من الإجراءات الرياضية والإحصائية التي طورتها مجموعة الخوارزميات العددية (NAG) للغات برمجة متعددة (C، C++، Fortran، Visual Basic ، Java، C#) وحزم برمجية (MATLAB، Excel، R ، LabVIEW ). يتضمن فصل التحسين في مكتبة NAG إجراءات لحل مسائل البرمجة الخطية ذات مصفوفات القيود الخطية المتفرقة وغير المتفرقة، بالإضافة إلى إجراءات لتحسين الدوال التربيعية وغير الخطية، ومجموع مربعات الدوال الخطية أو غير الخطية ذات القيود غير الخطية، والمحدودة أو بدون قيود. تحتوي مكتبة NAG على إجراءات للتحسين المحلي والعالمي، وللمسائل المستمرة أو الصحيحة.
أوبتيم جيهلغة نمذجة قائمة على لغة جافا لتحسين الأداء، مع توفر نسخة مجانية. [ 34 ] [ 35 ]
SAS /ORمجموعة من الحلول للتحسين الخطي، والتحسين الصحيح، والتحسين غير الخطي، والتحسين بدون مشتقات، والتحسين الشبكي، والتحسين التوافقي، والتحسين المقيد؛ ولغة النمذجة الجبرية OPTMODEL؛ ومجموعة متنوعة من الحلول الرأسية الموجهة لمشاكل/أسواق محددة، وكلها متكاملة تمامًا مع نظام SAS .
إكسبريسبرنامج لحل البرامج الخطية واسعة النطاق، والبرامج التربيعية، والبرامج غير الخطية العامة، وبرامج الأعداد الصحيحة المختلطة. يتضمن واجهة برمجة تطبيقات (API) للعديد من لغات البرمجة، بالإضافة إلى لغة نمذجة Mosel، ويعمل مع AMPL و GAMS . مجاني للاستخدام الأكاديمي.
VisSimلغة تخطيطية بصرية لمحاكاة الأنظمة الديناميكية .

انظر أيضاً

ملحوظات

  1. ↑ فون نيومان، ج. (1945). "نموذج للتوازن الاقتصادي العام". مجلة الدراسات الاقتصادية . 13 (1): 1-9 . Bibcode : 1945RvES...13....1N . doi : 10.2307/2296111 . JSTOR 2296111 . 
  2. ↑ كيميني، جي جي ؛ مورغنسترن، أو ؛ طومسون، جي إل (1956). "تعميم نموذج فون نيومان للاقتصاد المتوسع". إيكونومتريكا . 24 (2): 115-135 . doi : 10.2307/1905746 . JSTOR 1905746 . 
  3. ↑ لي، وو (2019). التوازن العام والديناميات الهيكلية: منظورات الاقتصاد الهيكلي الجديد (باللغة الصينية). بكين: دار النشر للعلوم الاقتصادية. ص 122-125 . ISBN  978-7-5218-0422-5.
  4. 1 2 جيرارد سيركسما؛ يوري زوولز (2015). التحسين الخطي والأعداد الصحيحة: النظرية والتطبيق (الطبعة الثالثة ). الصحافة اتفاقية حقوق الطفل. ص. 1. رقم ISBN   978-1498710169.
  5. ↑ "البرمجة الخطية | التعريف والحقائق | بريتانيكا" . www.britannica.com . تاريخ الاسترجاع: 20 نوفمبر 2023 .
  6. 1 2 3 جورج ب. دانتزيج (أبريل 1982). "ذكريات عن أصول البرمجة الخطية" (ملف PDF) . رسائل بحوث العمليات . 1 (2): 43-48 . doi : 10.1016/0167-6377(82)90043-8 . مؤرشف من الأصل في 20 مايو 2015.
  7. ^ ألكسندر شريفر (1998). نظرية البرمجة الخطية والأعداد الصحيحة . جون وايلي وأولاده. ص 221 – 222. ISBN  978-0-471-98232-6.
  8. 1 2 3 دانتزيج، جورج ب.؛ ثابا، موكوند نارين (1997). البرمجة الخطية . نيويورك: سبرينغر. ص. xxvii. ISBN  0387948333. OCLC 35318475 . 
  9. 1 2 3 ليونيد خاشيان (1979). “خوارزمية متعددة الحدود للبرمجة الخطية”. دوكلادي أكاديمي ناوك SSSR . 224 (5): 1093-1096 .
  10. 1 2 ناريندرا كارماركار (1984). "خوارزمية جديدة متعددة الحدود للبرمجة الخطية". كومبيناتوريكا . 4 (4): 373-395 . doi : 10.1007/BF02579150 . S2CID 7257867 . 
  11. ↑ م. غروندمان؛ ف. كواترا؛ إ. عيسى (2011). "تثبيت الفيديو الموجه تلقائيًا باستخدام مسارات كاميرا مثالية قوية من المستوى الأول". مؤتمر رؤية الحاسوب وأنماط التعرف 2011 (ملف PDF) . الصفحات 225-232 . doi : 10.1109/CVPR.2011.5995525 . ISBN  978-1-4577-0394-2. S2CID 17707171 . 
  12. ↑ فازيراني (2001 ، ص 112) 
  13. 1 2 3 دانتزيج وثابا (2003)
  14. 1 2 بادبيرغ (1999)
  15. 1 2 3 فوكودا، كومي ؛ تيرلاكي، تاماس (1997). توماس م. ليبلينغ؛ دومينيك دي ويرا (محرران). "طرق التقاطع: نظرة جديدة على خوارزميات المحور". البرمجة الرياضية، السلسلة ب . 79 ( 1-3 ): 369-395 . CiteSeerX 10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181 .   
  16. ↑ بورغواردت (1987)
  17. ↑ تود (2002)
  18. ↑ مورتي (1983)
  19. ↑ باباديميتريو وستيغليتز​
  20. ↑ روس، سي. (1990). "مثال أُسّي لقاعدة تيرلاكي المحورية لطريقة سيمبلكس المتقاطعة". البرمجة الرياضية . السلسلة أ. 46 (1): 79-84 . doi : 10.1007/BF01585729 . MR 1045573. S2CID 33463483 .  
  21. ↑ سترانج، جيلبرت (1 يونيو 1987). " خوارزمية كارماركار ومكانتها في الرياضيات التطبيقية". مجلة الرياضيات الذكية . 9 (2): 4-10 . doi : 10.1007/BF03025891 . ISSN 0343-6993 . MR 0883185. S2CID 123541868 .   
  22. ↑ فايديا، برافين م. (1987). خوارزمية للبرمجة الخطية تتطلبيا(((م+ن)ن2+(م+ن)1.5ن)ل){\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}العمليات الحسابية . الندوة السنوية الثامنة والعشرون لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب. FOCS.
  23. ↑ فايديا، برافين م. (1989). "تسريع البرمجة الخطية باستخدام ضرب المصفوفات السريع". الندوة السنوية الثلاثون حول أسس علوم الحاسوب . الندوة السنوية الثلاثون حول أسس علوم الحاسوب. FOCS. ص 332-337 . doi : 10.1109/SFCS.1989.63499 . ISBN  0-8186-1982-1.
  24. ↑ لي، ين-تات؛ سيدفورد، آرون (2015). صيانة عكسية فعالة وخوارزميات أسرع للبرمجة الخطية . FOCS '15 أسس علوم الحاسوب. arXiv : 1503.01752 .
  25. ↑ كوهين، مايكل ب.؛ لي، ين-تات؛ سونغ، تشاو (2018). حل البرامج الخطية في زمن ضرب المصفوفات الحالي . المؤتمر السنوي الحادي والخمسون لجمعية آلات الحوسبة حول نظرية الحوسبة. STOC'19. arXiv : 1810.07896 .
  26. ↑ لي، ين-تات؛ سونغ، تشاو؛ تشانغ، تشيوي (2019). حل مشكلة تقليل المخاطر التجريبية في وقت ضرب المصفوفات الحالي . مؤتمر نظرية التعلم. COLT'19. arXiv : 1905.04447 .
  27. ^ جيانغ، شونهوا؛ سونغ، تشاو؛ وينشتاين، عمري. تشانغ، هينججي (2020). مصفوفة ديناميكية أسرع معكوسة لLPs أسرع . أرخايف : 2004.07470 .
  28. ^ إليس، تيبور. ترلاكي، تاماس (2002). "طرق النقطة المحورية مقابل الطرق الداخلية: إيجابيات وسلبيات" . المجلة الأوروبية للبحوث التشغيلية . 140 (2): 170.سيتيسيركس 10.1.1.646.3539 . دوى : 10.1016/S0377-2217(02)00061-9 . 
  29. ↑ أنسترايشر، كورت م.؛ تيرلاكي، تاماس (1994). "خوارزمية سيمبلكس رتيبة للبرمجة الخطية" . بحوث العمليات . 42 (3): 556-561 . doi : 10.1287/opre.42.3.556 . ISSN 0030-364X . JSTOR 171894 .  
  30. ↑ "دليل مرجعي لـ lp_solve (5.5.2.5)" . mit.edu . تم الاطلاع عليه بتاريخ 10-08-2023 .
  31. ↑ "واجهات اللغة الخارجية" . تم الاطلاع عليه بتاريخ 3 ديسمبر 2021 .
  32. ↑ "أمر lp_solve" . تم الاطلاع عليه بتاريخ 3 ديسمبر 2021 .
  33. ↑ "COR@L – أبحاث التحسين الحسابي في جامعة ليهاي" . lehigh.edu .
  34. ↑ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf مؤرشف بتاريخ 20 يوليو 2011 في أرشيف الإنترنت (Wayback Machine). استُخدم برنامج OptimJ في نموذج تحسين لخطوط تجميع النماذج المختلطة، جامعة مونستر.
  35. ↑ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 مؤرشف بتاريخ 29-06-2011 في Wayback Machine. تم استخدام OptimJ في تقنية حساب التوازن الأمثل التقريبي للألعاب الفرعية المتكررة.

مراجع

  • كانتوروفيتش، LV (1940). "حول طريقة فعالة واحدة لحل بعض المشكلات المتطرفة من الدرجة الأولى" [ طريقة جديدة لحل بعض فئات المشكلات المتطرفة ] . دوكلادي أكاد العلوم SSSR . 28 : 211 - 214.
  • إف إل هيتشكوك: توزيع منتج من عدة مصادر إلى العديد من المواقع ، مجلة الرياضيات والفيزياء، 20، 1941، 224-230.
  • جي بي دانتزيج: تعظيم دالة خطية للمتغيرات الخاضعة للمتباينات الخطية ، 1947. نُشرت الصفحات  339-347 في كتاب تي سي كوبمانز (محرر): تحليل النشاط للإنتاج والتخصيص ، نيويورك-لندن 1951 (وايلي وتشابمان-هول).
  • جي إي بيزلي، محرر. التطورات في البرمجة الخطية والبرمجة العددية . أكسفورد ساينس، 1996. (مجموعة من الدراسات الاستقصائية)
  • بلاند، روبرت ج. (1977). "قواعد جديدة للمحورية المحدودة لطريقة سيمبلكس". رياضيات بحوث العمليات . 2 (2): 103-107 . doi : 10.1287/moor.2.2.103 . JSTOR 3689647 . 
  • بورغواردت، كارل-هاينز (1987). خوارزمية سيمبلكس: تحليل احتمالي . الخوارزميات والتوافقية. المجلد  1. سبرينغر-فيرلاغ.(السلوك المتوسط ​​في المسائل العشوائية)
  • ريتشارد دبليو. كوتل (محرر). كتاب جورج ب. دانتزيج الأساسي . منشورات ستانفورد للأعمال، مطبعة جامعة ستانفورد، ستانفورد، كاليفورنيا، 2003. (مختارات من أوراق جورج ب. دانتزيج )
  • جورج ب. دانتزيج وموكوند ن. ثابا. 1997. البرمجة الخطية 1: مقدمة . سبرينغر-فيرلاغ.
  • دانتزيج، جورج ب.؛ ثابا، موكوند ن. (2003). البرمجة الخطية 2: النظرية والتوسعات . سبرينغر-فيرلاغ.(شامل، يغطي على سبيل المثال خوارزميات المحورية والنقطة الداخلية، والمشاكل واسعة النطاق، والتفكيك وفقًا لـ Dantzig–Wolfe و Benders ، ويقدم البرمجة العشوائية .)
  • إدموندز، جاك؛ جايلز، ريك (1977). "علاقة الحد الأدنى والحد الأقصى للدوال شبه المعيارية على الرسوم البيانية". دراسات في البرمجة العددية الصحيحة . حوليات الرياضيات المتقطعة. المجلد  1. الصفحات 185-204 . doi : 10.1016/S0167-5060(08)70734-9 . ISBN  978-0-7204-0765-5.
  • فوكودا، كومي؛ تيرلاكي، تاماس (1997). توماس م. ليبلينغ؛ دومينيك دي ويرا (محرران). "طرق التقاطع: نظرة جديدة على خوارزميات المحور". البرمجة الرياضية، السلسلة ب . 79 ( 1-3 ): 369-395 . CiteSeerX 10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181 .   
  • غوندزيو، جاك؛ تيرلاكي، تاماس (1996). "3. نظرة حسابية على طرق النقطة الداخلية" . في: جيه إي بيزلي (محرر). التطورات في البرمجة الخطية والبرمجة العددية الصحيحة . سلسلة محاضرات أكسفورد في الرياضيات وتطبيقاتها. المجلد  4. نيويورك: مطبعة جامعة أكسفورد. الصفحات 103-144 . MR 1438311. ملف Postscript متاح على موقع غوندزيو الإلكتروني وعلى موقع جامعة ماكماستر الإلكتروني الخاص بتيرلاكي .  
  • مورتي، كاتا ج. (1983). البرمجة الخطية . نيويورك: جون وايلي وأولاده، ص.  482 + 19. ISBN 978-0-471-09725-9. MR 0720547 . (مرجع شامل للمناهج الكلاسيكية). 
  • إيفار د. نيرينغ وألبرت و. تاكر ، 1993، البرامج الخطية والمسائل ذات الصلة ، دار النشر الأكاديمية. (مستوى ابتدائي )
  • بادبيرج، م. (1999). التحسين الخطي والامتدادات، الطبعة الثانية . سبرينغر-فيرلاغ.(سرد مكتوب بعناية لخوارزميات سيمبلكس الأولية والثنائية وخوارزميات الإسقاط، مع مقدمة للبرمجة الخطية الصحيحة - مع عرض مشكلة البائع المتجول لأوديسيوس . )
  • باباديميتريو، كريستوس هـ .؛ ستيغليتز، كينيث. التحسين التوافقي: الخوارزميات والتعقيد (طبعة منقحة مع مقدمة جديدة  ). دوفر.(علوم الحاسوب)
  • تود، مايكل ج. (فبراير 2002). "الجوانب المتعددة للبرمجة الخطية". البرمجة الرياضية . 91 (3): 417-436 . doi : 10.1007/s101070100261 . S2CID 6464735 . (استطلاع رأي مدعو، من الندوة الدولية حول البرمجة الرياضية.)
  • فاندرباي، روبرت ج. (2001). البرمجة الخطية: الأسس والتوسعات . سبرينغر فيرلاغ.
  • فازيراني، فيجاي ف. (2001). خوارزميات التقريب . سبرينغر-فيرلاغ. رقم ISBN 978-3-540-65367-7.(علوم الحاسوب)

للمزيد من القراءة

  • ديميتريس أليفراس ومانفريد دبليو بادبيرج، التحسين الخطي والتوسعات: المشاكل والحلول ، Universitext، Springer-Verlag، 2001. (مشاكل من بادبيرج مع الحلول.)
  • دي بيرج، مارك؛ فان كريفيلد، مارك؛ أوفرمارس, مارك ; شوارزكوف، أوتفريد (2000). الهندسة الحسابية (الطبعة الثانية المنقحة  ). سبرينغر-فيرلاغ . رقم ISBN 978-3-540-65620-3.الفصل 4: البرمجة الخطية: الصفحات  63-94. يصف خوارزمية تقاطع نصف المستوى العشوائية للبرمجة الخطية.
  • مايكل ر. غاري وديفيد س. جونسون (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ISBN 978-0-7167-1045-5.A6: MP1: البرمجة العددية الصحيحة، صفحة 245. (علوم الحاسوب، نظرية التعقيد)
  • جارتنر، بيرند؛ ماتوسيك، جيري (2006). فهم واستخدام البرمجة الخطية . برلين: سبرينغر. رقم ISBN 3-540-30697-8.(مقدمة تمهيدية لعلماء الرياضيات وعلماء الحاسوب)
  • كورنيليس روس، تاماس تيرلاكي، جان فيليب فيال، طرق النقطة الداخلية للتحسين الخطي ، الطبعة الثانية، سبرينغر-فيرلاغ، 2006. (مستوى الدراسات العليا)
  • ألكسندر شريفر (2003). التحسين التوافقي: متعددات الوجوه والكفاءة . سبرينغر.
  • ألكسندر شريفر، نظرية البرمجة الخطية والأعداد الصحيحة . جون وايلي وأولاده، 1998، ISBN 0-471-98232-6(رياضي)
  • جيرارد سيركسما؛ يوري زوولز (2015). التحسين الخطي والأعداد الصحيحة: النظرية والتطبيق . الصحافة اتفاقية حقوق الطفل. رقم ISBN 978-1-498-71016-9.باستخدام أداة الحل عبر الإنترنت: https://online-optimizer.appspot.com/
  • جيرارد سيركسما؛ ديبيش غوش (2010). الشبكات في العمل: تمارين نصية وحاسوبية في تحسين الشبكات . سبرينغر. ISBN 978-1-4419-5512-8.(نمذجة التحسين الخطي)
  • إتش بي ويليامز، بناء النماذج في البرمجة الرياضية ، الطبعة الخامسة، 2013. (النمذجة)
  • ستيفن ج. رايت، 1997، طرق النقاط الداخلية الأولية-الثنائية ، SIAM. (مستوى الدراسات العليا)
  • يينيو يي ، 1997، خوارزميات النقطة الداخلية: النظرية والتحليل ، وايلي. (مستوى الدراسات العليا المتقدم)
  • زيغلر، غونتر م. ، الفصول 1-3 و6-7 في محاضرات حول متعددات الوجوه ، سبرينغر-فيرلاغ، نيويورك، 1994. (الهندسة)