: مشاكل البرمجة الخطية (LPP)

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

2. أنواع مشاكل البرمجة الخطية

3. نماذج لتسجيل الأشخاص المتأثرين بالمشروع

4. الشكل القانوني لمشاكل البرمجة الخطية

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

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

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

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

الشكل 1 - الحد الأقصى للوظيفة الموضوعية

تتم كتابة النموذج الرياضي لـ ZLP على النحو التالي:

الحد الأقصى (أو الأدنى) Z=z(X)،(1)

يمكن تمثيل ODR بنظام المعادلات الخطية أو المتباينات.

Vector X = (x 1, x 2, .... x p) هو ناقل تحكم أو تأثير تحكم.

الخطة المقبولة X، التي يصل فيها معيار المثالية Z=z(X) إلى قيمة متطرفة، تسمى الأمثل ويشار إليها بـ X*، القيمة القصوى للدالة الموضوعية بـ Z*=z(X*).

أنواع مشاكل البرمجة الخطية

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

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

عند إنتاج المنتجات، تكون المؤسسة محدودة بالموارد المتاحة، والتي سيتم الإشارة إلى كميتها بواسطة m، ومتجه الموارد B = (b 1, b 2, ..., b t). تُعرف أيضًا المعاملات التكنولوجية a ij، والتي توضح معدل استهلاك المورد i لإنتاج وحدة من المنتج j. تتميز كفاءة إنتاج الوحدة j من المنتجات بالربح p j .

مطلوب تحديد خطة الإنتاج X = (x 1, x 2, ..., x p)، مما يؤدي إلى تعظيم ربح المؤسسة بالموارد المحددة.

تبدو الوظيفة الموضوعية هكذا

تحت القيود

في كثير من الأحيان يتم إنشاء نطاق المنتجات من قبل منظمة أعلى، أي أنه يجب احتواء أحجامها ضمن حدود معينة D في j وD في j: ثم يتم تعيين القيد التالي:

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

مع الاحتفاظ بنفس الترميز، نكتب من خلال b j وc j، على التوالي، سعر البيع والتكاليف لكل وحدة من المنتج j. ويمكن اعتبار ما يلي كمعايير الأمثلية:

1) الحد الأقصى للربح

2) الحد الأدنى من تكاليف الإنتاج

3) الحد الأقصى للإنتاج من حيث القيمة (الإيرادات من مبيعات المنتجات)

مثال. يمكن للمؤسسة إنتاج أربعة أنواع من المنتجات 1 و2 و3 و4. ويتم ضمان مبيعات أي حجم. خلال هذا الربع، تمتلك الشركة قوة عاملة تبلغ 100 نوبة عمل، ومنتجات نصف جاهزة تزن 260 كجم، ومعدات آلية تصل إلى 370 نوبة عمل. يتم عرض معدلات استهلاك الموارد والربح لكل وحدة من كل نوع من المنتجات في الجدول 1.

ضروري:

أ) وضع نموذج رياضي لمشكلة تحديد خطة الإنتاج التي يتم من خلالها تحقيق أقصى قدر من الربح؛

ب) حل المشكلة باشتراط أن يكون عدد وحدات المنتج الثالث أكبر بثلاث مرات من عدد وحدات المنتج الأول؛

ج) اكتشف التشكيلة المثالية في ظل ظروف إضافية: إنتاج المنتج الأول 25 وحدة على الأقل، والثالث - لا يزيد عن 30، والثاني والرابع - بنسبة 1:3.

الجدول 1

البيانات الأولية

النموذج الرياضي للمشكلة:

دالة الهدف:

الحد الأقصى: Z=40x1 +50x2 +100x3 +80x4

مع القيود:

أ) لموارد العمل:

2.5x1 +2.5x2 +2x3 +1.5x4 ؟ 100؛

للمنتجات نصف المصنعة:

4x1 +10x2 +4x3 +6x4 ؟ 260؛

للأدوات الآلية:

8x1 +7x2 +4x3 +10x4 ؟ 370؛

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

ب) سيتم التعبير عن المتطلبات الإضافية للتكوين من خلال الشرط

3x1 =x3، أي 3x1x3 =0؛

ج) دعونا نعرض شروط الحدود وشرط التكوين على النحو التالي: x 1 ?

× 3؟30، 3*س 2 = × 4.

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

دعونا صياغة المشكلة رياضيا. دع عدد n من المنتجات يلزم إنتاجه باستخدام مجموعات متجانسة من المعدات. يتم تحديد خطة الإنتاج لكل نوع من المنتجات لفترة معينة من خلال مجموعة x j (j = 1,2, ...p). قوة كل نوع من المعدات محدودة وتساوي b i. المصفوفة التكنولوجية A=||a ij || معروفة، حيث ij هو عدد وحدات المنتج j المنتج لكل وحدة زمنية على الجهاز i. المصفوفة C هي مصفوفة تكلفة، حيث c ij هي التكاليف المرتبطة بإنتاج وحدة من المنتج j على المعدات i. X هو متجه لحجم الإخراج.

نموذج المشكلة سيأخذ الشكل التالي:

الوظيفة الموضوعية - تقليل تكاليف تنفيذ جميع الأوامر

مع القيود:

أ) بواسطة قوة المعدات

ب) للإنتاج

ج) حالة عدم السلبية

تسمى هذه المشكلة بمشكلة التوزيع أو التوزيع.

إذا كان مسموحًا بتجاوز الخطة لبعض أنواع المنتجات، فسيأخذ القيد (ب) الشكل

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

أ) الحد الأقصى للربح

ب) الحد الأدنى من تكلفة وقت الآلة

لأن يحتوي أي نموذج على أماكن مبسطة؛ من أجل التطبيق الصحيح للنتائج التي تم الحصول عليها، من الضروري فهم واضح لجوهر هذه التبسيطات، والذي يسمح لنا في النهاية باستخلاص استنتاج حول مقبوليتها أو عدم مقبوليتها. إن التبسيط الأكثر أهمية في النماذج المدروسة هو افتراض وجود علاقة متناسبة بشكل مباشر (خطي) بين أحجام استهلاك الموارد وأحجام الإنتاج، والتي يتم تحديدها باستخدام معايير التكلفة a ij . ومن الواضح أن هذا الافتراض لا يتحقق دائما. وبالتالي، فإن أحجام استهلاك العديد من الموارد (على سبيل المثال، الأصول الثابتة) تتغير فجأة - اعتمادًا على التغييرات في برنامج الإنتاج X. تتضمن فرضيات التبسيط الأخرى افتراضات حول استقلال الأسعار j عن الأحجام x j، والتي تكون صالحة فقط لحدود معينة من تغييرهم. ومن المهم أيضًا معرفة هذه النقاط "الضعيفة" لأنها تشير إلى اتجاهات أساسية لتحسين النموذج.

نماذج تسجيل PAP

هناك 3 أشكال لتسجيل PAP:

1) في شكل وظائف

الحد الأقصى (أو الحد الأدنى) Z =، الحد الأقصى (أو الحد الأدنى) Z =،

2) شكل ناقل

(المنتج العددي للمتجهات)

تحت القيود

أ 1 × 1 + أ 2 × 2 +..+ أ ن × ن = ب

أين هي المتجهات

C = (C 1، C 2 .. C n)، X = (X 1، X 2 .. X n)، و.

3) شكل المصفوفة

تحت القيود

حيث C = (ج 1، ج 2،... ج ن)،

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

إذا كانت جميع القيود في مشكلة البرمجة الخطية عبارة عن معادلات وتم فرض شروط غير سلبية على جميع المتغيرات x j، فإنها تسمى مشكلة برمجة خطية في شكل قانوني أو مشكلة برمجة خطية قانونية (CLP).

تحت القيود

ومن أجل الانتقال من ZLP إلى CLLP، من الضروري الانتقال من قيود عدم المساواة إلى قيود المساواة واستبدال المتغيرات التي لا تخضع لشروط عدم السلبية.

قواعد جلب ZLP إلى الشكل الأساسي:

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

2) إذا كانت هناك عدم مساواة بين القيود، فمن خلال إدخال متغيرات غير سلبية إضافية يتم تحويلها إلى مساواة؛

3) إذا كان بعض المتغير xk ليس له قيود على الإشارة، فإنه يتم استبداله في الدالة الموضوعية وفي جميع القيود بالفرق بين متغيرين جديدين غير سالبين: xk=x * k - xl، حيث l هو الفهرس الملخص، x * ك>=، XL >=0.

لنلقي نظرة على مثال. دعنا نأتي بالصيغة الأساسية:

دعونا نقدم متغيرات التسوية x 4، x 5، x 6 في كل معادلة من نظام القيود. سيتم كتابة النظام على صورة المعادلات، وفي المعادلتين الأولى والثالثة من نظام القيود يتم إدخال المتغيرات x 4، x 6 على الجانب الأيسر بعلامة "+"، وفي المعادلة الثانية x يتم إدخال الرقم 5 بعلامة "-".

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

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

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

تحسين البرمجة الخطية البسيطة

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

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

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

مجموعة كل الحلول الممكنة تسمى مجال الحلول الممكنة(ODR).

يتم استدعاء الحل المقبول الذي يتم من خلاله تحقيق الحد الأقصى (الحد الأدنى) لقيمة الوظيفة الخطة المثالية لـ PAP.

مصطلحات "الخطة" و"الخطة المثلى" تنشأ من التطبيقات الاقتصادية.

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

دعونا نفكر في خوارزميات الانتقال من نموذج إلى آخر.

• 
  متماثل  قانوني.ويتم الانتقال عن طريق إضافة متغير إضافي غير سلبي إلى الجانب الأيسر من كل متباينة. إذا كانت المتراجحة "≥"، يضاف متغير التوازن إلى الجانب الأيسر من المتراجحة بعلامة "+". إذا كانت المتراجحة ""، فسيتم إضافة متغير التوازن إلى الجانب الأيسر من المتراجحة بعلامة "-". تسمى المتغيرات الجديدة المقدمة ورقة التوازن. يتم استبدال مشكلة تصغير الدالة Z بمشكلة تعظيم الدالة (–Z) ويتم استخدام أن min Z = –max (–Z).
• 
  الكنسي  متماثل.لتنفيذ مثل هذا التحول، تم العثور على حل عام لنظام المعادلات – القيود، ويتم التعبير عن الدالة المستهدفة من حيث المتغيرات الحرة. وبعد ذلك، وبالاستفادة من عدم سلبية المتغيرات الأساسية، يمكننا استبعادها من المشكلة. سيحتوي الشكل المتماثل للمشكلة على عدم مساواة تتعلق بالمتغيرات الحرة فقط ودالة موضوعية تعتمد فقط على المتغيرات الحرة. تم العثور على قيم المتغيرات الأساسية من الحل العام لنظام المعادلات الأصلي.
• 
  عام  قانوني.يتم تمثيل كل متغير لم يُفرض عليه شرط عدم السلبية على أنه الفرق بين متغيرين جديدين غير سلبيين. يتم تحويل المتباينات إلى معادلات عن طريق إدخال متغير التوازن على الجانب الأيسر من كل متباينة بنفس الطريقة التي تم وصفها في الانتقال من الشكل المتماثل إلى الشكل القانوني. يتم استبدال مشكلة تصغير الدالة Z بمشكلة تعظيم الدالة (–Z) بنفس الطريقة التي تم وصفها أثناء الانتقال من الشكل المتماثل إلى الشكل القانوني.

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

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

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

مثال 1

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

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

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

النظرية 2 يجب أن يكون هناك نقطتان تعسفيتان في الفضاء ر ن. ثم لأي نقطة من القطعة [ PQ] يجب أن يتم تنفيذه: .where .

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

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

النظرية 3 نصف المساحة عبارة عن مجموعة محدبة.

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

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

مثال 2

المجموعات التالية هي المضلعات.

مجموعة محدودة

مجموعة غير محدودة

نقطة واحدة

مجموعة فارغة

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

مثال 3

نقاط زاوية المثلث هي رؤوسه (توجد ثلاث منها). نقاط زاوية الدائرة هي نقاط الدائرة التي تحدها (يوجد منها عدد لا نهائي).

تسمى نقطة الزاوية في متعدد السطوح به قمة.

دعونا نفكر في ZLP المعطى في شكل متماثل.

النظرية 4 تتوافق الخطة المثالية لـ ZLP مع قمة القرار متعدد السطوح الذي يحدده نظام القيود الخاص به.

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

2.1. تعريف وأشكال التسجيل

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

أ) مشكلة LP الأساسية في النموذج الإحداثي لها الشكل:

,
.

يمكن كتابة هذه المسألة باستخدام علامة الجمع:

,

,

,
,
.

ب) مشكلة LP الأساسية في شكل متجه لها الشكل: ،

,

أين
;
;

,
;;
.

ج) مشكلة LP الأساسية في شكل مصفوفة لها الشكل:

,
,

أين
,,.

2.2. الحد من المشكلة الخطية العامة

البرمجة إلى النموذج الكنسي

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

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

متغير غير سلبي
يسمى متغير إضافي. توفر النظرية التالية الأساس لإمكانية حدوث مثل هذا التحول.

نظرية 2.2.1.كل قرار
عدم المساواة (2.2.1) يتوافق مع حل فريد للمعادلة (2.2.2) وعدم المساواة
، وعلى العكس من ذلك، لكل حل للمعادلة (2.2.2)ج
يتوافق مع الحل
عدم المساواة (2.2.1).

دليل.يترك
حل عدم المساواة (2.2.1). ثم. دعونا نأخذ رقما
. انه واضح
. بالتعويض في المعادلة (2.2.2) نحصل على

لقد تم إثبات الجزء الأول من النظرية.

لنكن الآن ناقلًا يحقق المعادلة (2.2.2) مع
، أي تجاهل القيمة غير السالبة على الجانب الأيسر من المساواة الأخيرة
، نتلقى، الخ

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

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

3. الأسلوب الرسومي لحل المشكلات

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

3.1. المفاهيم العامة والأمثلة

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

(3.1.1)

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

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

خط المستوىويسمى الخط المستقيم الذي تقوم عليه الدالة الهدف يأخذ قيمة ثابتة. معادلة خط المستوى لها الشكل

، أين
. جميع خطوط المستوى متوازية مع بعضها البعض. وضعها الطبيعي
.

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

قيم
زيادة في اتجاه المتجه
. لذلك، من الضروري تحريك خط المستوى
في اتجاه هذا المتجه الموازي لنفسه إلى الخط المرجعي ل 1 في المهمة القصوى وفي الاتجاه المعاكس - في المهمة الدنيا (حتى الخط المرجعي ل 2).

دعونا نعطي الحل للمثال 1.1. تذكر أننا بحاجة إلى إيجاد القيمة العظمى للدالة
تحت القيود

حل. نحن نبني منطقة من الحلول الممكنة. نحن نرقم قيود المشكلة. في نظام الإحداثيات الديكارتي المستطيل (الشكل 2)، نقوم ببناء خط مستقيم

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

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

ومجال حل القيد (2). نجد الجزء المشترك لأنصاف مستويات الحلول مع مراعاة القيود (3). نسلط الضوء على المنطقة الناتجة من الحلول الممكنة باللون الداكن في الشكل 2.

بناء خط المستوى
وناقلات
مما يدل على اتجاه زيادة الدالة وعمودي على الخط

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

مثال 3.1. العثور على الحد الأدنى من وظيفة
مع نظام القيود

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

لذا،
. دعونا نحسب.

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

مثال 3.2. العثور على الحد الأدنى من وظيفة
تحت القيود

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

وللمشكلة عدد لا نهائي من الحلول المثالية وهي نقاط القطعة
. هذه النقاط
,
نجد من خلال حل أنظمة المعادلات المقابلة:

;
;

,
;
,
;

;
.

دعونا نحسب.

إجابة:
في
,
.

مثال 3.3. حل مشكلة البرمجة الخطية

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

المشكلة ليس لها حل بسبب عدم حدود الوظيفة الهدف.

إجابة:
.

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

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

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

وتحتاج إلى العثور على الحد الأقصى لوظيفة الهدف الخطية

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

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

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

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

لاحظ أن عدد المتغيرات الإضافية غير السلبية المقدمة يساوي دائمًا عدد المتباينات في نظام القيود الأصلي.

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

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

مثال. اكتب مسألة التحسين الخطي التالية بالصيغة الأساسية: ابحث عن الحد الأدنى للدالة
تحت القيود

حل

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

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

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

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

العثور على الحد الأقصى للدالة

تحت القيود

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

لضمان التوحيد في تسجيل الأشخاص المتأثرين بالمشروع، ما يسمى الشكل الكنسيالسجلات.

يُقال إن ZLP مكتوب بالشكل الأساسي إذا كان يحتوي على النموذج التالي:

دعونا نلاحظ الميزات التالية للشكل القانوني:

1) مطلوب لتقليل الوظيفة الموضوعية؛

2) جميع القيود الخطية، باستثناء متطلبات عدم سلبية المتغيرات، لها شكل المساواة؛

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

دعونا نبين أنه يمكن اختزال أي ZLP إلى الشكل الأساسي.

1) إذا كان مطلوبًا في ZLP تعظيم الوظيفة الموضوعية f، فسنقوم بتعيين g = - f وتتطلب التقليل من وظيفة ز. وستكون النتيجة ZLP جديدة، وهي تعادل الحل الأصلي بمعنى أن كل حل أمثل للمشكلة الأصلية سيكون حلاً أمثل للمشكلة الجديدة والعكس صحيح.

2) افترض أن ZLP لديه قيد خطي للنموذج

ولنستبدل هذا القيد بالقيدين التاليين:

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

وبالمثل، يتم استبدال قيد العرض بقيدين:

3) لنفترض أنه في ZLP ليست كل المتغيرات تخضع لشرط عدم السلبية. ثم كل متغير والتي لا تخضع لشرط عدم السالبة يمكن تمثيلها بالفرق بين متغيرين غير سالبين:

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

باستخدام هذه التقنيات، يتم تقليل أي ZLP إلى الشكل الأساسي.

مثال. تقليل إلى الشكل الكنسي

دعونا نفعل الخطوات الموضحة.

الآن نحصل على ZLP في شكل أساسي:

2.7. مفهوم خطة الدعم.

دع VLP يُعطى في شكل قانوني (2.3 - 2.5). لنفترض أن نظام المعادلات (2.4) تم اختزاله إلى صيغة جوردان بأطراف يمين غير سالبة:

(2.6)

أين
.

وبمساواة المتغيرات الحرة بالصفر نحصل على الحل الأساسي للنظام (2.4)

بسبب الظروف
مجموعة قيم المتغيرات (2.7) تفي أيضًا بالقيود (2.5). لذلك (2.6) هو قرار مقبول من حزب الشعب.

يسمى الحل المقبول (2.7). الأساسية المسموح بهاالقرار أو الخطة الأساسية لـ ZLP.في هذه الحالة يقولون أن المتغيرات
تشكيل أساس مقبول.

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

إذا كانت ZLP قابلة للحل، فهناك خطة دعم مثالية.

3. طريقة Simplex لحل المشكلات

3.1. الخصائص العامة والمراحل الرئيسية للطريقة البسيطة

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

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

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

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

عند حل مشكلة ما باستخدام الطريقة البسيطة يمكن تمييز المراحل التالية:

1) إحضار ZLP إلى الشكل الأساسي؛

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

3) دراسة الخطة المرجعية للأمثل.

4) دراسة ZLP لعدم القدرة على التحديد بسبب عدم الحدود من الأسفل على ODD للوظيفة الموضوعية؛

5) الانتقال إلى خطة مرجعية جديدة "أفضل".