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

1.

2. اتجاهات الاستخدام حصيرة. نماذج في الاقتصاد.

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

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

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

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

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

تتضمن البرمجة الرياضية عددًا من الأقسام أهمها ما يلي:

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

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

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

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

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

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

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

3. مفهوم النموذج الرياضي ، أنواع الرياضيات. عارضات ازياء

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

النماذج مقسمة إلى:

1. خطي، حيث يتم وصف جميع التبعيات بواسطة العلاقات الخطية ،

2. غير خطي، حيث توجد علاقات غير خطية ؛

3. العشوائيةالتي تأخذ في الاعتبار الطبيعة العشوائية للعمليات قيد الدراسة ،

4. حتمية، والتي تأخذ في الاعتبار متوسط ​​القيم لجميع المعلمات.

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

6. ثابتة، حيث لا يؤخذ عامل الوقت بعين الاعتبار.

7. تحسينالنماذج التي يتم الاختيار بناءً عليها التطرفبعض المعايير ،

8. عدم التحسين، حيث لا يوجد معيار للأمثل.

9. النماذج الكبيرة(للأسرة بأكملها)

10. نماذج مصغرة(الروابط الفردية أو عمليات الاقتصاد).

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

4. بيان عام لمشاكل البرمجة الرياضية.

ضع في اعتبارك البيان العام لمشكلة البرمجة الرياضية.

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

Z = f (x1، x2، ...، xn)

في نطاق معين لتغيير هذه المتغيرات

gi (x1، x2، ...، xn) ريبي (أنا = 1 ، 2 ، ... ، م) ،

حيث Ri هي إحدى العلامات ≥ ، = ، ≤.

5. مشكلة تحسين خطة الإنتاج. الصياغة الاقتصادية وبناء نموذج رياضي للمشاكل.

الوضع الاقتصادي:

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

الإعداد الرياضي:

لنفترض أن j هو مؤشر نوع المنتج j = 1 ، n

ط - فهرس نوع المورد ط = 1 ، م

و ij هي تكاليف المواد الخام أنا- النوع الأول لإنتاج وحدة الإنتاج يالنوع

Аi هو حد معين لحجم الموارد المتاحة من النوع الأول ؛

Pj - الربح المحصل من بيع وحدة إنتاج من النوع j ؛

xj هو حجم إخراج النوع j.

ض \ u003d P1x 1 + P2x 2 + ... + Pnx n → الأعلى

a11x 1 + a12x 2 +… + a1nx n A1

a21x 1 + a22x 2 +… + a2nx n ≤ A2

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

a m1x1 + a m2x2 +… + a m n x n ≤ Am

س ≥ 0 ، ي = 1 ، ن

6. مهمة الرجيم. الصياغة الاقتصادية وبناء نموذج رياضي للمشكلة.

الوضع الاقتصادي

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

الإعداد الرياضي:

j هو فهرس نوع التغذية ، j = 1 ، n

أنا - مؤشر نوع المغذيات ، أنا = 1 ، م

Аi هو المدخول اليومي المطلوب من النوع الأول من المغذيات ؛

Сj هي تكلفة وحدة التغذية من النوع j.

دعنا نقدم متغيرات غير معروفة:

хj - الحجم اليومي لتغذية الحيوانات عرض ياءصارم.

من حيث التدوين المقدم مهمة معينةستكتب بعد ذلك

a11x1 + a12x2 +… + a1nxn ≥ A1

a21x1 + a22x2 +… + a2nxn ≥ A2

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

am1x1 + am2x2 +… + و mnxn ≥Am

س ≥ 0 ، ي = 1 ، ن

7. مهمة النقل . الصياغة الاقتصادية وبناء نموذج رياضي للمشكلة.

الوضع الاقتصادي :

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

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

الإعداد الرياضي :

دعنا نقدم تسميات المعلمات المعينة:

ي - مؤشر المستهلك ، ي = 1 ، ن

ط - فهرس المورد ، أنا = 1 ، م

Аi هو حجم المنتجات المتاحة من المورد الأول ؛

Bj - حجم الطلب على منتجات المستهلك من j-th ؛

Cij هي تكلفة الوحدة لنقل وحدة من المنتج من المورد الأول إلى المستهلك من الفئة j.

دعنا نقدم متغيرات غير معروفة:

хij هو حجم نقل المنتجات من المورد الأول إلى المستهلك من العاشر.

ض = С11x11 + С12x12 +… + С1nx1n + С21x21 +… + Сm (n -1) xm (n-1) + Сmnxmn → دقيقة

قيود المهام.

1. من كل مورد ، لا يمكنك سحب المنتجات أكثر من الكمية المتاحة:

x11 + x12 +… + x1n ≤ A1

x21 + x22 +… + x2n ≤ A2 (2)

…………………….

xm1 + xm2 +… + xmn ≤ صباحا

ثانيًا. يجب تلبية حاجة كل مستهلك للمنتجات

x11 + x21 +… + xm1 ≥B1

x12 + x22 +… + xm2 ≥B2

……………………. (3)

x1n + x2n +… + xmn ≥ مليار

ثالثا. حالة غير سلبية: xij ≥0، i = 1، m ؛ ي = 1 ، ن

غالبًا ما يكون من المناسب كتابة البيان الرياضي في شكل مطوي:

، أنا = 1 ، م ، ي = 1 ، ن

8. مشكلة اختيار المهام أو التخصيصات. الصياغة الاقتصادية وبناء نموذج رياضي للمشكلة.

الوضع الاقتصادي :

متاح نأنواع العمل و نفناني الأداء. يمكن لكل فنان أداء أي وظيفة ، ولكن وظيفة واحدة فقط. يتم تحديد تكلفة أداء كل عمل من قبل كل مؤدي. من الضروري تعيين فناني الأداء للعمل بطريقة تجعل التكلفة الإجمالية لإنجاز العمل ضئيلة للغاية.

الإعداد الرياضي .

دعونا نقدم تدوين المعلمات المعطاة.

ط - فهرس الأعمال ، أنا = 1 ، م

j هو مؤشر فناني الأداء ، j = 1 ، n

Cij هي تكلفة أداء الوظيفة رقم i من قبل منفذ j-th.

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

1 - إذا تم تعيين المؤدي من الفئة j للوظيفة من الدرجة الأولى ؛

0 - خلاف ذلك.

فيما يتعلق بالتدوين المقدم ، يمكن كتابة هذه المشكلة على النحو التالي:

ض = С11x11 + С12x12 +… + С1nx1n + С21x21… + С (n-1) (n-1) x (n-1) (n-1) + Сnnxnn → دقيقة

أنا مجموعة القيود.

يجب تعيين فنان واحد فقط لكل عمل:

x11 + x12 +… + x1n = 1

س 21 + س 22 + ... + س 2 ن = 1

……………………..

xn1 + xn2 +… + xnn = 1

ثانيًا. مجموعة التقييد.

يمكن لكل منفذ تنفيذ مهمة واحدة فقط:

x11 + x21 +… + xn1 = 1

x12 + x22 +… + xn2 = 1

……………………..

x1n + x2n +… + xnn = 1

س ij = (0،1) أنا = 1 ، ن ؛ ي = 1 ، ن

9. مشكلة قطع المواد. الصياغة الاقتصادية وبناء نموذج رياضي للمشكلة.

الوضع الاقتصادي .

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

الإعداد الرياضي .

دعنا نقدم الترميز:

أنا هو فهرس الفراغات ،

Аi - العدد المطلوب من الفراغات من النوع الأول ؛

ي - فهرس خيارات القطع ،

Cj هو حجم النفايات عند قطع وحدة من المواد الأولية وفقًا للخيار j ؛

و ij هو عدد الفراغات من النوع i عند قطع وحدة من مادة أولية وفقًا للخيار j.

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

xj هي كمية المواد الخام المقطوعة وفقًا للخيار j.

فيما يتعلق بالتدوين المقدم ، يمكن كتابة هذه المشكلة على النحو التالي:

ض \ u003d С1x1 + С2x2 + ... + Сnxn → دقيقة

a11x1 + a12x2 +… + a1nxn = A1

a21x1 + a22x2 +… + a2nxn = A2

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

am1x1 + am2x2 +… + amnxn = صباحا

س ≥ 0 ، ي = 1 ، ن

يتيح لك استخدام النماذج الرياضية توفير ما يصل إلى 20٪ من المواد الخام.

تم بناء النموذج الرياضي للقطع على مرحلتين.

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

يتم تنفيذ خيارات قطع وحدة من المواد المصدر في شكل الجدول التالي:

رقم الخيار

فارغ i1

i2 فارغة

الرسائل الفارغة

الفراغات مرتبة بترتيب غير متزايد لأحجامها. يتم بناء المتغيرات بطريقة التعداد الكامل.

10. الشكل العام لنموذج مشكلة LP وخصائصه

الشكل العام لـ LLP هو:

ض \ u003d С1x1 + ... + Сnxn ماكس (دقيقة)

a11 X1 + a12 X2 +… + a1n Xn R1 a1

a21 X1 + a22 X2 +… + a2n Xn R2 a2

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

am1 X1 + am2 X2 +… + amnxn جمهورية مقدونيا صباحا

س 0 ، ي = 1 ، ك ، ك ≤ ن

بشكل عام ، كل رمز R1 ، R2 ، ... ، Rm يعني إحدى العلامات: ≥ ، = أو ≤.

يحتوي الشكل العام لنموذج مشكلة LP على الميزات التالية.

1. يتم تقديم نظام القيود في شكل معادلات (شروط جامدة) وعدم مساواة (شروط غير جامدة).

2. عدم فرض الشروط غير السلبية على جميع المتغيرات

3. وظيفة الهدف تميل إما إلى الحد الأقصى أو إلى الحد الأدنى.

11. الشكل القياسي لنموذج مشكلة LP وخصائصه

النموذج القياسي على النحو التالي.

أوجد الحد الأقصى أو الأدنى للدالة الموضوعية z:

ض = С1x1 +… + Сnxn → حد أقصى (دقيقة) (1)

تخضع للقيود التالية:

a11 X1 + a12 X2 +… + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

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

am1 X1 + am2 X2 +… + amn Xn ≥ صباحا

س 0 ، ي = 1 ، ك ، ك ≤ ن

ميزات النموذج القياسي لنموذج مشكلة LP هي كما يلي:

1. يتم تقديم نظام القيود في شكل عدم المساواة (شروط غير صارمة)

2. فرض شروط غير سلبية على جميع المتغيرات

3. تميل وظيفة الهدف إما إلى الحد الأقصى أو الحد الأدنى

12. الشكل المتعارف عليه من نموذج مشكلة LP ومميزاته

الشكل المتعارف عليه هو:

أوجد الحد الأدنى للدالة الموضوعية z:

ض = С1x1 +… + Сnxn → دقيقة

تخضع للقيود التالية:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = صباحًا

Xj ≥0 ، ي = 1 ، ن

ميزات النموذج المتعارف عليه هي كما يلي:

1. نظام القيود مقدم في شكل معادلات (شروط صارمة).

2. تنطبق الشروط غير السلبية على جميع المتغيرات

3. وظيفة الهدف تميل إلى

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

13. خطة المهام الأساسية الممكنة ، المقبولة ، المثلى ، ODZ لمهمة LP

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

التعريف 2.تسمى مجموعة جميع الخطط لمشكلة البرمجة الخطية مجال القيم المقبولة للمتغيرات ( ODZ ).

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

14. أنواع سجلات مهام LP: موسعة ، مطوية ، مصفوفة ، ناقلات.

يمكن كتابة نماذج مشكلة LP في أشكال مختلفة.

1. عرض موسع لسجل النموذج

Z = c1 X1 + c2 X2 +… + cn Xn → دقيقة

a11 X1 + a12 X2 +… + a1n Xn = a1 ،

a21 X1 + a22 X2 +… + a2n Xn = a2 ،

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

a m1 X1 + am2 X2 +… + amn Xn = am ،

X 0 ، ي = 1 ، ن.

2. العرض المطوي:

,

X 0 ، ي = 1 ، ن.

3. نموذج لمشكلة LP في شكل مصفوفة:

X ≥ 0

أين

a11 a12… a1n X1 a1

A = a21 a22… a2n ، X = X2 ، A0 = a2

… … … … … …

am1 am2… amn X3 صباحًا

4. نموذج لمشكلة LP في شكل متجه:

أين

X1 a11 a12 a1n a1

X2، a21، a22، a2n، a2

… … … … …

Х في الساعة 1 صباحًا 2 صباحًا 2 صباحًا

15. الانتقال من الشكل القياسي والشكل العام لمشكلات LP إلى المتعارف عليه.نظرية الاتصال

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

1. التحويل المتغير. إذا كان بعض المتغير Xk غير موجب (Xk ≤ 0) ، فسيتم تقديم متغير جديد Xk "، بحيث يكون Xk" = –Xk. من الواضح أن Xk "≥ 0. بعد ذلك ، في كل قيد ووظيفة موضوعية ، يتم استبدال المتغير Xk بـ [ – Xk "].

إذا كان بإمكان بعض المتغيرات Xt أن تأخذ أي قيم ، فسيتم استبدالها باختلاف متغيرين غير سالبين Xt 'و Xt' '، أي من المفترض أن xt = Xt' - Xt '' ، حيث Xt '0 ≥ و Xt '' 0.

2. تحول القيد.إذا كان أي من القيود في النموذج له شكل من عدم المساواة ، فإنه يتم تحويله إلى مساواة عن طريق إضافة (إذا كانت المتباينة من النوع ≤) أو الطرح (إذا كانت المتباينة من النوع ≥) من جانبها الأيسر. تسمى هذه المتغيرات متغيرات التوازن. متغيرات التوازن متضمنة في دالة الهدف مع معاملات صفرية. يأخذ متغير التوازن قيمة المؤشر بالتتابع بعد القيم الموجودة بالفعل. على سبيل المثال ، إذا كان نظام القيود يحتوي على 5 متغيرات ، فسيكون متغير الرصيد الأول هو X6 ، والثاني - X7 ، إلخ.

16. الانتقال من الشكل الأساسي لنموذج ZLP إلى المعيار

للانتقال من الشكل المتعارف عليه إلى النموذج القياسي ، كل من

المعادلات التي سيتم استبدالها بنظام عدم المساواة:

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

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

أ) ضرب أي معادلة في ثابت غير الصفر ؛

ب) إضافة إلى أي معادلة من أي معادلة أخرى مضروبة في أي ثابت.

من الملائم كتابة النظام الأولي للمعادلات الخطية قبل التحويل في شكل مصفوفة أو جدول:

نكتب المشكلة في الشكل القياسي.

17. مفهوم المستوى الفائق لنصف المستوى ، المستوى الفائق الداعم.

18. هندسي. تفسير نظام القيود والوظيفة الموضوعية في مشاكل LP

19. مجموعة محدبة: نقاط (الزاوية) القصوى للمجموعة. متعدد السطوح محدب

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

مجموعة محدبة

تعريفتسمى النقطة x من المجموعة M بالزاوية أو النقطة القصوى إذا لم تكن داخلية لأي جزء ينتمي بالكامل إلى المجموعة المحددة.

نظرية 1. يمكن تمثيل أي نقطة في مقطع ما على أنها مجموعة محدبة من نقاط أركانها.

س \ u003d λ 1 أ + λ 2 ب

λ 1 ، λ 2 0 مزيج محدب من نقاط الزاوية A و B

λ1 + λ2 = 1

نظرية 2. يمكن تمثيل أي نقطة من مجموعة محدبة مغلقة كمجموعة محدبة من نقاط الزاوية الخاصة بها.

20. خوارزمية الطريقة الرسومية لحل مشاكل LP

1. يتم التحقق مما إذا كان LPP الأصلي في النموذج القياسي ، وإذا لم يكن كذلك ، فيجب تحويل المهمة إلى النموذج القياسي.

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

3. منطقة القيم المقبولة للمتغيرات لـ ZLP قيد الإنشاء.

4. يتم بناء ناقل توجيه ج .

5. يتم رسم isocel الأولي من خلال ODZ (عموديًا على متجه الاتجاه).

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

7. من أجل تحديد إحداثيات النقطة المثلى ، من الضروري حل نظام المعادلات الخطية المقابلة.

8. للعثور على القيمة المثلى للدالة الهدف ، من الضروري استبدال القيم المثلى للمتغيرات في دالة الهدف وحساب قيمتها.

20. خوارزمية رسومية. طريقة حل مشكلة LP

خوارزمية الطريقة الرسومية.

1. من خلال البناء المتتالي لكل شرط من شروط نظام قيود المشكلة ، يتم تنفيذ بناء ODZ.

2. يتم تكوين متجه التوجيه C بواسطة معاملات متغيرات دالة الهدف.

3. يتم رسم التساوي الأولي عموديًا على متجه الاتجاه من خلال الأصل.

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

5. لتحديد إحداثيات النقطة المثلى ، من الضروري حل نظام المعادلات الخطية المقابلة لتلك الشروط التي تقع عند تقاطعها النقطة المثلى.

6. للعثور على القيمة المثلى للدالة الهدف ، من الضروري استبدال إحداثيات النقطة المثلى في دالة الهدف وحساب قيمتها.

23. النظريات حول مجموعة القيم المقبولة لمشكلة LP والوظيفة الموضوعية

نظرية ODZ.مجال الحلول المقبولة لمشكلة LP هو مجموعة محدبة (مغلقة ومحددة في فضاء ذي أبعاد n)

النظرية 2. حول الوظيفة الموضوعية لمشكلة البرمجة الخطية.

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

24. نظرية نقطة الزاوية. كافية و شرط ضروري

25. النتائج الطبيعية من النظرية على خصائص حلول مشاكل واستنتاجات LP. مفهوم خط الأساس.

النتائج من النظريات.

تعريف. يخطط = (х1 ، х2 ، ... ، n) ، التي تتوافق إحداثياتها الإيجابية مع المتجهات المستقلة خطيًا ، تسمى الخطة الأساسية PLP .

النتيجة 1. لا تحتوي الخطة المرجعية على أكثر من م إحداثيات موجبة.

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

النتيجة 2. كل نقطة زاوية في ODZ هي خطة مرجعية.

27. خوارزمية طريقة simplex.

عند حل مشكلات LP بالطريقة البسيطة ، من الضروري تنفيذ التسلسل التالي من الإجراءات.

1. يتم التحقق مما إذا كانت مشكلة LP في شكل أساسي. إذا لم يكن الأمر كذلك ، فمن الضروري تحويل النموذج الأصلي إلى شكل أساسي.

2. يتم تحديد الخطة المرجعية الأولية وقيمة وظيفة الهدف لهذه الخطة المرجعية.

3. تم إنشاء جدول المفرد الأولي.

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

5. في الأساس ، يتم إدخال متجه ، والذي يتوافق مع أكبر تقدير إيجابي. يسمى هذا العمود عمود التمكين.

6. يُشتق المتجه من الأساس ، والذي يتوافق مع نسبة المفرد المحسوبة بالصيغة 0< Ө ≤ . Данная строка называется разрешающей строкой.

7. تم بناء جدول بسيط جديد. تم تغيير العمودين B و C B وفقًا لذلك ، ويتم ملء باقي الجدول من الجدول السابق باستخدام تحويلات Gaussian ، مع اعتبار صف الفهرس m + 1 من الصفوف وتحويله أيضًا باستخدام تحويلات Gaussian. ننتقل إلى تنفيذ الفقرة 4 من هذه الخوارزمية.

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

28. اختيار الأساس وبناء خطة مرجعية أولية لحل المشاكل بطريقة simplex.

29. الجداول البسيطة ، وملءها. صيغ لحساب معاملات صف الفهرس.

30 . نظرية المثالية لخطة مشكلة البرمجة الخطية هي نتيجة لنظرية تقدير الأمثلية لحل المشكلات بطريقة simplex.

نظرية 1: إذا كان لبعض المتجهات Ā j في النظام

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \ u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \ u003d a 2

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

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

تم استيفاء العلاقة Z j - c j> 0 ، ثم الخطة X B0 ليست مثالية ومن الممكن تمريرها إلى الخطة X B1 مثل Z (X B1) ≤ Z (X B0).

هنا Z j = (С، Ā j) هو المنتج القياسي للمتجهات.

C هو متجه يتكون من معاملات في المتغيرات الأساسية للدالة الهدف Z

Ā j هو متجه يتكون من معاملات التمدد للمتجه المقابل من حيث متجهات الأساس.

c j هو معامل دالة الهدف Z ذات المتغير Х j

عاقبة من النظريات: إذا كانت لجميع المتجهات 1 ، Ā 2 ، ... ، Ā n من بعض الخطط المرجعية Х العلاقة Z j - c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

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

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

31. اختيار ناقل يدخل الأساس ومشتق من الأساس. علاقة بسيطة.

للتبديل إلى خطة مرجعية جديدة ، هناك حاجة إلى أحد النواقل المجانية الدخول في الأساس ، وإخراج بعض نواقل الأساس. للتعريف بالأساس ، نختار متجهًا له إحداثي إيجابي واحد على الأقل. دع المتجه A m + 1 يكون مثل هذا المتجه.

تقسيم -

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

يجب أن تكون إحداثيات المتجه X1 غير سالبة ، أي .

لو ، فسيكون هذا الإحداثي غير سالب.

دع الحد الأدنى فيما يتعلق (5) يتم الحصول عليه عند i = 1 ، ثم إذا أخذنا

ثم أول إحداثي للمتجه 1 Xسيصبح صفرا.

العلاقة (6) تسمى علاقة بسيطة. وبالتالي ، فقد انتقلنا من خط الأساس الأصلي 0 X(المتجهات الأساسية A1 ، A2 ، ... Am) للخطة المرجعية 1 X(النواقل الأساسية А2 ، А3 ، ... ، Аm ، Am + 1).

32. عنصر الجواز من الجدول اختياره. قاعدة الإزالة الكاملة للأردن لإعادة حساب الجدول البسيط.

33. القاعدة الرباعية لإعادة حساب الجدول البسيط

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

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

1. التفرد . إذا كانت تقديرات جميع النواقل المجانية سلبية تمامًا ، فإن تصميم الدعم الذي تم الحصول عليه يكون مثاليًا وفريدًا. (انظر المثال في الفقرة السابقة).

2. البديل الأمثل (مجموعة الحلول المثلى).

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

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

4. ليس لدى LLP الحل الأمثل ، لأن نظام القيود غير متسق. نظرًا لأنه عند حل LLP ، يجب أن تكون طريقة simplex المعتادة هي الخطة المرجعية الأولية ، فمن المؤكد أن نظام المعادلات الخطية ليس غير متسق. لذلك ، لا يمكن أن تحدث مثل هذه الحالة عند حل الطريقة البسيطة المعتادة.

5. إذا كان ODZ يتكون من نقطة واحدة ، فإن حل هذه المشكلة يكون بسيطًا ويمكن الحصول عليه بدون استخدام طريقة simplex.

35. متى يتم استخدام طريقة الأساس الاصطناعي؟

صناعي.

36. بناء مشكلة M بطريقة الأساس الاصطناعي

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

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

وبالتالي ، في المشكلة الممتدة ، لدينا خط أساس (على الرغم من أن بعض المتغيرات الأساسية مصطنعة).

تم إنشاء الجدول البسيط الأولي.

37. بناء خط مؤشر بطريقة الأساس الاصطناعي

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

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

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

38. معيار الأمثلية في طريقة الأساس الاصطناعي. العلامة هي بناء الخطة الأساسية الأولية للمهمة الأصلية.

39. خوارزمية طريقة الإرسال المزدوج البسيط

خوارزمية طريقة الإرسال المزدوج البسيط:

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

2. حدد خط الدليل بأكبر عنصر سلبي مطلق في عمود الأعضاء الأحرار A0

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

4. أعد حساب الجدول البسيط وفقًا لقاعدة عمليات حذف الأردن الكاملة

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

6. علامة الحصول على الحل الأمثل بطريقة الإرسال البسيط المزدوج هي معيار الأمثل لطريقة الإرسال البسيط العادية.

41- نماذج النقل المفتوحة والمغلقة. الانتقال من نموذج النقل المفتوح إلى نموذج مغلق.

أنواع مهام النقل.

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

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

(على سبيل المثال ، إذا كانت ∑ Ai = ∑ Bj) ، وإلا فإن مشكلة النقل تسمى يفتح. لحل مشكلة النقل ، من الضروري إغلاقه.

يمكن تحويل مهمة النقل المفتوح إلى مهمة مغلقة بالطريقة التالية.

دع Ai> ∑Bj. في هذه الحالة ، من الضروري تقديم مستهلك وهمي n + 1 مع حجم احتياجات Ai - ∑Bj. يُفترض أن تكون تكاليف الوحدة للنقل من الموردين إلى المستهلك الوهمي 0 ، لأنه في الواقع لن يكون هذا النقل نفذت وسيبقى جزء من المنتجات مع الموردين.

إذا Bj> ∑Ai. في هذه الحالة ، من الضروري تقديم مورد وهمي m + 1 بحجم مخزون ∑Bj - Ai. يُفترض أن تكون تكاليف الوحدة للنقل من مورد وهمي إلى المستهلكين مساوية لـ 0 ، لأنه في الواقع لن يتم تنفيذ هذا النقل ولن يحصل المستهلكون على بعض المنتجات.

42. طرق تكوين التوزيع الأولي في مشكلة النقل: طريقة الركن الشمالي الغربي وطريقة أقل عنصر في المصفوفة.

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

طريقة أصغر عنصر في المصفوفة.

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

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

يتم إجراء المزيد من التوزيع أولاً قدر الإمكان على الخلايا التي تحتوي على علامتين ، ثم - بعلامة واحدة ، ثم تتم إعادة توازن المشكلة إلى الحشوات (m + n - 1). ننظم الحشوات عند تمرير الطاولة من اليسار إلى اليمين ومن أعلى إلى أسفل.

43. خصائص مهام النقل

مشكلة النقل لها بعض الخصائص التي يمكن أن تنعكس في النظريات التالية.

نظرية 1. دائمًا ما يكون هناك حل لمشكلة النقل المغلق.

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

نظرية 3. دائمًا ما يعتمد نظام قيود مشكلة النقل المغلق خطيًا.

ويترتب على هذه النظرية أن توزيع مشكلة النقل المغلق له دائمًا متغيرات أساسية m + n - 1 ومتغيرات وقت الفراغ (m - 1) (n - 1).

44. تدهور التوزيع في مشاكل النقل والقضاء على الانحطاط. تركيبة شطب.

يسمى التوزيع بالتدهور إذا كان عدد الخلايا أقل من m + n - 1.

45. النظريات المثلى لمشكلة النقل.

نظرية.إذا كان لبعض توزيع مهمة النقل لك

تم استيفاء الشروط:

أ). ui + vj = cij للخلايا المشغولة

ب) ui + vj ≤ сij ، للخلايا المجانية ،

ثم هذا التوزيع هو الأمثل.

تسمى قيم واجهة المستخدم إمكانات الصف ، وتسمى القيم vj إمكانات العمود.

46. ​​إمكانيات وطرق حسابها.

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

عدد المعادلات المبنية على هذا الشرط هو m + n - 1 ، وعدد المجهولين ui و vj هو m + n. الذي - التي. عدد المتغيرات أكبر من عدد المعادلات ، وجميع المعادلات مستقلة خطيًا. حل مثل هذا النظام من المعادلات الخطية غير محدد ، لذلك يجب تخصيص أي قيمة لأحد الإمكانات. عمليًا ، ui = 0. نظام معادلات m + n - 1 مع m + n - 1 متغيرات غير معروفة يتم الحصول عليها. يمكن حل هذا النظام بأي طريقة. في الممارسة العملية ، لحساب الإمكانات ، يتم أخذ الخلايا المشغولة في الاعتبار ، والتي يُعرف بها أحد إمكاناتها ، وبناءً على الشرط أ) من النظرية ، يتم حساب قيم الإمكانات غير المعروفة المتبقية.

47. حساب تقديرات أمثلية لتوزيع مهام النقل ومعيار الأمثل.

بناءً على العلاقة ب) من النظرية ، يمكننا كتابة الصيغة التالية لحساب التقديرات: δ اي جاي= ui + vj - сij. من أجل عدم الخلط بين التقديرات وحجم حركة المرور ، يتم وضع (التقديرات) في دوائر.

تقديرات الأمثل في خلايا TK المجانية هي معيار أمثل يتحقق من التوزيع للأمثل. إذا كانت تقديرات جميع الخلايا الحرة أقل من أو تساوي الصفر ، فإن هذا التوزيع هو الأمثل.

48. إعادة توزيع الإمدادات في مشكلة النقل

إذا لم يكن التوزيع هو الأمثل ، فمن الضروري إعادة توزيع الإمدادات.

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

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

49. سلاسل إعادة التوزيع وأنواعها.

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

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

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

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

50. اختيار حجم إعادة التوزيع.

تحديد حجم المنتجات المنقولة. عند تحديد حجم المنتجات التي تم نقلها خلال دورة العد ، يجب أن ننطلق من الاعتبارات التالية:

أ) بعد التحول في خلايا الجدول ، لا ينبغي الحصول على الأرقام السالبة ؛

ب) يجب أن تصبح إحدى الخلايا المشغولة حرة.

من أجل تلبية هذه الشروط ، من الضروري تحديد حجم المنتجات المنقولة على النحو التالي: θ = min (ij) - ، حيث (ij) هو حجم النقل من خلايا دورة إعادة الحساب المميزة بعلامة " -" لافتة.

θ = دقيقة (20 ؛ 30) = 20

تتم إضافة θ إلى قيم الخلايا المميزة بعلامة "+". يتم طرح θ من قيم الخلايا المميزة بعلامة "-". يتم الكتابة فوق قيمة العرض للخلايا المتبقية بدون تغييرات. نتيجة لذلك ، حصلنا على الجدول التالي.

53. خوارزمية طريقة الإمكانات.

الخوارزمية:

1. تحقق من استيفاء المعادلة للمهمة إذا لم يكن الأمر كذلك ، يتم إدخال مورد أو مستهلك وهمي في المهمة

2. تتم كتابة شرط المهمة في شكل جدول نقل

3. يجري بناء خط أساس أولي

4. يتم تحديد إمكانات الإمدادات والمستهلكين

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

6. قم بتحميل خلية منظور. قم بإعداد خطة أساسية جديدة على شكل جدول نقل. انتقل إلى النقطة 4.

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

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

حيث Cij 'هي التكلفة المخفضة لإنتاج وحدة إنتاج واحدة.

Cij "- تكلفة نقل وحدة إنتاج واحدة.

المهام مع حظر التوريد.

في بعض الحالات ، لا يمكن نقل المنتجات على أي طريق.

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

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

المحاسبة عن القيود المفروضة على صبيب الطرق.

في بعض مهام النقل ، في بعض الطرق ، يكون ملف الإنتاجيةمما هو ضروري لتلبية طلب نقطة الاستهلاك.

مع مراعاة الطبيعة الإلزامية لبعض عمليات التسليم في مشكلة النقل.

في بعض الحالات ، تتطلب المهمة ، على سبيل المثال ، على طول طريق Ak Bs ، أن يتم التسليم في وحدات المجلد A. في هذه الحالة ، يتم خصم العرض الإلزامي من حجم إنتاج النقطة A والحجم S Bs ويتم حل المشكلة فيما يتعلق بالتوريد الاختياري. بعد الحصول على الحل الأمثل ، يُضاف العرض بالضرورة إلى الحجم الموجود في خلية Ak Bs.

56. الاستنتاجات الممكنة مع الاقتصادية. تفسير التوزيع الأمثل لمشاكل النقل المفتوح.

عند استلام التوزيع الأمثل ، من الضروري العودة إلى المشكلة الأصلية وجعل الوضع الاقتصادي المناسب. الاستنتاجات. هم كالتالي:

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

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

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

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

يجب ألا تكون هناك مهمة لتحسين خطة الإنتاج. تبدو هكذا:

المهمة الأولية:

أ 11 × 1 + أ 12 × 2 + ... + أ 1 بكسل × ص ≤v 1 | 1

أ 21 × 1 + أ 22 × 2 + ... + أ 2 بكسل × ص ≤v 2 | في 2

……………….. |.. (1)

أ تي 1 × 1 + أ تي 2 × 2 + ... + أ تين س ن ≤v 1 | في تي

س ي ≥0 ، ي = 1 ، ن (2)

ض = ج 1 × 1 + ص 2 × 2 + ... + ج ن × ن -> حد أقصى (3)

س \ u003d (× 1 ، × 2 ، ... ، × ن)

a ij - عدد المواد الخام من النوع i ، المصروفة لإنتاج النوع j من المنتج

مشكلة مزدوجة

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

ط - سعر النوع الأول من المواد الخام المتاحة في المؤسسة.

أ 11 ص 1 + أ 21 ص 2 + ... + أ تي 1 ص تي≥s 1

أ 12 × 1 + أ 22 ص 2 + ... + أ تي 2 × ن ≥s 2

……………….. (1’)

أ 1 صص 1 + أ 2 صص 2 +… + أ tpفي تي≥s ص

أنا ≥0 ، ي = 1 ، م (2 بوصة)

F = b 1 y 1 + b 2 y 2 +… + b m y m -> min (3 ')

58. التطابق بين العناصر الهيكلية للمشكلات المباشرة والمزدوجة

يمكن ربط كل مشكلة برمجة خطية

مهمة مزدوجة وفقًا للقواعد التالية:

1. في جميع قيود المشكلة الأصلية ، يجب أن تكون المصطلحات المجانية

تكون على اليمين ، وتتصالح مع المجهول على اليسار.

2. يجب أن يكون للقيود - عدم المساواة في المشكلة الأصلية علامات ،

موجهة في اتجاه واحد.

3. إذا تم تصغير دالة الهدف في المسألة الأصلية ، يجب كتابة قيود عدم المساواة بعلامة "" ، ثم في المسألة المزدوجة سيتم تصغير الوظيفة الهدف وستكون علامات قيود عدم المساواة "".

4. كل قيد من المشكلة الأصلية يتوافق مع متغير في

مهمة مزدوجة. إذا كان المتغير يتوافق مع متباينة ، فهو غير سالب ، وإذا كان يتوافق مع المساواة ، يكون المتغير بدون قيود على الإشارة ("تعسفي").

5. يتم الحصول على معاملات المتغيرات في قيود المشكلة المزدوجة عن طريق تبديل المصفوفة المكونة من

معاملات متغيرات المشكلة الأصلية.

6. الشروط الحرة للمشكلة الأصلية هي المعاملات في

المتغيرات في الهدف وظيفة المشكلة المزدوجة ، ومجانية

المصطلحات في المشكلة المزدوجة هي معاملات المتغيرات في

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

59- بناء المشاكل المزدوجة للمسائل الأصلية المكتوبة بالشكل القياسي والقانوني والعامة للنموذج (بناء المشاكل المزدوجة المتماثلة وغير المتماثلة)

النموذج القياسي (الأصلي)

Σ أ ij س j ≤ ب أنا ، أنا = 1 ، ن (1)

س ي ≥0 ، ي = 1 ، ن (2)

z = Σ c j x j -> حد أقصى (3)

معيار مزدوج

Σ أ ij y i ≤ c j ، j = 1 ، n (1)

يي ≥0 ، ي = 1 ، م (2)

F = Σ b i y i -> min (3)

المشكلة الأصلية في الشكل الأساسي:

Σ أ ij س ج = ب أنا ، أنا = 1 ، م (1)

س ي ≥0 ، ي = 1 ، ن (2)

ض = Σ ج ي س ج -> دقيقة (3)

مزدوج الكنسي

Σ أ ij y i ≤ c j ، j = 1 ، n (1)

y i - أي (2)

F = Σ b i y i -> حد أقصى (3)

دعونا نعطي تفسيراً اقتصادياً لزوج من المشاكل المزدوجة. ضع في اعتبارك مشكلة الاستخدام الرشيد للموارد. دع المؤسسة لديها موارد b1 ، b2 ، ... bm التي يمكن استخدامها لإنتاج أنواع n من المنتجات. دعنا نعرف أيضًا تكلفة وحدة من النوع j من المنتج cj (j = 1 ، n) ومعدل استهلاك المورد i (i = 1 ، m) لإنتاج وحدة ياء الإنتاج- aij. مطلوب تحديد حجم الإنتاج لكل نوع xj (j = 1، n) ، مع زيادة التكلفة الإجمالية

و = c1x1 + ... + cnxn (1)

في الوقت نفسه ، يجب ألا يتجاوز استهلاك الموارد مدى توفرها:

a11x1 +… + a1nxn<=b1 }

…………………….. } (2)

am1x1 +… + amnxn<=bm }

كل ما هو معروف بمعناه الاقتصادي غير سلبي:

Xj> = 0 (j = 1، n). (3)

لاحظ أن هذه المشكلة تشكل مشكلة مزدوجة متماثلة.

مشاكل مزدوجة غير متماثلة.

لنأخذ ZLP إلى الحد الأقصى في الشكل المتعارف عليه:

ماكس Z = (ن ؛ ي = 1) Σcj * xj

(ن ؛ ي = 1) Σaij * xj = bi (i = 1، m)

Xj> = 0 (j = 1، n).

60- نظرية الازدواجية الرئيسية والثانية (اذكر النظريات واشرحها)

نظرية الازدواجية الأولى.

النظرية: إذا كانت إحدى المشاكل المزدوجة لها خطة مثالية ، فإن الأخرى قابلة للحل ، أي لديه خطة اختيار. في هذه الحالة ، تتطابق القيم القصوى للوظائف الموضوعية (j = من 1 إلى n) Σcjxj * = (i = من 1 إلى m) Σbiyi * إذا كان في الأصل. المشكلة ، الوظيفة الموضوعية غير محدودة في مجموعة الخطط ، ثم في المشكلة المزدوجة يكون نظام القيود غير متسق.

نظرية الازدواجية الثانية وتفسيرها الاقتصادي.

بغرض حلول صالحةكانت أزواج المشاكل المزدوجة هي الأمثل ، فهي ضرورية وكافية لتحقيق الشرط: xj * (∑aij yi * -cj) = 0 ، j من 1 إلى n ، yi * (∑aij xj * -bi) = 0 ، I من 1 إلى م. هذه هي شروط التراخي التكميلي. ويترتب على ذلك: إذا تم تحويل أي قيود على المشكلة المزدوجة من خلال الخطة المثلى إلى مساواة صارمة ، فعندئذٍ المكون المقابل في opt. يجب أن تكون خطة المشكلة المزدوجة مساوية للصفر.إذا اختار بعض المكونات. الخطة تساوي صفرًا ، ثم يتم تحويل القيد المقابل للمشكلة المزدوجة بواسطة خطة opt. إلى مساواة صارمة xj *> 0 ، لذلك (i = من 1 إلى m) Σaij yi * = cj opt.plan ، ثم إذا التكاليف> الأسعار ، حجم الإنتاج = 0 Σaij yi *> cj وبالتالي xj * = 0

yi *> 0 لذلك (j = من 1 إلى n) Σaij xj * = bi (أجناس الموارد = مخزون الموارد).

(ي = 1 إلى ن) Σaij xj *

معنى النظرية كما يلي:

إذا كان تقدير التكلفة لاستهلاك الموارد لإنتاج وحدة من سعر المنتج الثاني \ u003d ، فسيتم تضمين هذا النوع من المنتج الثاني في الخطة المثلى ؛

إذا تجاوزت التكاليف السعر ، فلا ينبغي إنتاج المنتج ؛

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

إذا لم يتم إنفاق المورد بالكامل ، فإن تقدير التكلفة = 0.

61. بناء خطة الدعم الأمثل للمشكلة المزدوجة من الجدول البسيط للمشكلة الأصلية

معلومات من أعمدة المصفوفة العكسية للتحولات الخطية التي أدت إلى النتيجة المثلى. توفر أعمدة المصفوفة D-1 معلومات مفيدة للغاية.

العمود A3: سعر "الظل" للمورد S2 هو y01 = 0 ، ويبقى العمود

مفرد ومن السطر الأول يمكن قراءة أن x3 = 9 ، أي عند تنفيذ الخطة المثلى التي تم العثور عليها ، سيكون المورد الأول زائدًا ، وسيصل هذا الفائض (نقص الاستخدام) إلى 9 وحدات تقليدية فقط.

العمود A4: سعر "الظل" للمورد S2 يساوي y02 = 1 ، وسيتم استخدام المورد بالكامل وستؤدي زيادته المحتملة إلى زيادة في دالة الهدف (أي الدخل). ولأن y02 = 1 ، ثم الزيادة في المورد S2 بمقدار 1 c.u. سيعطي إضافة من حيث الدخل بواسطة. مع هذه الزيادة في المورد S2 ، سيكون الحد الأقصى للدخل بالفعل Zmax = 58 ألف غريفنا. + 1000 غريفنا = 59 ألف غريفنا. على التين. يوضح الشكل 6.2 هذا الوضع ، وسيتم تقديم التعليق أدناه. ويتبع أيضًا من العمود A4 أنه مع زيادة في المورد S2 بمقدار 1 c.u. بالنسبة للنقطة المثلى الجديدة ، سينخفض ​​إنتاج البضائع T1 بمقدار طن (عند تقاطع صف المتغير الأساسي x1 والعمود A4 هو "-1/2") ، وسيزداد ناتج البضائع T2 بمقدار 3 / 2 طن (لأنه في الصف الذي يحتوي على المتغير الأساسي x2 في العمود A4 لدينا "3/2". ما قيل عن العمود A4 سيتم التعليق عليه أدناه باستخدام الإنشاءات الرسومية (الشكل 6.2). العمود A5: "الظل "سعر المورد S3 يساوي y03 = 2. هذا يعني أن زيادة المورد S3 بمقدار 1 c.u. سيجلب إضافة في Z إلى.Z = y03 · .v3 = 2.1 = 2 (ألف هريفنيا) وسيكون Zmax = 58 ألف هريفنيا. + 2 ألف غريفنا = 60 ألف غريفنا. في نفس الوقت ، على النحو التالي من العمود A5 من الجدول. في الشكل 3 ، سيزداد إنتاج T1 بمقدار ½ طن وسينخفض ​​T2 بمقدار طن. سيزداد مخزون المواد الخام S1 (انظر السطر 1) بمقدار 3/2 cu.

62. فكرة طريقة البرمجة الديناميكية وتفسيرها الهندسي. مبدأ بيلمان للأمثل.

تم العثور على الحل الأمثل للمشكلة بطريقة البرمجة الديناميكية على أساس المعادلة الوظيفية

لتعريفه ، تحتاج إلى:

1. اكتب المعادلة الوظيفية لآخر حالة من العملية (تتوافق مع l \ u003d n-1)

fn-1 (Sl-1) = الأمثل (Rn (Sn-1 ، Un) + f0 (Sn))

2. ابحث عن Rn (Sn-1، Un) من مجموعة منفصلة من قيمها لبعض Sn-1 الثابتة و Un من المناطق المسموح بها المقابلة (منذ f0 (Sn) = 0 ، ثم f1 (Sn-1) = الأمثل (Rn (Sn-1 ، Un)

نتيجة لذلك ، بعد الخطوة الأولى ، يُعرف الحل Un والقيمة المقابلة للوظيفة f1 (Sn-1)

3. قلل قيمة l بواحد واكتب المعادلة الوظيفية المقابلة. بالنسبة إلى l = n-k (k = 2، n) يبدو

fk (Sn-k) = الأمثل (Rn-k + 1 (Sn-k، Un-k + 1) + fk-1 (Sn-k + 1)) (2)

4. ابحث عن الحل الأمثل المشروط بناءً على التعبير (2)

5. تحقق مما تساوي قيمة l. إذا كان l = 0 ، يتم إكمال حساب الحلول المثلى الشرطي ، ويتم العثور على الحل الأمثل للمشكلة للحالة الأولى من العملية. إذا كانت l لا تساوي 0 ، فانتقل إلى الخطوة 3.

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

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

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

رياضيا ، هو مكتوب كتعبير عن النموذج:

fn-1 (Sl) = الأمثل (Rl + 1 (Sl ، Ul + 1) + fn- (l + 1) (Sl + 1)) (1)

(l = 0، n-1) يعني الأمثل في التعبير الحد الأقصى أو الحد الأدنى اعتمادًا على حالة المشكلة.

63- متطلبات المشكلات التي يتم حلها بواسطة طريقة DP

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

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

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

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

64- الصياغة الاقتصادية وبناء نموذج رياضي للمشكلة التي تم حلها بطريقة DP (على سبيل المثال مشكلة توزيع الاستثمارات الرأسمالية). علاقة تكرار بيلمان.

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

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

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

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

يتم إجراء جميع الحسابات التي تجعل من الممكن العثور على القيمة المثلى للتأثير الذي تم تحقيقه في خطوات n ، fn (S0) ، وفقًا للصيغة (1) ، والتي تسمى معادلة Bellman الوظيفية الأساسية أو علاقة التكرار. عند حساب القيمة التالية للدالة fn-1 ، يتم استخدام قيمة الوظيفة fn- (l + 1) التي تم الحصول عليها في الخطوة السابقة ، والقيمة المباشرة للتأثير Rl + 1 (Sl ، Ul + 1) ، تم تحقيقه نتيجة اختيار الحل Ul + 1 لأنظمة Sl حالة معينة. عملية حساب قيمة الدالة fn-1 (l = 0 ، n-1)

يتم تنفيذه في ظل الحالة الأولية الطبيعية f0 (Sn) = 0 ، مما يعني أنه خارج الحالة النهائية للنظام ، يكون التأثير صفرًا.

65. مشكلة توزيع الاستثمارات الرأسمالية (مثال).

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

لنبدأ بالتوزيع الأمثل لاستثمارات رأس المال المخصصة بمقدار K بين مؤسستين. شكلت إدارات التخطيط في المؤسسات ، على أساس حساباتها ، وظائف الدخل q (x) للمؤسسة P1 و h (x) للمؤسسة P2. تعني هذه الوظائف أنه إذا تلقت المؤسسة الأولى أو الثانية استثمارًا بمبلغ x ، فإن المشروع الأول

سيتم استلام الدخل q (x) ، ويمكن أن تأخذ القيمة الثانية h (x) وقيمة x قيمًا منفصلة مستمرة أو معروفة من 0 إلى K.

لذلك ، دع الشركة P1 تخصص استثمارات رأسمالية بالمبلغ x ، ثم يتم تخصيص مبلغ K - x للشركة P2. في هذه الحالة ، سيتم استلام الدخل q (x) من المؤسسة الأولى ، و h (K - x) من الثانية. إذا تم تخصيص الاستثمارات K لفترة تخطيط واحدة ، فسيكون إجمالي الدخل من المؤسستين R (K ، x) = q (x) + h (K - x). من الواضح أن x ، وبالتالي ، يجب اختيار K - x بحيث تأخذ R (K ، x) قيمتها القصوى ، والتي نشير إليها بواسطة F (K):

هذا الإدخال يشبه الهيكل العظمي لإدخالات أكثر اكتمالاً.

معادلة بيلمان الوظيفية. تكمل مهمتنا من خلال توزيع الاستثمارات الرأسمالية على فترتين تخطيط (مرحلتين) . دعنا نقرر في البداية تخصيص المبلغ x للمشروع الأول P1 ، و x للمؤسسة الثانية P1. بشكل عام ، سيكون الدخل مساويًا لـ R (K ، x) = q (x) +

ح (ك - س). إذا أخذنا في الاعتبار أن الاستثمارات يتم توزيعها على فترتين (مرحلتين) ، فسيكون رصيد الاستثمارات في المشروع الأول x ، حيث ، وفي الثانية -. (K - x) ، حيث وفقًا لذلك ، الدخل لـ ستكون الفترة الثانية q (.x) - وفقًا للمرفق الأول و h [. (K - x)] - وفقًا للمرفق الثاني. يبدأ تحسين البرمجة الديناميكية ، كقاعدة عامة ، من المرحلة النهائية. لذلك ، نبدأ من المرحلة الثانية ، مع الإشارة إلى F1 أقصى دخل ممكن من مؤسستين في الثانية

منصة. يحصل

ثم ، إلى المرحلة الأخيرة المدروسة (في حالتنا ، المرحلة الثانية) ، نضيف نوعًا ما المرحلة السابقة (في حالتنا ، المرحلة الأولى) ونجد الحد الأقصى للدخل من المرحلتين معًا:

وبالمثل ، بالنسبة لمراحل n ، نحصل عليها

حيث Fn-1 هي الوظيفة الموضوعية التي تعطي أفضل نتيجة للمراحل (n - 1) الأخيرة. معادلة بيلمان الوظيفية الناتجة متكررة ، أي يربط قيمة Fn بقيمة Fn-1.

بشكل عام ، فإن معادلة بيلمان لها الشكل

حيث ، Fn-1 - أقصى دخل لـ (n - 1) المراحل الأخيرة ، Fn -

الحد الأقصى للدخل لجميع المراحل n.

66. مفهوم حل مشاكل البرمجة غير الخطية

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

وإحضار الحد الأقصى المطلوب (الحد الأقصى أو الأدنى) للوظيفة الموضوعية

f = f (x1، x2، ...، xn)، (13.2)

حيث f (х1، ...، хn) و qi (1، ...، хn) (m، 1 i =) غير خطية حقيقية ،

التوابع العادية لعدد n المتغيرات الحقيقية.

وفقًا لخصائصها العامة ، يمكن لمشكلات البرمجة غير الخطية

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

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

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

تعتبر مشكلة ، والعملية التكرارية للحسابات تبدأ من النقطة

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

67. مفهوم البرمجة البارامترية والصحيحة .

البيان والنموذج الرياضي لـ ZCLP.

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

و = (ن ، ي = 1) ∑CjXi كحد أقصى

(ن ، ي = 1) ∑AijXj = ثنائي ، أنا = 1 ، م

عدد صحيح xi ، j = 1 ، n

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

1. طرق القطع

2. التوحيدية

3- الطرق التقريبية ..

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

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

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

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

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

مع قيود:

أين س ي- مجهول؛ aij, ب ط, سي جيهتعطى ثوابت.

يمكن كتابة كل أو بعض معادلات نظام القيد على هيئة متباينات.

النموذج الرياضي في تدوين أقصر له الشكل

مع قيود:

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

تشكل مجموعة الحلول المقبولة منطقة الحلول المقبولة (ODD).

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

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

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

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

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

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

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

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

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

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

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

2. بناء ناقل .

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

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

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

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

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

يمكن أن تكون مشكلة 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. الانتقال من حل أساسي إلى آخر.

T10. بيان مشكلة البرمجة الخطية

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

لتجميع نموذج رياضي ، من الضروري:

1. حدد متغيرات المهمة ؛

2. وضع نظام القيود.

3. تعيين وظيفة الهدف.

متغيرات المهمةالكميات × 1 ، × 2 ، ... ، × ن تسمى ، والتي تميز العملية الاقتصادية بالكامل. عادة ما يتم كتابتها على أنها متجه X \ u003d (x 1 ، x 2 ، ... ، x n).

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

تسمى الوظيفة الموضوعيةالوظيفة F (X) = f (x 1، x 2، ...، x n) لمتغيرات المهمة ، والتي تميز جودة المهمة المطلوب إيجاد الحد الأقصى لها.

مشكلة عامة في البرمجة الرياضيةتمت صياغتها على النحو التالي: أوجد متغيرات المهمة x 1، x 2، ...، x n التي توفر الحد الأقصى للدالة الهدف

F (X) \ u003d f (x 1 ، x 2 ، ... ، x n) ® max (min) (2)

واستيفاء نظام القيود (1).

إذا كانت الوظيفة الهدف (2) ونظام القيد (1) خطية ، فإن مشكلة البرمجة الرياضية تسمى مشكلة البرمجة الخطية (LPP).

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

2. أمثلة على تجميع النماذج الرياضية للمشاكل الاقتصادية

تؤدي دراسة حالات الإنتاج المحددة إلى ZLP ، والتي يتم تفسيرها على أنها مشاكل الاستخدام الأمثل للموارد المحدودة.

1.مشكلة خطة الإنتاج المثلى

لإنتاج نوعين من المنتجات T 1 و T 2 ، يتم استخدام ثلاثة أنواع من الموارد S 1 و S 2 و S 3. يظهر في الجدول مخزون الموارد ، وعدد وحدات الموارد التي يتم إنفاقها على تصنيع وحدة الإنتاج ، وكذلك الربح من بيع وحدة الإنتاج:

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

حل.

دعنا نشير إلى x 1 ، x 2 - عدد وحدات الإنتاج ، على التوالي ، T 1 و T 2 ، المخطط لها للإنتاج. لتصنيعها ، (x 1 + x 2) وحدات من المورد S 1 ، (x 1 + 4x 2) وحدات من المورد S 2 ، (x 1) وحدات من المورد S 3 ستكون مطلوبة. يجب ألا يتجاوز استهلاك الموارد S 1 و S 2 و S 3 احتياطياتها ، على التوالي 8 و 20 و 5 وحدات.

ثم يمكن صياغة النموذج الاقتصادي الرياضي للمشكلة على النحو التالي:

ابحث عن خطة الإنتاج X \ u003d (x 1، x 2) التي تفي بنظام القيود:

والحالة

تحتها الوظيفة يأخذ على القيمة القصوى.

يمكن تعميم المشكلة بسهولة في حالة إنتاج أنواع n من المنتجات باستخدام أنواع m من الموارد.

2.مشكلة النظام الغذائي الأمثل

هناك نوعان من الأطعمة K 1 و K 2 تحتوي على العناصر الغذائية S 1 و S 2 و S 3. يوضح الجدول محتوى عدد وحدات المغذيات في 1 كجم لكل نوع من أنواع العلف ، والحد الأدنى المطلوب من العناصر الغذائية ، وكذلك تكلفة 1 كجم من العلف:

من الضروري وضع حصص يومية ذات تكلفة دنيا ، بحيث لا يقل محتوى كل نوع من المغذيات عن الحد المقرر.

حل.

دعنا نشير إلى x 1 ، x 2 - كمية العلف K 1 و K 2 المدرجة في النظام الغذائي اليومي. ثم سيتضمن هذا النظام الغذائي (3 × 1 + × 2) وحدات من المغذيات S 1 ، (× 1 + 2 × 2) وحدات من المادة S 2 ، (× 1 + 6 × 2) وحدات من المغذيات S 3. نظرًا لأن محتوى العناصر الغذائية S 1 و S 2 و S 3 في النظام الغذائي يجب أن يكون 9 و 8 و 12 وحدة ، على التوالي ، يمكن صياغة النموذج الاقتصادي الرياضي للمشكلة على النحو التالي:

قم بتكوين نظام غذائي يومي X \ u003d (x 1 ، x 2) ، تلبية لنظام القيود:

والحالة

تحتها الوظيفة يأخذ الحد الأدنى من القيمة.

نماذج تسجيل PLP

في LLP ، مطلوب إيجاد الحد الأقصى لوظيفة الهدف الخطية:

مع قيود:

وحالة عدم السلبية

حيث يُعطى a ij و b i و c j (،) ثوابت.

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

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

من أجل الانتقال من أحد أشكال تدوين LLP إلى آخر ، يجب أن يكون المرء قادرًا على الانتقال من قيود عدم المساواة إلى قيود المساواة والعكس صحيح.

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

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

مثال 1. اكتب بالصيغة المتعارف عليها ZLP:

مع قيود:

حل.

تظل الوظيفة الموضوعية دون تغيير:

يتحول نظام عدم المساواة إلى نظام للمساواة:

عند حل LLP بطريقة رسومية ، يلزم الانتقال من النموذج الأساسي إلى النموذج القياسي.

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

لتحويل LLP الأساسي الأصلي إلى LLP القياسي المكافئ:

أ) يتم اختيار عنصر غير صفري a qp في المصفوفة الممتدة لنظام القيد. هذا العنصر يسمى متساهل، و q - الصف الأول والعمود p يسمى تمكين الصف وتمكين العمود.

ب) تتم إعادة كتابة سلسلة الحل دون تغيير ، ويتم استبدال جميع عناصر عمود الحل ، باستثناء عمود الحل ، بأصفار. يتم تحديد العناصر المتبقية من المصفوفة المعززة باستخدام "قاعدة المستطيل":

ضع في اعتبارك أربعة عناصر للمصفوفة الموسعة: العنصر a ij المراد تحويله ، والعنصر الحل a qp والعناصر a i p و a qj. لإيجاد العنصر a ij ، يتبع العنصر a ij طرح حاصل ضرب العنصرين a i p و a qj الواقعين عند الرؤوس المقابلة للمستطيل ، مقسومًا على عنصر الحل a qp:

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

مثال 2. التغيير إلى النموذج القياسي:

حل.

باستخدام طريقة Jordan-Gauss ، نأتي بنظام معادلات قيود LLP إلى نظام مكافئ من عدم المساواة. دعنا نختار العنصر الثالث من الصف الأول كعنصر حل:

الرقم -9 الذي تم الحصول عليه في العمود الأخير من الصف الأخير يجب كتابته إلى دالة الهدف مع الإشارة المعاكسة. نتيجة للتحولات ، يأخذ LLP الشكل:

لأن المتغيرين x 2 و x 3 غير سالبين ، ثم بعد استبعادهما ، يمكننا كتابة ZLP في شكل متماثل:

في الشكل الأساسي لـ LLP ، يمكن تصغير الوظيفة الموضوعية وتعظيمها. للانتقال من إيجاد الحد الأقصى لإيجاد الحد الأدنى أو العكس، يكفي تغيير علامات معاملات الوظيفة الهدف: F 1 = - F. المشكلة الناتجة و LLP الأصلي لهما نفس الحل الأمثل ، وتختلف قيم الوظائف الموضوعية في هذا الحل فقط في لافتة.

خصائص ZLP

1. مجموعة الحلول المقبولة لنظام قيود مشكلة البرمجة الخطية هي محدبة.

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

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

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

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

النقطة X تسمى تركيبة خطية محدبةالنقاط X 1 ، X 2 ، ... ، X n إذا تم استيفاء الشروط التالية:

X \ u003d α 1 X 1 + α 2 X 2 + ... + α n X n ،

αj ≥ 0 ، Σαj = 1.

من الواضح أنه في الحالة الخاصة لـ n = 2 ، تكون المجموعة الخطية المحدبة من نقطتين عبارة عن جزء يربط بينهما.

3. كل حل أساسي مقبول من نظام القيد LLP المتعارف عليه يتوافق مع نقطة زاوية لمحلول متعدد السطوح ، والعكس بالعكس ، لكل نقطة زاوية في متعدد السطوح الحل هناك يتوافق مع حل أساسي مقبول.

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

وبالتالي ، يجب البحث عن الحد الأقصى للدالة الخطية LLP بين عدد محدود من الحلول الأساسية المقبولة.

محاضرة 2

في شكل قانوني

الحل المقبول لـ PLP(خطة مقبولة).

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

ضروري

مثال.

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

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

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

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

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

3. ODR - نقطة واحدة آه ، إذن ؛

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

أ

الشكل 2 الشكل 3

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

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

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

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

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

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

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

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

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

6. أي من الحلول هو "الأفضل" لمشكلة تعظيم الوظيفة إذا ?

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

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

9. ما يسمى حل نظام من المتباينات الخطية بمتغيرين؟ أنشئ على المستوى مجال الحلول الممكنة لمثل هذا النظام من عدم المساواة الخطية ، والتي:

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

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

3) ليس له حل.

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

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

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

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

1) يتم الوصول إليه في نقطة واحدة ، و- في جزء التسوية الحاسوبية ؛

2) يتم الوصول إليها في نقطة واحدة من المواد المستنفدة للأوزون ، و.

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

1) لديها حلول مثالية فريدة من نوعها و ؛

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

محاضرة 2

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

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

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

3. حالات خاصة للحل الجرافيكي لشركة LLP

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

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

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

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

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

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

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

تسمى مجموعة الحلول الممكنة مجال الحلول المجدية لـ LLP.

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

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

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

الانتقال إلى الترميز المتعارف عليه ZLP.

مثال.

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

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

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

أساس حل المشكلات الاقتصادية هو النماذج الرياضية.

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

يتضمن رسم نموذج رياضي ما يلي:

• اختيار متغير المهمة
• وضع نظام القيود
• اختيار الوظيفة الموضوعية

متغيرات المهمةتسمى الكميات X1 ، X2 ، Xn ، والتي تميز العملية الاقتصادية بالكامل. عادة ما يتم كتابتها كمتجه: X = (X 1، X 2، ...، X n).

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

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

بشكل عام ، يمكن كتابة مشكلة البرمجة الخطية على النحو التالي:

يعني هذا الإدخال ما يلي: أوجد الحد الأقصى للدالة الهدف (1) والمتغيرات المقابلة X = (X 1، X 2، ...، X n) بشرط أن تلبي هذه المتغيرات نظام القيود (2) وغير - شروط السلبية (3).

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

مجموعة الحلول المجدية (الخطط) لنماذج المشكلة مجموعة من الحلول الممكنة(ODR).

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

مثال على تجميع نموذج رياضي

مهمة استخدام الموارد (المواد الخام)

حالة:لتصنيع أنواع n من المنتجات ، يتم استخدام أنواع من الموارد. اصنع نموذجًا رياضيًا.

معروف:

• ب i (i = 1،2،3 ، ... ، م) هي احتياطيات كل نوع من أنواع الموارد ؛
• أ ij (i = 1،2،3 ، ... ، م ؛ ي = 1،2،3 ، ... ، ن) هي تكاليف كل نوع من الموارد من أجل إنتاج وحدة حجم النوع j من المنتج ؛
• c j (j = 1،2،3 ، ... ، n) هو الربح من بيع وحدة حجم من النوع j من المنتج.

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

حل:

نقدم متجهًا للمتغيرات X = (X 1 ، X 2 ، ... ، X n) ، حيث x j (j = 1،2 ، ... ، n) هو حجم إنتاج النوع j من منتج.

تكاليف النوع الأول من الموارد لإنتاج حجم معين x j من المنتجات تساوي ij x j ، وبالتالي ، فإن القيود المفروضة على استخدام الموارد لإنتاج جميع أنواع المنتجات لها الشكل:
ربح بيع منتج من النوع j يساوي c j x j ، وبالتالي فإن دالة الهدف تساوي:

إجابة- النموذج الرياضي يشبه:

الشكل المتعارف عليه لمشكلة البرمجة الخطية

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

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

يمكن تمثيله في ترميز التنسيق والمتجه والمصفوفة.

مشكلة البرمجة الخطية المتعارف عليها في تدوين الإحداثيات لها الشكل:

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

• A هي مصفوفة معاملات نظام المعادلات
• X عبارة عن مصفوفة عمود لمتغيرات المهمة
• Ao هو عمود المصفوفة للأجزاء اليمنى من نظام القيد

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

اختزال مشكلة البرمجة الخطية العامة إلى شكل متعارف عليه

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

يمكن القيام بذلك على النحو التالي:

خذ المتباينة الخطية a 1 x 1 + a 2 x 2 + ... + a n x n ≤b وأضف إلى جانبها الأيسر بعض القيمة x n + 1 بحيث تصبح المتباينة هي المساواة a 1 x 1 + a 2 x 2 + ... + أ ن س ن + س ن + 1 = ب. علاوة على ذلك ، هذه القيمة x n + 1 غير سالبة.

دعونا نفكر في كل شيء بمثال.

مثال 26.1

اختصر مشكلة البرمجة الخطية إلى شكل متعارف عليه:

حل:
دعنا ننتقل إلى مشكلة إيجاد الحد الأقصى للدالة الهدف.
للقيام بذلك ، نقوم بتغيير علامات معاملات الوظيفة الهدف.
لتحويل المتباينات الثانية والثالثة لنظام القيد إلى معادلات ، نقدم متغيرات إضافية غير سالبة × 4 × 5 (تم تمييز هذه العملية بالحرف D في النموذج الرياضي).
يتم إدخال المتغير x 4 في الجانب الأيسر من المتراجحة الثانية بعلامة "+" ، لأن المتباينة لها الصيغة "≤".
يتم إدخال المتغير x 5 في الجانب الأيسر من المتراجحة الثالثة بعلامة "-" ، لأن المتباينة لها الصيغة "≥".
يتم إدخال المتغيرات × 4 × 5 في دالة الهدف بمعامل. يساوي الصفر.
نكتب المشكلة في شكل أساسي.