ما هو البرنامج الخطي. باختصار عن البرمجة الخطية. البرامج الخطية ذات المصفوفات

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

هنا سننظر في مشكلة البرمجة الخطية مع قيود المساواة - ما يسمى بمشكلة البرمجة الخطية الأساسية (0PLP).

فيما يلي ، سوف نوضح كيف يمكن للمرء أن ينتقل من مشكلة قيود عدم المساواة إلى LPLP ، والعكس صحيح.

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

هناك عدد من المتغيرات

مطلوب للعثور على مثل هذه القيم غير السالبة لهذه المتغيرات التي من شأنها أن ترضي النظام المعادلات الخطية:

وعلاوة على ذلك ، من شأنه أن يقلل دالة خطية

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

دعونا نتفق على استدعاء أي مجموعة من المتغيرات

معادلات مرضية (2.1).

الحل الأمثل هو الحلول الممكنة التي تصبح فيها الدالة الخطية (2.2) هي الحد الأدنى.

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

قد يتضح أن المعادلات (2.1) تتعارض مع بعضها البعض ؛ قد يتضح أن لديهم حلًا ، لكن ليس في منطقة القيم غير السلبية. ثم لا توجد حلول مجدية لـ OZLP. أخيرًا ، قد يتضح أن الحلول الممكنة لـ DLP موجودة ، ولكن من بينها لا يوجد حل مثالي: الوظيفة L في منطقة الحلول الممكنة غير محدودة من الأسفل.

سوف نتعرف على أمثلة على ميزات OZLP هذه في المستقبل.

دعونا ننظر أولاً وقبل كل شيء في مسألة وجود حلول مقبولة لـ LPLP.

عند حل هذا السؤال ، يمكننا استبعاد الدالة الخطية L من الاعتبار ، والتي يجب تصغيرها - يتم تحديد وجود حلول مجدية فقط من خلال المعادلات (2.1).

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

دعونا نقدم ملخصًا موجزًا ​​لبعض عبارات الجبر الخطي ، دون الخوض في براهين النظريات المقابلة

مصفوفة نظام المعادلات الخطية

يسمى جدول يتكون من المعاملات في

المصفوفة الممتدة لنظام المعادلات الخطية هي نفس المصفوفة ، مكملة بعمود من المصطلحات المجانية:

رتبة المصفوفة هي أكبر ترتيب لمُحدد غير صفري يمكن الحصول عليه بحذف بعض الصفوف وبعض الأعمدة من المصفوفة.

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

مثال 1. تم إعطاء نظام من ثلاث معادلات بأربعة مجاهيل:

تحديد ما إذا كان النظام تعاوني؟

المحلول. مصفوفة النظام:

مصفوفة ممتدة:

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

بحساب هذا المحدد وفقًا لقاعدة معروفة ، نحصل على:

هذا المحدد لا يساوي صفرًا ، مما يعني أن رتبة مصفوفة النظام هي 3. من الواضح أن رتبة المصفوفة الموسعة تساوي أيضًا 3 ، حيث يمكن تكوين نفس المحدد من عناصر مصفوفة ممتدة. ويترتب على المساواة في صفوف المصفوفات أن نظام المعادلات ثابت.

مثال 2. للتحقق من توافق نظام من معادلتين مع ثلاثة مجاهيل:

المحلول. مصفوفة النظام الممتدة:

(الجانب الأيسر هو مصفوفة النظام).

دعونا نجد رتبة مصفوفة النظام عن طريق تكوين جميع المحددات الممكنة من الدرجة الثانية:

لذا ، فإن جميع المحددات المحتملة من الدرجة الثانية ، المكونة من عناصر مصفوفة النظام ، تساوي الصفر ؛ ومن ثم مرتبة هذه المصفوفة للنظام

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

ومن ثم ، فإن رتبة المصفوفة الممتدة لا تساوي رتبة مصفوفة النظام: Грг ، وبالتالي ، فإن نظام المعادلات غير متناسق.

مثال 3. للتحقق من اتساق نظام ثلاث معادلات ذات أربعة مجاهيل:

مصفوفة النظام الممتدة للحل (مع مصفوفة النظام):

لنجد رتبة مصفوفة النظام. خذ مُحددًا من الدرجة الثالثة يتكون من عناصره ، على سبيل المثال:

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

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

نظرًا لوجود محدد غير صفري للترتيب الثاني ، على سبيل المثال ،

ثم رتبة مصفوفة النظام هي

باستخدام نفس المنطق ، سنتأكد من أن مرتبة المصفوفة الممتدة تساوي اثنين: وبالتالي ، فإن نظام المعادلات ثابت

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

لذلك ، إذا كان نظام المعادلات والقيود الخاصة بـ LPLP متسقًا ، فإن مصفوفة النظام والمصفوفة الممتدة لها نفس الرتبة.

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

من الواضح أن رتبة النظام لا يمكن أن تكون أكبر من عدد المعادلات:

من الواضح أيضًا أن رتبة النظام لا يمكن أن تكون أكبر من العدد الإجمالي للمتغيرات:

في الواقع ، تُعرَّف رتبة مصفوفة النظام بأنها الترتيب الأكبر للمُحدد المكون من عناصر المصفوفة ؛ بما أن عدد خطوطها متساوية ، إذن ؛ بما أن عدد أعمدته متساوٍ إذن.

تعتمد بنية مشكلة البرمجة الخطية بشكل أساسي على مرتبة نظام القيد (2.1).

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

منذ ذلك الحين المحدد المكون من معاملات ،

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

لذلك ، بالنسبة لنظام قيود المعادلات ، فإن LPLP لديها حل فريد:

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

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

من الواضح أن هذه الحالة التافهة لا يمكن أن تهمنا.

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

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

مهمة تشغيل. يحدد أو يغير القيمة الحالية لبعض المتغيرات. هذا يغير محتوى عنصر ذاكرة معين مخصص لهذا المتغير. لأن الهدف من أي خوارزمية هو الوصول إلى موقع ذاكرة معين القيمة المطلوبة، تقريبًا أي برنامج يحتوي على هذا المشغل. عوامل الإدخال والإخراج. تُستخدم إجراءات إدخال البيانات القياسية لتحديد القيم الأولية لمتغيرات معينة وتتكون من اسم إجراء وقائمة إدخال تحتوي على أسماء المتغيرات التي سيتم إدخال قيمها من لوحة المفاتيح أو من ملف ، أي سيتم تعيين بعض القيم المحددة للمتغيرات.
في كثير من الأحيان ، يكون من الأنسب استخدام أمر الإدخال لتحديد القيم الأولية ، بدلاً من أمر التعيين ، لأنه إذا كنت بحاجة إلى استخدام البرنامج مع بيانات مصدر أخرى ، فلن تضطر إلى تغيير نص البرنامج.
إذا كان هناك أمر إدخال في سجل الخوارزمية ، فسيتم مقاطعة تنفيذه ويتم نقل التحكم إلى البرنامج الذي يمكنه تنفيذ إدخال البيانات. بعد إدخال البيانات ، يتم نقل التحكم إلى الأمر التالي للخوارزمية.
إجراء إدخال البيانات في باسكال هو:
قراءة (قائمة الدخول) ؛
READLN (قائمة الدخول).
عند تنفيذ إجرائي READ و READLN ، يدخل البرنامج حالة الانتظار لإدخال البيانات. إذا تم تحديد عدة متغيرات في قائمة الإدخال ، فيمكن إدخالها في سطر واحد ، مفصولة عن بعضها بحرف مسافة ، أو في سطور منفصلة (في عمود) ، مع استكمال إدخال كل قيمة باستخدام مفتاح Enter.
لن ينتهي الإجراء حتى يتم إدخال القيم لجميع المتغيرات في القائمة. يجب أن يتطابق نوع قيم الإدخال مع المتغير المقابل.
تختلف عبارة READLN عن عبارة READ في أنه بعد إدخال المقدار المطلوب من البيانات ، ينتقل المؤشر إلى السطر التالي.
إذا تم إدخال البيانات من لوحة المفاتيح ، فإن قائمة الإدخال هي قائمة بالمتغيرات ، أي سلسلة من أسماء المتغيرات مفصولة بفواصل. إذا كان الإدخال من ملف ، فإن المتغير الأول في قائمة الإدخال هو متغير ملف مرتبط باسم ملف حقيقي.
تُستخدم الإجراءات القياسية لإخراج نتائج العمليات الحسابية لإخراج قيمها إلى شاشة أو طابعة أو ملف. إجراءات الاستدلال في باسكال هي:
اكتب (قائمة الإخراج) ؛
WRITELN (قائمة الإخراج).
قائمة عناصر المخرجات أوسع بكثير مما كانت عليه في إجراءات الإدخال. قد تشمل:
محددات الكميات ، والتي سيتم إخراج قيمها إلى الجهاز أو الملف المقابل ؛
التعبيرات ، التي سيتم حساب قيمتها أولاً ثم إخراجها إلى الجهاز ؛
أصبحت كميات (رقمية ، حرف ، سلسلة).
الفرق بين WRITE و WRITELN هو أن عبارة WRITE تبدأ في الموقع الحالي للمؤشر على شاشة العرض ، ويظل المؤشر على نفس السطر بعد نهاية الإخراج. تطبع جملة WRITELN القيم من الموقع الحالي ، ثم ينتقل المؤشر إلى السطر التالي. يمكنك استخدام عبارة WRITELN بدون قائمة إخراج لتحريك المؤشر إلى سطر جديد.
إذا تم تنفيذ الإخراج على شاشة العرض ، فإن قائمة المخرجات هي قائمة من المتغيرات ، أو سلسلة من أسماء المتغيرات أو الثوابت أو التعبيرات مفصولة بفواصل. إذا تم تنفيذ الإخراج إلى ملف ، فإن المتغير الأول في قائمة الإخراج هو متغير ملف مرتبط باسم ملف حقيقي.
في أمر الإخراج ، بعد عنصر قائمة الإخراج ، مفصولاً بنقطتين ، يمكنك تحديد تنسيق الإخراج ، أي عرض الشاشة التي سيتم وضع القيم عليها. عند عرض بيانات صالحة ، يمكنك أيضًا تحديد عدد الأرقام العشرية في الجزء الكسري المراد عرضه.
مثال: اكتب (أ: 10: 3 ، ب: 8).
عامل لاستدعاء خوارزمية مساعدة. ينفذ باسكال إجراءات روتينية وإجراءات وظيفية. يسمى الروتين الفرعي باسمه بالمعلمات الفعلية. في هذه الحالة ، بدلاً من الوسيطات الفعلية ، يمكن أن تكون هناك قيم محددة ، وأسماء للمتغيرات الفعلية ، والتعبيرات ، وبدلاً من النتائج - فقط أسماء المتغيرات الفعلية. في هذه الحالة ، يجب أن يكون عدد وأنواع وغرض المعلمات الرسمية والفعلية في قوائم المعلمات المقابلة هو نفسه.

العمل المخبري رقم 1

الموضوع: "البرمجة الخوارزميات الخطية... العمل مع المصحح "

موضوعي

1.1 إتقان أبسط هيكل لبرنامج سي.

1.2 اكتساب المهارات في تنظيم المدخلات والمخرجات في لغة سي.

دعم فني

2.1 الكمبيوتر الشخصي

2.2 لوحة المفاتيح.

2.3 العرض.

2.4 جهاز الطباعة.

برمجة

3.1 غرفة العمليات نظام ويندوز

3.2 نظام البرمجة Visual C ++ الإصدار 6.0 أو Borland C ++ الإصدار 3.1 والإصدارات الأحدث.

صياغة المشكلة

جاري الكتابة أبسط برنامجمع معالجة البيانات.

5.1 موضوع العمل والغرض منه.

5.2 بيان المشكلة.

5.3 نص البرنامج.

5.4 نتائج تنفيذ البرنامج.

5.5 مخططات خوارزمية البرامج.

معلومات عامة

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

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

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

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

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

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

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

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

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

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

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

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

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

حدد نوع Win32 Console Application ؛

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

يتكون أي برنامج 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) ؛