مقالات

4: البرمجة الخطية - طريقة Simplex


أهداف التعلم

في هذا الفصل سوف:

  1. التحقيق في تطبيقات العالم الحقيقي للبرمجة الخطية والطرق ذات الصلة.
  2. حل مشاكل تعظيم البرمجة الخطية باستخدام طريقة simplex.
  3. حل مشاكل تصغير البرمجة الخطية باستخدام طريقة simplex.

Thumbnail: متعدد الوجوه لخوارزمية بسيطة ثلاثية الأبعاد. (CC BY-SA 3.0 ؛ Sdo عبر ويكيبيديا)


1. العام مقابل الشكل القانوني

حيث c عبارة عن متجه صف مع n من العناصر ، و x متجه عمود مع n من العناصر ، و b متجه عمود مع عناصر m (حيث m هو عدد القيود) ، و A عبارة عن مصفوفة m في n.

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


4: البرمجة الخطية - طريقة Simplex

Simplex Algorithm هي تقنية تحسين معروفة في البرمجة الخطية.
الشكل العام لـ LPP (مشكلة البرمجة الخطية) هو

  • قم ببناء المصفوفة الخاصة بك A. سوف تحتوي A على معاملات القيود.
  • سوف تحتوي المصفوفة ب على مقدار الموارد.
  • وستحتوي المصفوفة ج على معاملات دالة موضوعية أو تكلفة.

للمشكلة أعلاه & # 8211
مصفوفة أ & # 8211 عند التكرار 0

الجدول في التكرار 1

حساب الأرباح النسبية & # 8211 (Cj & # 8211 Zj) ، حيث Cj هو المعامل في Z و Z هو yi * CB
C1 & # 8211 Z1 = 1 & # 8211 (1 * 0 + 2 * 0)
C2 & # 8211 Z2 = 1 & # 8211 (1 * 0 + 1 * 0)
C3 & # 8211 Z3 = 0 & # 8211 (0 * 0 + 1 * 0)
C4 & # 8211 Z4 = 0 & # 8211 (1 * 0 + 0 * 0)

لذا فإن الأرباح النسبية هي- 1 ، 1 ، 0 ، 0 (كما هو موضح في الجدول)
من الواضح أنه ليست كل الأرباح النسبية أقل أو تساوي 0. لذلك سيتم إجراء التكرار التالي.
تحديد إدخال المتغير وترك المتغير.
أقصى ربح نسبي 1 في المؤشر 1. لذا فإن x1 سيدخل الأساس.

الحد الأدنى (8 ، 5) هو 5 الموجود في الفهرس 2. لذا فإن x3 ستترك الأساس.

منذ إدخال x1 ، نفذ عمليات الصف المطلوبة لإنشاء مصفوفة هوية.

الفهرس المحوري = [2، 4]
العنصر المحوري = 2

قسّم الصف الثاني على العنصر المحوري ، أي 2 لجعله 1.
وطرح 1 * R2 من R1 لتصبح 0
انظر الجدول التالي.

الجدول في التكرار 2

الأرباح النسبية = 0 ، 1/2 ، -1/2 ، 0
الفهرس المحوري = [1، 5]
العنصر المحوري = 1/2
قم بإجراء عمليات الصف اللازمة.
انظر الجدول التالي

يمكن أن تحدث الحالات التالية أثناء تنفيذ هذه الخوارزمية.

  • حالة 1 & # 8211 حل غير محدود
    إذا كان العمود المقابل لأقصى ربح نسبي يحتوي فقط على أرقام حقيقية غير موجبة ، فسنكون & # 8217t قادرين على إجراء اختبار النسبة الدنيا. لذلك تم الإبلاغ عنه كحل غير محدود.
  • الحالة 2 & # 8211 حل بديل
    إذا كان أي من المتغيرات غير الأساسية & # 8217 ربح نسبي في أي تكرار يساوي 0 ، فإنه يحتوي على حلول بديلة. سوف توجد العديد من الحلول المثلى.

مثال 2
المثال أعلاه كان حالة مساواة حيث تمكنا من إيجاد الأساس الأولي. الآن سنقوم بعمل بسيط على مثال لا يوجد فيه تشكيل للهوية.

قم بتحويل المشكلة أعلاه إلى شكل قياسي ، أي

حيث x3 و x4 و x5 متغيرات الركود. هذه ستشكل الهوية وبالتالي الأساس الأولي.
الجدول في التكرار 0

يستمر الآن كمثال سابق.
الجدول عند التكرار 1


مثال رقمي

النظر في المثال العددي التالي لاكتساب فهم أفضل:

مع القيود التالية:

مع إضافة متغيرات الركود للحصول على المعادلات التالية:


يمكن اشتقاق اللوحة البسيطة على النحو التالي:

في الصف الأخير ، يجب تحديد العمود الذي يحتوي على أصغر قيمة. على الرغم من وجود قيمتين أصغر ، فإن النتيجة ستكون هي نفسها بغض النظر عن أي واحدة يتم تحديدها أولاً. لهذا الحل ، يتم تحديد العمود الأول. بعد العثور على أقل معامل ، سيتم إجراء العملية المحورية من خلال البحث عن المعامل b i x 1 < displaystyle < frac <>>>>>. بما أن المعامل في الصف الأول هو 1 و 4 للصف الثاني ، يجب أن يكون الصف الأول محوريًا. ويمكن إنشاء اللوحة التالية:

بإجراء عملية الصف ، تظل كل الصفوف الأخرى (بخلاف الصف الأول) في العمود 1 أصفارًا:

نظرًا لوجود قيمة سالبة واحدة في الصف الأخير ، يجب إجراء نفس العمليات مرة أخرى. أصغر قيمة في الصف الأخير موجودة في العمود الثالث. وفي العمود الثالث ، يحتوي الصف الثاني على أصغر معاملات b i x 3 < displaystyle < frac <>>>>> وهو 1.2. وبالتالي ، سيتم اختيار الصف الثاني للتدوير. لوحة البسيط هي كالتالي:

من خلال إجراء عملية الصف لإنشاء أعمدة أخرى أعمدة ، يمكن اشتقاق ما يلي


4: البرمجة الخطية - طريقة Simplex

يستطيع Octave حل مشاكل البرمجة الخطية باستخدام دالة glpk. وهذا يعني أن أوكتاف يمكن أن يحل

تخضع للقيود الخطية أ * س = ب أين س & جنرال الكتريك 0.

تدعم وظيفة glpk أيضًا أشكال مختلفة من هذه المشكلة.

[xopt، fmin، errnum، extra] = glpk (c، A، b، lb، ub، ctype، vartype، sens، param)

قم بحل برنامج خطي باستخدام جنو GLPK مكتبة.

بالنظر إلى ثلاث حجج ، تحل glpk LP القياسي التالي:

ولكن قد يحل أيضًا مشاكل النموذج

صفيف عمود يحتوي على معاملات دالة الهدف.

مصفوفة تحتوي على معاملات القيود.

صفيف عمود يحتوي على قيمة الجانب الأيمن لكل قيد في مصفوفة القيد.

مصفوفة تحتوي على الحد الأدنى لكل متغير. إذا لم يتم توفير lb ، فإن الحد الأدنى الافتراضي للمتغيرات هو صفر.

مصفوفة تحتوي على الحد الأعلى لكل متغير. إذا لم يتم توفير ub ، فمن المفترض أن يكون الحد الأعلى الافتراضي غير محدود.

مصفوفة من الأحرف تحتوي على معنى كل قيد في مصفوفة القيد. قد يكون كل عنصر من عناصر المصفوفة أحد القيم التالية

قيد حر (غير محدود) (يتم تجاهل القيد).

قيد عدم المساواة بحد أعلى (A (i،:) * x & lt = b (i)).

قيد المساواة (A (i:) * x = b (i)).

متباينة ذات حد أدنى (A (i،:) * x & gt = b (i)).

قيد عدم المساواة مع كل من الحدود العلوية والسفلية (A (i،:) * x & gt = -b (i)) و (A (i،:) * x & lt = b (i)).

صفيف عمود يحتوي على أنواع المتغيرات.

إذا كان المعنى هو 1 ، فإن المشكلة تكمن في التصغير. إذا كان المعنى هو -1 ، فالمشكلة هي التعظيم. القيمة الافتراضية هي 1.

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

مستوى الرسائل التي يتم إخراجها من خلال إجراءات الحل:

رسائل الخطأ والتحذير فقط.

الإخراج الكامل (يشمل الرسائل الإعلامية).

خيار التحجيم. يمكن دمج القيم مع عامل تشغيل أحادي المعامل OR وقد تكون كما يلي:

عوامل المقياس الدائري للقوة اثنين.

تخطي إذا تم تحجيم المشكلة بشكل جيد.

بدلاً من ذلك ، يمكن أيضًا تحديد قيمة 128 (GLP_SF_AUTO) ، وفي هذه الحالة يختار الروتين خيارات القياس تلقائيًا.

استخدم البسيط البدائي ثنائي الطور.

استخدم ثنائي الطور البسيط ، وإذا فشل ، فانتقل إلى البسيط البدائي.

استخدم ثنائي الطور البسيط.

خيار التسعير (لكل من الأجهزة الأولية والثنائية المفرد):

حد التكرارات البسيطة. يتم تقليله بمقدار واحد في كل مرة عند إجراء تكرار مفرد واحد ، والوصول إلى القيمة الصفرية يشير إلى القائم بالحل لإيقاف البحث.

تردد الإخراج ، في التكرارات. تحدد هذه المعلمة عدد المرات التي يرسل فيها المحلل معلومات حول الحل إلى الإخراج القياسي.

خيار تقنية التفرع (لـ MIP فقط):

المتغير الكسري الأول.

ارشادي من قبل Driebeck و Tomlin.

الكلفة الزائفة الهجينة.

خيار تقنية التراجع (لـ MIP فقط):

أفضل الكشف عن مجريات الأمور.

إذا تم تعيين هذه العلامة ، فإن المحلل البسيط يستخدم المحول المسبق LP المدمج. وإلا فلن يتم استخدام المحلول المسبق LP.

حدد الحل الذي تريد استخدامه. إذا كانت المشكلة تتعلق بـ MIP ، فسيتم تجاهل هذه العلامة.

اختبار نسبة التمريرين في Harris & rsquo.

حد البحث بالمللي ثانية.

تأخير الإخراج ، بالثواني. تحدد هذه المعلمة المدة التي يجب أن يقوم الحل خلالها بتأخير إرسال معلومات حول الحل إلى الإخراج القياسي.

إذا كانت هذه المعلمة غير صفرية ، فاحفظ نسخة من المشكلة بتنسيق CPLEX LP في الملف & quotoutpb.lp & quot. لا توجد طريقة حاليًا لتغيير اسم ملف الإخراج.

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

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

يستخدم التسامح النسبي لاختيار العناصر المحورية المؤهلة للجدول البسيط. لا يوصى بتغيير هذه المعلمة إلا إذا كان لديك فهم تفصيلي للغرض منها.

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

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

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

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


4: البرمجة الخطية - طريقة Simplex

Para mis visitantes del mundo de habla hispana، este sitio se encuentra disponible en espa ol en:


طريقة Simplex هي أول خوارزمية حل لحل مشاكل LP. إنه تنفيذ فعال لحل سلسلة من أنظمة المعادلات الخطية. باستخدام استراتيجية جشعة أثناء القفز من قمة مجدية للرأس المجاور التالي ، تنتهي الخوارزمية عند الحل الأمثل. الهدف من هذا الموقع هو تعزيز فهم عملية تطوير أسلوب Simplex.

للبحث في الموقع ، جرب E dit | فهرس في الصفحة [Ctrl + f]. أدخل كلمة أو عبارة في مربع الحوار ، على سبيل المثال & quot المعلمة & quot أو & quot خطي & quot إذا لم يكن الظهور الأول للكلمة / العبارة هو ما تبحث عنه ، فجرّب F ind Next.

  • صنع القرار القيادي
  • البرمجة الخطية (LP) واستراتيجية البحث عن الهدف
  • خوارزميات حل LP الحرة المتغيرة الاصطناعية
  • تحسين عدد صحيح ونماذج الشبكة
  • أدوات التحقق من صحة نمذجة LP
  • منطقة الحساسية لنماذج LP
  • النمذجة الاحتمالية
  • محاكاة الأنظمة
  • الكلمات الرئيسية والعبارات التجارية
  • خلاصة وافية لمراجعة موقع الويب
  • مجموعة من كائنات تعلم JavaScript E-labs
  • موارد علوم القرار

مقدمة

الطريقة الجبرية:نماذج LP ذات متغيرات القرار متعددة الأبعاد

الحد الأقصى (أو الحد الأدنى)
تخضع الى:
AX & # 163 أ
BX & # 179 ب
DX = د
ربما مع بعض المتغيرات المقيدة: بعض Xi's & # 179 0 ، وبعض Xi's & # 163 0 ، وجميع الآخرين غير مقيد تسجيل الدخول.

يتم استخدام الترميز العرفي: C = بالنسبة لمعاملات الوظيفة الموضوعية (المعروفة باسم معاملات التكلفة ، لأنه تاريخيًا ، كانت مشكلة LP الأولى مشكلة تقليل التكلفة) ، و X = يستخدم لمتغيرات القرار.

فيما يلي إجراء من أربع خطوات لخوارزمية الحل الجبري:

[(إجمالي عدد المتغيرات بما في ذلك متغيرات الركود والفائض) - (عدد المعادلات)]

المتغيرات التي يجب ضبطها على الصفر هي الركود والفائض و المتغيرات المقيدة (أي Xi & # 179 0 ، أو Xi's & # 163 0) فقط. بعد ضبط هذه المتغيرات العديدة على الصفر ، ابحث عن المتغيرات الأخرى عن طريق حل نظام المعادلات التربيعي الناتج.

تذكر أن: النظام الخطي AX = b له حل إذا وفقط إذا كانت رتبة A تساوي مرتبة المصفوفة المعززة (A ، B).

يسمى كل حل لأي نظام من المعادلات الحل الأساسي (BS). تسمى BS ، والتي تكون مجدية ، بالحلول الأساسية المجدية (BFS).
في كل حل أساسي ، تسمى المتغيرات ، التي تحددها مساوية للصفر ، المتغيرات غير الأساسية (NBV) ، وتسمى جميع المتغيرات الأخرى التي تحسبها باستخدام نظام المعادلات المتغيرات الأساسية (BV).
لاحظ أن قائمة متغيرات القرار ، والتي تعتبر من أجل حل أمثل ، متاحة بسهولة في لوحة الحلول المثلى لـ QSB.

سلاك هو بقايا مورد. الفائض هو فائض الإنتاج.

عدد الحلول الأساسية: بعد تحويل جميع المتباينات إلى مساواة ، دع T = إجمالي عدد المتغيرات بما في ذلك متغيرات الركود والفائض ، E = عدد المعادلات ، و R = العدد الإجمالي لمتغيرات الركود والفائض ومتغيرات القرار المقيد ، ثم الحد الأقصى لعدد الحلول الأساسية هو:

أين ! لتقف على Factorials. على سبيل المثال ، 4! = (1) (2) (3) (4) = 24. لاحظ أنه بالتعريف 0! = 1.

لاحظ أنه إذا كانت E & gt T أو T & gt R + E ، فقد تكون صيغة LP الأولية خاطئة. تمت مناقشة علاجات الإجراءات التصحيحية في الجانب المظلم من LP: قسم أدوات التحقق من النمذجة.

النتيجة الرئيسية: إذا كانت مشكلة LP لها حدود حل (حلول) ، فإن الطريقة الجبرية تولد الحل (الحلول).

مثال 1: مشكلة بدون أي متغير مقيد:

ماكس X1 + X2
تخضع الى:
X1 + X2 & # 179 10
X1 & # 163 8
X2 & # 163 12

عند تقديم متغيرات الركود والفائض ، لدينا:

X1 + X2 - S1 = 10
X1 + S2 = 8
X2 + S3 = 12

بالنسبة لهذه المشكلة E = 3 ، T = 5 ، R = 3 ، لذلك ، هناك 3 على الأكثر! / [2! . (3 - 2)! ] = 3 حلول أساسية. لمعرفة الحلول الأساسية ، نلاحظ أن هناك 3 معادلات بها 5 مجاهيل ، مع ضبط أي 2 = 5 - 3 متغيرات الركود والفائض على صفر ، وحل أنظمة المعادلات الثلاثة الناتجة ، لدينا:

S1 S2 S3 X1 X2 X1 + X2
0 0 10 8 2 10
10 0 0 8 12 20*
0 10 0 -2 12 10

الحل الأمثل هو S1 = 10 ، S2 = 0 ، S3 = 0 ، X1 = 8 ، X2 = 12 ، مع القيمة المثلى 20.

مثال 2: مشكلة بمتغير واحد مقيد:

تُنسب المشكلة التالية إلى أندرياس إنجي وبيترا هون.

تكبير 3X1 + X2 - 4X3
تخضع الى:
X1 + X2 - X3 = 1 ،
X2 & # 179 2 ،
X1 & # 179 0

بعد إضافة متغير الفائض ، لدينا:

تكبير 3X1 + X2 - 4X3
تخضع الى:
X1 + X2 - X3 = 1 ،
X2 - S1 = 2 ،

لا يمكن حل مشكلة LP بالطريقة الرسومية. ومع ذلك ، فإن الطريقة الجبرية عامة بمعنى أنها لا تضع أي قيود على أبعاد المشكلة. لاحظ أن لدينا معادلتين بهما متغير فائض ومتغير قرار مقيد. معلمات هذه المشكلة هي: T = 4 ، R = 2 ، و E = 2. وهذا يعطي العدد الإجمالي للحلول الأساسية الممكنة: 2! / [(2!). (0!)] = 1. من خلال ضبط الفائض ومتغيرات X1 على الصفر نحصل على:

وبالتالي فإن الحل الأمثل هو X1 = 0 ، X2 = 2 ، X3 = 1 ، مع القيمة المثلى -2.

مثال 3: مشكلة النجار:

تقديم متغيرات الركود والفائض لتحويل جميع التفاوتات إلى مساواة ، لدينا:

2X1 + X2 + S1 = 40
X1 + 2X2 + S2 = 50

لدينا هنا معادلتان مع 4 مجاهيل. نظرًا لأن كلا المتغيرين X1 و X2 مقيدان ، يجب علينا تعيين أي متغيرين بما في ذلك هذين المتغيرين إلى الصفر. لحل أنظمة المعادلات الست الناتجة ، لدينا:

لذلك ، من الجدول أعلاه ، نرى أن الحل الأمثل هو S1 = 0 ، S2 = 0 ، X1 = 10 ، X2 = 20 ، مع القيمة المثلى 110 دولار.

مثال 4: مشكلة ذات قيود مختلطة:

X1 + 2X2 كحد أدنى
تخضع الى:
X1 + X2 & # 179 4
-X1 + X2 & # 163 2
X1 & # 179 0 ، و X2 غير مقيد في تسجيل الدخول.

عند تقديم متغيرات الركود والفائض ، لدينا:

X1 + X2 - S1 = 4
-X1 + X2 + S2 = 2

لدينا هنا معادلتان مع 4 مجاهيل. نظرًا لأن X1 فقط مقيد ، يجب علينا تعيين أي متغيرين من المتغيرات S1 و S2 و X1 على صفر. لحل أنظمة المعادلات الست الناتجة ، لدينا:

X1 X2 S1 S2 X1 + 2X2
0 4 0 -2 غير ممكن
0 2 -2 0 غير ممكن
1 3 0 0 7*

لذلك ، من الجدول أعلاه ، نرى أن الحل الأمثل هو X1 = 1 ، X2 = 3 ، S1 = 0 ، S2 = 0 ، مع القيمة المثلى 7.

مثال 5: مشكلة النقل:

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

مصفوفة تكلفة النقل للوحدة
D1 د 2 يتبرع
O1 20 30 200
O2 10 40 100
الطلب 150 150 300

دع Xij تشير إلى كمية الشحنة من المصدر i إلى الوجهة j. صيغة LP لمشكلة تقليل تكلفة النقل الإجمالية هي:

الحد الأدنى 20 × 11 + 30 × 12 + 10 × 21 + 40 × 22

تخضع الى:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
X12 + X22 = 150
كل Xij & # 179 0

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

الحد الأدنى 20 × 11 + 30 × 12 + 10 × 21 + 40 × 22

تخضع الى:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
كل Xij & # 179 0

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

X11 X12 X21 X22 إجمالي تكلفة النقل
0 200 150 -50
غير ممكن
200 0 -50 150 غير ممكن
150 50 0 100 8500
50 150 100 0 6500*

وبالتالي ، فإن الإستراتيجية المثلى هي X11 = 50 و X12 = 150 و X21 = 100 و X22 = 0 ، مع أقل تكلفة نقل إجمالية قدرها 6500 دولار.

مثال 6: مشكلة ذات قيود قليلة جدًا:

كمثالنا الأخير ، ضع في اعتبارك المشكلة التالية:

ماكس X1 + X2
تخضع الى:
X1 + X2 & # 163 5

تقديم متغير Slack لدينا:

معلمات هذه المشكلة هي: T = 3 ، R = 1 ، و E = 1. هذا يعطي العدد الإجمالي للحلول الأساسية الممكنة 1! / [(1!). (0!)] = 1. من خلال ضبط متغير فترة السماح على صفر ، لدينا هذه المعادلة المفردة X1 + X2 = 5 مع متغيرين يجب حلهما. لذلك ، لا توجد نقطة ركن ، علاوة على ذلك ، فإن المنطقة المجدية أيضًا غير محدودة. ومع ذلك ، فإن أي حل تعسفي مثل X1 = 0 ، X2 = 5 هو الحل الأمثل لمشكلة LP ، بقيمة مثالية تبلغ 5.

للحصول على طريقة جبرية محسّنة ، قم بزيارة موقع خوارزميات الحل لنماذج LP.


لمزيد من الأمثلة العددية والامتدادات والبراهين اقرأ المقالات التالية:

Arsham H.، Affine Geometric Method for Linear Programs، Journal of Scientific Computing، Vol. 12 ، العدد 3 ، 289-303 ، 1997.
Arsham H. ، الروابط بين نظام المعادلات الخطي ، انعكاس المصفوفة ، وروتينات برنامج الحل الخطي ، مجلة التربية الرياضية في العلوم والتكنولوجيا، المجلد. 29 ، رقم 5 ، 764-769 ، 1998.

تمحور عمليات الصف

ستكون هناك حاجة أيضًا إلى محور GJ لاحقًا خلال طريقة Simplex ، والآن هو الوقت المناسب لتطوير العادات المطلوبة في تلك الأوقات اللاحقة.

يستخدم التحويل المحوري عمليات الصف (المعروفة باسم عمليات صف جاوس-جوردان) لتغيير إدخال مصفوفة واحد (المحور) إلى "1" ، ثم تغيير كافة الإدخالات الأخرى في عمود المحور إلى قيم صفرية.

بمجرد اختيار المحور ، يجب أن تكون عمليات الصف المحورية على النحو التالي:

الخطوة 1: قم بعمل المحور "1" عن طريق قسمة الصف المحوري على الرقم المحوري

الخطوة 2: اجعل باقي الأعمدة المحورية في أعمدة صفرية عن طريق إضافة مضاعف مناسب للصف المحوري إلى كل صف.

ملاحظة: يُطلق على الرقم المتغير إلى "1" اسم Pivot ، وعادة ما يكون محاطًا بدائرة ولا يمكن أن يكون صفراً. إذا كان صفرًا ، فقم بتبادل هذا الصف بصف أسفله مع عنصر غير صفري في هذا العمود (إذا لم يكن هناك أي شيء ، يكون التحويل مستحيلًا).

مثال عددي: باستخدام عمليات الصف Gauss-Jordan ، حل نظام المعادلات التالي:

2X1 + X2 + X3 = 3
X1 + 3X3 = 1
2 × 1 + س 2 = 2

الهدف هو تحويل معاملات نظام المعادلات إلى مصفوفة الهوية التالية. النتائج على عناصر RHS (؟) توفر الحل (إن وجد).

1 0 0 ?
0 1 0 ?
0 0 1 ?
الخطوة 1. استخدم عمليات الصف عمودًا بعد عمود

أ) احصل أولاً على الرقم 1 في الصف المناسب بضربه بالمقلوب. ملاحظة: إذا كان هناك 0 في هذا الموضع ، فتبادل الصفوف مع صف أدناه بعنصر غير صفري إن أمكن.

ب) قم بتقليل جميع القيم الأخرى في العمود إلى الصفر عن طريق إضافة المضاعف المناسب للصف الذي يحتوي على 1 لكل صف.

دعنا نطبق الإجراء أعلاه على مثالنا العددي.

تدوينات: Old Row [] ، New Row <>. بوضع هاتين المصفوفتين بجانب بعضهما البعض ، تكون المصفوفة المعززة هي:


الحل هو X1 = -2 ، X2 = 6 ، X3 = 1 ، والتي يمكن التحقق منها بالتبديلات.

طريقة Simplex

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

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

    قم بتحويل LP إلى النموذج التالي:

حول مسألة التصغير إلى مشكلة تعظيم (بضرب دالة الهدف في -1).
يجب أن تكون جميع المتغيرات غير سالبة.
يجب أن تكون جميع قيم RHS غير سالبة (اضرب كلا الجانبين في -1 ، إذا لزم الأمر).
يجب أن تكون جميع القيود بصيغة & # 163 (باستثناء الشروط غير السلبية). لا توجد مساواة صارمة أو قيود & # 179.
إذا تعذر استيفاء هذا الشرط ، فاستخدم تهيئة طريقة Simplex: Articicial-Free.

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

    تحديد متغير الإدخال: المتغير المدخل هو المتغير الذي يحتوي على أكبر قيمة موجبة Cj (في حالة التعادل ، نختار المتغير الذي يتوافق مع أقصى يسار الأعمدة).

مناقشة قصيرة حول استراتيجية الأسلوب البسيط: في بداية الإجراء البسيط ، تتكون مجموعة الأساس من متغيرات الركود. تذكر أن BVS الأولى بها متغيرات الركود فقط. يعرض الصف Cj الزيادة في قيمة دالة الهدف التي ستنتج إذا تم إحضار وحدة واحدة من المتغير المقابل للعمود j إلى الأساس. يجيب هذا الصف على السؤال التالي: هل يمكننا تحسين الوظيفة الموضوعية بالانتقال إلى معيار BVS جديد؟ سوف نسميها صف المؤشر (لأنه يشير إلى ما إذا كان شرط الأمثل قد استوفى).

سيؤدي معيار إدخال متغير جديد في BVS إلى أكبر تحسين لكل وحدة للوظيفة الموضوعية. يحافظ معيار إزالة متغير من BVS الحالي على الجدوى (التأكد من أن RHS الجديد ، بعد التمحور يظل غير سلبي).

تحذير: عندما تحصل أثناء تكرارات Simplex على RHS سالب ، فهذا يعني أنك حددت متغيرًا صادرًا خاطئًا. أفضل علاج هو البدء من جديد.

لاحظ أن هناك حلًا يتوافق مع كل لوحة مفردة. العددية للمتغيرات الأساسية هي قيم RHS ، بينما المتغيرات الأخرى (المتغيرات غير الأساسية) تساوي دائمًا الصفر.

لاحظ أيضًا أن المتغيرات يمكن أن تخرج وتدخل الأساس بشكل متكرر أثناء خوارزمية simplex.

تنص الوصفات العددية على أن خوارزمية Simplex هي "دائمًا تقريبًا" O (max (N، M)) ، مما يعني أن عدد التكرار هو عامل لعدد المتغيرات أو عدد القيود ، أيهما أكبر.

التفسير الهندسي لطريقة Simplex: تبدأ الطريقة البسيطة دائمًا من الأصل (وهي نقطة الزاوية) ثم تنتقل من نقطة الزاوية إلى نقطة الزاوية المجاورة حتى تصل إلى نقطة الزاوية المثلى (إذا كانت مقيدة). لذلك ، في كل تكرار من التكرارات البسيطة ، نبحث عن حل أفضل بين رؤوس جهاز Simplex. البسيط في فضاء ذو ​​أبعاد n هو أبسط شكل به n + 1 رءوس. على سبيل المثال ، المثلث هو بسيط في فضاء ثنائي الأبعاد بينما الهرم هو بسيط في الفضاء ثلاثي الأبعاد. يمكن رؤية هذه الحركات عندما تقابل كل لوحة مفردة بنقطة زاوية محددة في الطريقة الرسومية ، على سبيل المثال. مشكلة النجار ، كما هو موضح لاحقًا.

مثال عددي: مشكلة النجار

تخضع الى:
2X1 + X2 & # 163 40
X1 + 2X2 & # 163 50
وكلاهما X1 و X2 غير سالبين.

بعد إضافة متغيري الركود S1 و S2 تكون المشكلة مكافئة لما يلي:

تخضع الى:
2X1 + X2 + S1 = 40
X1 + 2X2 + S2 = 50
والمتغيرات X1 و X2 و S1 و S2 كلها غير سالبة.

الحل الموضح في هذه اللوحة هو: S1 = 40 ، S2 = 50 ، X1 = 0 ، X2 = 0. هذا الحل هو الأصل ، كما هو موضح في الطريقة الرسومية.

هذا الجدول ليس هو الأمثل لأن بعض عناصر Cj موجبة. المتغير الوارد هو X1 والمتغير الصادر هو S1 (عن طريق اختبار C / R). العنصر المحوري موجود بين قوسين. بعد التمحور ، لدينا:

حل هذا الجدول هو: X1 = 20 ، S2 = 30 ، S1 = 0 ، X2 = 0. هذا الحل هو نقطة الزاوية (20 ، 0) ، كما هو موضح في الطريقة الرسومية.

هذا الجدول ليس هو الأمثل ، لأن بعض عناصر Cj موجبة. المتغير الوارد هو X2 والمتغير الصادر هو S2 (عن طريق اختبار C / R). العنصر المحوري موجود بين قوسين. بعد التمحور ، لدينا:

حل هذا الجدول هو: X1 = 10 ، X2 = 20 ، S1 = 0 ، و S2 = 0. هذا الحل هو نقطة الزاوية (10 ، 20) ، كما هو موضح في الطريقة الرسومية.

هذه اللوحة هي الأمثل ، لأن جميع عناصر Cj غير موجبة وكل عناصر RHS غير سلبية. الحل الأمثل هو X1 = 10 ، X2 = 20 ، S1 = 0 ، S2 = 0. لإيجاد القيمة المثلى ، عوض بهذا الحل في دالة الهدف 5X1 + 3X2 = 5 (10) + 3 (20) = 110 دولار.

ماروس آي ، التقنيات الحسابية للطريقة البسيطة ، كلوير للنشر ، 2002.

بيان حقوق النشر: يُسمح بالاستخدام العادل ، وفقًا لإرشادات الاستخدام العادل للوسائط التعليمية المتعددة لعام 1996 ، للمواد المعروضة على موقع الويب هذا للأغراض غير التجارية وأغراض الفصول الدراسية فقط.
قد يتم عكس هذا الموقع كما هو (بما في ذلك هذه الإشعارات) ، على أي خادم له وصول عام ، ومرتبط بصفحات ويب أخرى. جميع الملفات متاحة على http://home.ubalt.edu/ntsbarsh/Business-stat للنسخ المتطابق.

يرجى مراسلتي عبر البريد الإلكتروني بتعليقاتكم واقتراحاتكم واهتماماتكم. شكرا لك.

تم إطلاق هذا الموقع في 25/2/1994 م ، وتم مراجعة مواده الفكرية بشكل شامل سنويًا. الإصدار الحالي هو الإصدار الثامن. يتم فحص جميع الروابط الخارجية مرة واحدة في الشهر.


250+ أعلى MCQs حول تقنيات وإجابات التحسين

الهياكل الخرسانية سابقة الإجهاد أسئلة متعددة الخيارات حول "تقنيات التحسين".

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

2. في البرمجة الخطية ، يعتمد الحل على _________
أ) خصائص الشد
ب) خصائص الانفعال
ج) الخصائص الأولية
د) لا شيء مما ذكر
الجواب: ج
توضيح: في مشكلة البرمجة الخطية ، تكون الوظيفة الموضوعية والقيود عبارة عن وظائف خطية لمتغيرات التصميم ويستند الحل على الخصائص الأولية لأنظمة المعادلات الخطية وخصائص الأنظمة بشكل متناسب ، ويتم استخدام ميزات الجمع والقسمة والحتمية في الصيغة الرياضية لمشكلة البرمجة الخطية.

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

4. يمكن حل مشاكل البرمجة الخطية بواسطة _________
أ) طريقة بسيطة منقحة
ب) الطريقة المصنفة
ج) طريقة اشتقاق اللحظة
د) طريقة الجوف
الجواب: أ
توضيح: يمكن حل مشاكل البرمجة الخطية بشكل ملائم عن طريق طريقة simplex المنقحة وخوارزمية simplex لحل مشكلة البرمجة الخطية العامة هي إجراء تكراري ينتج عنه حل مثالي دقيق في عدد محدود من الخطوات.

5. واحدة من أقوى التقنيات لحل البرمجة غير الخطية هي تحويل _________
أ) البيانات
ب) المشاكل
ج) المواد
د) العمل
الجواب: ب
توضيح: من أقوى التقنيات لحل البرمجة غير الخطية تحويل المشكلة ببعض الوسائل إلى شكل يسمح بتطبيق خوارزمية simplex ، وبالتالي ، تبين أن الطريقة البسيطة هي واحدة من أقوى الأجهزة الحسابية لـ حل مسائل البرمجة الخطية وغير الخطية.

6. في البرمجة غير الخطية ، تكون حدود معالم الوظيفة _________
أ) الخط الموازي
ب) خطوط متعرجة
ج) خطوط مستقيمة
د) خطوط شبه منحرف
الجواب: ج
توضيح: في مسائل البرمجة غير الخطية ، تكون الوظيفة الموضوعية و / أو القيود دالة غير خطية لمتغيرات التصميم وبما أن حدود المنطقة المجدية أو ملامح القيم المتساوية لوظيفة الاستحقاق هي خطوط مستقيمة فلا يحتاج الحل الأمثل بالضرورة تكون عند تقاطع القيود.

7. إحدى التقنيات التي تم تطويرها لحل البرمجة غير الخطية هي؟
أ) البرمجة الفردية
ب) البرمجة اللغوية متعددة الخطوط
ج) البرمجة العكسية
د) البرمجة الديناميكية
الجواب: د
توضيح: على مر السنين ، تم تطوير العديد من التقنيات لحل مشاكل البرمجة غير الخطية وبعض التقنيات البارزة هي: طريقة الاتجاهات الممكنة ، وتقنية التصغير التسلسلي غير المقيد ، والبرمجة الخطية المتسلسلة ، والبرمجة الديناميكية.

8. يمكن تجميع طريقة التوجيه المجدي تحت _________
أ) الطرق المباشرة للنهج
ب) الطريقة المتسلسلة للنهج
ج) طريقة إنهاء النهج
د) طريقة المقاربة الصفائحية
الجواب: أ
توضيح: في البرمجة غير الخطية ، يمكن تجميع طريقة الاتجاه المجدي وفقًا للطرق المباشرة للنهج في مسائل التحسين المقيدة العامة غير الخطية المتباينة ، واثنين من الإجراءات المعروفة التي تجسد فلسفة طريقة الاتجاهات الممكنة هما خوارزمية Rosens gradient projection algorithum و Zountendijks إجراء.

9. أول إجراء برمجة غير خطية يتم استخدامه في أي سنة؟
أ) 1950
ب) 1940
ج) 1960
د) 1970
الجواب: ج
توضيح: ربما كانت هذه الطريقة (طريقة الاتجاه المجدي) هي أول إجراء برمجة غير خطية يتم استخدامه في مشاكل التحسين الإنشائي بواسطة schmist في عام 1960 وهذه الطريقة تبدأ من نقطة أولية ممكنة ، ويتم الوصول إلى أقرب حد والاتجاه الجديد الممكن هو تم العثور عليها ويتم اتخاذ خطوة مناسبة على طول هذا الاتجاه الممكن للحصول على نقطة التصميم الجديدة ويتكرر الإجراء حتى يتم الوصول إلى نقطة التصميم المثلى.

10. أحد العناصر التي تؤخذ في الاعتبار في اقتصاد النظام الإنشائي للخرسانة سابقة الإجهاد هو؟
أ) التحسين الهيكلي
ب) تحسين الشعاع
ج) تحسين البلاطة
د) التحسين المستعرض
الجواب: أ
Clarification: Structural optimization together with the efficient management of labour, materials and the use of new construction techniques, development and use of indigenous and new materials of construction would result in considerable economy in the overall cost of prestressed concrete structural systems.


Standard formulation

In practice, optimization problems are formulated in terms of matrices—a compact symbolism for manipulating the constraints and testing the objective function algebraically. The original (or “primal”) optimization problem was given its standard formulation by von Neumann in 1947. In the primal problem the objective is replaced by the product (px) of a vector x = (x1, x2, x3, …, xن) تي , whose components are the objective variables and where the superscript “transpose” symbol indicates that the vector should be written vertically, and another vector p = (ص1, ص2, ص3, …, صن), whose components are the coefficients of each of the objective variables. In addition, the system of inequality constraints is replaced by Ax ≤ b, where the م بواسطة ن matrix A replaces the م constraints on the ن objective variables, and b = (ب1, ب2, ب3, …, بم) تي is a vector whose components are the inequality bounds.


CE 367R - Optimization Techniques for Transportation Engineering

This assignment has four questions. The first involves writing Python code to implement the simplex method for linear programming. The remaining three involve applications of linear programming. You should solve these using your Python code, and check your answer using SciPy's optimization library. (You can access the demonstration we used in class here.)

In any of the problems below where you need to use big-م values for artificial variables, use 9999 as the value of م.

Question 1: Python code

Download these files and unzip to a convenient location, or fork this Repl.it. At the end of simplex.py you will find a function simplex which performs the simplex method on a given tableau. The "skeleton" of the simplex method is provided. What you need to do is implement three functions: one for identifying a variable with negative reduced cost to enter the basis (or to indicate that none exist and the current solution is optimal) another to identify a variable which should leave the basis to make room for the entering variable and a third to perform the arithmetic associated with a simplex pivot. These functions are selectEnteringColumn , selectLeavingRow , and pivot .

Once this is done, you can run the simplex method on a given tableau. See the file runSimplex.py for how this is done. The initial tableau can either be given explicitly, or the name of a file containing the initial values can be given. The version in hw5.zip reads from a file containing the initial tableau for the example we solved on the board in class.

This code represents tableaux as lists-of-lists. For instance, the tableau with entries

0 󔼒 󔼔 󔼔 0 0 0
20 1 2 2 1 0 0
20 2 1 2 0 1 0
20 2 2 1 0 0 1

is stored as the following list-of-lists:

Printing a list-of-lists directly in Python gives ugly results, so I've provided the prettyPrint function which tries to present the tableau in a nicer format (tab-separated columns, with each row in a different line). The function itself is provided in simplex.py , and you can see an example of how to use it in runSimplex.py .

The usual Python convention for lists is used to index the rows. So, the top row of the tableau (containing the reduced costs) is the zero-th row, and the rows below it representing the basic variables are counted starting from one. Likewise, the leftmost column (containing the values of the basic variables) is the zero-th column, and the columns to the right start from one. So, in the tableau shown above, tableau[1][2] is equal to 2.

The function selectEnteringColumn should scan the tableau and identify a variable which can be added to the basis (one with a negative reduced cost). The function should return the number of the column corresponding to this variable, keeping in mind the numbering convention above. If multiple variables have a negative reduced cost, you can choose any of them. إذا لا variable has a negative reduced cost, the current solution is optimal. In this case, this function must return the value None . (That is, using the statement " return None ".) This is the specific value used in simplex.py to terminate.

The function selectEnteringRow is given a tableau and a variable which is entering the basis (specified by its column number col ). Use the ratio test as discussed in class for this. If multiple variables are tied according to the ratio test, your code can return any of them.

The function pivot performs the arithmetic associated with a simplex pivot, given a tableau, and the indices of the pivot row and column. Use the row operations discussed in class to do this.

The autograder is run in the usual way (run grader.py ), and will be used to grade this question. The runSimplex.py file may be useful in debugging or solving the problems below.

Question 2: Production planning

Your company makes two products: a concrete patching product (called "PatchMatch") and a long-lasting masonry mortar product (called "Immortal Mortar", with a discount for customers who can say it five times fast). Both of these products are highly demanded every ton of PatchMatch produced gives you a profit of $140, and every ton of Immortal Mortar produced gives you a profit of $160.

The secret to your products is a special type of clay found in some soil in Austin, TX, with limited availability (you only have access to 28 cubic meters per week.) Every ton of PatchMatch uses 2 cubic meters of Austin clay, and every ton of Immortal Mortar uses 4 cubic meters. Producing a ton of either product requires 5 hours of blending time a total of 50 hours per week is available on your blending machines. Finally, the vats for curing PatchMatch and Immortal Mortar have capacities of 8 tons and 6 tons, respectively. How much of each product should you produce each week?

Your answer to this question must include the following. In the PDF file, provide the following:

  1. A plot of the feasible region, with all extreme points labeled.
  2. A formulation of this optimization problem in standard form.
  3. An optimal solution to the problem, expressed in real-world terms (how many tons to produce of each product, and the weekly profit).
  4. Identify the optimal solution on the plot above. What are the two constraints which are active at this optimal solution? (These are the "bottleneck" constraints which is limiting your profit relaxing any of the other constraints will not help.)

In the ZIP file, provide the following:

  1. A text file showing the initial tableau for your Python code (in the format of class_tableau.txt in hw4.zip .
  2. A Python file which provides the optimal solution using the SciPy library.

Question 3: Maintenance scheduling

You must allocate a $20 million maintenance budget among six bridges located in your state. Assume that the benefits from investing in maintenance in each bridge are directly proportional to the amount invested. This is related to higher-quality pavement, which is safer and more fuel efficient, reductions in long-term maintenance costs, and the current deterioration level of the bridge. In reality, the benefits would not be linear in the amount invested -- we'll return to this for Homework 6. For now, assume that each $1 million spent repairing the six bridges will yield benefits of $50 million, $4 million, $2 million, $1 million, $3 million, and $2 million, respectively.

You must decide how much money to spend on each bridge, keeping in mind the budget limit. Furthermore, the state is divided into two regions. The first two bridges are in Region 1, and the last four bridges are in Region 2. The state mandates that the amount of maintenance funding invested in the two regions not differ by more than $1 million. Which bridges do you invest in, and how much do you spend?

Your answer to this question must include the following. In the PDF file, provide the following:

  1. A formulation of this optimization problem in standard form.
  2. An optimal solution to the problem, expressed in real-world terms (how much to spend on each bridge, and what the total benefits will be.)

In the ZIP file, provide the following:

  1. A text file showing the initial tableau for your Python code (in the format of class_tableau.txt in hw4.zip .
  2. A Python file which provides the optimal solution using the SciPy library.

Question 4: The diet problem

You have budgeted unwisely and have run out of money for food this semester. You use your knowledge of optimization to try to survive until your summer internship paychecks start arriving, and have identified six foods that will comprise your diet, most of which have a high calorie-to-dollar ratio. Identify the daily diet that achieves the nutrition targets listed below at minimum price. Your answer to this question should include how much of each food you are eating, and the daily cost.

Your answer to this question must include the following. In the PDF file, describe how much of each food you will eat, the daily cost, and the daily amount of each nutrient you are getting. In the ZIP file, provide the following:

  1. A text file showing the initial tableau for your Python code (in the format of class_tableau.txt in hw4.zip .
  2. A Python file which provides the optimal solution using the SciPy library.

Disclaimer: I am not a medical professional and I do not endorse the resulting diet in any way.


Linear Programming - Simplex Applet

You are visitor number to this page since last reboot.

Simplex Applet:

Enter Your Linear Program:

How the Applet Works:

  • يحل - Solve your linear program.
  • Abort - Abort the execution of the algorithm.
  • Clear - Allows you to clear fields.
  • About - Brings up an about window.
  • First Choice Menu - With this options you can chose clear the field results or clear the field linear program. It is also, available the options of no clear fields and clear all fields.
  • Second Choice Menu - Chose the algorithm you want Simplex, Revised Simplex, Primal Dual or Simplex Dual. .
  • Third Choice Menu - Chose output options.

Linear Programming:

min cx (Standard Form)
subject to Ax = b
x >= 0

Where "x" is the vector of variables to be solved, "A" is the matrix of known coefficients and "c" and "b" are vectors of known coefficients. The Expression "cx" is called the objective function and the equations "Ax = b" are called the constraints.

Syntax of Linear Program:

A Small Example:

2 constraints and 2 variables

min: x1 + 1.5 x2
c1: 0.5 x1 + x2 >= 7.5
2 x1 + x2 >= 15
x1 >= 0
x2 >= 0


شاهد الفيديو: السمبلكس simplex (شهر اكتوبر 2021).