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

Linear Programming

البرمجة الخطية هي فرع من الاستمثال الرياضي وهذا الفرع يبحث في إيجاد النقاط المثلى لدالة معينة وفق قيود (constraints) معينة.
البرمجة الخطية هي حالة خاصة جداً بحيث أن الدالة هي خطية والقيود عبارات عن متراجحات خطية .
ولها تطبيقات كثيرة ،
مثلاً في متغيرين $x_1,x_2$ نريد أن نجد أصغر قيمة للمقدار $c_1x_1 + c_2 x_2$ ولكن بشرط أن يحقق الحل المتراجحات التالية:

$\begin{array}{l}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{array}$

في حالة متغيرين في مجموعة حل نظام المتراجحات تكون عادة محددة بمضلع ما . والمبرهنة^[م] الرئيسة للبرمجة الخطية هي أن النقطة المثلى (إن وجدت) هي أحد رؤوس المضلع!

يمكن تعميمها لـ n من المتغيرات بـ m من المتراجحات .
لتكن $c,x \in \mathbb R^n , b \in \mathbb R^m, A \in \mathbb R^{m \times n}$

فإن مسألة البرمجة الخطية تصاغ بالشكل المصفوفي المختصر:

$\begin{array}{ll}\mbox{minimize} & c^T x \\ \mbox{subject to} & Ax \leq b \end{array}$

تكون مجموعة حل نظام المتباينات عبارة فوق-مسطح polytope في الفضاء $\mathbb R^n$ ، وتكون النقطة المثلى إن وجدت أحد رؤوس فوق-المسطح.
وتسمى هذه المنطقة المحصورة بالمسطح بالمجموعة الممكنة feasible set ، وإن كانت المجموعة خالية فإن المسألة غير ممكنة infeasible .

لذا يجب البحث عن النقطة المثلى عبر رؤوس هذا المسطح والتي قد يكون عددها كبيراً عندما تكون n بالمئات أو الآلاف.

خوارزمية السبملكس (simplex algorithm) هي خوارزمية لحل مسائل البرمجة الخطية ، ولذا كانت طريقة simplex طريقة منظمة للبحث عن النقطة المثلى. وقد طورها George Dantzig عام 1948 .

ما زال في طور الإنشاء

نبذة عن كاتب الموضوع

$User picture$

علي ، عضو مؤسس في شبكة رمز

هنالك نقص في شرحك لموضوع

قدم بواسطة مهند البغدادي في جمعة, 08/28/2009 - 11:01

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

رد

اتمنى توضيح ان البرمجه

قدم بواسطة Anonymous في ثلاثاء, 05/04/2010 - 18:53

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

رد

علِّق

التعليق: *

Every instance heading tags will be modified to include an id attribute for anchor linking.
Every instance of "" in the input text will be replaced with a collapsible mediawiki-style table of contents. Accepts options for title, list style, minimum heading level, and maximum heading level as follows: . All arguments are optional and defaults are shown.
وسوم html المسموح بها: <a> <i> <p> <b> <center> <em> <strong> <code> <ul> <ol> <li> <dl> <dt> <div> <dir> <span> <br> <br /> <blockquote> <h1> <h2> <h3> <h4> <h5> <h6> <hr> <img> <sub> <sup> <table> <tbody> <thead> <tr> <td>
LaTeX formulas are automatically converted into images.
تتحول مسارات مواقع وب و عناوين البريد الإلكتروني إلى روابط آليا.
Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.
Use [# ...] to insert automatically numbered footnotes. Textile variant.
Web page addresses and e-mail addresses turn into links automatically. (Better URL filter.)
Link to content with [[some text]], where "some text" is the title of existing content or the title of a new piece of content to create. You can also link text to a different title by using [[link to this title|show this text]]. Link to outside URLs with [[http://www.example.com|some text]], or even [[http://www.example.com]].
Glossary terms will be automatically marked with links to their descriptions. If there are certain phrases or sections of text that should be excluded from glossary marking and linking, use the special markup, [no-glossary] ... [/no-glossary]. Additionally, these HTML elements will not be scanned: a, abbr, acronym, code, pre.
Images can be added to this post.

معلومات أكثر عن خيارات التنسيق

كلمة التحقق

This question is for testing whether you are a human visitor and to prevent automated spam submissions.