طريقة Simplex لحل مسائل البرمجة الخطية. التحقق من الأمثلية للحل الذي تم العثور عليه
أكاديمية كورسك للدولة والخدمة البلدية
قسم أمن المعلومات والمجال التكنولوجي
مقال
بالانضباط "طرق الحلول الأمثل"
حول هذا الموضوع "فكرة الطريقة البسيطة"
أكملها: طالب في السنة الثانية
تخصصات "اقتصاد"
موسكاليفا أو إس.
تدقيق بواسطة: دكتوراه، أستاذ مشارك Pogosyan S. L.
كورسك – 2012
مقدمة ……………………………………………………………………….3
1. فكرة الطريقة البسيطة ……………………………………….4
2. تنفيذ الطريقة البسيطة باستخدام المثال ………………..……6
3. التنفيذ الجدولي لطريقة بسيطة بسيطة…………….10
الخلاصة ………………………………………………………………….15
قائمة الأدبيات المستخدمة……………………………….16
مقدمة.
تعد طريقة Simplex مثالًا نموذجيًا للحسابات التكرارية المستخدمة في حل معظم مشكلات التحسين.
في المخطط الحسابي للطريقة البسيطة، يتم تنفيذ عملية مرتبة يتم فيها، بدءًا من نقطة زاوية أولية مقبولة (عادةً الأصل)، إجراء انتقالات متتالية من نقطة متطرفة مقبولة إلى أخرى حتى يتم الوصول إلى نقطة مقابلة للحل الأمثل. وجد.
فكرة الطريقة البسيطة
دعونا نفكر في طريقة عالمية لحل مشكلة البرمجة الخطية الأساسية، باستخدام نالمتغيرات و مقيود المساواة، والمعروفة باسم الطريقة البسيطة.
مجموعة خطط المشكلة القانونية هي مجموعة محدبة متعددة السطوح الرقم النهائينقاط الزاوية. وإذا كان لهذه المشكلة الحل الأمثل، فسيتم تحقيقها على الأقل عند نقطة زاوية واحدة.
ترتبط أي نقطة زاوية بخطة أساسية للمشكلة، حيث تكون المتغيرات فيها صفرًا، والمتغيرات المتبقية تتوافق مع أعمدة مستقلة خطيًا لمصفوفة الشرط. تشكل هذه الأعمدة المستقلة خطيًا مصفوفة أساس غير مفردة.
يعد التكرار على جميع النقاط الأساسية مكلفًا من الناحية الحسابية وبالتالي غير فعال. في عام 1947، اقترح J. Danzig إجراءً منظمًا لتعداد نقاط الزاوية، حيث يكفي فحص جزء صغير منها فقط للعثور على الحل الأمثل. هذا الإجراء يسمى طريقة بسيطة.
اقترح J. Danzig استبدال نقطة عند الانتقال من نقطة متطرفة إلى أخرى مصفوفة الأساسناقل واحد فقط. وهذا يعني أنه خلال هذا التحول يجب علينا استبعاد أحد المتغيرات الأساسية - جعله غير أساسي ( يساوي الصفر) ، وأدخل مكانه متغيرًا جديدًا من بين المتغيرات غير الأساسية (الصفر) - اجعله أساسيًا (إيجابيًا).
اتضح أن مثل هذا الاستبدال هندسيًا يؤدي إلى الانتقال من نقطة زاوية إلى نقطة مجاورة (مجاورة) مرتبطة بها النقطة السابقةالحافة المشتركة.
من جميع النقاط المجاورة، تلك التي دالة الهدفيزيد أكثر. وبما أن عدد نقاط الزاوية محدود، فمن خلال عدد محدود من التحولات التي تحدث في الرأس أعلى قيمةسيتم إنشاء الوظيفة الموضوعية، أو عدم حدود الوظيفة الموضوعية على مجموعة غير محدودة من الخطط.
المخطط العامتتكون الطريقة البسيطة من الخطوات الرئيسية التالية: الخطوة 0. تحديد الأساس الأولي ونقطة الزاوية الأولية المقابلة (خط الأساس).
الخطوة 1. التحقق من خط الأساس الحالي لتحقيق الأمثل . إذا تم استيفاء معيار المثالية، الذي - التي الخطة مثالية والحل كامل. خلاف ذلكانتقل إلى الخطوة 2.
الخطوة 2. العثور على المتغير الذي تم إدخاله في المتغيرات الأساسية. (من شرط زيادة الدالة الموضوعية).
الخطوه 3. إيجاد متغير مستثنى من المتغيرات الأساسية (من شرط الحفاظ على قيود المشكلة).
خطوة 4 . إيجاد إحداثيات خط الأساس الجديد (نقطة الزاوية المجاورة). انتقل إلى الخطوة 1.
تشكل الخطوات المتكررة 1-4 تكرارًا واحدًا للطريقة البسيطة.
يترتب على هذا الرسم البياني، أولاً، لبدء الطريقة البسيطة، يجب أن يكون لديك نوع من نقطة الزاوية - خطة أساسية أولية، وثانيًا، يجب أن تكون قادرًا على فحص نقطة الزاوية الحالية لتحقيق الأمثلية دون حساب جميع النقاط المجاورة الرؤوس. يمكن حل هذه المشكلات بسهولة إذا كانت مشكلة LP الأساسية معينة نوع خاص.
تعريف. سنقول أن مسألة LP الأساسية لها "الشكل المفضل" إذا: الطرف الأيمن من المعادلات؛ تحتوي مصفوفة الشرط على مصفوفة فرعية بحجم الوحدة.
بمعنى آخر، في أي معادلة يوجد متغير ذو معامل يساوي واحدمفقودة من المعادلات الأخرى. الشرط الأول ليس مرهقاً، لأنه في حالة الجانب الأيمن السلبي من بعض المعادلات، يكفي ضربه في (-1). في مسألة النوع التفضيلي، يكون العثور على خط الأساس الأولي أمرًا بسيطًا للغاية.
تنفيذ الطريقة البسيطة باستخدام مثال
دعونا نوضح استخدام الطريقة البسيطة مع مثال. دعونا نفكر مشكلة قانونيةليرة لبنانية
| و (خ) = س 1 + 2س 2 + 0س 3 + 0س 4 > الأعلى | ||
| -س 1 + 2س 2 + س 3 = 4, | ||
| 3س 1 + 2س 2 + س 4 = 12, | ||
| س ي? 0، ي = 1,2,3,4. | ||
مصفوفة الحالة أ = (أ 1 , أ 2 , أ 3 , أ 4) حيث
ناقل الهدف ج =(ج1، ج2، ج3، ج4) = (1, 2, 0, 0); ناقلات الأجزاء الصحيحة ب=(ب 1 ،ب 2) = (4, 12).
الخطوة 0.العثور على نقطة زاوية البداية (خط الأساس).
المشكلة لها شكل مفضل، حيث أن الأطراف اليمنى للمعادلات موجبة، وأعمدة مصفوفة الشرط أ 3, أ 4 تشكل مصفوفة وحدة. وهذا يعني مصفوفة الأساس الأولي = (أ 3 ,أ 4)؛ س 3 و س 4 - المتغيرات الأساسية س 1 و س 2 - المتغيرات غير الأساسية ج ب = (ج 3, ج 4) = = (0, 0).
يبدو خط الأساس الأولي س 0 =(0, 0, س 3 , س 4) = (0, 0, 4, 12); و(س س) = 0.
الخطوة 1.التحقق من الخطة الأساسية لتحقيق الأمثل.
لنحسب التقديرات البسيطة للمتغيرات غير الأساسية باستخدام الصيغة (5.1)
? 1 = 1 > - ج 1 = 0·(-1) + 0 ·3 - 1 = -1 .
? 2 = 2 > - ج 2 = 0 2 + 0 2 - 2 = -2 .
وبما أن التقديرات سلبية، فإن الخطة س- ليس الأمثل. سوف نبحث عن خط أساس جديد (نقطة الزاوية المجاورة) بقيمة أكبر للدالة الهدف.
الخطوة 2. العثور على المتغير الذي تم إدخاله في الأساس.
يمكن زيادة الدالة الموضوعية بإدخال أحد المتغيرات غير الأساسية إلى المتغيرات الأساسية (مما يجعلها موجبة) س 1 أو س 2، منذ كلا التقديرين ؟ ي× 2.
الخطوه 3.تعريف المتغير المشتق من الأساس.
بعد إدخال المتغير في الأساس × 2سوف تبدو الخطة الجديدة
س" =(0, س 2, س 3 , س 4).
هذه الخطة ليست أساسية، لأنها تحتوي على إحداثي صفري واحد فقط، مما يعني أنه من الضروري جعل أحد المتغيرات صفراً (استبعاد من الأساس) س 3 أو س 4 . دعونا نستبدل إحداثيات الخطة س" =(0, س 2, س 3 ,س 4) في معوقات المشكلة. نحن نحصل
2س 2 + س 3 = 4,
2س 2 + س 4 = 12.
دعونا نعبر عن المتغيرات الأساسية من هنا س 3 و س 4 عبر متغير س 2 , دخلت في الأساس.
| س 3 = 4 - 2س 2, | ||
| س 4 = 12 - 2س 2 . | ||
لذلك المتغيرات س 3 و س 4 يجب أن تكون غير سلبية، نحصل على نظام من عدم المساواة
| 4 - 2س 2 ? 0, | ||
| 12 - 2س 2 ? 0. | ||
كلما ارتفعت القيمة س 2 , كلما زادت وظيفة الهدف. سوف نجد القيمة القصوىمتغير أساسي جديد لا يخالف قيود المشكلة أي يحقق الشروط (2.8)، (2.9).
دعونا نعيد كتابة المتباينات الأخيرة في الصورة
2س 2 ? 4,
2س 2 ? 12,
من أين تأتي القيمة القصوى؟ س 2 = دقيقة ( 4/2، 12/2 ) = 2. استبدال هذه القيمة في التعبيرات (2.6)، (2.7) لـ س 3 و س 4 , نحن نحصل س 3 = 0. ولذلك س 3 مشتقة من الأساس .
الخطوة 4.تحديد إحداثيات خط الأساس الجديد.
خط الأساس الجديد (نقطة الزاوية المجاورة) هو:
س" = (0, س 2, 0, س 4)
أساس هذه النقطة يتكون من أعمدة أ 2 و أ 4 , لذا =( أ 2, أ 4). هذا الأساس ليس وحدويا، لأن المتجه أ 2 = (2,2), وبالتالي فإن المشكلة (2.2)-(2.5) ليس لها شكل مفضل فيما يتعلق بالأساس الجديد. دعونا نحول شروط المشكلة (2.3)، (2.4) بحيث تأخذ الشكل المفضل بالنسبة للمتغيرات الأساسية الجديدة س 2, س 4, وهذا هو، بحيث المتغير س 2 تم تضمينه في المعادلة الأولى بمعامل يساوي واحد، ولم يكن موجودا في المعادلة الثانية. دعونا نعيد كتابة معادلات المشكلة
- س 1 + 2 س 2 + س 3 = 4, (ص 1)
3س 1 +2 س 2 + س 4 = 12. (ص 2)
دعونا نقسم المعادلة الأولى على المعامل في س 2 . نحصل على معادلة جديدة = ص 1/2 ما يعادل الأصلي
1/2 س 1 + س 2 + 1/2 س 3 = 2. ()
نستخدم هذه المعادلة، التي نسميها الحل، لحذف المتغير س 2 من المعادلة الثانية للقيام بذلك، تحتاج إلى ضرب المعادلة في 2 والطرح منها ص 2 . نحن نحصل = ص 2 - 2= ص 2 -ص 1:
4 س 1 - س 3 + س 4 = 8. ()
ونتيجة لذلك، حصلنا على تمثيل جديد "مفضل" للمشكلة الأصلية فيما يتعلق بالمتغيرات الأساسية الجديدة س 2 , س 4:
F(س) = س 1 + 2 س 2 + 0 س 3 + 0 س 4 ؟ الأعلى
1/2 س 1 + س 2 + 1/2 س 3 = 2 ()
4 س 1 - س 3 + س 4 = 8 ()
س ي? 0, ي = 1,2,3,4
استبدال هنا تمثيل خط الأساس الجديد س 1 = (0, س 2, 0, س 4) سنجد إحداثياتها على الفور، حيث أن قيم المتغيرات الأساسية تساوي الأطراف اليمنى للمعادلات
س" = (0, 2, 0, 8); F(س 1)=4.
هذا يكمل التكرار الأول للطريقة البسيطة. بعد ذلك، تستمر عملية حل المشكلة من الخطوة 1، والتي تتكون من التحقق من الخطة الموجودة للتأكد من أنها مثالية. وينتهي الحل عندما يتبين أن جميع التقديرات البسيطة للخطة الأساسية الحالية غير سلبية.
لن نقوم بتنفيذ التكرار الثاني وفقًا لمخطط الأول، لأنه أكثر ملاءمة لتنفيذ جميع حسابات الطريقة البسيطة في شكل جدول.
التنفيذ الجدولي لطريقة بسيطة بسيطة
سنوضح التنفيذ الجدولي باستخدام نفس المثال (2.2)-(2.5).
الخطوة 0. يبدأ الحل بإنشاء جدول بسيط أولي. تم ملؤها أولاً الجزء الأيمنالجداول من العمود الثالث. في اثنين الخطوط العليايتم تسجيل الأسماء متغيرات المشكلة (س 1, ...,س 4) ومعاملات الدالة الموضوعية لهذه المتغيرات. فيما يلي معاملات المعادلات - عناصر مصفوفة الشرط أ، وذلك تحت المتغير س 1 تقع عمود أ 1، تحت المتغير س 2 - عمود أ 2 إلخ. يتم إدخال الجوانب اليمنى من القيود (الأرقام) في العمود الأيمن ب ط > 0).
ثم نجد أعمدة مصفوفة الشرط التي تشكل أساس الوحدة - في مثالنا هذا أ 3 و أ 4 - والمتغيرات الأساسية المقابلة لها س 3, س 4 اكتب في العمود الثاني. وأخيرا، في العمود الأول نكتب معاملات الدالة الهدف للمتغيرات الأساسية.
الجدول 1- الجدول البسيط الأولي
| المتغيرات الأساسية | القيم المتغيرة الأساسية ( س ب = ب) |
|||||
| × 1 | × 2 | × 3 | × 4 | |||
| × 3 | أ 11 = -1 | |||||
| × 4 | ||||||
| خط التقييم ؟ ي | ? 1 = -1 | ? 2 = -2 |
وبما أن المشكلة لها شكل مفضل، فإن قيم المتغيرات الأساسية تساوي الأطراف اليمنى للمعادلات الموجودة في العمود الأخير. وبما أن المتغيرات غير الأساسية هي صفر، فإن خط الأساس الأولي هو
سس = (0، 0، س 3 , س 4) = (0, 0, 4, 12).
الخطوة 1.للتحقق من الخطة سس لتحقيق الأمثلية نحسب التقديرات البسيطة للمتغيرات غير الأساسية س 1 و س 2 وفقا للصيغة
؟ ي = ب, أ ي > - ج ي .
? 1 = ب، أ 1 > - ج 1 = 0·(-1) + 0 ·3 - 1 = -1 .
مع تنفيذ جدولي لحساب النتيجة ? 1 نحتاج إلى إيجاد مجموع منتجات عناصر العمود الأول ( ج ب) إلى عناصر العمود المقابلة أ 1 لمتغير غير أساسي س 1 . يتم حساب النتيجة بنفس الطريقة ? 2 , كمنتج عددي للعمود الأول ( ج ب) لكل عمود في المتغير × 2.
? 2 = 2 > - ج 2 = 0 2 + 0 2 - 2 = -2 .
تتم كتابة تقديرات Simplex في الصف الأخير من الجدول البسيط، والذي يسمى صف دلتا. في هذه الحالة، لا يتم ملء الخلايا الخاصة بالمتغيرات غير الأساسية فحسب، بل يتم أيضًا ملء الخلايا الأساسية. من السهل التحقق من أن التقديرات البسيطة لأعمدة الوحدة الأساسية لمصفوفة الشرط تساوي الصفر. في الخلية الأخيرة من سطر التقييم نكتب قيمة الدالة الهدف عند النقطة xo.لاحظ أنه بما أن الإحداثيات غير الأساسية للخطة الأساسية تساوي الصفر، فمن الملائم حساب الدالة الهدف باستخدام الصيغة
F(س)= ج ب، × ب >,
ضرب عددي في العمودين الأول والأخير من الجدول.
منذ بين التقديرات ؟ يهنالك سلبي , ثم الخطة س o ليس الأمثل، ومن الضروري إيجاد خطة أساسية جديدة من خلال استبدال أحد المتغيرات الأساسية بآخر جديد من بين المتغيرات غير الأساسية.
الخطوة 2.منذ كلا التقديرين ? 1 و ? 2 ثم يمكن إدراج أي من المتغيرات في الأساس س 1, س 2 . دعونا ندخل في الأساس المتغير ذو أكبر تقدير سلبي مطلق، أي س 2 .
يسمى عمود الجدول البسيط الذي يوجد فيه المتغير الذي تم إدخاله في الأساس بالعمود الرئيسي.
في المثال، سيكون العمود البادئ في × 2 .
الخطوه 3.إذا كانت جميع العناصر في العمود السابق سلبية، فلا يوجد حل للمشكلة والحد الأقصى F(س) ؟؟؟. في المثال، جميع عناصر العمود السابق موجبة، وبالتالي يمكننا إيجاد القيمة القصوى س 2 , حيث يصبح أحد المتغيرات الأساسية القديمة صفرًا. أذكر أن القيمة القصوى × 2 =دقيقة(4/2, 12/2)=2.
وفقا للجدول، يتم حساب هذه القيمة كما أصغر نسب مكونات خط الأساس (من العمود الأخير) إلى ما يقابله إيجابيعناصر العمود الرئيسي.
أصغر نسبة موجودة في الصف مع المتغير الأساسي × 3.لذلك المتغير × 3مستبعدة من المتغيرات الأساسية ( س 3 = 0).
يسمى السطر الذي يحتوي على المتغير المراد استبعاده من الأساس بالخط الرئيسي.
في المثال، سيكون السطر الرئيسي هو السطر الأول.
العنصر الموجود عند تقاطع الصف الأمامي والعمود الأمامي يسمى العنصر الرئيسي.
في حالتنا، العنصر الرئيسي أ 12 = 2.
طاولة 2- جدول بسيط أولي يحتوي على صف وعمود رئيسيين
| التغييرات الأساسية. | القيم المتغيرة الأساسية | المعادلات |
|||||
| × 2 | |||||||
| ج3=0 | × 3 | -1 | 2 | 1 | 0 | 4 | |
| 2 | |||||||
| خط التقييم ؟ ي | ? 1 = -1 | ? 2 = -2 | |||||
الخطوة 4. للحصول على خطة أساسية جديدة نقوم بتقليص المشكلة إلى شكل جديد مفضل بالنسبة للمتغيرات الأساسية الجديدة.
للقيام بذلك، دعونا نبني جدولًا بسيطًا جديدًا، في العمود الثاني منه بدلاً من المتغير المستبعد × 3لنكتب متغيرًا أساسيًا جديدًا × 2وفي العمود الأول ( مع ب) بدلاً من من 3دعونا نكتب معامل الدالة الهدف في × 2: ج2=2. في الجدول البسيط الجديد، العمود في × 2يجب يصبح واحدًا (العنصر الرئيسي يجب أن يساوي واحدًا، وجميع العناصر الأخرى يجب أن تصبح صفرًا). يتم تحقيق ذلك من خلال تحويلات صفوف الجدول التالية.
أ.نقسم جميع عناصر السطر الرئيسي على العنصر الرئيسي ونكتبها في نفس السطر كعنصر جديد الجداول البسيطة.
السلسلة الناتجة ص 1"دعنا نسميها متساهلة.
ب.نضيف إلى السطر الثاني المتبقي خط الحل، مضروبًا في هذا الرقم بحيث يصبح العنصر الموجود في العمود الرئيسي صفرًا.
ص 2" = ع 2 + (- 2) ص 1" = ع 2 - ع 1.
ج.دعونا نملأ السطر الأخير عن طريق حساب التقديرات ؟ ي" = - - ج ي, أين ج ب "، أ ي" -الأعمدة المقابلة للجدول البسيط الجديد، وقيمة الدالة الهدف و(خ)= .
نحصل على جدول بسيط ثانٍ بأساس جديد.
الجدول 3- نتيجة التكرار الأول
| التغييرات الأساسية. | القيم المتغيرة الأساسية | المعادلات | ||||||
| -1/2 | ||||||||
| × 4 | 4 | 0 | -1 | 1 | 8 | ص 2" = ع 2 - ص 1 | ||
| التقديرات ؟ ي" | -2 | |||||||
خط الأساس الجديد س " = (0، × 2، 0، × 4) = (0, 2, 0, 8 ). منذ التقييم ؟ 1 = -2 ثم خطط س " ليس الأمثل. للانتقال إلى خطة أساسية جديدة (لنقطة الزاوية المجاورة)، سنقوم بتنفيذ تكرار آخر للطريقة البسيطة.
لأن? 1 ثم يتم إدخال متغير في الأساس × 1. العمود الأول يحتوي على × 1 -قيادة.
نجد العلاقات بين مكونات الخطة الأساسية وما يقابلها إيجابيعناصر العمود السابق واتخذ الصف ذو النسبة الأصغر باعتباره الصف السابق. في الجدول 2، في العمود الرئيسي فقط العنصر الثاني أكبر من الصفر (= 4)، وبالتالي سيكون السطر الثاني هو السطر الرئيسي، والأساس الموجود فيه عامل × 4خاضعة للاستبعاد من الأساس.
نختار العمود الرئيسي والصف الرئيسي ونجد عند تقاطعهما العنصر الرئيسي (= 4).
نقوم ببناء جدول بسيط (ثالث) جديد، مع استبدال المتغير الأساسي فيه × 4 على × 1 ، ومرة أخرى تحويل صفوف الجدول بحيث يصبح العنصر البادئ يساوي واحدًا، وتصبح العناصر المتبقية في العمود البادئ صفرًا. للقيام بذلك، قم بتقسيم السطر السابق (الثاني) على 4، ثم قم بإضافة السطر الثاني الناتج مقسومًا على 2 إلى السطر الأول. الخط الأخيرحساب باستخدام الصيغ لتقديرات البسيط ؟ ي"" = ""، أ ي""> - ج ي, أين ج ب""، أ ي"" - الأعمدة المقابلة للجدول البسيط الجديد. تم العثور على قيمة الدالة الهدف على خط الأساس الجديد باستخدام الصيغة و(س"")= ""، س ب"" >.
الجدول 4- نتيجة التكرار الثاني
| أساسي يتغير | القيم المتغيرة الأساسية | المعادلات |
|||||
| ص 1 "" = ص1"+ص2""/2 |
|||||||
| ص 2 "" = ص 2 "/4 |
|||||||
| التقديرات ؟ ي "" | و(س"")= 8 | ||||||
خط الأساس الجديد س "" = (× 1، × 2، 0, 0) = (2, 3, 0, 0 ). وبما أن جميع التقديرات غير سلبية، ثم الخطة س ""- الخطة المثالية .
هكذا، س* = (2, 3, 0, 0 ), و(س*) = 8.
خاتمة
طرق مدروسة لحل المشكلات البرمجة الخطيةتستخدم على نطاق واسع في الممارسة العملية. ومع ذلك، تجدر الإشارة إلى ذلك
فالنموذج الرياضي دائمًا أفقر من النموذج الحقيقي نظام اقتصادي. فهو يصف هذا النظام بشكل تقريبي فقط، مع إبراز بعض خصائصه وإهمال البعض الآخر. وللتعويض عن هذا القصور في الاقتصاد الرياضي، يجري تطوير عدة أنواع من النماذج، كل منها مصمم ليعكس جانبا محددا من الواقع الاقتصادي بحيث أنه عند حل مشكلة اقتصادية معينة، من الممكن اختيار النموذج الذي يناسبها. .
قائمة المراجع المستخدمة
1. أشمانوف إس. البرمجة الخطية. - م: ناوكا، 1981.
2. إدخال المتغيرات الطبيعية الأساسية. بناء جدول بسيط. تعريف الخطة الصفرية.
طريقة سيمبلكس. خوارزمية الطريقة البسيطة.
طريقة سيمبلكس- خوارزمية الحل مشكلة التحسينالبرمجة الخطية من خلال تعداد رؤوس متعدد السطوح المحدب في الفضاء متعدد الأبعاد. تم تطوير هذه الطريقة من قبل عالم الرياضيات الأمريكي جورج دانزيج في عام 1947.
فكرة طريقة بسيطةيتكون من حقيقة أن المهمة الوصفية المطروحة تُترجم إلى شكل رياضي. تحتوي الصيغة الرياضية للمشكلة على معادلة الدالة الهدف التي تشير إلى النتيجة المرجوة - تحديد الحد الأدنى أو الأقصى للدالة الهدف؛ أنظمة القيود الخطية المحددة بالمساواة أو عدم المساواة. تلقى الوصف الرياضييؤدي إلى شكل مصفوفة. ثم يتم تقليل وصف المصفوفة للمشكلة إلى الشكل الأساسي. بعد النظام المعادلات الخطيةوبعد اختزالها إلى الشكل الأساسي، نبدأ في حل مشكلة البرمجة الخطية. تتكون خوارزمية حل هذه المشكلة من سلسلة من مصفوفات البناء. كل خطوة من خطوات الحل تقربك من الحصول على النتيجة المرجوة.
في المخطط الحسابي للطريقة البسيطة، يتم تنفيذ عملية مرتبة يتم فيها، بدءًا من نقطة زاوية أولية مقبولة (عادةً الأصل)، إجراء انتقالات متتالية من نقطة متطرفة مقبولة إلى أخرى حتى يتم الوصول إلى نقطة مقابلة للحل الأمثل. وجد.
خوارزمية طريقة Simplex
1. نأتي بنظام القيود الشكل الكنسي(عندما يكون النظام محدودا). علاوة على ذلك، يمكن تحديد أساس واحد في النظام.
2. ابحث عن الأصل الخطة المرجعية(الحلول الأساسية غير السلبية لنظام المعادلات KZLP). يتم تحديد كل من الخطط المرجعية بواسطة نظام من المتجهات المستقلة خطيًا الموجودة في نظام معين من المتجهات n أ 1 , أ 2 ,…, ن. يتم تحديد الحد الأعلى لعدد الخطط المرجعية الموجودة في مشكلة معينة من خلال عدد المجموعات مع نانومتر);
3. نحن نبني جدول بسيط (جدول بسيطمصفوفة تعمل كوسيلة لتعداد الحلول الأساسية المقبولة لمشكلة البرمجة الخطية (غير المنحلة) عند حلها باستخدام الطريقة البسيطة. يتم تشكيلها من مصفوفة معاملات نظام معادلات البرمجة الخطية المختزلة إلى الشكل القانوني، وتحولها المتسلسل وفقا لما يسمى خوارزمية بسيطةيسمح بعدد محدود من الخطوات (التكرارات) للحصول على النتيجة المرجوة - خطة توفر قيمة قصوى للوظيفة الهدف).
4. ب جدول بسيطنحن نتحقق من ناقلات السلبية، أي. التقديرات زيج – سيجالمكتوبة في السطر يجب أن تكون ≥ 0 (كحد أدنى)، Zj – Сj ≥ 0(إلى الحد الأقصى). إذا كانت التقديرات تستوفي شروط المثالية، فسيتم حل المشكلة.
5. إذا تم انتهاك شروط المثالية بالنسبة لبعض المتجهات، فمن الضروري إدخال ناقل يتوافق مع:
الحد الأقصى [θ 0 ي (Zj – Сj)] ; دقيقة [θ 0 ي (Zj – Сj)] ; θ 0 ي = دقيقة، أين × ط> 0
عنصر ناقل θ يالذي يتوافق θ 0 ييسمى مباحًا؛ يُطلق على الصف والعمود الذي يقع فيه اسم الدليل؛ ويترك المتجه الموجود في صف الدليل الأساس.
6. دعونا نوجد معامل التمدد لجميع المتجهات في الأساس الجديد. دعونا نطبق طريقة جيوردانو جاوس
دعونا نتحقق من الخطة المرجعية المثالية. إذا كان التقدير يلبي شروط المثالية، فسيتم حل المشكلة، وإذا لم يكن الأمر كذلك، فسيتم تنفيذ الخطوات من 5 إلى 7.
2. إدخال المتغيرات الطبيعية الأساسية. بناء جدول بسيط. تعريف الخطة الصفرية.
الطريقة البسيطة هي الأكثر فعالية في الحل المهام المعقدةويمثل عملية تكرارية (خطوة بخطوة) تبدأ بـ صفر(المرجع) الحل (قمة الرأس ن- متعدد السطوح الأبعاد). التالي في البحث الخيار الأمثلتفترض الخطة الحركة على طول نقاط الزاوية (رؤوس متعدد السطوح) حتى تصل قيمة الوظيفة الهدف إلى القيمة القصوى (الدنيا). دعونا نفكر في خوارزمية الطريقة البسيطة باستخدام مثال مشكلة تخطيط معدل الدوران بموارد المواد الخام المحدودة.
الشركة تبيع نمجموعات المنتجات، وجود ممحدودية الموارد المادية والمالية بأنا ≥0 (1 ≥ أنا≥ م) . تكاليف الموارد للجميع معروفة أنا- نوع إنتاج وبيع وحدة سلع كل مجموعة، معروضة على شكل مصفوفة ( أط) والربح الذي تحصل عليه المؤسسة من بيع وحدة من السلع ي-المجموعة المدرجة في وظيفة الهدف ز(X). ولا تختلف طريقة البرمجة الخطية عن النظام (1) - (2):
Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)
أ 11 × 1 + أ 12 × 2 +… أ 1ن × ن ≥ ب 1،
أ 21 × 1 + أ 22 × 2 +… أ 2 ن × ن ≥ ب 2 (2)
أ م1 × 1 + أ م2 × 2 +…أ من × ن ≥ ب م،
X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0
تشمل مراحل حل المشكلة باستخدام الطريقة البسيطة ما يلي:
1) وضع خطة مرجعية صفرية. نقدم متغيرات جديدة (أساسية) غير سلبية، وبفضلها يصبح نظام المتباينات (2) نظام معادلات:
أ 11 × 1 + أ 12 × 2 +… أ 1ن X ن + X ن+1 = ب 1
أ 21 × 1 + أ 22 × 2 +… أ 2ن X ن + X ن+2 = ب 2 (3)
……………………………………..
أ m1 X 1 + أ m2 X 2 +…أ مليون X ن + X ن+م = ب م،
إذا أخذنا متغيرات الإدخال كمتجهات للأعمدة، فإنها تمثل أعزب (أساسي) ثلاثة أبعاد. لاحظ أن المتغيرات الأساسية لها بسيطة المعنى الجسدي- هذا بقيةمورد محدد في المستودع لخطة إنتاج معينة، ولذلك يسمى هذا الأساس طبيعي. نحل النظام (3) بالنسبة للمتغيرات الأساسية:
X n+1 = ب 1، -أ 11 × 1 - أ 12 × 2 -…أ 1ن × ن
X n+2 = ب 2 - أ 21 × 1 - أ 22 × 2 -…أ 2ن × ن (4)
………………………………………..
X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n
نعيد كتابة الدالة الهدف في النموذج
ز(X) = 0-(-س 1 Х 1 -س 2 Х 2 -س 3 Х 3 -…-س ن Х ن) (5)
بافتراض أن المتغيرات الأساسية المطلوبة X 1 = X 2 = X 3 = ... = X n = 0، نحصل على خطة مرجعية صفرية X = (0, 0, ...0, b 1, b 2, b 3 ... b m)، حيث Z(X) = 0 (جميع الموارد في المخزون، ولم يتم إنتاج أي شيء). ندخل الخطة في جدول بسيط.
| يخطط | أساس | ج ط / ج ي | معنى العاشر ط | × 1 | × 2 | Xn | Xn+1 | Xn+2 | × ن + 3 | قمين |
| Xn+1 | ب 1 | 11 | 12 | 13 | ب1/أ12 | |||||
| Xn+2 | ب 2 | 21 | 22 | 23 | ب2/أ22 | |||||
| Xn+3 | ب 3 | 31 | 32 | 33 | ب3/أ32 | |||||
| ض(س) = 0 | -ج 1 | - ج2 | - ج3 | فِهرِس. خط |
2) من المعاملات السالبة لخط الفهرس، نختار الأكبر في القيمة المطلقة، التي تحدد العمود السابق وتوضح أي متغير في التكرار التالي (الخطوة) سينتقل من الرئيسي (المجاني) إلى الأساسي (في الواقع، مجموعة المنتجات التي تجلب مبيعاتها الحد الأقصى للدخل). ثم نقسم احتياطيات المواد الخام b i على معاملات التكلفة المقابلة، وندخل النتائج في جدول ونحدد الحد الأدنى للقيمة Q min (يتم تحديد المورد الذي يحد احتياطيه بشدة من إنتاج مجموعة المنتجات المحددة). تحدد هذه القيمة الخط الرئيسي والمتغير Xi، والذي في الخطوة التالية (التكرار) سيترك الأساس ويصبح حرًا.
3) يتم الانتقال إلى خطة جديدة نتيجة لإعادة حساب الجدول البسيط باستخدام طريقة Jordan-Gauss. أولاً، نستبدل X j في الأساس بـ X i في العمود الرئيسي. دعونا نقسم جميع عناصر الخط الرئيسي على العنصر الحاسم (RE)، ونتيجة لذلك فإن مكان RE في الخط الرئيسي سيكون 1. وبما أن X i أصبحت أساسية، فإن معاملاتها المتبقية يجب أن تساوي 0 تم العثور على عناصر جديدة في هذه الخطة وفقا لقاعدة المستطيل
NE=SE – (أ*ب)/إعادة (6)
يتم تقييم الخطة الناتجة باستخدام معاملات خط الفهرس: إذا كانت جميعها إيجابية، فإن الخطة هي الأمثل، وإذا لم تكن كذلك، فيمكن تحسين الخطة عن طريق إجراء التكرار (الخطوة) التالية؛
مثال.تم تخصيص 20 ألف روبل لشراء المعدات لموقع الإنتاج. يمكن وضع المعدات على مساحة لا تزيد عن 72 مترًا مربعًا. يمكنك طلب المعدات من نوعين: النوع أ الذي يتطلب مساحة إنتاج 6 متر مربع وتوفير 6 آلاف وحدة. المنتجات لكل وردية (السعر 5000 روبل) والنوع ب، تتطلب مساحة 12 مترًا مربعًا وتنتج 3 آلاف وحدة (السعر 2000 روبل). ما هي خطة اقتناء المعدات الأمثل لضمان الاداء العاليحبكة؟
دعونا نشير إلى كمية المعدات المشتراة من النوع A وB بـ X 1 وX 2، على التوالي.
إنتاجية الموقع (دالة موضوعية): Z(X) =6Х 1 +3Х 2.
ترتبط القيود الرئيسية
نقداً: 5Х 1 +2Х 2 ≥ 20،
مع مساحة موقع الإنتاج: 6Х 1 +12Х 2 ≥ 72.
نقدم متغيرات أساسية جديدة X 3 (الباقي مالبعد شراء المعدات) وX 4 (المساحة المتبقية بعد وضع المعدات) وإعادة كتابة القيود في شكل نظام من المعادلات:
5X 1 +2X 2 + X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6X 1 +12X 2 + X 4 = 72 (X 4 = 72 – 6X 1 – 12X 2)
في هذه الحالة، دالة الهدف: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .
نقوم بعمل الخطة المرجعية (0): X = (0، 0، 20، 72)، أي. لم يتم شراء أي شيء بعد (لم يتم إنفاق أي أموال، والمكان فارغ). صنع جدول بسيط
| يخطط | أساس | ج ط / ج ي | معنى العاشر ط | × 1 | × 2 | × 3 | × 4 | قمين | |||
| × 3 | 20/5=4 | ||||||||||
| × 4 | 72/6=12 | ||||||||||
| ض(س) = 0 | - 6 | - 3 | خط الفهرس | ||||||||
| →× 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| × 4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| ض(س) = 6*4=24 | -0,6 | 1,2 | خط الفهرس | ||||||||
| × 1 | 0,25 | -1/24 | - | ||||||||
| → × 2 | -1/8 | 5/48 | - | ||||||||
| ض(س) =6*2+3*5=27 | 9/8 | 1/16 | خط الفهرس | ||||||||
من الواضح أن العمود السابق يتوافق مع X 1، نظرًا لأنه يحتوي على أكبر مؤشر 6. نجد الحد الأدنى لقيمة Q min = 4 (أشد قيود الموارد) من خلال تحديد صف بادئ يوضح أن X 3 مشتق من المتغيرات الأساسية ، ويتم إدخال X بدلاً من ذلك 1 . نعيد حساب عناصر الخط الرئيسي ونقسمها على 5 وباستخدام الصيغة (6) نحدد عناصر الخط الثاني والمؤشر. دالة الهدف للخطة الأولى تساوي Z(X) = 6*4+3*0 = 24.
ومع ذلك، يظل أحد معاملات صف الفهرس للعمود X 2 سالبًا -0.6، وبالتالي فإن هذه الخطة ليست مثالية، ويلزم تكرار (خطوة) أخرى لتحسينها. حدد العمود الثاني كقائد و الحد الأدنى للقيمة Q min = 5 نحدد الخط الرئيسي بالمتغير الأساسي X 4. بعد إجراء نفس التحولات، نحصل على الخطة الثانية، والتي ستكون الأمثل، لأن جميع معاملات المؤشر إيجابية.
دعونا نحلل النتائج التي تم الحصول عليها. في حل مثاليتبلغ القيمة القصوى للوظيفة الهدف 27 ألف روبل، بينما تتم إزالة كلا الموردين من الأساس، وبالتالي يتم إنفاقهما بالكامل.
دعونا نتأكد من ذلك: 5*2+2*5 = 20 ألف روبل، 6*2+12*5=72 متر مربع. الحل المطلوب هو X = (2; 5;0;0). وهذا لا يحدث دائما.
محاضرة رقم 10
الموضوع: طريقة Simplex للمشاكل ذات الأساس الاصطناعي
تعتمد طريقة الحل البسيط على إدخال متغيرات (أساسية) إضافية تجعل من الممكن تكوين مصفوفة وحدة. إذا تم تقديم قيود المشكلة في شكل عدم المساواة:
أ i1 X 1 + أ i2 X 2 +…أ في X n ≥ ب i (1)
أو المعادلات:
أ i1 X 1 + أ i2 X 2 +…أ في X n = ب i (1*)،
فمن المستحيل الحصول على الخطة المرجعية بالشكل المطلوب. في هذه الحالة، للامتثال للمساواة (1*)، نقدم أساس مصطنع ي i والمتغيرات الاصطناعية لا ترتبط بشكل مباشر بمحتوى المهمة، ولكنها تجعل من الممكن إنشاء خطة مرجعية (بدء):
أ i1 X 1 + أ i2 X 2 +…أ في X n +Y i = b i (2)
سيتم كتابة الوظيفة الموضوعية عند حل المشكلة إلى الحد الأقصى بالشكل:
Z(X) =∑C j X j +(-M)∑Y i (3)،
عند حل مشكلة مماثلة على الأقل:
Z(X)=∑C j X j +(M)∑Y i (3*)،
حيث M هو رقم موجب كبير جدًا، وهو نوع من العقوبة لاستخدام المتغيرات الاصطناعية.
في حالة المتباينات (1)، نقدم في البداية متغيرات إضافية X n + i بعلامة الطرح. لن تكون مصفوفتها موحدة، لذلك، في كل عدم مساواة في النظام (1) نقدم متغيرات مصطنعة У i:
أ i1 X 1 +أ i2 X 2 +…أ في X n –X n+i +Y i =b i (4)
الدالة الهدف في هذه الحالة هي Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (للإيجاد الحد الأقصى). طلب أساس مصطنعيمنح الأسلوب البسيط مرونة أكبر ويسمح باستخدامه لمجموعة واسعة من المهام.
مثال . تحديد قيم الربح القصوى والدنيا لإنتاج نوعين من المنتجات A وB، إذا كانت تكاليف الإنتاج والربحية من مبيعات وحدة المنتج موضحة في الجدول. الشرط الرئيسي هو العمالة الكاملة للعاملين في المؤسسة.
رياضياً سيتم كتابة قيود مخرجات الإنتاج على شكل نظام مختلط:
1Х 1 + 1Х 2 ≥ 6،
2×1 + 1×2 =8.
لندخل المتغير الأساسي X 3 للمتباينة الأولى، والمتغير الاصطناعي Y 1 للمعادلة الثانية:
1X 1 + 1X 2 + X 3 = 6،
2X 1 + 1X 2 + ص 1 = 8.
دعونا نعبر عن X 3 وY 1 من نظام المعادلات الناتج، ولتحديد الحد الأقصى، تخيل الدالة الموضوعية:
Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
بالنسبة للخطة المرجعية - X=(0,0,6,8). لنقم ببناء جدول بسيط:
| يخطط | أساس | ج ط / ج ي | معنى العاشر ط | × 1 | × 2 | × 3 | ص 1 | قمين |
| × 3 | 6/1=6 | |||||||
| ص 1 | -م | 8/2=4 | ||||||
| Z(X) = -8M | -2 م-3 | -م-2 | خط الفهرس | |||||
| × 3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →× 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| ض(س) = 3*4=12 | - 0,5 | م+1.5 | خط الفهرس | |||||
| → × 2 | -1 | - | ||||||
| × 1 | -1 | - | ||||||
| ض(س) =3*2+2*4=14 | م+1 | خط الفهرس |
كقاعدة عامة، يبدأ تحسين الخطة المرجعية بإزالة المتغير الاصطناعي Y 1 من الأساس. تم الحصول على الخطة المثالية X = (2,4,0,0) في التكرار الثاني، بحد أقصى للدخل 14. ألف. فرك. ، ومعاملات صف الفهرس غير سالبة. من السهل التحقق من أنه في هذه المهمة، باستخدام الخطة المثالية، يتم استخدام الموارد بالكامل (2*1+4*1=6; 2*2+1*4=8).
عند إيجاد الحد الأدنى من الربحية، نقوم بصياغة الدالة الهدف بشكل مختلف (يتم إدخال +MY 1 كمصطلح:
Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X1 + 2X2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
الخطة المرجعية هي نفسها، لكن معاملات صف الفهرس في الجدول البسيط مختلفة. يتم تحديد العمود البادئ، كما كان من قبل، بواسطة أكبر معامل إيجابي في القيمة المطلقة لـ X 1، ويتم تحديد الصف البادئ بالقيمة الدنيا لـ Q min = 4. في التكرار الأول، يتم اشتقاق المتغير الاصطناعي Y 1 من أساس.
| يخطط | أساس | ج ط / ج ي | معنى العاشر ط | × 1 | × 2 | × 3 | ص 1 | قمين | ||
| × 3 | 6/1=6 | |||||||||
| ص 1 | م | 8/2=4 | ||||||||
| Z(X) = 8M | 2 م-3 | م-2 | خط الفهرس | |||||||
| × 3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →× 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| ض(س) = 3*4=12 | - 0,5 | -م+1.5 | خط الفهرس | |||||||
تشير القيم السلبية الناتجة للمعاملات في خط الفهرس X i إلى أفضلية الخطة الأولى، في حين أن الحد الأدنى للدخل هو 12 ألف روبل.
يتم توفيره فقط من خلال إنتاج المنتج A (لا يتم إنتاج المنتج B)، ولا يتم استخدام المواد الخام بالكامل (الباقي X 3 = 2t)، في حين يتم استيفاء الشرط الرئيسي - توظيف العمال بشكل كامل في الإنتاج.
محاضرة رقم 11
الموضوع: مشكلة النقل المغلق
1. الصياغة الرياضية المغلقة مشكلة النقل. تحديد العدد المطلوب من المجهولين.
2. مراحل تحديد خطة حل مشكلة النقل.
العثور على الخطة الأمثل. هذه الطريقة عالمية فهي تسمح بحل مشاكل البرمجة الخطية من أي بعد في صيغة عامة. ومع ذلك، تتطلب هذه الطريقة تقليل المشكلة الأصلية إلى النموذج الأساسي.
الفكرة الرئيسية للطريقة البسيطة هي الانتقال من قمة ODR إلى أخرى بحيث تنخفض قيمة CF مع كل انتقال. هذه هي الطريقة التي يمكنك من خلالها الانتقال من أي قمة إلى القمة المثالية والحصول على الخطة المثالية.
على سبيل المثال: لنفترض أن الخطة المرجعية X =(x1,x2,…,xm,0,0,…,0) والنظام المرتبط بها من المتجهات المستقلة خطيًا: A1,A2,…,A معروفة، إذن بالنسبة لهذه الخطة المرجعية يمكنك حساب القيمة CF Z=(c1x1+c2x2+…+cmxm) وكتابة شروط الحد في النموذج التالي x1A1+x2A2+…+xmAm=b
نظرًا لأن المتجهات A1، A2،…، Am مستقلة خطيًا، فيمكن توسيع أي متجه Aj إلى هذه المتجهات: Aj=x1jA1+x2jA2+…+xmjAm (*) دعونا نقدم القيم Zj Zj=x1jc1+x2jc2+…+ xmjcm، حيث xij هو المعامل المطابق لـ Ai في متجه التمدد Aj حسب المتجهات الأساسية
النظرية 1: تحسين الخطة المرجعية
إذا تم استيفاء الشرط Zj-Cj>0 لبعض الفهارس j، فيمكن تقليل قيمة CF و:
· إذا كان CF محدودًا من الأسفل، فمن الممكن بناء خطة مرجعية بقيمة CF أصغر، وهي نفس القيمة السابقة
· إذا لم يكن TF محدودًا من الأسفل، فمن الممكن بناء خطة تتوافق مع قيمة صغيرة بشكل تعسفي لـ TF
النظرية 2: معيار الأمثلية للخطة المرجعية
إذا كان لبعض الفهرس j في الخطة المرجعية عدم المساواة Zj-Cj0. دع هذا الحد الأدنى يتحقق للمتجه Ak، فهذا المتجه هو الذي يجب اشتقاقه من الأساس. يسمى السطر المقابل لهذا المتجه بالدليل ويشار إليه بـ "à".
4. بعد تحديد أدلة الأعمدة والصفوف، قم بملء جدول بسيط جديد. في مثل هذا الجدول، سيظهر Ai بدلاً من السطر الإرشادي. حشوة طاولة جديدةيبدأ بخط إرشادي. كأحد مكونات الخطة المرجعية، يتم كتابة القيمة اوى0 X'l=اوى0=Xk/Xkl هناك، ويتم تحديد العناصر المتبقية من هذا الخط بواسطة الصيغة X'lj X'lj=Xkj/Xkl حيث Xkl هو العنصر تقع عند تقاطع أدلة الصف والعمود، وعلى وجه التحديد يتم تقسيم جميع العناصر السابقة للخط الدليلي، وفي مكانها العنصر السابقتظهر وحدة Xkl تلقائيًا. قاعدة عامةلإعادة حساب الخط الدليلي، يمكنك كتابته على النحو التالي: Ak (العنصر الجديد في الخط الدليلي) = (العنصر القديم في الخط الدليلي)/(العنصر الذي يقف عند تقاطع العمود الدليلي والصف)
5. تتم إعادة حساب جميع عناصر الصفوف المتبقية من الجدول، بما في ذلك الصف السفلي الإضافي. تتم إعادة الحساب وفقًا للصيغ
· بالنسبة لمكونات الخطة المرجعية X’i=Xi-Ԩ0Xil=Xi-(Xk/Xkl)*Xil
· للمكونات الموسعة على الأساس X'ij=Xij-(Xkj/Xkl)*Xil
· ل خط إضافي Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)
تم بناء كل هذه الصيغ وفقًا لقاعدة واحدة:
(بريد إلكتروني جديد)=(بريد إلكتروني قديم)-(بريد إلكتروني لاتجاه الصف الجديد)*(بريد إلكتروني لاتجاه العمود في الصف المقابل)
بعد ملء الجدول البسيط الجديد، يحدث الانتقال إلى المرحلة الثانية من الخوارزمية.
طرق الأساس الطبيعي والاصطناعي. المفاهيم الأساسية وخوارزميات الأساليب.
بالنسبة لمعظم مشاكل البرمجة الخطية، تنشأ صعوبات في حلها مرتبطة بتحديد الخطة المرجعية الأولية والجدول البسيط الأولي الذي تبدأ منه جميع التكرارات. ويرجع ذلك إلى حقيقة أنه في المسائل الحقيقية بين المتجهات Ai لا توجد متجهات تحتوي على مكون واحد غير صفري فقط، أي متجهات بالشكل (0,0,0,…,0,1,0,…,0) أو أن عددهم لا يكفي لتشكيل الأساس. أي أنه من غير الممكن تكوين أساس طبيعي.
تعتمد طريقة الأساس الاصطناعي على الإدخال الاصطناعي في نموذج رياضيمشاكل مثل هذه النواقل.
دعونا نعطي ZLP من الشكل الكنسي
F: C1X1=C2X2+…+CnXnàmin
a11x1+a21x2+…+an1xn=b1
a12x1+a22x2+…+an2xn=b2
…………………………
a1mx1+a2mx2+…+anmxn=bm
ثم يتم تحويله إلى النموذج
F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin
a11x1+a21x2+…+an1xn+xn+1=b1
a12x1+a22x2+…+an2xn+xn+2=b2
……………………………….
a1mx1+a2mx2+…+anmxn+xn+m=bm
حيث M لا نهاية لها أعداد كبيرة. في المشكلة الناتجة، يكون الأساس الأولي مرئيًا على الفور؛ ويجب أن تؤخذ المتجهات ذات المتغيرات المقدمة بشكل مصطنع xn+1، xn+2،…، xn+m كما هي. حيث أن هذه المتجهات سيكون لها الشكل: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). يتم بعد ذلك حل المشكلة المحولة باستخدام خوارزمية الطريقة البسيطة. الخطة المرجعية الأولية للمسألة المحولة لها الشكل (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, بي ام). يبدو الجدول البسيط الأصلي كما يلي:
| أساس | معامل في الرياضيات او درجة قوات التحالف | يخطط | ج1 | ج2 | … | CN | م | م | … | م |
| أ1 | أ2 | … | ان | +1 | و+2 | … | ان+م | |||
| +1 | م | ب1 | a11 | a21 | … | an1 | 1 | 0 | … | 0 |
| و+2 | م | ب2 | a12 | a22 | … | an2 | 0 | 1 | … | 0 |
| … | … | … | … | … | … | … | … | … | … | … |
| ان+م | م | بي ام | a1m | a2m | … | أنم | 0 | 0 | … | 1 |
| Z0 | ||||||||||
نحدد عناصر السطر الإضافي باستخدام الصيغ Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi
لتحديد الاختلافات Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n
Zj-Cj=M∑mj=1aij-Cj
بعد استلام الجدول البسيط الأصلي، يتم تحويله، ومحاولة استخلاصه من المتجهات الأساسية المقابلة للمتغيرات الإضافية المقدمة.
نظرًا لأن M جدًا رقم ضخم، فسيكون هناك الكثير من بين الاختلافات Zj-Cj أرقام إيجابية. أي أنه سيكون هناك العديد من المرشحين لإدراجهم في الأساس بين المتجهات A1,A2,…,An
إذا كان بعض المتجهات يتوافق مع المتغيرات المقدمة بشكل مصطنع xn+1,xn+2,...,xn+m، فسيتم اشتقاق المتجه المقابل من الأساس، ويتم شطب العمود البسيط في الجدول الذي يحتوي على هذا المتجه ولا يتم إرجاعه إليها مرة أخرى. في نهاية تحويل الجدول البسيط، هناك خياران ممكنان:
· تم اشتقاق جميع المتجهات المقابلة للمتغيرات الاصطناعية من الأساس، وفي هذه الحالة ستختفي جميع أعمدة الجدول البسيط المقابلة للمتغيرات الإضافية، وسيكون الحل المشكلة الأصلية
· ستظل الخطة المثالية الناتجة تحتوي على بعض المتغيرات الإضافية، وهذا يعني أن ODD للمشكلة الأصلية فارغ، أي أن قيودها متناقضة، وبالتالي فإن المشكلة الأصلية ليس لها حلول على الإطلاق.
مشاكل البرمجة الخطية المزدوجة. بيان المشكلات وخصائصها.
مشاكل مزدوجة متماثلة:
النموذج القياسي الأول
و(خ)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+…+an1xn>=b1
a12x1+a22x2+…+an2xn>=b2
…………………………………………..
a1mx1+a2mx2+…+anmxn>=bm
مشكلة مزدوجة
د(ص)=b1y1+b2y2+…+bmymàmax
a11y1+a12y2+…+a1mym=0, V j=1,m
زوج غير سبعيني من المشاكل المزدوجة
المشكلة الأصلية في شكل قانوني
و(خ)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+..+an1xn=b1
a12x1+a22x2+..+an2xn=b2
…………………………..
محاضرة 3.الجداول البسيطة. خوارزمية الطريقة البسيطة.
§ 3 طريقة بسيطة
3.1. الفكرة العامة للطريقة البسيطة. التفسير الهندسي
تنطبق الطريقة الرسومية على فئة ضيقة جدًا من مشاكل البرمجة الخطية: يمكنها حل المشكلات التي لا تحتوي على أكثر من متغيرين بشكل فعال. تم الأخذ في الاعتبار النظريات الأساسية للبرمجة الخطية، والتي يترتب عليها أنه إذا كان لمشكلة البرمجة الخطية حل أمثل، فإنها تتوافق على الأقل مع نقطة زاوية واحدة من الحل متعدد السطوح وتتزامن، وفقًا لـ على الأقل، مع أحد الحلول الأساسية المقبولة لنظام القيود. تمت الإشارة إلى طريقة لحل أي مشكلة في البرمجة الخطية: تعداد عدد محدود من الحلول الأساسية الممكنة لنظام القيود واختيار الحل الأمثل من بينها الذي تمثل الدالة الهدف الحل الأمثل له. هندسيًا، يتوافق هذا مع تعداد جميع النقاط الزاوية لمحلول متعدد السطوح. سيؤدي هذا البحث الشامل في النهاية إلى الحل الأمثل (إذا كان موجودا)، لكن تنفيذه العملي يرتبط بصعوبات هائلة، لأنه بالنسبة للمشاكل الحقيقية، فإن عدد الحلول الأساسية الممكنة، على الرغم من أنها محدودة، يمكن أن تكون كبيرة للغاية.
يمكن تقليل عدد الحلول الأساسية المسموح بالبحث عنها إذا لم يتم إجراء البحث بشكل عشوائي، ولكن مع مراعاة التغيرات في الدالة الخطية، أي. التأكد من أن كل حل تالٍ "أفضل" (أو على الأقل "ليس أسوأ") من الحل السابق، وفقًا لقيم الدالة الخطية (زيادتها عند إيجاد الحد الأقصى، وخفضها عند إيجاد الحد الأدنى 
).
يتيح لك هذا البحث تقليل عدد الخطوات عند العثور على الحل الأمثل. دعونا نشرح ذلك بمثال بياني.
دع منطقة الحلول الممكنة تكون ممثلة بمضلع ABCDE. لنفترض أن نقطة الزاوية أيتوافق مع الحل الأساسي الممكن الأصلي. سيتطلب البحث العشوائي اختبار خمسة حلول أساسية ممكنة تتوافق مع نقاط الزاوية الخمس للمضلع. لكن واضح من الرسم أنه بعد القمة أمن المفيد الانتقال إلى قمة مجاورة في،ومن ثم إلى النقطة الأمثل مع.فبدلاً من خمسة، مررنا بثلاثة رؤوس فقط، مما أدى إلى تحسين الدالة الخطية باستمرار.
شكلت فكرة تحسين الحل بشكل متتابع الأساس لطريقة عالمية لحل مشاكل البرمجة الخطية - الطريقة البسيطة أو طريقة التحسين المتسلسل للخطة.
يتكون المعنى الهندسي للطريقة البسيطة من انتقال متسلسل من أحد رؤوس متعدد السطوح القيد (يسمى الأولي) إلى الرأس المجاور، حيث تأخذ الدالة الخطية أفضل قيمة (على الأقل ليس الأسوأ) فيما يتعلق بالقيمة هدف المشكلة؛ حتى يتم العثور على الحل الأمثل - القمة التي يتم فيها تحقيق القيمة المثلى لوظيفة الهدف (إذا كانت المشكلة لها قيمة نهائية مثالية).
تم اقتراح الطريقة البسيطة لأول مرة من قبل العالم الأمريكي ج. دانزيج في عام 1949، ولكن في عام 1939 تم تطوير أفكار الطريقة من قبل العالم الروسي إل. كانتوروفيتش.
الطريقة البسيطة، التي تسمح بحل أي مشكلة في البرمجة الخطية، هي طريقة عالمية. حاليًا، يتم استخدامه لحسابات الكمبيوتر، ولكن يمكن حل الأمثلة البسيطة باستخدام الطريقة البسيطة يدويًا.
لتنفيذ الطريقة البسيطة - التحسين المتسلسل للحل - من الضروري إتقانها ثلاثة عناصر رئيسية:
طريقة لتحديد بعض الأولية مقبولة الحل الأساسيمهام؛
قاعدة الانتقال إلى الحل الأفضل (بتعبير أدق، وليس الأسوأ)؛
معيار للتحقق من الأمثلية الحل الموجود.
لاستخدام الطريقة البسيطة، يجب اختزال مشكلة البرمجة الخطية إلى الشكل الأساسي، أي. يجب تقديم نظام القيود في شكل معادلات.
تصف الأدبيات بتفاصيل كافية: العثور على خطة الدعم الأولية (الحل الأساسي المقبول الأولي)، وكذلك باستخدام طريقة الأساس الاصطناعي، وإيجاد خطة الدعم المثالية، وحل المشكلات باستخدام الجداول البسيطة.
3.2. خوارزمية الطريقة البسيطة.
دعونا نفكر في حل ZLP باستخدام الطريقة البسيطة ونقدمه فيما يتعلق بمشكلة التعظيم.
1. بناء على شروط المشكلة يتم تجميع نموذجها الرياضي.
2. يتم تحويل النموذج المكتمل إلى النموذج الأساسي. وفي هذه الحالة يمكن تحديد أساس بخطة مرجعية أولية.
3. يتم كتابة النموذج القانوني للمشكلة في شكل جدول بسيط بحيث تكون جميع الحدود الحرة غير سلبية. إذا تم تحديد الخطة المرجعية الأولية، فانتقل إلى الخطوة 5.
الجدول البسيط: يتم إدخال نظام معادلات القيد والدالة الموضوعية في شكل تعبيرات تم حلها بالنسبة للأساس الأولي. خط يحتوي على معاملات الدالة الهدف 
، مُسَمًّى 
- سلسلة أو سلسلة من الوظيفة الهدف.
4. العثور على المخطط المرجعي الأولي عن طريق إجراء تحويلات بسيطة مع عناصر حل إيجابية تتوافق مع الحد الأدنى من العلاقات البسيطة، ودون مراعاة علامات العناصر 
-خطوط. إذا تمت مواجهة صف 0 أثناء التحويلات، وجميع عناصره، باستثناء الحد الحر، هي أصفار، فإن نظام معادلات القيد للمشكلة غير متسق. إذا واجهنا صفًا من 0 لا توجد فيه عناصر إيجابية أخرى، باستثناء الحد الحر، فإن نظام المعادلات المقيدة ليس له حلول غير سلبية.
وسوف نسمي اختزال النظام (2.55)، (2.56) إلى أساس جديد التحول البسيط . إذا تم اعتبار التحويل البسيط بمثابة عملية جبرية شكلية، فيمكن ملاحظة أنه نتيجة لهذه العملية، يتم إعادة توزيع الأدوار بين متغيرين مدرجين في نظام معين وظائف خطية: يتحول أحد المتغيرين من التابع إلى المستقل، والآخر، على العكس من ذلك، ينتقل من المستقل إلى التابع. تُعرف هذه العملية في الجبر باسم خطوة القضاء على الأردن.
5. يتم فحص خطة الدعم الأولية التي تم العثور عليها للتأكد من أنها مثالية:
أ) إذا كان في 
- لا توجد عناصر سلبية في الصف (بدون احتساب المدة الحرة)، فالخطة هي الأمثل. إذا لم تكن هناك أصفار، فهناك خطة مثالية واحدة فقط؛ إذا كان هناك صفر واحد على الأقل، فهناك عدد لا حصر له من الخطط المثالية؛
ب) إذا ج 
– يوجد عنصر سلبي واحد على الأقل في الصف، وهو ما يتوافق مع عمود من العناصر غير الإيجابية 
;
ج) إذا كان في 
– يحتوي الصف على عنصر سلبي واحد على الأقل، والعمود الخاص به يحتوي على عنصر إيجابي واحد على الأقل، ثم يمكنك الانتقال إلى عنصر جديد الخطة المرجعية، أقرب إلى الأمثل. للقيام بذلك، يجب تعيين العمود المحدد كعمود تحليل، باستخدام الحد الأدنى لنسبة الإرسال البسيط، والعثور على صف التحليل وإجراء تحويل بسيط. يتم فحص الخطة المرجعية الناتجة مرة أخرى للتأكد من أنها مثالية. يتم تكرار العملية الموضحة حتى يتم الحصول على الخطة المثالية أو حتى يتم إثبات عدم إمكانية حل المشكلة.
يسمى عمود المعاملات للمتغير الموجود في الأساس بالحل. وبالتالي، يتم اختيار متغير يتم إدخاله في الأساس (أو اختيار عمود حل) بواسطة العنصر السالب 
-سلاسل، ونحن نقدم وظيفة متزايدة 
.
من الأصعب قليلاً تحديد المتغير الذي سيتم استبعاده من الأساس. للقيام بذلك، يقومون بتكوين نسب المصطلحات الحرة إلى العناصر الإيجابية لعمود الحل (تسمى هذه العلاقات بسيطة) ويجدون الأصغر بينها، والذي يحدد الصف (الحل) الذي يحتوي على المتغير المستبعد. إن اختيار متغير مستبعد من الأساس (أو اختيار خط الحل) وفقًا للحد الأدنى من العلاقة البسيطة يضمن، كما تم تحديده بالفعل، إيجابية مكونات الأساس في الخطة المرجعية الجديدة.
في النقطة 3 من الخوارزمية، من المفترض أن جميع عناصر عمود المصطلحات الحرة غير سلبية. هذا المطلب ليس ضروريًا، ولكن إذا تم استيفاءه، فسيتم تنفيذ جميع التحويلات البسيطة اللاحقة فقط باستخدام عناصر حل إيجابية، وهو أمر مناسب للحسابات. إذا كانت هناك أرقام سالبة في عمود المصطلحات الحرة، فسيتم اختيار عنصر الحل على النحو التالي:
1) انظر إلى السطر المقابل لبعض المصطلحات الحرة السلبية، على سبيل المثال 
- صف، واختيار أي عنصر سلبي فيه، ويتم أخذ العمود المقابل كحل (نفترض أن قيود المشكلة متسقة)؛
2) تكوين علاقات عناصر عمود المصطلحات الحرة بالعناصر المقابلة لعمود الحل التي لها نفس العلامات (العلاقات البسيطة)؛
3) اختر أصغر العلاقات البسيطة. سيحدد هذا سلسلة التمكين. فليكن مثلا ر-خط؛
4) عند تقاطع عمود الحل والصف، تم العثور على عنصر الحل. إذا كان العنصر مباحا 
-سلاسل، ثم بعد التحويل البسيط، سيصبح الحد الحر لهذه السلسلة موجبًا. خلاف ذلك، في الخطوة التالية ننتقل مرة أخرى إلى 
-خط. إذا كانت المشكلة قابلة للحل، فبعد عدد معين من الخطوات، لن تكون هناك عناصر سلبية في عمود المصطلحات المجانية.
إذا تم وضع حالة إنتاج حقيقية معينة في شكل PLP، فإن المتغيرات الإضافية التي يجب إدخالها في النموذج في عملية تحويله إلى الشكل الأساسي يكون لها دائمًا معنى اقتصادي معين.