الانتقال من قيود النموذج الرياضي الخطي. إنشاء نموذج رياضي لمشكلة البرمجة الخطية. اختيار حجم إعادة التوزيع

محاضرة 2

الخامس شكل قانوني

قرار مقبول من LPP(خطة مقبولة).

الحل الأمثل لـ LPP.

يحتاج

مثال.

دعنا نكتب المهمة في شكل قانوني

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

إلا عندما تكون المشكلة الحل الأمثل الوحيدلربما حالات خاصة:

1. مشكلة لها عدد لا حصر له من الحلول المثلى - يتم الوصول إلى الحد الأقصى للوظيفة في الفترة الزمنية ( البديل الأمثل)- الشكل 2؛

2. المهمة غير قابل للحل بسبب عدم حدود IDT ، أو - الشكل 3 ؛

3. المعاملة الخاصة والتفضيلية - نقطة واحدة اه اذن

4. المهمة غير قابل للحل إذا كان ODR منطقة فارغة.

أ

الصورة 2 الصورة 3

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

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

مثال... حل المسألة بيانيا البرمجة الخطية (البديل الأمثل):

أسئلة لضبط النفس

1. اكتب مشكلة البرمجة الخطية بشكل عام.

2. اكتب مشكلة البرمجة الخطية بالصيغة الأساسية والقياسية.

3- ما هي التحولات التي يمكن استخدامها للانتقال من الشكل العام أو القياسي لمشكلة البرمجة الخطية إلى الشكل الأساسي؟

4. أعط تعريف الحلول الممكنة والأمثل لمشكلة البرمجة الخطية.

5. أي من الحلول هو "الأفضل" لمشكلة تصغير دالة ، إذا ?

6. أي من الحلول هو "الأفضل" لمشكلة تكبير دالة ، إذا ?

7. اكتب الصيغة القياسية للنموذج الرياضي لمشكلة البرمجة الخطية بمتغيرين.

8. كيف نبني نصف مستوى معطى بواسطة متباينة خطية في متغيرين ?

9. ما يسمى حل نظام من المتباينات الخطية في متغيرين؟ بناء على المستوى ، منطقة الحلول الممكنة لمثل هذا النظام من المتباينات الخطية ، والتي:

1) لديه حل فريد ؛

2) لديه عدد لا حصر له من الحلول ؛

3) ليس لها حل واحد.

10. قم بتدوين ملاحظة لـ دالة خطية متجه متدرج ، اسم نوع خطوط المستوى. كيف يتم وضع خطوط التدرج والمستوى بالنسبة لبعضها البعض؟

11. قم بصياغة خوارزمية لطريقة رسومية لحل LPP القياسي بمتغيرين.

12. كيف تجد إحداثيات الحل والقيم؟

13. ارسم منطقة الحلول الممكنة ، خطوط التدرج والمستوى لمشاكل البرمجة الخطية ، حيث:

1) يتم بلوغه في نقطة واحدة ، و- على المقطع ODR ؛

2) يتم بلوغه في نقطة واحدة من تسوية المنازعات بالاتصال الحاسوبي المباشر ، و.

14. أعط توضيحًا هندسيًا لـ LPP ، إذا كان:

1) لديها الحلول المثلى الوحيدة لـ و ؛

2) العديد من الحلول المثلى ل.

محاضرة 2

طريقة رسوميةإيجاد الحل الأمثل

1. أشكال النماذج الرياضية الخطية وتحولاتها

2. طريقة رسومية لحل مشكلة البرمجة الخطية

3. حالات خاصة للحل الرسومي لـ LPP

4. الحل الرسومي للمشاكل الاقتصادية للبرمجة الخطية

أشكال النماذج الرياضية الخطية وتحولاتها

يمكن كتابة النموذج الرياضي لمشكلة البرمجة الخطية (LPP) بأحد الأشكال الثلاثة.

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

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

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

يسمى حل لنظام القيود الذي يلبي شروط عدم سلبية المتغيرات قرار مقبول من LPP(خطة مقبولة).

تسمى مجموعة الحلول الممكنة مجال الحلول المقبولة من LPP.

يسمى الحل المجدي الذي تصل فيه الوظيفة الهدف إلى قيمة قصوى الحل الأمثل لـ LPP.

الأشكال الثلاثة للكتابة LPP متكافئة بمعنى أنه يمكن اختزال كل منها إلى شكل مختلف باستخدام التحولات الرياضية.

يحتاج الانتقال من نموذج رياضي إلى آخريرتبط بطرق حل المشكلات: على سبيل المثال ، يتم تطبيق طريقة simplex ، المستخدمة على نطاق واسع في البرمجة الخطية ، على مشكلة مكتوبة في شكل أساسي ، ويتم تطبيق الطريقة الرسومية على الشكل القياسي للنموذج الرياضي.

الانتقال إلى الشكل المتعارف عليه لكتابة ZLP.

مثال.

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

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

لذلك ، في مشكلة استخدام المواد الخام ، تظهر بقية المواد الخام ، وفي مشكلة اختيار التقنيات المثلى - الوقت غير المستخدم للمؤسسة لتقنية معينة ؛ في مشكلة القطع - تحرير الفراغات بطول معين على الخطة ، إلخ.

تعريف. البرمجة الخطية (LP) -علم طرق البحث وإيجاد القيم المتطرفة (الأكبر والأصغر) لدالة خطية ، والتي تخضع مجهولاتها لقيود خطية.

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

تعريف.يسمى التعبير الرياضي للوظيفة الموضوعية وقيودها نموذج رياضي للمشكلة الاقتصادية.

الخامس نظرة عامةتتم كتابة النموذج الرياضي لمشكلة البرمجة الخطية (LP) على شكل

مع قيود:

أين س ي- غير معروف؛ ij, ب ط, ج ي- قيم ثابتة.

يمكن كتابة كل أو بعض معادلات نظام القيود في شكل متباينات.

النموذج الرياضي في تدوين أكثر إيجازًا له الشكل

مع قيود:

تعريف.الحل المقبول (خطة) لمشكلة البرمجة الخطية هو ناقل = ( x 1 , x 2 ,..., x ن) ،استيفاء نظام القيود.

تشكل مجموعة الحلول الممكنة مجال الحلول الممكنة (ODS).

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

حل عملي أساسي (NS 1 , NS 2 ، ... ، xص , 0, …, 0) هو الحل المرجعي ، حيث ص -رتبة نظام القيود.

يمكن أن يكون النموذج الرياضي لمشكلة LP قانونيًا وغير قانوني.

7- حل مسائل البرمجة الخطية بالطريقة الرسومية... الرسوم البيانية الدالة القيود. خطوط المستوى.

طريقة رسومية لحل مسائل البرمجة الخطية

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

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

لإيجاد القيمة القصوى للدالة الهدف في الحل الرسومي لمشاكل LP ، استخدم المتجه إل() على السطح NS 1 أوه 2 , الذي نشير إليه . يوضح هذا المتجه اتجاه أسرع تغيير في الوظيفة الموضوعية. بمعنى آخر ، المتجه هو المستوى الطبيعي لخط المستوى إل()

أين ه 1 و ه 2 - نواقل الوحدة على طول المحاور ثور 1 و ثور 2 على التوالي هكذا = (∂L / ∂х 1 ، ∂L / ∂х 2 ). إحداثيات المتجه هي معاملات دالة الهدف لام ().سيتم النظر في إنشاء خط المستوى بالتفصيل عند حل المشكلات العملية.

خوارزمية لحل المشاكل

1. أوجد منطقة الحلول الممكنة لنظام قيود المشكلة.

2. بناء ناقل .

3. ارسم خطًا مستويًا إل 0 , وهو عمودي .

4. حرك خط المستوى في اتجاه المتجه للمهام إلى الحد الأقصى وفي الاتجاه المعاكس , للمهام إلى الحد الأدنى.

يتم نقل خط المستوى حتى يكون له نقطة مشتركة واحدة فقط مع منطقة الحلول المقبولة. ستكون هذه النقطة ، التي تحدد الحل الوحيد لمشكلة LP ، هي النقطة القصوى.

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

حيث 0 ≤ ر≤ 1 و 1 و 2 - الحلول المثلى في نقاط الزاوية في ODR.

يمكن أن تكون مشكلة LP غير قابلة للحل عندما تكون القيود التي تحددها متناقضة.

5. أوجد إحداثيات النقطة القصوى وقيمة دالة الهدف فيها.

مثال 3.تحديد الخيار الأمثل لتحرير المنتج

تنتج الشركة نوعين من الآيس كريم: الكريمة والشوكولاتة. لتصنيع الآيس كريم ، يتم استخدام منتجين أوليين: الحليب والمواد المالئة ، وتكاليف كل 1 كجم من الآيس كريم والإمدادات اليومية مذكورة في الجدول.

أظهرت دراسة سوق المبيعات أن الطلب اليومي على الآيس كريم يتجاوز الطلب على آيس كريم الشوكولاتة ولكن بما لا يزيد عن 100 كيلوغرام.

إضافة إلى ذلك فقد وجد أن الطلب على آيس كريم الشوكولاتة لا يتجاوز 350 كيلوغراماً في اليوم. سعر التجزئة 1 كجم من الآيس كريم الكريمي 16 روبل ، الشوكولاته - 14 روبل.

ما هي كمية الآيس كريم من كل نوع التي يجب أن تنتجها الشركة من أجل زيادة الدخل من مبيعات المنتجات؟

حل.دعنا نشير: x 1 - الحجم اليومي لإنتاج الآيس كريم ، كجم ؛ x 2 - الانتاج اليومي من آيس كريم الشوكولاتة، كغم.

لنقم بعمل نموذج رياضي للمشكلة.

أسعار الآيس كريم معروفة: 16 روبل و 14 روبل على التوالي ، لذا فإن الوظيفة الموضوعية ستبدو كما يلي:

سنضع حدودا على الحليب للآيس كريم. استهلاكه للآيس كريم الكريمي - 0.8 كجم ، للشوكولاتة - 0.5 كجم. مرقة الحليب 400 كغ. لذلك ، ستبدو المتباينة الأولى كما يلي:

0.8x 1 + 0.5x 2 ≤400 - المتباينة الأولى هي قيد. تتكون بقية التفاوتات بطريقة مماثلة.

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

شكل عابدف -مجال الحلول المقبولة. نبني ناقل (16 ؛ 14). خط المستوى إليتم الحصول على 0 من المعادلة 16x 1 + 14x 2 = Const. نختار أي رقم ، على سبيل المثال الرقم 0 ، ثم 16x 1 + 14x 2 = 0. في الشكل ، بالنسبة للخط L 0 ، يتم تحديد رقم موجب معين لا يساوي الصفر. جميع خطوط المستوى موازية لبعضها البعض. خط المستوى العادي المتجه.

حرك خط المستوى في اتجاه المتجه. نقطة الخروج إل 0 من منطقة الحلول الممكنة هي النقطة د، يتم تحديد إحداثياته ​​على أنها تقاطع للخطوط المستقيمة المعطاة بواسطة المعادلات:

بحل النظام ، نحصل على إحداثيات النقطة د(312.5 ؛ 300) ، حيث سيكون هناك حل أمثل ، أي

وبالتالي ، يجب أن تنتج الشركة 312.5 كجم من الآيس كريم و 300 كجم من آيس كريم الشوكولاتة يوميًا ، بينما يبلغ الدخل من المبيعات 9200 روبل.

8. الحد من مشكلة البرمجة الخطية التعسفية إلى المشكلة الرئيسية.تحويل قيود عدم المساواة إلى المعادلات المقابلة.

9. طريقة بسيطة... وصف وخوارزمية الطريقة وإمكانية تطبيقها.

لحل المشكلة باستخدام طريقة simplex ، من الضروري:

1. حدد طريقة للعثور على حل الدعم الأمثل

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

3. حدد المعايير التي تسمح لك بالتوقف في الوقت المناسب عن البحث عن حلول الدعم بشأن الحل الأمثل أو تمرير استنتاج بشأن عدم وجود حل أمثل.

خوارزمية طريقة simplex لحل مشاكل البرمجة الخطية

1. قم بإحضار المشكلة إلى الشكل المتعارف عليه

2. ابحث عن حل الدعم الأولي باستخدام "أساس الوحدة" (إذا لم يكن هناك حل دعم ، فلن يكون هناك حل للمشكلة ، بسبب عدم توافق نظام القيود)

3. احسب تقديرات توسعات المتجهات على أساس حل الدعم واملأ جدول طريقة simplex

4. إذا تم استيفاء معيار تفرد الحل الأمثل ، ينتهي حل المشكلة

5. إذا تم استيفاء شرط وجود مجموعة من الحلول المثلى ، فعند العد البسيط يتم إيجاد جميع الحلول المثلى

10. مشكلة النقل.تعريف وأنواع وطرق إيجاد الحل الأولي لمشكلة النقل.

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

1. إيجاد حل الدعم الأولي.

2. التحقق من هذا الحل للأمثل.

3. الانتقال من حل دعم إلى آخر.

3.1 مشكلة البرمجة العامة الخطية

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

تتضمن البرمجة الخطية عددًا من طرق الحل التجريبية (التقريبية) التي تسمح ، في ظل ظروف معينة ، للجميع الخيارات الممكنةلاختيار الحل الأفضل والأمثل لمشاكل الإنتاج. تتضمن هذه الطرق ما يلي - الرسم ، البسيط ، الطريقة المحتملة (طريقة التوزيع المعدلة - MODI) ، Hitchkova ، Kreko ، طريقة التقريب Vogel وغيرها.

توحد بعض هذه الطرق باسم شائع - طريقة التوزيع أو النقل.

مهد البرمجة الخطية هي روسيا. الأعمال الأولى على البرمجة الخطية للأكاديمي المستقبلي L.V. تم نشر Kantorovich في عام 1939. وفي عام 1975 ، حصل على جائزة نوبل في الاقتصاد لتطوير أساليب البرمجة الخطية. نظرًا لأن معظم أعمال الأكاديمي L.V. تكرس Kantorovich لحل مشاكل النقل ، ويمكن اعتبار أن جائزة نوبل المحددة تعترف أيضًا بمزايا علوم النقل الروسية.

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

ميزات نموذج البرمجة الخطية هي كما يلي:

يتم التعبير عن الوظيفة والقيود الموضوعية من خلال التبعيات الخطية (المساواة أو عدم المساواة) ؛

عدد التبعيات دائمًا أقل من عدد المجهول (حالة عدم اليقين) ؛

عدم سلبية المتغيرات المطلوبة. الشكل العام لكتابة نموذج البرمجة الخطي في شكل مختصر هو كما يلي:

تجد NS ij ≥ 0 (j = 1، 2 ... n) تحت قيود من النوع التالي:

هذه القيود تقلل (أو تعظم) الوظيفة الموضوعية

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

أ 11 × 1 + أ 12 × 2 + ... + أ 1 ن س ن = ب 1 ؛

أ 21 س 1 + أ 22 س 2 + ... + أ 2 ن س ن = ب 2 ; (3.1)

……………………………..

أ م س 1 + أ م 2 س 2 + ... + أ م ن س ن = ب م ..

إذا كان النموذج مكتوبًا في شكل متباينات بأرقام غير سالبة ، فهذا يعني أنه يحتوي على الشكل

أ 11 × 1 + أ 12 × 2 + ... + أ 1 ن × ن ≤ ب 1 ؛

أ 21 س 1 + أ 22 س 2 + ... + أ 2 ن س ن ≤ ب 2 ; (3.2)

……………………………..

أ م س 1 + أ م 2 س 2 + ... + أ م ن س ن ≤ ب م ، ..

ثم يتم تقليل هذا السجل إلى العنوان الأساسيشكل (3.1) عن طريق إدخال متغيرات إضافية x ن +1> 0 (أنا=1,2…م) إلى يسار المتباينة (أو إلغاء عدد المتغيرات ، إذا كانت علامة عدم المساواة موجهة في الاتجاه الآخر). المتغيرات الإضافية تشكل الأساس.

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

L = s 1 x 1 + s 2 x 2 ... s n x n →دقيقة ، (3.3)

أين ق 1 ، ق 2 ... ق ن- معاملات دالة الهدف إلمع المتغيرات NSي.

متغيرات إضافية تدخل دالة الهدف مع صفر معاملات.

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

الحل الأساسي لنظام المعادلات الخطية (3.1) هو حل يتم فيه إعطاء قيم صفرية للمتغيرات غير الأساسية.

يُطلق على الحل الأساسي اسم مقبول تكون فيه المتغيرات المدرجة في الأساس غير سلبية.

الحل الأمثل هو حل عملي يزيد (أو يصغر) الوظيفة الهدف (3.3).

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

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

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

3.2 طريقة الرسم التحليلي

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

حل مشكلة ذات متغيرين × 1و × 2، التي لا ينبغي أن تكون سالبة بمعنى المشكلة ، يتم إجراؤها في نظام الإحداثيات الديكارتية. المعادلات × 1= 0 و × 2= 0 هي محاور نظام إحداثيات الربع الأول

دعونا نفكر في طريقة الحل باستخدام مثال محدد.

مثال 3.1.يوجد 300 طن من منتجات الخرسانة الرغوية و 200 طن من الفولاذ في المستودع. تحتاج شركة السيارات إلى تسليم هذه المنتجات إلى المنشأة قيد الإنشاء. تمتلك شركة السيارات شاحنات كاماز - 5320 و

ZIL-4314. لرحلة واحدة ، يمكن لـ KamAZ-5320 تسليم 6 أطنان من الخرسانة الرغوية و 2 طن من الفولاذ ، وستكون أرباح الرحلة 4 آلاف روبل. تقدم ZIL-4314 طنين من الخرسانة الرغوية و 4 أطنان من الفولاذ في رحلة واحدة ، وربح الرحلة 6 آلاف روبل. من الضروري تنظيم النقل بطريقة تضمن أكبر ربح لشركة السيارات.

دعونا نبني نموذجًا رياضيًا للمشكلة. دعونا نشير بمقدار x 1 العدد المطلوب من راكبي KamAZ-5320 وعبر NS 2 العدد المطلوب من الدراجين ZIL-4314.

إجمالي النقلفي منتجات الخرسانة الرغوية هو 6 × 1 + 2× 2، ومن الفولاذ 2 × 1 + 4× 2... قيود النقل بناءً على عدد العناصر المتاحة هي 6 × 1 + 2× 2 ≤ 300 طن للخرسانة الرغوية و 2 × 1 + 4× 2 ≤ 200 طن للصلب.

إجمالي الربح بالألف روبل يتم التعبير عنها كـ 4 NS 1 + 6NS 2 ، والتي تحتاج إلى تعظيم والتي هي معيار الأمثل في المشكلة قيد النظر. لذلك ، يبدو النموذج الرياضي للمشكلة كما يلي. من الضروري تعظيم الوظيفة الموضوعية

إل = 4× 1 + 6× 2 →كحد أقصى تحت الشروط: 6 × 1 + 2× 2 ≤ 300; 2× 1 + 4× 2 ≤ 200؛ × 1 ≥ 0;× 2 ≥ 0.

ضع في اعتبارك المعادلة 6 × 1 + 2× 2 = 300. لبناء خط مستقيم موصوف في هذه المعادلة ، نجد نقطتين على هذا الخط المستقيم. في × 1= 0 من معادلة الخط المستقيم نجد 2 × 2 = 300 ، حيث x 2 = 150. لذلك ، فإن النقطة A ذات الإحداثيات (0.150) تقع على الخط المستقيم المطلوب. في × 2= 0 لدينا 6 × 1= 300 ، ومن أين س 1 = 50 ، والنقطة دذات الإحداثيات (50،0) موجودة أيضًا على الخط المطلوب. ارسم خطًا مستقيمًا عبر هاتين النقطتين ميلادي(الشكل 3.1).

عدم المساواة الخطية 6 × 1 + 2× 2 ≤ 300 عبارة عن نصف مستوي يقع على أحد جانبي الخط المستقيم المركب 6 × 1 + 2× 2 = 300. لمعرفة أي جانب من هذا الخط المستقيم تقع نقاط نصف المستوى المطلوب ، نعوض بـ 6 × 1 + 2× 2 ≤ 300 إحداثيات أي نقطة لا تقع على خط الحدود. على سبيل المثال ، الأصل هو 0- (0،0). بالنسبة له ، المتباينة 6 ∙ 0 + 2 ∙ 0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой ميلاديوفي التين. 3.1 مظلل.

المعادلة 2 × 1 + 4× 2= 200 سنبني على نقطتين. في × 1 = 0 4× 2 = 200 من اين × 2 = 50. ثم النقطة هإحداثياته ​​(0.50) وينتمي إلى الخط المطلوب. في × 2= 0, 2× 2 = 200 نقطة معيقع على خط مع إحداثيات (100،0). التعويض بإحداثيات النقطة في المتباينة مع(0،0) ، نحصل على 2 ∙ 0 + 4 ∙ 0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2× 1+ 4× 2= 200.

يتطلب نظام قيود المشكلة أن الخطط ( × 1 ؛ × 2) استيفاء جميع التفاوتات الأربعة ، أي أن التصميمات المقبولة هي نقاط ( × 1 ؛ × 2) يجب أن يكون في نفس الوقت في جميع الطائرات النصفية الأربعة. يتم استيفاء هذا المطلب فقط من خلال النقاط الموجودة داخل وعلى حدود المضلع. OEKD، وهو مضلع الحلول الممكنة.

رؤوس المضلع في الحلول الممكنة هي النقاط O ، E ، K ، D ،سطر القطعة OE ، EK ، KD ، OD- ضلوعه. أي نقطة في المضلع OEKDهو مخطط المشكلة مستوفياً جميع شروطها. تتكون رؤوس المضلع من تقاطع خطين مستقيمين وتتوافق مع الخطط الأساسية للمشكلة ، ومن بينها أفضل خطة (مثالية). وبالتالي ، سيكون هناك العديد من الخطط الأساسية حيث توجد رؤوس في المضلع للحلول الممكنة.

يمكن أيضًا الحصول على تمثيل هندسي واضح للوظيفة الموضوعية. إل = 4× 1 + 6× 2... دعونا نصلح بعض قيمة الوظيفة الهدف ، على سبيل المثال إل= 120 المعادلة 4 × 1 + 6× 2 = 120 يعرّف الخط المار بنقطة الخامسبالإحداثيات (× 1 = 0 ؛ × 2 = 20) والنقطة إلمع إحداثيات (( NS 1 = 30; NS 2 = 0). الجزء BLيقع داخل المضلع OEKD... لذلك ، بالنسبة لجميع خطط (نقاط) هذا المقطع ، تكون قيمة الوظيفة الهدف هي نفسها وتساوي 120. من خلال تعيين قيم أخرى للوظيفة الهدف ، نحصل على خطوط متوازية ، والتي تسمى خطوط المستوىدالة الهدف.

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

يسمى الاتجاه التصاعدي العمودي على خط المستوى اتجاه أكبر زيادةالوظيفة الموضوعية وتحدد أقصى نمو لها. يمكن ضبط هذا الاتجاه بدون رسم خطوط مستوية. لهذا فمن الضروري على المحاور × 1و × 2لتأجيل المقاطع التي تساوي معاملات دالة الهدف ، ومن بينها ، كإحداثيات ، لإنشاء متجه أكبر زيادة في الوظيفة الهدف. في الرياضيات يطلق عليه الانحداروالدلالة بواسطة غراد. التدرج للوظيفة إل = 4 × 1 + 6 × 2سيكون هناك متجه ن| 4 ؛ 6 | ... لتسهيل بنائه ، سنقوم بزيادة الإحداثيات ، على سبيل المثال ، 10 مرات ، أي ن | 40 ؛ 60 | ... دعونا نبني انحدار دالة الهدف إل، والتي من أجلها نربط النقطة بالإحداثيات (40 ؛ 60) بالأصل. يتم رسم خطوط مستوى الوظيفة الموضوعية بشكل عمودي على اتجاه التدرج اللوني.

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

6× 1 + 2× 2= 300;

2× 1 + 4× 2= 200.

دعونا نساوي المعاملات عند x 1 بضرب المعادلة الثانية في 3 ، ثم نطرح الأولى من المعادلة الثانية. نحصل على 10 × 2= 300,× 2 = 30. استبدال القيمة x 2 = 30 في أي من المعادلات ، على سبيل المثال ، في الأولى ، نحدد القيمة NS 1:

6× 1+ 2NS · 30 = 300,

من أين 6 × 1 = 300-60 = 240 إذن × 1 = 40.

وبالتالي ، من أجل الحصول على أكبر ربح ، تحتاج شركة السيارات إلى إكمال 40 رحلة على KamAZ-5320 و 30 رحلة على ZIL-4314. سيكون الحد الأقصى للربح في هذه الحالة

إل = 4× 1 + 6× 2= 4 40 + 6 30 = 340 ألف روبل.

استنادًا إلى المثال المدروس والتفسير الهندسي لمشكلة التحسين بمتغيرين ، يمكن استخلاص الاستنتاجات التالية:

1) في الفضاء ثنائي الأبعاد ، تكون منطقة الحلول الممكنة مضلعًا ؛

2) يتوافق كل جانب من جوانب المضلع مع قيمة متغير واحد يساوي صفرًا ؛

3) كل رأس من مضلع الحلول الممكنة يتوافق مع قيم متغيرين تساوي الصفر ؛

4) خط مستقيم يتوافق مع كل قيمة دالة موضوعية ؛

5) الحل الأمثل للمسألة يتوافق مع قمة المضلع ، حيث تكتسب الدالة الهدف القيمة المثلى ، وإحداثيات هذا الرأس هي المتغيرات المثلى.

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

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

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

في التين. الشكل 3.2 ب يصور المجموعات غير المحدبة. في مجموعات nonconvex ، يمكن للمرء أن يشير إلى نقطتين على الأقل من المقطع AB لا تنتمي إلى المجموعة قيد الدراسة.

3.3 طريقة Simplex

طريقة Simplexهي طريقة شائعة لحل مشاكل البرمجة الخطية. حصلت هذه الطريقة على اسمها من كلمة "simplex" ، والتي تشير إلى أبسط مضلع محدب ، وعدد رؤوسه دائمًا يزيد بمقدار واحد عن بُعد المسافة. تم تطوير طريقة simplex في الولايات المتحدة من قبل عالم الرياضيات J. Danzig في أواخر الأربعينيات.

تتضمن طريقة simplex الحصول على حل أساسي غير سلبي لنظام المعادلات الخطية المتعارف عليها من النوع (3.1) ، والتقليل اللاحق (تعظيم) الوظيفة الموضوعية (3.3) وإيجاد القيم المثلى للمتغيرات المطلوبة بهذه الطريقة x 1، x 2 ... x n.

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

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

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

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

تتمثل المشكلة العامة للبرمجة الخطية في تقليل (تعظيم) الوظيفة الموضوعية ، والتي ترتبط متغيراتها بنظام المعادلات الخطية ، وتخضع لشرط عدم السلبية.

فليكن من الضروري تقليل الشكل الخطي

إل = مع 1 x 1 + مع 2 x 2 + ... مع n x n.

في ظل الظروف (من أجل الوضوح ، يتم الاحتفاظ بالمعاملات الصفرية وواحدة في المعادلات):

1× 1+ 0x 2 + ... 0س م + أ 1 م + 1 س م + 1 ... + أ 1 ن س ن = ب 1 ؛

0× 1 + 1× 2 +… 0س م + أ 2 م + 1 س م + 1 ... + أ 2 ن س ن = ب 2 ؛

……………………………………………

0× 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n = b m.

في نظام المعادلات هذا ، يوجد بالفعل أساس جاهز ، حيث تحتوي كل معادلة قيود على مجهول مع معامل يساوي واحدًا ، وهو غائب في المعادلات الأخرى ، أي من معاملات المتغيرات NS 1 , NS 2 …, س ميمكنك تكوين مصفوفة الهوية.

لنحل معادلات المتغيرات الأساسية:

س 1 = ب 1 - (أ 1 م + 1 × م + 1 ... + أ 1 ن × ن) ؛

س 2 = ب 2 - (أ 2 م + 1 × م + 1 ... + أ 2 ن × ن) ؛

………………………………

س م = ب م - (أ مم + 1 س م + 1 ... + أ م ن × ن) ،

ونعبر عن الوظيفة الموضوعية من حيث المتغيرات الحرة ، مع استبدال تعبيراتها من حيث المتغيرات الحرة بدلاً من المتغيرات الأساسية:

L = ص 1 ب 1 + ص 2 ب 2 + سمبم - (ص 1 أ 1 م + ص 2 أ 2 م + 1 + ... + سم م ن + 1) س م + 1 - ... - (ج 1 أ 1 ن + ص 2 أ 2 ن +… + cma mn) xn… + cnx n ..

المتغيرات × 1 ، × 2 ... ، × م، بمساعدة الخطة الأساسية الأولى ، هي أساسية ، والباقي س م +1 ، س م +2 ، ... س ن -مجانا. يجب أن يكون هناك دائمًا العديد من المتغيرات الأساسية كما توجد معادلات في النظام. بناءً على حالة اللاسلبية ، فإن أصغر قيمة للمتغيرات الحرة هي صفر. الحل الأساسي الذي تم الحصول عليه لنظام المعادلات هو الحل المبدئي المقبول ، أي س 1 = ب 1 ، س 2 = ب 2 ، ... س م = ب م ، س م +1 = 0,...، x n = 0.

هذا الحل يتوافق مع قيمة دالة الهدف

إل = ص 1 ب 1 + ص 2 ب 2 + ... ص م ب م.

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

تتكون الجداول المفردة على النحو التالي (انظر الجدول 3.1). يتم وضع جميع المتغيرات في أعلى الجدول. NS 1 , NS 2 …, x نوالمعاملات ج ي، والتي يتم تضمين المتغيرات المقابلة لها في وظيفة الهدف. العمود الأول ج طيتكون من معامل دالة الهدف للمتغيرات المدرجة في الأساس. يتبع ذلك عمود من المتغيرات الأساسية وشروط المعادلات المجانية. تمثل عناصر الأعمدة المتبقية من الجدول معاملات المتغيرات التي يتم تضمينها في نظام المعادلات. وبالتالي ، فإن كل صف من الجدول يتوافق مع معادلة النظام ، ويتم حلها فيما يتعلق بالمتغير الأساسي. يوضح الجدول أيضًا متغيرًا للخطة يتوافق مع الوظيفة الموضوعية لأساس معين.

الصف السفلي من الجدول يسمى فهرس... كل عنصر من عناصره (تقدير) ∆ يحدد

∆ي = ض ي - ج ج ،

أين ج ي- معاملات المتغيرات المقابلة في دالة الهدف ؛ ض ي -مجموع حاصل ضرب معاملات دالة الهدف للمتغيرات الأساسية بواسطة المتغيرات المقابلة - العناصر ي- عمود الجدول.

طاولة 3.1

جدول مفرد بصلاحية أولية

في الممارسة العملية ، غالبًا ما يتم تحديد القيود في مشكلة البرمجة الخطية ليس من خلال المعادلات ، ولكن من خلال عدم المساواة.

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

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

مطلوب للعثور على مجموعة من القيم غير السالبة التي ترضي عدم المساواة (4.1) ، علاوة على ذلك ، ستقلل من الوظيفة الخطية:

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

أين توجد بعض المتغيرات الجديدة التي سوف نسميها "إضافية". وفقًا للشروط (4.1) ، تكون هذه المتغيرات الإضافية ، كما ينبغي ، غير سلبية.

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

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

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

مثال 1 توجد مشكلة برمجة خطية مع قيود عدم المساواة: أوجد القيم غير السالبة للمتغيرات التي تحقق الشروط

وتقليل الوظيفة الخطية

مطلوب إحضار هذه المهمة إلى شكل OZLP.

حل. نقوم بتقليل التفاوتات (4.4) إلى الشكل القياسي ؛

نقدم متغيرات إضافية:

يتم تقليل المهمة لإيجاد القيم غير السالبة للمتغيرات

تلبية المعادلات (4.6) وتقليل الدالة الخطية (4.5).

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

مثال 2. توجد مشكلة برمجة خطية مع قيود المساواة (LPPP):

والوظيفة المراد تصغيرها

مطلوب كتابتها كمشكلة برمجة خطية مع قيود عدم المساواة.

حل. منذ ذلك الحين ، سنختار اثنين من المتغيرات مجانًا. لاحظ أنه لا يمكن اختيار المتغيرات كمتغيرات حرة ، لأنها مرتبطة بأول المعادلات (4-7): يتم تحديد قيمة أحدهما تمامًا بواسطة قيمة الآخر ، ويجب أن تكون المتغيرات الحرة مستقلة

للسبب نفسه ، من المستحيل اختيار المتغيرات على أنها مجانية (ترتبط بالمعادلة الثانية). دعنا نختار كمتغيرات مجانية ونعبر عن كل المتغيرات الأخرى من خلالها:

بما أن الشروط (4 9) يمكن استبدالها بعدم المساواة:

دعنا نمرر في تعبير الدالة الخطية L إلى المتغيرات الحرة بالتعويض في L بدلاً من تعبيراتها (4.9). نحن نحصل.

مفاهيم النمذجة الأساسية

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

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

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

اقتصاد- هذا هو نظام الإنتاج الاجتماعي الذي يقوم في الواقع بإنتاج وتوزيع وتبادل واستهلاك السلع المادية اللازمة للمجتمع.

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

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

تتكون مشكلة البرمجة الخطية من دالة موضوعية ونظام قيود وشرط غير سلبي للمتغيرات.

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

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

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

أوجد الطرف الأقصى للدالة

مع قيود

في ظل ظروف غير سلبية

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

مخازن أنا- نوع المورد.

نفقات أنا- نوع المورد للإنتاج ينوع المنتج ؛

ربح الوحدة ي- نوع المنتج.

في التدوين المضغوط ، تأخذ مشكلة البرمجة الخطية الشكل:

يوضح الترميز المضغوط أن نموذج مشكلة البرمجة الخطية العامة يتضمن خمسة عناصر رئيسية:

المتغيرات ، التي توجد قيمتها في عملية حل المشكلة ؛

المعاملات الفنية والاقتصادية للمتغيرات في القيود ؛

حجم الجانب الأيمن من المتباينات ، والتي تسمى ثوابت المشكلة ؛

معاملات المتغيرات في دالة الهدف ، والتي تسمى تقديرات متغيرة ؛

مؤشر متغير

مؤشر التقييد.

الهدف وظيفة(دالة الهدف) عبارة عن تعبير رياضي تريد العثور على أقصى قيمة له ، أي القيمة القصوى أو الدنيا.

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

يمكن تغيير المتغيرات بشكل تعسفي في ظل ظروف المشكلة قيد النظر. عامل , تسمى معاملاتها التي تشكل عمود وحدة أساسي.شكل المتغيرات الأساسية أساس الوحدةأنظمة. يتم استدعاء المتغيرات التي لم يتم تضمينها في أساس الوحدة مجانا.

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

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

تحتوي المتغيرات الإضافية والمساعدة دائمًا على معاملات وحدة (+1 أو -1).

المعاملات الفنية والاقتصادية (a ij)مع المتغيرات في نظام القيود ، يتم التعبير عن معدلات موارد الإنتاج أو معدل الإنتاج لكل وحدة قياس للمتغير.

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

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

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

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

يتم تحديد موارد الإنتاج في وحدات مختلفة: الأرض - بالهكتار ، وموارد العمالة - في أيام العمل أو في ساعات العمل ، والمعدات - في عدد نوبات الماكينة ، أو الوردية أو الإنتاج اليومي ، إلخ.

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

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

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

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

v تعكس في المهمة فقط تلك الظروف التي تحد بالفعل من إمكانيات الإنتاج ؛

v كثرة القيود تزيد من حجم المشكلة وتجعل من الصعب حلها

هناك ثلاثة أنواع من القيود: المساواة (=) ، اكتب عدم المساواة أقل من أو يساوي () ، اكتب عدم المساواة أكبر من أو يساوي (). على سبيل المثال،

أين أنا = 1, 2, … , م... يشار إلى المعاملات المتغيرة ijأين الفهرس أنا- رقم القيد ، الفهرس ي- عدد متغير ، أعضاء أحرار ( الجزء الصحيحالقيود) يشار إليها ب ط، فهرس أنا- رقم القيد.

تسمى قيود النوع الأول القيود العليا ، لأن الجانب الأيسر من المتباينة لا يمكن أن يكون أعلى من قيمة معينة (ثابت). تسمى قيود النوع الثالث قيودًا من أسفل ، حيث لا يمكن أن يكون الجانب الأيسر من المتباينة أقل من قيمة معينة (ثابت).

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

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

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

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

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

تتم كتابة شرط عدم سلبية المتغيرات في النموذج

س ي≥ 0 ، ي = 1 ، 2 ، ... ، ن.

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

ي = 1, …, ن. (1.6)

المتجه x = (x 1 , x 2 , …, xن) ، المكونات س يالتي تفي بالقيود (1.2) و (1.3) [أو (1.5) و (1.6) في المشكلة الدنيا] تسمى قرار مقبولأو خطة مقبولةمهام LP. يتم استدعاء مجموعة كافة الخطط الصالحة العديد من الخطط الصالحة.

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

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

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

1) إذا كان مطلوبًا في المشكلة الأصلية تحديد الحد الأقصى للدالة الخطية ، فيجب تغيير العلامة والبحث عن الحد الأدنى من هذه الوظيفة ؛

2) إذا كان الجانب الأيمن في القيود سالبًا ، فيجب مضاعفة هذا القيد بـ - 1 ؛

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

المتغيرات الإضافية إس جفي قيود النوع أكبر من أو يساوي () يتم إدخالها بعلامة الطرح:

للقضاء على سلبية المتغيرات الإضافية - إس جإدخال متغيرات اصطناعية بعلامة الجمع + م جبقيم كبيرة جدًا.