البرامج الخطية. البرامج الخطية - التجميع المجرد للبرامج البسيطة

1.2 باختصار حول البرمجة الخطية.

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

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

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

البرمجة الخطية هي تقنية التحسين الأكثر استخدامًا. تتضمن مشكلات البرمجة الخطية ما يلي:

الاستخدام الرشيد للمواد الخام والمواد ؛ قطع المهام الأمثل ؛

· تعظيم الاستفادة من برنامج الإنتاج للمؤسسات ؛

التنسيب الأمثل وتركيز الإنتاج ؛

وضع خطة مثالية للنقل وعملية النقل ؛

إدارة مخزون الإنتاج ؛

والعديد من الآخرين ينتمون إلى مجال التخطيط الأمثل.

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

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

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

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

1.3 المهمة الرئيسية للبرمجة الخطية

تم تعيين المشكلة الرئيسية للبرمجة الخطية (OLPP) على النحو التالي: هناك عدد من المتغيرات. مطلوب للعثور على القيم غير السالبة التي من شأنها أن ترضي النظام المعادلات الخطية:

{1.1}

وبالإضافة إلى ذلك ، من شأنه أن يقلل من وظيفة الهدف الخطية (TF)

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

الحل المقبول لـ OLP هو أي مجموعة من المتغيرات التي تحقق المعادلات (1.1).

الحل الأمثل هو الحلول الممكنة ، حيث يصبح المرشح الرقمي هو الحد الأدنى.

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

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

{1.2}

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

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

{1.3}

أين توجد المتغيرات الإضافية ، والتي هي أيضًا غير سلبية.

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

المعاملات في الصيغة (1.3) من قبل تساوي الصفر.

1.3 بناء القيود والانحدار لوظيفة الهدف: 1.4. منطقة الحلول المجدية هي القطعة AB. 1.5 النقطة (أ) هي الأمثل. إحداثيات النقطة أ: ؛ ؛ . 2. حل مشكلة البرمجة الخطية بطريقة simplex. مهمة مباشرة. يمكن تمثيل مشكلة البرمجة الخطية لأي رأس في شكل مضغوط على النحو التالي: للحصول على ، نستخدم الخوارزمية الواردة في ...

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

المهام f1 (x) = max = g1 (x) - للمؤسسة الأولى ؛ - للمؤسسات الأخرى. حل مشكلة التوزيع الأمثل للأموال بين المؤسسات بطريقة البرمجة الديناميكية الجدول 12 الصناديق ذات الألف غرام. النبات 1 2 3 4 G1 (x) G2 (x) G3 (x) G4 (x) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57100 62 62 ...

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

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

المهمة 1.1. حساب الصيغة

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

حيث C هي درجة الحرارة بالدرجة المئوية و F هي درجة الحرارة بالفهرنهايت.

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

في هذه الحالة:

البيانات الأولية هي رقم حقيقي واحد يمثل درجة الحرارة بالدرجة المئوية ،

والنتيجة هي رقم حقيقي آخر.

قبل كتابة البرنامج ، دعنا نفتح Visual C ++ IDE:

ابدأ / برامج / Microsoft Visual Studio / Microsoft Visual C ++ 6.00

1) ملف> جديد ...

2) في النافذة المفتوحة:

حدد نوع تطبيق Win32 Console ؛

أدخل اسم مشروع في مربع النص اسم المشروع ؛

أدخل (حدد باستخدام الزر ...) اسم الدليل حيث توجد ملفات المشروع في حقل نص الموقع ، على سبيل المثال G: / ASOIZ /

انقر فوق زر الفأرة الأيسر على زر موافق.

3) تطبيق Win32 Console - يتم فتح مربع الحوار Stepl of 1 وفيه:

حدد النوع مشروع فارغ ؛

انقر فوق الزر "إنهاء".

4) بعد النقر ، ستظهر نافذة مشروع جديد ، حيث يتم النقر فوق الزر "موافق".

1) ملف > جديد .... سيؤدي ذلك إلى فتح مربع حوار جديد.

2) في علامة التبويب الملفات:

حدد نوع الملف (في هذه الحالة: C ++ Source File) ؛

في حقل النص File Name ، أدخل اسم الملف المطلوب ؛

يجب تمكين مربع الاختيار "إضافة إلى المشروع" ؛

انقر فوق الزر "موافق".

نكتب نص البرنامج التالي:

دعنا نفكر في كل سطر من البرنامج على حدة.

في بداية البرنامج ، يتم كتابة توجيه ما قبل المعالج ، والذي بموجبه يتم توصيل ملف الرأس بالكود المصدري للبرنامج . هذا ملف يحتوي على أوصاف لبيانات cin و cout I / O.

يتكون أي برنامج C ++ من وظائف ، يجب أن تحمل إحداها الاسم main ، مما يشير إلى أن تنفيذ البرنامج يبدأ معه. بعد الأقواس الموجودة بين قوسين معقوفين () ، يتم كتابة جسم الوظيفة ، أي البيانات التي سيتم تنفيذها.

أي فراغ عند كتابة برنامج له شكل:

#تضمن<…>

#تضمن<…>

إعلان المتغيرات

إدخال البيانات الأولية ؛

حساب النتيجة

نتيجة الإخراج

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

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

أنواع رئيسية:

int (قصير ، بدون إشارة) - عدد صحيح ،

تعويم (مزدوج ، طويل مزدوج) - حقيقي

شار - حرف

منطقي

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

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

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

لعرض النتيجة في البيان 6 ، يتم استخدام الكائن كوت.يتم عرض سلسلة تتكون من خمسة عناصر. هذه هي الخيط "فهرنهايت:"، قيمة متغيرة الفهر، خط "، بالدرجات المئوية:"، قيمة متغيرة سلوعامل القفز خط جديد إندل.

تم تصميم البيان الأخير (البيان 7) من هذا البرنامج للعودة منه ونقل القيمة إلى البيئة الخارجية.

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

لبدء البرنامج ، اضغط على الزر الموجود على شريط الأدوات أو مجموعة المفاتيح Ctrl + F5.

عند تشغيل البرنامج بدلا من الحروف الروسية نرى ؟؟؟ وهو ناتج عن معايير مختلفة لتشفير الحروف السيريلية في أنظمة التشغيل MS DOS و Windows. لإصلاحها ، أضف وظيفة CharToOem إلى البرنامج (يتم تمييز الوظائف الإضافية باللون الأحمر من أجل الوضوح)

#تضمن

#تضمن

char * RUS (const char * text)

CharToOem (نص ، buf) ؛

أجرة تعويم ، سل ؛

كوت<

سل = 5/9 * (فهر - 32) ؛

كوت<

كوت<

دور روس ()لا يمكن استخدامه أكثر من مرة في سلسلة عمليات<< для одного объекта كوت، لذلك قمنا بتقسيمها إلى قسمين.

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

سل = 5. / 9 * (فهر - 32) ؛

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

المتغيرات

المتغير هو قيمة يمكن أن - أثناء تشغيل البرنامج -

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

يُعطى كل متغير اسمه ونوعه ، على سبيل المثال:

رقم var: عدد صحيح ؛ س ، ص: حقيقي ؛ الخيار: شار ؛

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

يتم تحديد نوع المتغيرات بناءً على النطاق والدقة المطلوبة لتمثيل البيانات.

عند التصريح ، يمكنك تعيين قيمة أولية لمتغير ، أي تهيئةلها. يُفهم التهيئة على أنها تحديد القيمة التي يتم إجراؤها قبل بدء البرنامج. يتم التصريح عن المتغيرات الأولية بعد الكلمة الأساسية const:

رقم ثابت: عدد صحيح = 100 ؛ س: حقيقي = 0.02 ؛ الخيار: char = "u" ؛

بشكل افتراضي ، يتم تعيين جميع المتغيرات المعلنة في البرنامج الرئيسي على الصفر.

التعبيرات

التعبير هو قاعدة لتقييم قيمة. في التعبير تشارك -

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

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

• 1. عملية أحادية لا ، أحادية ناقص - ، تأخذ العنوان @.
• 2. عمليات مثل الضرب: * / div mod و shl shr.
• 3. عمليات نوع الإضافة: + - أو xor.
• 4. العمليات العلائقية: = o = in.

يتم تقييم الدوال المستخدمة في التعبير أولاً.

أمثلة التعبير:

t + sin (x) / 2 * x - النتيجة من نوع حقيقي ؛ أ

(س> 0) و (ص

هيكل البرنامج

يتكون برنامج PASCAL من عنوان اختياري وأقسام وصف وقسم بيان:

إسم البرنامج؛ (رأس) أقسام الإعلان تبدأ نهاية أقسام البيان. (* البرنامج ينتهي بنقطة *)

قد يحتوي البرنامج على ملفات تعليقات،محاطة بأقواس متعرجة () أو أقواس من النموذج (* *).

يظهر الهيكل العام للبرنامج في الشكل. 2.1.

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

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

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

أرز. 2.1.

يجب أن يأتي قسم وصف الوحدة ، إذا كان موجودًا ، أولاً. يبدأ الوصف بالكلمة الرئيسية "الاستخدامات" ، متبوعة بقائمة مفصولة بفواصل لجميع الوحدات المتصلة بالبرنامج ، القياسية والمخصصة ، على سبيل المثال: استخدامات crt ، رسم بياني ، my_module ؛

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

في قسم إعلان المتغيرات ، يجب تحديد جميع المتغيرات التي سيتم استخدامها في البرنامج الرئيسي.

يتم استخدام قسم إعلان الثوابت بحيث يمكن استخدام أسمائها في البرنامج بدلاً من قيم الثوابت. هناك استخدام آخر لقسم التصريح الثابت: فهو يصف المتغيرات التي يجب تخصيص قيمة لها قبل بدء البرنامج:

الوزن الثابت: الحقيقي = 61.5 ؛ ن = 10 ؛

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

يتم استخدام الملصقات لتنظيم الانتقال إلى عامل معين باستخدام عامل القفز غير المشروطاذهب إلى.

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

إدخال لوحة المفاتيح. تم تحديد الإجراءات التالية لإدخال لوحة المفاتيح: read and readln: read (list)؛ readln [(قائمة)] ؛

تحتوي الأقواس على قائمة بأسماء المتغيرات مفصولة بفواصل. تشير الأقواس المربعة إلى أن القائمة قد تكون مفقودة. على سبيل المثال:

قراءة (أ ، ب ، ج) ؛ readln (ذ) ؛ readln.

الانتباه

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

يتم إدخال قيمة كل متغير على النحو التالي:

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

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

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

الإخراج على الشاشة. عند الإخراج ، يتم إجراء التحويل العكسي: من التمثيل الداخلي إلى الأحرف المعروضة على الشاشة. للقيام بذلك ، تحدد اللغة الإجراءات المعيارية كتابة وكتابة: write (list)؛ writeln [(قائمة)] ؛

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

يمكنك إخراج القيم المنطقية ، والأعداد الصحيحة ، والحقيقية ، وأنواع الأحرف والسلسلة. لا يمكن أن تحتوي القائمة على أسماء المتغيرات فحسب ، بل يمكن أن تحتوي أيضًا على التعبيرات ، بالإضافة إلى حالة الأحرف الخاصة بها - الثوابت. بالإضافة إلى ذلك ، يمكنك تعيين كل قيمة إخراج صيغة،على سبيل المثال: writeln (أ: 4 ، ب: 6: 2) ؛

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

15. طرق التحليل. طرق البرمجة الخطية.

15.1. الطرق التحليلية

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

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

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

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

جزء لا يتجزأ من طرق التحسين هو البرمجة الخطية.

15.2. مفاهيم البرمجة الخطية الأساسية

أول ذكر (1938) للطرق الرياضية في الإدارة الفعالة للإنتاج يعود لعالم الرياضيات السوفيتي ل.ف.كانتوروفيتش. بعد ذلك بعام ، في عام 1939 ، نشر L.V Kantorovich العمل "الطرق الرياضية لتنظيم وتخطيط الإنتاج" وطبق النتائج التي تم الحصول عليها عمليًا. تم تقديم مصطلح "البرمجة الخطية" من قبل عالم الرياضيات الأمريكيين J. Danzig و T. Koopmans في أواخر الأربعينيات. قام J. Dantzig بتطوير الجهاز الرياضي لطريقة simplex لحل مشاكل البرمجة الخطية (1951). تُستخدم طريقة simplex لحل مجموعة كبيرة من مشكلات البرمجة الخطية وهي إحدى الطرق الرئيسية حتى الآن.

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

أن تكون فريدة من نوعها لمهمة معينة ؛

تقاس بوحدات الكمية ؛

تعتمد خطيًا على معلمات الإدخال.

بناءً على ما تقدم ، يمكننا صياغة مشكلة البرمجة الخطية بشكل عام:

أوجد أقصى دالة موضوعية

تحت قيود في شكل مساواة:

(2.2)

تحت قيود في شكل عدم المساواة:

(2.3)

وشروط عدم سلبية معلمات الإدخال:

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

(2.5)

قدمت

أين
- متغيرات الإدخال ؛

الأعداد موجبة وسالبة وتساوي الصفر.

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

يمكن حل مشاكل البرمجة الخطية تحليليًا وبيانيًا.

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

, أنا = 1 ، ... ، م ،

، ي = 1 ، ... ، ن.

تم تطوير الطرق الحسابية الرئيسية لحل مشاكل البرمجة الخطية خصيصًا للمشكلة الأساسية.

15.4. مشكلة عامة في البرمجة الخطية

من الضروري تعظيم (تقليل) دالة خطية لـ نالمتغيرات.

تحت قيود

, أنا=1,…, ك,

, أنا=1+ ك,…, م,

, …,

هنا ك≤ م, ص≤ ن. يتم الحصول على المشكلة القياسية كحالة خاصة للمشكلة العامة لـ ك= م, ص= ن؛ الكنسي - في ك=0, ص= ن.

مثال.

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

الجدول 1. معدلات استهلاك المواد الخام

لإنتاج

الصيغة الاقتصادية والرياضية للمشكلة لها الشكل

ابحث عن هذه القيم المتغيرة X = (x1، x2، x3)، ل

دالة الهدف

في ظل قيود الشروط: