برنامج خطي مزدوج

الموسوعة الحرة

البرنامج الثنائي لبرنامج خطي معين هو برنامج خطي آخر مشتق من البرنامج الخطي الأصلي (البرنامج الأولي ) بالطريقة التخطيطية التالية:

  • يصبح كل متغير في برنامج البرمجة الخطية الأولي قيدًا في برنامج البرمجة الخطية الثنائي؛
  • يصبح كل قيد في برنامج البرمجة الخطية الأولي متغيرًا في برنامج البرمجة الخطية الثنائي؛
  • ينعكس اتجاه الهدف - يصبح الحد الأقصى في الأصل الأدنى في الأصل الثنائي والعكس صحيح.

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

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

تنتمي هذه النظريات إلى فئة أوسع من نظريات الازدواجية في مجال التحسين . وتُعدّ نظرية الازدواجية القوية إحدى الحالات التي تكون فيها فجوة الازدواجية (الفجوة بين القيمة المثلى للأصل والقيمة المثلى للثنائي) تساوي صفرًا.

شكل الألبوم المزدوج

لنفترض أن لدينا البرنامج الخطي:

قم بتعظيم c T x بشرط A x ≤ b ، x ≥ 0.

نرغب في بناء حدٍّ أعلى للحل. لذا، نُنشئ توليفة خطية من القيود، بمعاملات موجبة، بحيث تكون معاملات x في القيود على الأقل cT . تُعطينا هذه التوليفة الخطية حدًّا أعلى للدالة الهدف. المتغيرات y في برنامج البرمجة الخطية الثنائي هي معاملات هذه التوليفة الخطية. يحاول برنامج البرمجة الخطية الثنائي إيجاد هذه المعاملات التي تُقلل الحد الأعلى الناتج. وهذا يُعطي برنامج البرمجة الخطية التالي: [ 1 ] : 81-83

تقليل b T y بشرط A T y ≥ c ، y ≥ 0

يُطلق على هذا الألبوم اسم النسخة المزدوجة من الألبوم الأصلي.

تفسير

لنظرية الازدواجية تفسير اقتصادي. [ 2 ] [ 3 ] إذا فسرنا البرمجة الخطية الأولية على أنها مشكلة " تخصيص موارد " كلاسيكية، فيمكن تفسير البرمجة الخطية المزدوجة على أنها مشكلة "تقييم موارد".

لنفترض مصنعًا يخطط لإنتاج سلع1،...،ن{\displaystyle 1,\ldots ,n}والتي تنتجها باستخدام المواد الخام1،...،م{\displaystyle 1,\ldots ,m}إنتاج وحدة واحدة من السلعةأنا{\displaystyle i}يحتاج المصنعأجأنا≥0{\displaystyle A_{ji}\geq 0}وحدات من المواد الخامج{\displaystyle j}. يتركx{\displaystyle x}يكون جدول إنتاج المصنع (الإنتاج)xأنا{\displaystyle x_{i}}وحدات من السلعأنا{\displaystyle i})، يتركج≥0{\displaystyle c\geq 0}لتكن أسعار السوق (وحدة من السلعة)أنا{\displaystyle i}يمكن بيعه مقابلجأنا{\displaystyle c_{i}})، ودعب≥0{\displaystyle b\geq 0}كميات المواد الخام المتوفرة لدى المصنع (لديهبج{\displaystyle b_{j}}وحدات من المواد الخامج{\displaystyle j}تتمثل القيود في أنx≥0{\displaystyle x\geq 0}(لا يمكنها إنتاج سلع سلبية)، وأن المصنع لا يستطيع إنتاج إلا كمية السلع التي تسمح بها كميات المواد الخام المتوفرة لديه، أيأx≤ب{\displaystyle Ax\leq b}يرغب المصنع في تحقيق أقصى قدر من إجمالي إيراداتهج⊤x{\displaystyle c^{\top }x}.

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

تحقيق أقصى استفادةج⊤x{\displaystyle c^{\top }x} رهناً بـأx≤ب،x≥0{\displaystyle Ax\leq b,x\geq 0}

والآن لنفترض مصنعًا آخر يرغب في شراء كامل مخزون المواد الخامب{\displaystyle b}من المصنع السابق. وهو يقدم نطاق سعري لـy{\displaystyle y}(وحدة من المواد الخام)أنا{\displaystyle i}لyأنا{\displaystyle y_{i}}لكي يُقبل العرض، يجب أن يكون الأمر كما يلي:أتيy≥ج{\displaystyle A^{T}y\geq c}وإلا فإن المصنع الأول قد يربح أموالاً أكثر من خلال إنتاج منتج معين بدلاً من بيع المواد الخام المستخدمة في إنتاج السلع. وينبغي أيضاً أن يكونy≥0{\displaystyle y\geq 0}لأن المصنع الأول لن يبيع مواده بسعر سلبي. ويرغب المصنع الثاني في تقليل الكمية إلى أدنى حد ممكن.ب⊤y{\displaystyle b^{\top }y}بحيث يغطي ذلك كامل مخزون المواد الخام للمصنع الأول. ثم، تصبح مسألة التحسين للمصنع الثاني هي مسألة البرمجة الخطية المزدوجة:

التقليل ب⊤y{\displaystyle b^{\top }y}رهناً بـأ⊤y≥ج،y≥0{\displaystyle A^{\top }y\geq c,y\geq 0}

تنص نظرية الازدواجية على أن فجوة الازدواجية بين مسألتي البرمجة الخطية غير سالبة. بعبارة أخرى، يكون الحل الأمثل لهذه المسألة المزدوجة أكبر من أو يساوي الحل الأمثل للمسألة الأصلية، مما يعني أن العرض الأمثلب⊤y{\displaystyle b^{\top }y}لن يقل عائد المصنع الثاني أبدًا عن عائد المصنع الأول الأمثلج⊤x{\displaystyle c^{\top }x}إذا عُرض على المصنع الأول شراء كامل مخزونه من المواد الخام، بسعر الوحدة الواحدة،y{\displaystyle y}بحيثأ⊤y≥ج،y≥0{\displaystyle A^{\top }y\geq c,y\geq 0}إذاً، ينبغي عليها قبول العرض. ستحقق إيرادات لا تقل عن تلك التي كانت ستحققها من إنتاج السلع التامة الصنع.

وتنص نظرية الازدواجية القوية كذلك على أن فجوة الازدواجية تساوي صفرًا. وبوجود الازدواجية القوية، يكون الحل المزدوجy*{\displaystyle y^{*}}من الناحية الاقتصادية، يمثل "سعر التوازن" (انظر السعر الظلي ) للمواد الخام التي ينتجها مصنع ذو مصفوفة إنتاجأ{\displaystyle A}ومخزون المواد الخامب{\displaystyle b}سيقبلون ذلك مقابل المواد الخام، بالنظر إلى سعر السوق للسلع التامة الصنعج{\displaystyle c}. (لاحظ أنy*{\displaystyle y^{*}}قد لا يكون فريدًا، لذا قد لا يتم تحديد سعر التوازن بشكل كامل بواسطةأ{\displaystyle A}،ب{\displaystyle b}، وج{\displaystyle c}.)

لمعرفة السبب، انظر إلى أسعار المواد الخامy≥0{\displaystyle y\geq 0}هي من النوع الذي(أتيy)أنا<جأنا{\displaystyle (A^{T}y)_{i}<c_{i}}بالنسبة للبعضأنا{\displaystyle i}ثم سيشتري المصنع المزيد من المواد الخام لإنتاج المزيد من السلعأنا{\displaystyle i}لأن الأسعار "منخفضة للغاية". وعلى العكس من ذلك، إذا كانت أسعار المواد الخام مُرضيةأتيy≥ج،y≥0{\displaystyle A^{T}y\geq c,y\geq 0}لكنه لا يقلل منبتيy{\displaystyle b^{T}y}إذا كان سعر بيع المواد الخام مرتفعًا جدًا، فإن المصنع سيجني أرباحًا أكبر من إنتاج السلع، لأن الأسعار "مرتفعة جدًا". عند سعر التوازنy*{\displaystyle y^{*}}لا يستطيع المصنع زيادة أرباحه عن طريق شراء أو بيع المواد الخام.

لنظرية الازدواجية تفسير فيزيائي أيضًا. [ 1 ] : 86-87

بناء البرمجة الخطية الثنائية

بشكل عام، عند إعطاء برنامج خطي أولي، يمكن استخدام الخوارزمية التالية لإنشاء برنامجه الخطي الثنائي. [ 1 ] : 85 يُعرَّف البرنامج الخطي الأولي كما يلي:

  • مجموعة من n متغير: x1،...،xن{\displaystyle x_{1},\ldots ,x_{n}}.
  • لكل متغيرxأنا{\displaystyle x_{i}}، قيد الإشارة - يجب أن تكون الإشارة غير سالبة (xأنا≥0{\displaystyle x_{i}\geq 0}أو غير إيجابي (xأنا≤0{\displaystyle x_{i}\leq 0}أو غير مقيد (xأنا∈R{\displaystyle x_{i}\in \mathbb {R} }).
  • دالة الهدف: أقصى   ج1x1+⋯+جنxن{\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}
  • قائمة من m قيدًا. كل قيد j هو: أج1x1+⋯+أجنxن⪋بج{\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}حيث الرمز قبلبج{\displaystyle b_{j}}يمكن أن يكون أحد≥{\displaystyle \geq }أو≤{\displaystyle \leq }أو={\displaystyle =}.

يتم بناء برنامج البرمجة الخطية المزدوج على النحو التالي.

  • يصبح كل قيد أولي متغيرًا ثنائيًا. لذا يوجد m متغيرًا:y1،...،yم{\displaystyle y_{1},\ldots ,y_{m}}.
  • يكون قيد الإشارة لكل متغير ثنائي "معاكساً" لإشارة قيده الأصلي. لذا "≥بج{\displaystyle \geq b_{j}}"يصبح yج≤0{\displaystyle y_{j}\leq 0}و "≤بج{\displaystyle \leq b_{j}}"يصبح yج≥0{\displaystyle y_{j}\geq 0} و "=بج{\displaystyle =b_{j}}"يصبحyج∈R{\displaystyle y_{j}\in \mathbb {R} }.
  • دالة الهدف المزدوجة هي تقليل    ب1y1+⋯+بمyم{\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}
  • يصبح كل متغير أولي قيدًا ثنائيًا. لذا، يوجد n قيدًا. معامل المتغير الثنائي في القيد الثنائي هو معامل متغيره الأولي في قيده الأولي. وبالتالي، يكون كل قيد i كما يلي:أ1أناy1+⋯+أمأناyم⪋جأنا{\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}، حيث الرمز قبلجأنا{\displaystyle c_{i}}يشبه هذا قيد الإشارة على المتغير i في البرمجة الخطية الأولية.xأنا≤0{\displaystyle x_{i}\leq 0}يصبح "≤جأنا{\displaystyle \leq c_{i}}" وxأنا≥0{\displaystyle x_{i}\geq 0}يصبح "≥جأنا{\displaystyle \geq c_{i}}" وxأنا∈R{\displaystyle x_{i}\in \mathbb {R} }يصبح "=جأنا{\displaystyle =c_{i}}".

من هذه الخوارزمية، من السهل أن نرى أن ثنائي الثنائي هو العنصر الأولي.

صياغة المتجهات

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

البدائيمزدوجملحوظة
تعظيم c T x بشرط A x ≤ b ، x ≥ 0تقليل b T y بشرط A T y ≥ c ، y ≥ 0يُطلق على هذا اسم المسألة الثنائية "المتماثلة".
تعظيم c T x بشرط A x ≤ bتقليل b T y بشرط A T y = c ، y ≥ 0يُطلق على هذا اسم مشكلة ثنائية "غير متناظرة".
تعظيم c T x بشرط A x = b ، x ≥ 0تقليل b T y بشرط A T y ≥ c

نظريات الازدواجية

فيما يلي، افترض أن البرمجة الخطية الأولية هي "تعظيم c T x مع مراعاة [القيود]" والبرمجة الخطية الثنائية هي "تقليل b T y مع مراعاة [القيود]".

الازدواجية الضعيفة

تنص نظرية الازدواجية الضعيفة على أنه لكل حل ممكن x للمسألة الأصلية ولكل حل ممكن y للمسألة المزدوجة: c T x ≤ b T y . بعبارة أخرى، قيمة الهدف في كل حل ممكن للمسألة المزدوجة هي حد أعلى لقيمة الهدف في المسألة الأصلية، وقيمة الهدف في كل حل ممكن للمسألة الأصلية هي حد أدنى لقيمة الهدف في المسألة المزدوجة. إليك برهان لمسألة البرمجة الخطية الأصلية "تعظيم c T x بشرط A x ≤ b ، x ≥ 0":

  • ج ت س
  • = x T c [لأن هذا مجرد حاصل ضرب قياسي للمتجهين]
  • ≤ x T ( A T y ) [بما أن A T y ≥ c وفقًا للقيود المزدوجة، و x ≥ 0]
  • = ( x T A T ) y [بحسب خاصية التجميع]
  • = ( Ax ) T y [بحسب خصائص النقل]
  • ≤ b T y [بما أن A x ≤ b وفقًا للقيود الأولية، و y ≥ 0]

الازدواجية الضعيفة تعني:

أقصى x c T x ≤ أدنى y b T y

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

ازدواجية قوية

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

أقصى x c T x = أدنى y b T y

إن إثبات نظرية الازدواجية القوية أصعب؛ وعادة ما تستخدم البراهين نظرية الازدواجية الضعيفة كإجراء فرعي.

تعتمد إحدى البراهين على خوارزمية السمبلكس ، وتستند إلى إثبات أنها، مع قاعدة الارتكاز المناسبة، تُقدّم حلاً صحيحاً. يُثبت هذا البرهان أنه بمجرد انتهاء خوارزمية السمبلكس من إيجاد حل للمسألة الخطية الأولية، يُمكن استخلاص حل للمسألة الخطية الثنائية من الجدول النهائي. وبالتالي، بتطبيق خوارزمية السمبلكس، نحصل على حلول لكل من المسألة الأولية والثنائية في آنٍ واحد. [ 1 ] : 87-89

يستخدم برهان آخر مبرهنة فاركاس . [ 1 ] : 94

الآثار النظرية

1. تنص نظرية الازدواجية الضعيفة على أن إيجاد حل ممكن واحد لا يقل صعوبة عن إيجاد حل ممكن أمثل . لنفترض أن لدينا برنامجًا وسيطًا (أوراكل) يُعطي برنامجًا خطيًا (LP) حلاً ممكنًا عشوائيًا (إن وُجد). بفرض أن البرنامج الخطي هو "تعظيم c T x بشرط A x ≤ b ، x ≥ 0"، يمكننا بناء برنامج خطي آخر بدمج هذا البرنامج مع برنامجه المزدوج. يحتوي البرنامج الخطي المدمج على كل من x و y كمتغيرات.

أقصى 1

مع مراعاة الشروط التالية: A x ≤ b ، A T y ≥ c ، c T x ≥ b T y ، x ≥ 0، y ≥ 0

إذا كان للبرمجة الخطية المدمجة حل ممكن ( x , y )، فبحسب الازدواجية الضعيفة، يكون cTx = bTy . لذا ، يجب أن يكون x حلاً أعظميًا للبرمجة الخطية الأصلية، ويجب أن يكون y حلاً أصغريًا للبرمجة الخطية المزدوجة. أما إذا لم يكن للبرمجة الخطية المدمجة حل ممكن، فلن يكون للبرمجة الخطية الأصلية حل ممكن أيضًا.

2. تُقدّم نظرية الازدواجية القوية "توصيفًا جيدًا" للقيمة المثلى لبرنامج خطي، إذ تُتيح لنا إثبات أن قيمةً ما t هي القيمة المثلى لبرنامج خطي ما بسهولة. ويتم الإثبات على مرحلتين: [ 4 ] : ​​260-261

  • أظهر حلاً ممكناً للبرمجة الخطية الأولية بقيمة t ؛ وهذا يثبت أن الحل الأمثل هو على الأقل t .
  • أظهر حلاً ممكناً للبرمجة الخطية الثنائية بقيمة t ؛ وهذا يثبت أن الحل الأمثل هو على الأكثر t .

أمثلة

مثال صغير

لنفترض برنامج البرمجة الخطية الأولي، بمتغيرين وقيد واحد:

أقصى 3x1+4x2رهناً بـ 5x1+6x2=7x1≥0،x2≥0{\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}

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

تقليل 7y1رهناً بـ 5y1≥36y1≥4y1∈R{\displaystyle {\begin{aligned}{\text{تقليل }}&7y_{1}\\{\text{بشرط }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}

من السهل ملاحظة أن القيمة القصوى للبرمجة الخطية الأولية تتحقق عندما تكون قيمة x1 في أدنى حد لها (0) وقيمة x2 في أعلى حد لها في ظل القيد (7/6). القيمة القصوى هي 4 × 7/6 = 14/3.    

وبالمثل، يتم الوصول إلى الحد الأدنى للبرمجة الخطية الثنائية عندما يتم تقليل y 1 إلى حدها الأدنى في ظل القيود: يعطي القيد الأول حدًا أدنى قدره 3/5 بينما يعطي القيد الثاني حدًا أدنى أكثر صرامة قدره 4/6، لذا فإن الحد الأدنى الفعلي هو 4/6 والحد الأدنى هو 7 ⋅ 4/6 = 14/3.  

وفقًا لنظرية الازدواجية القوية، فإن الحد الأقصى للعدد الأولي يساوي الحد الأدنى للعدد المزدوج.

نستخدم هذا المثال لتوضيح برهان نظرية الازدواجية الضعيفة. لنفترض أننا نريد، في برنامج البرمجة الخطية الأولي، الحصول على حد أعلى للدالة الهدف.3x1+4x2{\displaystyle 3x_{1}+4x_{2}}يمكننا استخدام القيد مضروبًا في معامل ما، على سبيل المثالy1{\displaystyle y_{1}}لأيy1{\displaystyle y_{1}}نحصل على: y1⋅(5x1+6x2)=7y1{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}الآن، إذا y1⋅5x1≥3x1{\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}وy1⋅6x2≥4x2{\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}، ثمy1⋅(5x1+6x2)≥3x1+4x2{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}، لذا7y1≥3x1+4x2{\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}وبالتالي، فإن هدف البرمجة الخطية الثنائية هو حد أعلى لهدف البرمجة الخطية الأولية.

مثال المزارع

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

لنفترض مزارعًا يزرع القمح والشعير مع توفير كمية محددة من الأرض (L) ، والأسمدة (F) ، والمبيدات (P) . لزراعة وحدة واحدة من القمح، يلزم توفير وحدة واحدة من الأرض،F1{\displaystyle F_{1}}وحدات من الأسمدة وP1{\displaystyle P_{1}}يجب استخدام وحدات من المبيدات. وبالمثل، لزراعة وحدة واحدة من الشعير، وحدة واحدة من الأرض،F2{\displaystyle F_{2}}وحدات من الأسمدة وP2{\displaystyle P_{2}}يجب استخدام وحدات من المبيدات الحشرية.

تكمن المشكلة الأساسية في تحديد المزارع كمية القمح (x1{\displaystyle x_{1}}) والشعير (x2{\displaystyle x_{2}}) لتنمو إذا كانت أسعار بيعهاS1{\displaystyle S_{1}}وS2{\displaystyle S_{2}}لكل وحدة.

تحقيق أقصى استفادة:S1⋅x1+S2⋅x2{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}(تحقيق أقصى قدر من الإيرادات من إنتاج القمح والشعير)
رهناً بما يلي:x1+x2≤ل{\displaystyle x_{1}+x_{2}\leq L}(لا يمكن استخدام مساحة من الأرض أكبر من المتاحة)
F1⋅x1+F2⋅x2≤F{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}(لا يمكن استخدام سماد أكثر من المتاح)
P1⋅x1+P2⋅x2≤P{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}(لا يمكن استخدام كمية من المبيدات الحشرية تفوق الكمية المتاحة)
x1،x2≥0{\displaystyle x_{1},x_{2}\geq 0}(لا يمكن إنتاج كميات سالبة من القمح أو الشعير).

يصبح هذا في شكل مصفوفة:

تحقيق أقصى استفادة:[S1S2][x1x2]{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}
رهناً بما يلي:[11F1F2P1P2][x1x2]≤[لFP]،[x1x2]≥0.{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}

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

التقليل:ل⋅yل+F⋅yF+P⋅yP{\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}(تقليل التكلفة الإجمالية لوسائل الإنتاج كـ "دالة الهدف")
رهناً بما يلي:yل+F1⋅yF+P1⋅yP≥S1{\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}}(يجب ألا يقل سعر القمح الذي يحصل عليه المزارع عن دولار واحد )
yل+F2⋅yF+P2⋅yP≥S2{\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}(يجب ألا يقل سعر الشعير الذي يحصل عليه المزارع عن دولارين )
yل،yF،yP≥0{\displaystyle y_{L},y_{F},y_{P}\geq 0}(لا يمكن أن تكون الأسعار سالبة).

يصبح هذا في شكل مصفوفة:

التقليل:[لFP][yلyFyP]{\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}
رهناً بما يلي:[1F1P11F2P2][yلyFyP]≥[S1S2]،[yلyFyP]≥0.{\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}

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

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

تُستخدم المعاملات التي تحدد المتباينات في الفضاء الأولي لحساب دالة الهدف في الفضاء الثنائي، وهي كميات المدخلات في هذا المثال. كما تُستخدم المعاملات المستخدمة لحساب دالة الهدف في الفضاء الأولي لتحديد المتباينات في الفضاء الثنائي، وهي أسعار وحدات المخرجات في هذا المثال.

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

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

برنامج غير قابل للتنفيذ

يمكن أن يكون برنامج البرمجة الخطية غير محدود أو غير قابل للتنفيذ. تخبرنا نظرية الازدواجية بما يلي:

  • إذا كان العدد الأولي غير محدود، فإن العدد الثنائي غير ممكن؛
  • إذا كان الثنائي غير محدود، فإن الأول غير قابل للتحقيق.

مع ذلك، من الممكن أن يكون كل من الثنائي والأصلي غير قابلين للتطبيق. إليك مثال على ذلك:

تحقيق أقصى استفادة:2x1-x2{\displaystyle 2x_{1}-x_{2}}
رهناً بـ:x1-x2≤1{\displaystyle x_{1}-x_{2}\leq 1}
-x1+x2≤-2{\displaystyle -x_{1}+x_{2}\leq -2}
x1،x2≥0.{\displaystyle x_{1},x_{2}\geq 0.}

النظر إلى حل مسألة البرمجة الخطية على أنه متجه ذاتي (معمم)

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

المعادلات الذاتية للمصفوفة المربعة هي كما يلي:

صتيأ=ρصتيأz=ρz{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}

أينصتي{\displaystyle \mathbf {p} ^{T}}وz{\displaystyle \mathbf {z} }يمثلان المتجهين الذاتيين الأيسر والأيمن للمصفوفة المربعةأ{\displaystyle \mathbf {A} }، على التوالي، وρ{\displaystyle \rho }هي القيمة الذاتية.

يمكن توسيع المعادلات الذاتية المذكورة أعلاه للمصفوفة المربعة لتشمل نموذج التوازن العام لفون نيومان: [ 5 ] [ 6 ]

صتيأ≥ρصتيبأz≤ρبz{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}}

حيث المعاني الاقتصادية لـص{\displaystyle \mathbf {p} }وz{\displaystyle \mathbf {z} }تمثل أسعار التوازن لمختلف السلع ومستويات النشاط التوازني لمختلف الفاعلين الاقتصاديين، على التوالي.

يمكن توسيع نموذج توازن فون نيومان ليشمل نموذج التوازن الهيكلي التالي معأ{\displaystyle \mathbf {A} }وب{\displaystyle \mathbf {B} }كدوال ذات قيم مصفوفية: [ 7 ]

صتيأ(ص،u،z)≥ρصتيب(ص،u،z)أ(ص،u،z)z≤ρب(ص،u،z)z{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}}

حيث المعنى الاقتصادي لـu{\displaystyle \mathbf {u} }تمثل مستويات المنفعة لمختلف المستهلكين. وتُعد حالة خاصة من النموذج المذكور أعلاه هي

صتيأ(u)≥صتيبأ(u)z≤بz{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}}

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

إذا عرّفنا أ(u)=[0uأ0]{\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}}، ب=[جتي00ب]{\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}}، ص=[1y]{\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}}، z=[x1]{\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}إذاً، يمكن كتابة نموذج التوازن الهيكلي على النحو التالي:

[yتيأu]≥[جتيyتيب]{\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}

[uأx]≤[جتيxب]{\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}

دعونا نوضح نموذج التوازن الهيكلي بالمثال الصغير الذي ناقشناه سابقًا. في هذا المثال، لدينا أ=[56]{\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}}، أ(u)=[00u560]{\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}}و ب=[340007]{\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}.

لحل نموذج التوازن الهيكلي، نحصل على [ 8 ]

ص*=(1،2/3)تي،z*=(0،7/6،1)تي،u*=14/3{\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}

هذه النتائج تتوافق مع حلول مسائل البرمجة الخطية.

نستبدل نتائج الحسابات المذكورة أعلاه في نموذج التوازن الهيكلي، فنحصل على صتيأ(u)=(10/3،4،14/3)≥(3،4،14/3)=صتيبأ(u)z=(14/3،7)تي≤(14/3،7)تي=بz{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}}

التطبيقات

تُعدّ نظرية التدفق الأقصى والقطع الأدنى حالة خاصة من نظرية الازدواجية القوية: حيث يُمثّل تعظيم التدفق البرنامج الخطي الأولي، بينما يُمثّل تقليل القطع البرنامج الخطي الثنائي. انظر نظرية التدفق الأقصى والقطع الأدنى#صياغة البرنامج الخطي .

يمكن إثبات نظريات أخرى متعلقة بالرسوم البيانية باستخدام نظرية الازدواجية القوية، وخاصة نظرية كونيغ . [ 9 ]

يمكن إثبات نظرية المينيماكس لألعاب المجموع الصفري باستخدام نظرية الازدواجية القوية. [ 1 ] : الفقرة الفرعية 8.1

خوارزمية بديلة

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

التقليل∑أنا=1مجأناxأنا+∑ج=1ندجتج{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}
رهناً بـ∑أنا=1مأأناجxأنا+هـجتج≥زج،{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},}1≤ج≤ن{\displaystyle 1\leq j\leq n}
وأناxأنا+∑ج=1نبأناجتج≥حأنا،{\displaystyle f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},}1≤أنا≤م{\displaystyle 1\leq i\leq m}
xأنا≥0،تج≥0،{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}1≤أنا≤م،1≤ج≤ن{\displaystyle 1\leq i\leq m,1\leq j\leq n}

لدينا m  + n شرطًا، وجميع المتغيرات غير سالبة. سنُعرّف m + n متغيرًا ثنائيًا: y j و s i . فنحصل على:   

التقليل∑أنا=1مجأناxأنا+∑ج=1ندجتج{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}
رهناً بـ∑أنا=1مأأناجxأنا⋅yج+هـجتج⋅yج≥زج⋅yج،{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},}1≤ج≤ن{\displaystyle 1\leq j\leq n}
وأناxأنا⋅sأنا+∑ج=1نبأناجتج⋅sأنا≥حأنا⋅sأنا،{\displaystyle f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},}1≤أنا≤م{\displaystyle 1\leq i\leq m}
xأنا≥0،تج≥0،{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}1≤أنا≤م،1≤ج≤ن{\displaystyle 1\leq i\leq m,1\leq j\leq n}
yج≥0،sأنا≥0،{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}1≤ج≤ن،1≤أنا≤م{\displaystyle 1\leq j\leq n,1\leq i\leq m}

بما أن هذه مسألة تصغير، فإننا نرغب في الحصول على برنامج ثنائي يمثل حدًا أدنى للبرنامج الأصلي. بعبارة أخرى، نريد أن يكون مجموع جميع الحدود اليمنى للقيود هو القيمة القصوى بشرط ألا يتجاوز مجموع معاملات كل متغير أصلي معامله في الدالة الخطية. على سبيل المثال، يظهر x1 في n + 1 قيدًا. إذا جمعنا معاملات قيوده، نحصل على: a1,1 y1 + a1,2 y2 + ... + a1 , ;; n;; yn + f1 s1 . يجب ألا يتجاوز هذا المجموع c1 . ونتيجة لذلك، نحصل على :          

تحقيق أقصى استفادة∑ج=1نزجyج+∑أنا=1محأناsأنا{\displaystyle \sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}}
رهناً بـ∑ج=1نأأناجyج+وأناsأنا≤جأنا،{\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},}1≤أنا≤م{\displaystyle 1\leq i\leq m}
هـجyج+∑أنا=1مبأناجsأنا≤دج،{\displaystyle e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},}1≤ج≤ن{\displaystyle 1\leq j\leq n}
yج≥0،sأنا≥0،{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}1≤ج≤ن،1≤أنا≤م{\displaystyle 1\leq j\leq n,1\leq i\leq m}

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

انظر أيضاً

مراجع

  1. 1 2 3 4 5 6 7 جارتنر، بيرند؛ ماتوسيك، جيري (2006). فهم واستخدام البرمجة الخطية . برلين: سبرينغر. رقم ISBN 3-540-30697-8.الصفحات 81-104.
  2. ↑ ساكاروفيتش، ميشيل (1983)، مكملات حول الازدواجية: التفسير الاقتصادي للمتغيرات المزدوجة ، نصوص سبرينغر في الهندسة الكهربائية، نيويورك، نيويورك: سبرينغر نيويورك، ص 142-155 ، doi : 10.1007/978-1-4757-4106-3_9 ، ISBN  978-0-387-90829-8تم الاطلاع عليه بتاريخ 23 ديسمبر 2022
  3. ↑ دورفمان، روبرت (1987). البرمجة الخطية والتحليل الاقتصادي . بول أ. سامويلسون، روبرت م. سولو. نيويورك: منشورات دوفر. ISBN 0-486-65491-5. OCLC 16577541 . 
  4. ^ لوفاسز، لازلو ؛ بلامر ، دكتوراه في الطب (1986)، نظرية المطابقة ، حوليات الرياضيات المنفصلة، ​​المجلد. 29، شمال هولندا، ISBN  0-444-87916-1، MR 0859549 
  5. ↑ فون نيومان، ج. (1945). "نموذج للتوازن الاقتصادي العام". مراجعة الدراسات الاقتصادية . 13 : 1-9 .:
  6. ↑ كيميني، جي جي ؛ مورغنسترن، أو ؛ طومسون، جي إل (1956). "تعميم نموذج فون نيومان للاقتصاد المتوسع". إيكونومتريكا . 24 : 115-135 .
  7. ↑ لي، وو (2019). التوازن العام والديناميات الهيكلية: منظورات الاقتصاد الهيكلي الجديد (باللغة الصينية). بكين: دار النشر للعلوم الاقتصادية. ص 122-125 . ISBN  978-7-5218-0422-5.
  8. ↑ "نموذج التوازن العام والبرنامج الخطي المزدوج" . مشروع CRAN - R. تم الاطلاع عليه بتاريخ 26-06-2023 . وثائق مفصلة حول نموذج التوازن العام والبرنامج الخطي المزدوج في لغة R.
  9. ↑ أ. أ. أحمدي (2016). "المحاضرة 6: البرمجة الخطية والمطابقة" (ملف PDF) . جامعة برينستون .