أنواع البرمجة الخطية. حل مسائل البرمجة الخطية باستخدام الطريقة الرسومية

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

1. مفهوم البرمجة الرياضية

هو نظام رياضي يطور طرقًا للعثور على القيم المتطرفة دالة الهدفضمن مجموعة قيمها الممكنة، التي تحددها القيود.

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

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

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

اعتمادًا على خصائص الوظيفة الموضوعية ووظيفة القيد، يتم حل جميع المشكلات البرمجة الرياضيةوتنقسم إلى فئتين رئيسيتين:

• مشاكل البرمجة الخطية
• مهام البرمجة غير الخطية.

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

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

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

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

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

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

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

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

الشكل العامالمشكلة لها الشكل: العثور على الشروط

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

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

مشكلة LP في شكل قانوني.

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

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

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

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

قصة

تم ذكر طريقة النقطة الداخلية لأول مرة بواسطة I. I. Dikin في عام 1967.

مهام

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

تحت الظروف

, .

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

,

يمكن اختزال المشكلة الرئيسية إلى مشكلة أساسية عن طريق إدخال متغيرات إضافية.

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

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

أمثلة على المشاكل

الحد الأقصى للمطابقة

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

دعونا نقدم المتغيرات التي تتوافق مع زوج الولد والفتاة وتفي بالقيود:

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

الحد الأقصى للتدفق

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

دعونا نأخذ كمتغيرات كمية السائل المتدفق عبر الضلع. ثم

,

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

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

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

مهمة النقل

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

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

الدالة الهدف لها الشكل: والتي يجب تصغيرها.

لعبة محصلتها صفر

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

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

, , (),

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

خوارزميات الحل

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

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

أنظر أيضا

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

ملحوظات

الأدب

• توماس ه. كورمان وآخرون.الفصل 29. البرمجة الخطية // الخوارزميات: البناء والتحليل = مقدمة في الخوارزميات. - الطبعة الثانية. - م: "وليامز"، 2006. - ص 1296. - ISBN 5-8459-0857-4
• أكوليتش ​​آي إل.الفصل الأول. مسائل البرمجة الخطية، الفصل الثاني. مسائل البرمجة الخطية الخاصة // البرمجة الرياضية في الأمثلة والمسائل. - م: الثانوية العامة 1986. - 319 ص. -ردمك 5-06-002663-9
• كارمانوف ف.ج.البرمجة الرياضية. - الطبعة الثالثة. - م: نوكا، 1986. - 288 ص.
• دانزيج جورج برنارد "ذكريات بداية البرمجة الخطية"

روابط

• - حزمة تحسين مجانية مصممة لحل مشكلات البرمجة الخطية والأعداد الصحيحة والأهداف.
• Vershik A. M. "حول L. V. Kantorovich والبرمجة الخطية"
• Bolshakova I. V.، Kuralenko M. V. “البرمجة الخطية. الدليل التربوي والمنهجي للاختبار."
• بارسوف أ.س. “ما هي البرمجة الخطية”، محاضرات شعبية في الرياضيات، غوستخيزدات، 1959.
• إم إن فياليالمتباينات الخطية والتوافقيات. - ماكنمو، 2003.

مؤسسة ويكيميديا. 2010.

• سالتن، فيليكس
• جلاجو، مارتينا

تعرف على ما هي "البرمجة الخطية" في القواميس الأخرى:

البرمجة الخطية- - البرمجة الخطية مجال من مجالات البرمجة الرياضية مخصص لنظرية وطرق حل المسائل المتطرفة التي تتميز بـ الاعتماد الخطيبين… … دليل المترجم الفني

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

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

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

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

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

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

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

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

لقد حظيت البرمجة الخطية بتطور واسع النطاق نظرًا لأنه ثبت أنه يمكن صياغة عدد من مشكلات التخطيط والتحكم في شكل مشكلات برمجة خطية، والتي توجد طرق فعالة لحلها. وفقا للخبراء، ما يقرب من 80-85٪ من جميع مشاكل التحسين التي تم حلها في الممارسة العملية تتعلق بمشاكل البرمجة الخطية.

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

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

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

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

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

من ن المتغيرات س 1 , س 2 , …, X نمع القيود الوظيفية المفروضة:

(3.2)

والقيود المباشرة (اشتراط عدم سلبية المتغيرات)

, (3.3)

أين أ اي جاي , ب أنا , ج ي- إعطاء قيم ثابتة.

في نظام القيود (3.2)، يمكن أن تظهر العلامات "أقل من أو يساوي" و"يساوي" و"أكبر من أو يساوي" في وقت واحد.

يحتوي ZLP في شكل أكثر إيجازًا على الشكل:

,

مع القيود:

;

.

ناقل` X = (س 1 , س 2 , …, X ن) التي تلبي مكوناتها القيود الوظيفية والمباشرة للمشكلة يخطط(أو حل مقبول) زلب.

يتم تشكيل جميع الحلول الممكنة اِختِصاص مشاكل البرمجة الخطية، أو منطقة الحلول الممكنة (ODR). حل ممكن يوفر الحد الأقصى أو الأدنى من الوظيفة الهدف F(`X) ، تسمى الخطة المثلى للمشكلة ويشار إليها F(`X * )، أين ` X * =(س 1 * , س 2 * , …, X ن * ).

شكل آخر من أشكال تسجيل PPP:

,

أين F(`X * ) هي القيمة القصوى (الدنيا). F(مع, X) ، استحوذت على جميع الحلول المضمنة في المجموعة الحلول الممكنة X .

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

لتجميع نموذج رياضي تحتاج إلى:

1) تحديد المتغيرات.

2) إنشاء وظيفة موضوعية بناءً على هدف المشكلة؛

3) كتابة نظام القيود مع مراعاة المؤشرات الواردة في بيان المشكلة وأنماطها الكمية.

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

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

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

مشكلة البرمجة الخطية(LP)، يتكون من إيجاد الحد الأدنى (أو الحد الأقصى) للدالة الخطية تحت قيود خطية.

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

1. مشكلة إدارة وتخطيط الإنتاج.

2. مشاكل تحديد الوضع الأمثل للمعدات السفن البحرية، في ورش العمل.

3. مشكلة تحديد الخطة الأمثل لنقل البضائع (مشكلة النقل).

4. مشكلة التوزيع الأمثل للموظفين.

5. مشاكل حول الخلطات والنظام الغذائي (تخطيط تكوين المنتج)، وما إلى ذلك.

3. نموذج البرمجة الخطية وتمثيلها في الجداول الإلكترونية MS Excel.

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

الخطوات الأساسية لإنشاء نموذج برمجة خطية في Excel:

1. كتابة واختبار نموذج البرمجة الخطية الرمزية. يتم كتابة النموذج على الورق في شكل رياضي.

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

3. محاولة لتحسين النموذج باستخدام الوظيفة الإضافية SOLUTION SEARCH.

4. استخدام الوظيفة الإضافية البحث عن حل.

باستخدام جداول البيانات، يمكنك محاكاة المواقف الحقيقية وتقييم النتائج. بمعنى آخر، باستخدام جداول البيانات، يمكنك تحليل نتائج العمليات والتنبؤ بالآفاق المستقبلية للمؤسسة. هذه المهام في البيئة يتيح MS Excel حل المشكلة باستخدام الوظيفة الإضافية Search for Solution.

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

خوارزمية عامةالعمل مع الوظيفة الإضافية إيجاد حل.

1. على القائمة خدمةاختر فريقا إيجاد حل.
2. في الميدان يضبط الخلية المستهدفةأدخل عنوان الخلية التي تحتوي على الصيغة لتحسين النموذج.
3. لتعظيم قيمة الخلية المستهدفة عن طريق تغيير قيم الخلايا المؤثرة، اضبط المفتاح على القيمة القصوى . لتقليل قيمة الخلية المستهدفة عن طريق تغيير قيم الخلايا المؤثرة، اضبط المفتاح على الحد الأدنى للقيمة . لكي تكتسب الخلية المستهدفة قيمة رقم محدد، اضبط المفتاح على الموضع معنىوأدخل الرقم المناسب
4. في الميدان تغيير الخلاياأدخل عناوين الخلايا التي تغير قيمها، مع الفصل بينها بفواصل. يجب أن تكون الخلايا التي يتم تعديلها مرتبطة بشكل مباشر أو غير مباشر بالخلية المستهدفة. يُسمح بالتركيب حتى 200 خلايا قابلة للتغيير.
5. في الميدان قيودأدخل جميع القيود المفروضة على البحث عن حل.
6. انقر فوق الزر ينفذ.
7. لحفظ الحل الذي تم العثور عليه، حدد المفتاح في مربع الحوار نتائج البحث عن الحلولإلى موقع حفظ الحل الموجود. لاستئناف إدخال البيانات، اضبط المفتاح على استعادة القيم الأصلية.
8. لمقاطعة البحث عن حل، اضغط على المفتاح جوهر. مايكروسوفت اكسلسيتم إعادة حساب الورقة مع مراعاة قيم الخلايا الموجودة التي تؤثر على النتيجة.

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

5. حل مشكلة البرمجة الخطية باستخدام البرنامج ماجستير اكسل.

مثال.محل حلويات لصنع ثلاثة أنواع من الكراميل أ، ب، ج يستخدم ثلاثة أنواع رئيسية من المواد الخام: السكر ودبس السكر وهريس الفاكهة. معايير استهلاك السكر لإنتاج 1 كجم من الكراميل من كل نوع هي على التوالي المستويات التالية: 0.8 كجم؛ 0.5 كجم؛ 0.6 كجم؛ دبس السكر – 04 كجم؛ 0.4 كجم؛ 0.3 كجم؛ هريس الفاكهة - 0 كجم؛ 0.1 كجم؛ 0.1 كجم يمكن إنتاج الحلويات بأي كميات (المبيعات مضمونة)، ولكن المعروض من المواد الخام محدود: احتياطيات السكر - 80 كجم، دبس السكر - 60 كجم، هريس الفاكهة - 12 كجم. الربح من بيع 1 كيلو كراميل أ هو 10 غريفنا، اكتب في - 11 غريفنا، النوع مع – 12 غريفنا.

الجدول 1

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

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

15.1. الأساليب التحليلية

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

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

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

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

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

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

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

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

كن الوحيد الذي يقوم بمهمة معينة؛

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

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

وبناء على ما سبق يمكننا صياغة مشكلة البرمجة الخطية بشكل عام:

العثور على الحد الأقصى للوظيفة الهدف

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

(2.2)

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

(2.3)

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

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

(2.5)

بشرط

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

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

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

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

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

, ط = 1،…،م،

، ي=1،…،ن.

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

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

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

تحت القيود

, أنا=1,…, ك,

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

, …,

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

مثال.

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

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

لإنتاج

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

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

دالة الهدف

تحت شروط القيود: