برمجة خطية

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

التاريخ

خلال الحرب العالمية الثانية، وبنتيجة محدودية الموارد العسكرية، كلفت الحكومة البريطانية فريقاً من كبار العلماء دراسة مسائل كيفية توزيع مواردها العسكرية، وما يتناسب مع أفضل وضع دفاعي جوي وبري، ولقد أطلق على دراسات هذا الفريق اسم بحوث العمليات أو البحث العملياتي. ثم أخذت هذه التسمية تطلق على كافة الأبحاث والدراسات التي تتعامل مع مسائل البرمجة أو التوزيع ومسائل اتخاذ القرار. وقد حثَّت النتائج المشجعة لفريق بحوث العمليات البريطاني الإدارة العسكرية الجوية الأمريكية على تكوين فريق مشابه للقيام بالدراسات اللازمة في هذا المجال. فقد وجدت هذه الفرق أن أساليب مسائل التفضيل التقليدية، كطريقة مضاريب لاغرانج مثلاً، ليست ذات فائدة كبيرة في حل مسائل البرمجة الخطية، مما استوجب إيجاد أساليب أكثر فاعلية في عام 1947 م حين طور جورج دانتزغ Dantzig عضو الفريق الأمريكي لبحوث العمليات الطريقة المبسطة (السمبلكس) لحل مسألة البرمجة الخطية؛ لكن لم تنشر تفاصيل هذه الطريقة إلا في عام 1956م. وبعد نشر الطريقة المبسطة (السمبلكس) حدث تسارع كبير في استخدام وتطوير البرمجة الخطية. ومن المشاركات التطويرية المهمة في ذلك المجال أعمال جال Gal التي قام بها وحده أو بمشاركة آخرين معه، إذ قاموا بصَوْغ المسألة الثنائية لمسألة البرمجة الخطية. وفي أيامنا هذه نجد أن البرمجة الخطية تستخدم في مختلف المجالات الصناعية والاقتصادية والخدمية والعسكرية، وحيثما توجد عدة موارد محدودة الكمية مشتركة في تشكيل أو إنتاج سلعة أو تقديم خدمة معينة.

إن المسائل الاقتصادية أو العلمية، والتي يمكن أن تصاغ كمسألة برمجة خطية، يجب أن يتوفر فيها الأساسيات التالية:

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

2 ـ وجود عدد كبير من المتحولات أو المجاهيل التي يجب تحديد قيمها للوصول إلى الغاية المطلوبة، وتسمى هذه المتحولات بمتحولات القرار.

3 ـ وجود علاقات ارتباط خطية بين تلك المتحولات وتسمى هذه العلاقات بقيود المسألة.

إذن البرنامج الخطي هو استمثال optimization (تعظيم أو تقليل) دالَّة خطية، تحت قيود خطية. ويمكن رياضياً أن نعبر عن ذلك بالشكل التالي:

حيث المجموعة {I={1,2,...,m تعبر عن مجموعة الأدلة الكلية للقيود، والمجموعة I0 هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيود المساواة للمسألة، والمجموعة -I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أصغر أو تساوي للمسألة، والمجموعة +I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أكبر أو تساوي للمسألة.

نفترض أن التوابع

هي توابع خطية. إنه ليس قيداً إذا افترضنا أن جميع المتحولات (Xi(i=1,....,n ليست سالبة لأنه إذا وجد متحول xj يأخذ قيماً حقيقية لا على التعيين موجبة أو سالبة، يمكننا الاستعاضة عنه بالفرق -xj+- xj حيث المتحولان +xj و -xj يأخذان قيماً غير سالبة . أما إذا وجد متحول سالب من الشكل 0£ xj فإنه يمكننا أيضاً إبداله بمتحول جديد من الشكل yj=-xj.

آلية وضْع البرنامج الرياضي الخطي

لوضع البرنامج الرياضي الخطي يجب اتباع الخطوات التالية:

1 ـ تحديد المتحولات التي يجب علينا إيجاد قيمها (متحولات القرار) وتمثيلها برموز جبرية.

2 ـ تحديد جميع القيود والعلاقات الممكنة التي تربط بين هذه المتحولات، ويعبَّر عن ذلك بمعادلات خطية أو متراجحات بحيث تكون هذه القيود خطية.

3 ـ تحديد تابع الهدف وتمثيله بتابع خطي بالنسبة للمتحولات، وتحديد ما إذا كان الهدف من المسألة تعظيم التابع الهدفي أو تقليله.

ويمكننا أن نكتب البرنامج الرياضي الخطي بطريقة المصفوفات كما يلي:

حيث عدد المتحولات غير المعلومة هو n وعدد القيود m و A مصفوفة القيود m×n و c متجهة عمود بـ n مركبة و b متجهة عمود بـ m مركبة أيضاً و T يرمز إلى المنقول.

إن حل البرنامج السابق يعني إيجاد القيمة الحقيقية التي تعطي التابع قيمة أعظميه (قيمة مثلى للتابع) على منطقة القيود، التي تسمى عادة منطقة الإمكانات. أما إذا أردنا أن نفتش عن النقطة (قيم مثلى للمتحولات) من منطقة الإمكانات، والتي توافق القيمة فنكتب المسألة على الشكل التالي:

ويجب الإشارة هنا إلى أن العلاقة التالية في مسائل التفضيل دوماً صحيحة:

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

الثنائية في البرمجة الخطية

A series of linear constraints on two variables produces a region of possible values for those variables. Solvable problems will have a feasible region in the shape of a simple polygon.

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

والبرنامج الخطي الثنائي للبرنامج الرياضي الخطي التالي:

حيث

يعطى كما يلي:

حيث

إذا كان للمسألة (P) حل مثالي ولنرمز له بـ وكذلك للمسألة حل مثالي ولنرمز له بـ فعندئذ يكون لدينا.

أهم الخوارزميات لحل البرامج الرياضية الخطية

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

بـ

عملية حسابية وهي تعقيدية أسية. لكن في عام 1979م اقترح عالم روسي كاشيان (Khachian) طريقة جديدة لحل البرامج الرياضية الخطية بتعقيدية جبرية (O(n7L حيث n ترمز إلى عدد متحولات القرار و L ترمز إلى عدد البتات bits اللازمة لتوصيف معطيات الدخل للمسألة الخطية (c,b,A) وهذه الطريقة تعرف بطريقة القطوع الناقصة. إن هذه الطريقة مبنية بناء رياضياً مبدعاً، وهي تتفوق على طريقة السمبلكس نظرياً، لكن في المسائل العملية بقيت السمبلكس أكثر استعمالاً وموثوقية، لأن طريقة كاشيان لم تعط نتائج أكثر دقة وقناعة في المسائل العملية الحقيقية. في عام 1984م حصل تحول كبير في البرمجة الخطية، إذ نشر العالم الأمريكي كارماركار (Karmarkar) طريقتة الشهيرة ذات التعقيدية الجبرية (O(n3.5L وعلى ما يبدو، هذه الطريقة واعدة إذ عولج بها كثير من المسائل التطبيقية، ولا سيما في البحوث البترولية، وأعطت نتائج ممتازة. لكن مع كل هذا سيبقى أمام طريقة السمبلكس أيضاً أيام جميلة بسبب سهولتها الفائقة.

مثال1: مسألة المزج

يراد تحضير منتج ذي تركيب معين بحيث تحتوي الواحدة منه على الكميات (bi(i=1,...,m من العناصر (Bi(i=1,...,m كحد أدنى ويمكن تحضير هذا المنتج من المواد (Aj(j=1,...,n حيث تحتوي الواحدة من Aj على الكمية aij من العنصر Bi وتكلف الواحدة من Aj المبلغ cj ويراد تحضير هذا المنتج بأقل كلفة ممكنة.

يصاغ البرنامج الخطي لهذه المسألة على الشكل التالي:

مثال2: مسألة التنظيم الغذائي

اقترح طبيب على مريضه أن يتناول يومياً كحد أدنى كميات معينة bi من فيتامينات أو مقويات أساسية i=1,2,...,m)Bi) ضرورية لجسمه. يريد هذا المريض أن يحصل على هذه الفيتامينات بتناوله الخضراوات والفواكه المتوفرة في الأسواق المحلية ولنرمز لهذه المواد بـ (Aj(j=1,...,n . لنفترض أن ثمن الوحدة الواحدة (مقدرة بـ غ أو كغ او ....الخ) من المادة Aj هو cj وحدة نقدية حيث تحتوي هذه الوحدة على الكمية aij من الفيتامين الأساسي الأول Bi و a2j من الفيتامين الأساسي الثاني B2 وهكذا ...

والمطلوب في هذه المسألة تحديد الكميات (xj(j=1,...,n الواجب تناولها من المواد الغذائية من قبل المريض للحصول على تنظيم غذائي صحيح يحقق طلب الطبيب من جهة وبأقل التكاليف من جهة أخرى.

مثال3: مسألة تنظيم الإنتاج

لنفترض أن معملاً ينتج الأنواع (Aj(j=1,...,n من مادة معينة قابلة للتسويق، حيث يجري في عملية الإنتاج استخدام المواد الأولية (Bi(i=1,...,m المتوفر منها في المعمل وفي الوقت الحاضر الكميات (bi(i=1,...,m. إذا كانت الوحدة الواحدة من المنتج Aj تستهلك من المادة الأولية Bi الكمية aij وإذا كان الربح الصافي من إنتاج تلك الوحدة هو فالمطلوب تنظيم الإنتاج بحيث يحقق المعمل ربحاً أعظمياً.

أنظر ايضا

هناك كتاب ، A-level Mathematics/D1/Linear Programming، في معرفة الكتب.

Dynamic programming
Simplex algorithm, used to solve LP problems
Quadratic programming, a superset of linear programming
Leonid Kantorovich, one of the founders of linear programming
Shadow price
MPS file format
MIP example, job shop problem
INFORMS Institute for Operations Research and the Management Sciences

see also the "External links" section below

المصادر

الموسوعة العربية

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

قراءات اخرى

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 3-540-65620-0.{{cite book}}: CS1 maint: multiple names: authors list (link) Chapter 4: Linear Programming: pp.63-94. Describes a randomized half-plane intersection algorithm for linear programming.
V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37. [1]
V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45. [2]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 29: Linear Programming, pp.770-821.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP1: INTEGER PROGRAMMING, pg.245.
Bernd Gärtner, Jiří Matoušek (2006). Understanding and Using Linear Programming, Berlin: Springer. ISBN 3-540-30697-8
Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97. [3].
Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6
Michael J. Todd (February 2002). "The many facets of linear programming". Mathematical Programming 91 (3).
Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.

وصلات خارجية

Software

AIMMS Optimization Modeling AIMMS — include linear programming in industry solutions (free student license available);
Calc Optimization Solver — Kohei Yoshida’s spreadsheet add-in for OpenOffice.org Calc
CGAL — The Computational Geometry Algorithms Library includes a linear solver, which is exact and optimized for problems with few constraints or few variables
The Parma Polyhedra Library includes a MIP solver in exact precision
COIN-OR — COmputational INfrastructure for Operations Research, open-source library
GAMS — General Algebraic Modeling System
Cplex — Commercial library for linear programming
GLPK — GNU Linear Programming Kit; open source LP software
Gurobi — Parallel linear and mixed integer programming library
IMSL Numerical Libraries — Commercial libraries of math and statistical algorithms
HOPDM — Higher Order Primal Dual Method
LINDO — LP, IP, Global solver/modeling language
lp_solve — open-source solver with C library
MOSEK — Optimization software for LP,IP,QP,SOCP and MIP. Free trial is available. Free for students.
Mathematica — General technical computing system includes large scale linear programming support
OptimJ — Java-based algebraic modeling language; free evaluation version.
Premium Solver — Spreadsheet add-in
WhatsOP — LP modeling in 6 languages, made practical with easy "what-ifs" for students. Free Trial.
SAS — Includes optimization modeling language and solvers for LP, MILP, QP, and NLP
What's Best! — Spreadsheet add-in
Xpress-MP — Optimization software free to students
Vanguard Linear Programming Optimization Software
QSopt Optimization software for LP (free for research purposes).
Microarray Data Classification Server (MDCS) based on linear programming
Linear programming and linear goal programming A freeware program for MS-DOS
Simplex Method Tool A quick-loading web page
IBM's article on GLPK A technical article on GLPK with an introduction to Linear Programming by IBM
Orstat2000 — Includes easy-to-use modules for linear and integer programming (free for educational purposes).
Trilinos is a set of scientific tools with a few linear and non-linear program solvers.
TOMLAB provides optimization solvers in MATLAB, AMPL and .NET.
SCIP It can be used as a standalone program to solve mixed integer programs given in MPS Format.
GIPALS32.DLL — Linear programming callable library for Windows (free trial and academic license available).
CVXOPT — Python library that can be used for linear, second-order cone and semidefinite programming (open source, GPLv3)

الكلمات الدالة:

الحرب العالمية الثانية