2. إدخال المتغيرات الأساسية الطبيعية. بناء جدول بسيط. تعريف الخطة الصفرية.

طريقة سيمبلكس. خوارزمية الطريقة البسيطة.

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

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

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

خوارزمية طريقة Simplex

1. نأتي بنظام القيود الشكل الكنسي(عندما يكون النظام محدودا). علاوة على ذلك، يمكن تحديد أساس واحد في النظام.

2. ابحث عن الأصل الخطة المرجعية(الحلول الأساسية غير السلبية لنظام المعادلات KZLP). يتم تحديد كل من الخطط المرجعية بواسطة نظام من المتجهات المستقلة خطيًا m الموجودة في نظام معين من المتجهات n أ 1 , أ 2 ,…, ن. يتم تحديد الحد الأعلى لعدد الخطط المرجعية الموجودة في مشكلة معينة من خلال عدد المجموعات مع نانومتر);

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

4. ب جدول بسيطنحن نتحقق من ناقلات السلبية، أي. التقديرات زيج - سيجالمكتوبة في السطر يجب أن تكون ≥ 0 (كحد أدنى)، Zj – Сj ≥ 0(إلى الحد الأقصى). إذا كانت التقديرات تستوفي شروط المثالية، فسيتم حل المشكلة.

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

الحد الأقصى [θ 0 ي (Zj – Сj)] ; دقيقة [θ 0 ي (Zj – Сj)] ; θ 0 ي = دقيقة، أين × ط> 0

عنصر ناقل θ يالذي يتوافق θ 0 ييسمى مباحًا؛ يُطلق على الصف والعمود الذي يقع فيه اسم الدليل؛ ويترك المتجه الموجود في صف الدليل الأساس.

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

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

2. إدخال المتغيرات الأساسية الطبيعية. بناء جدول بسيط. تعريف الخطة الصفرية.

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

الشركة تبيع نمجموعات المنتجات، وجود ممحدودية الموارد المادية والمالية بأنا ≥0 (1 ≥ أنا≥ م) . تكاليف الموارد للجميع معروفة أنا- نوع إنتاج وبيع وحدة سلع كل مجموعة، معروضة على شكل مصفوفة ( أط) والربح الذي تحصل عليه المؤسسة من بيع وحدة من السلع ي-المجموعة المدرجة في وظيفة الهدف ز(X). ولا تختلف طريقة البرمجة الخطية عن النظام (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

أ 11 × 1 + أ 12 × 2 +… أ 1ن × ن ≥ ب 1،

أ 21 × 1 + أ 22 × 2 +… أ 2 ن × ن ≥ ب 2 (2)

أ م1 × 1 + أ م2 × 2 +…أ من × ن ≥ ب م،

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

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

1) وضع خطة مرجعية صفرية. نقدم متغيرات جديدة (أساسية) غير سلبية، وبفضلها يصبح نظام المتباينات (2) نظام معادلات:

أ 11 × 1 + أ 12 × 2 +… أ 1ن X ن + X ن+1 = ب 1

أ 21 × 1 + أ 22 × 2 +… أ 2ن X ن + X ن+2 = ب 2 (3)

……………………………………..

أ m1 X 1 + أ m2 X 2 +…أ مليون X ن + X ن+م = ب م،

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

X n+1 = ب 1، -أ 11 × 1 - أ 12 × 2 -…أ 1ن × ن

X n+2 = ب 2 - أ 21 × 1 - أ 22 × 2 -…أ 2ن × ن (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

نعيد كتابة الدالة الهدف في النموذج

ز(X) = 0-(-س 1 Х 1 -س 2 Х 2 -س 3 Х 3 -…-س ن Х ن) (5)

بافتراض أن المتغيرات الأساسية المطلوبة X 1 = X 2 = X 3 = ... = X n = 0، نحصل على خطة مرجعية صفرية X = (0, 0, ...0, b 1, b 2, b 3 ... b m)، حيث Z(X) = 0 (جميع الموارد في المخزون، ولا يتم إنتاج أي شيء). ندخل الخطة في جدول بسيط.

يخطط	أساس	ج ط / ج ي	معنى العاشر ط	× 1	× 2	× ن	Xn+1	Xn+2	× ن + 3	س دقيقة
	Xn+1		ب 1	11	12	13				ب1/أ12
Xn+2		ب 2	21	22	23				ب2/أ22
Xn+3		ب 3	31	32	33				ب3/أ32
ض(س) = 0	-ج 1	- ج2	- ج3				فِهرِس. خط

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

3) يتم الانتقال إلى خطة جديدة نتيجة لإعادة حساب الجدول البسيط باستخدام طريقة Jordan-Gauss. أولاً، نستبدل X j في الأساس بـ X i في العمود الرئيسي. دعونا نقسم جميع عناصر الخط الرئيسي على العنصر الحاسم (RE)، ونتيجة لذلك فإن مكان RE في الخط الرئيسي سيكون 1. وبما أن X i أصبحت أساسية، فإن معاملاتها المتبقية يجب أن تساوي 0 تم العثور على عناصر جديدة في هذه الخطة وفقا لقاعدة المستطيل

NE=SE – (أ*ب)/إعادة (6)

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

مثال.تم تخصيص 20 ألف روبل لشراء المعدات لموقع الإنتاج. يمكن وضع المعدات على مساحة لا تزيد عن 72 مترًا مربعًا. يمكنك طلب المعدات من نوعين: النوع أ الذي يتطلب مساحة إنتاج 6 متر مربع وتوفير 6 آلاف وحدة. المنتجات لكل وردية (السعر 5000 روبل) والنوع ب، تتطلب مساحة 12 مترًا مربعًا وتنتج 3 آلاف وحدة (السعر 2000 روبل). ما هي خطة اقتناء المعدات الأمثل لضمان الاداء العاليحبكة؟

دعونا نشير إلى كمية المعدات المشتراة من النوع A وB بـ X 1 وX 2، على التوالي.

إنتاجية الموقع ( دالة الهدف): Z(X) =6Х 1 +3Х 2.

ترتبط القيود الرئيسية

نقداً: 5Х 1 +2Х 2 ≥ 20،

مع مساحة موقع الإنتاج: 6Х 1 +12Х 2 ≥ 72.

نقدم متغيرات أساسية جديدة X 3 (الباقي مالبعد شراء المعدات) وX 4 (المساحة المتبقية بعد وضع المعدات) وإعادة كتابة القيود في شكل نظام من المعادلات:

5X 1 +2X 2 + X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 + X 4 = 72 (X 4 = 72 – 6X 1 – 12X 2)

في هذه الحالة، دالة الهدف: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

نقوم بعمل الخطة المرجعية (0): X = (0، 0، 20، 72)، أي. لم يتم شراء أي شيء بعد (لم يتم إنفاق أي أموال، والمكان فارغ). صنع جدول بسيط

يخطط	أساس	ج ط / ج ي	معنى العاشر ط	× 1	× 2	× 3	× 4	س دقيقة
	× 3							20/5=4
× 4							72/6=12
ض(س) = 0	- 6	- 3			خط الفهرس
	→× 1				0,4	0,2		4/0,4=10
× 4				9,6	-1,2		48/9,6=5
ض(س) = 6*4=24		-0,6	1,2		خط الفهرس
	× 1					0,25	-1/24	-
→ × 2					-1/8	5/48	-
ض(س) =6*2+3*5=27			9/8	1/16	خط الفهرس

من الواضح أن العمود السابق يتوافق مع X 1، نظرًا لأنه يحتوي على أكبر مؤشر 6. نجد الحد الأدنى لقيمة Q min = 4 (أشد قيود الموارد) من خلال تحديد صف بادئ يوضح أن X 3 مشتق من المتغيرات الأساسية ، ويتم إدخال X بدلاً من ذلك 1 . نعيد حساب عناصر السطر السابق ونقسمها على 5 وباستخدام الصيغة (6) نحدد عناصر الخط الثاني والسطر الفهرس. دالة الهدف للخطة الأولى هي Z(X) = 6*4+3*0 = 24.

ومع ذلك، يظل أحد معاملات صف الفهرس للعمود X 2 سالبًا -0.6، وبالتالي فإن هذه الخطة ليست مثالية، ويلزم تكرار (خطوة) أخرى لتحسينها. حدد العمود الثاني كقائد و الحد الأدنى للقيمة Q min = 5 نحدد الخط الرئيسي بالمتغير الأساسي X 4. بعد إجراء نفس التحولات، نحصل على الخطة الثانية، والتي ستكون الأمثل، لأن جميع معاملات المؤشر إيجابية.

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

دعونا نتأكد من ذلك: 5*2+2*5 = 20 ألف روبل، 6*2+12*5=72 متر مربع. الحل المطلوب هو X = (2; 5;0;0). وهذا لا يحدث دائما.

محاضرة رقم 10

موضوع: طريقة سيمبلكسللمشاكل ذات أساس مصطنع

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

أ i1 X 1 + أ i2 X 2 +…أ في X n ≥ ب i (1)

أو المعادلات:

أ i1 X 1 + أ i2 X 2 +…أ في X n = ب i (1*)،

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

أ i1 X 1 + أ i2 X 2 +…أ في X n +Y i = b i (2)

سيتم كتابة الوظيفة الموضوعية عند حل المشكلة إلى الحد الأقصى بالشكل:

Z(X) =∑C j X j +(-M)∑Y i (3)،

عند حل مشكلة مماثلة على الأقل:

Z(X)=∑C j X j +(M)∑Y i (3*)،

حيث M كبير جدًا رقم موجب، عدد إيجابي، نوع من العقوبة لاستخدام المتغيرات الاصطناعية.

في حالة المتباينات (1)، نقدم في البداية متغيرات إضافية X n + i بعلامة الطرح. لن تكون مصفوفتها موحدة، لذلك، في كل عدم مساواة في النظام (1) نقدم متغيرات مصطنعة У i:

أ i1 X 1 +أ i2 X 2 +…أ في X n –X n+i +Y i =b i (4)

الدالة الهدف في هذه الحالة هي Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (للإيجاد الحد الأقصى). طلب أساس مصطنعيمنح الأسلوب البسيط مرونة أكبر ويسمح باستخدامه لمجموعة واسعة من المهام.

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

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

1 × 1 + 1 × 2 ≥ 6،

2×1 + 1×2 =8.

لندخل المتغير الأساسي X 3 للمتباينة الأولى، والمتغير الاصطناعي Y 1 للمعادلة الثانية:

1X 1 + 1X 2 + X 3 = 6،

2X 1 + 1X 2 + ص 1 = 8.

دعونا نعبر عن X 3 وY 1 من نظام المعادلات الناتج، ولتحديد الحد الأقصى، تخيل الدالة الموضوعية:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

بالنسبة للخطة المرجعية - X=(0,0,6,8). لنقم ببناء جدول بسيط:

يخطط	أساس	ج ط / ج ي	معنى العاشر ط	× 1	× 2	× 3	ص 1	س دقيقة
	× 3							6/1=6
ص 1	-م						8/2=4
Z(X) = -8M	-2 م-3	-م-2			خط الفهرس
	× 3				0,5		-0,5	2/0,5=4
→× 1				0,5		0,5	4/0,5=8
ض(س) = 3*4=12		- 0,5		م+1.5	خط الفهرس
	→ × 2						-1	-
× 1					-1		-
ض(س) =3*2+2*4=14				م+1	خط الفهرس

كقاعدة عامة، يبدأ تحسين الخطة المرجعية بإزالة المتغير الاصطناعي Y 1 من الأساس. تم الحصول على الخطة المثالية X = (2,4,0,0) في التكرار الثاني، بحد أقصى للدخل 14. ألف. فرك. ، ومعاملات صف الفهرس غير سالبة. من السهل التحقق من أنه في هذه المهمة، باستخدام الخطة المثالية، يتم استخدام الموارد بالكامل (2*1+4*1=6; 2*2+1*4=8).

عند إيجاد الحد الأدنى من الربحية، نقوم بصياغة الدالة الهدف بشكل مختلف (يتم إدخال +MY 1 كمصطلح:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X1 + 2X2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

الخطة المرجعية هي نفسها، لكن معاملات صف الفهرس في الجدول البسيط مختلفة. يتم تحديد العمود البادئ، كما كان من قبل، بواسطة أكبر معامل موجب في القيمة المطلقة لـ X 1، ويتم تحديد الصف البادئ بالقيمة الدنيا لـ Q min = 4. في التكرار الأول، يتم اشتقاق المتغير الاصطناعي Y 1 من أساس.

يخطط	أساس	ج ط / ج ي	معنى العاشر ط	× 1	× 2	× 3	ص 1	س دقيقة
	× 3							6/1=6
ص 1	م						8/2=4
Z(X) = 8M	2 م-3	م-2			خط الفهرس
	× 3				0,5		-0,5	2/0,5=4
→× 1				0,5		0,5	4/0,5=8
ض(س) = 3*4=12		- 0,5		-م+1.5	خط الفهرس

تشير القيم السلبية الناتجة للمعاملات في خط الفهرس X i إلى أفضلية الخطة الأولى، في حين أن الحد الأدنى للدخل هو 12 ألف روبل.

يتم توفيره فقط من خلال إنتاج المنتج A (لا يتم إنتاج المنتج B)، ولا يتم استخدام المواد الخام بالكامل (الباقي X 3 = 2t)، في حين يتم استيفاء الشرط الرئيسي - توظيف العمال بشكل كامل في الإنتاج.

محاضرة رقم 11

الموضوع: مشكلة النقل المغلق

1. الصياغة الرياضية المغلقة مشكلة النقل. تحديد العدد المطلوب من المجهولين.

2. مراحل تحديد خطة حل مشكلة النقل.

محاضرة 3.الجداول البسيطة. خوارزمية الطريقة البسيطة.

§ 3 طريقة بسيطة

3.1. الفكرة العامة للطريقة البسيطة. التفسير الهندسي

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

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

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

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

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

تم اقتراح الطريقة البسيطة لأول مرة من قبل العالم الأمريكي ج. دانزيج في عام 1949، ولكن في عام 1939 تم تطوير أفكار الطريقة من قبل العالم الروسي إل. كانتوروفيتش.

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

لتنفيذ الطريقة البسيطة - التحسين المتسلسل للحل - من الضروري إتقانها ثلاثة عناصر رئيسية:

طريقة لتحديد أي حل أساسي مبدئي ممكن لمشكلة ما؛

قاعدة الانتقال إلى الحل الأفضل (بتعبير أدق، وليس الأسوأ)؛

معيار للتحقق من الأمثلية الحل الموجود.

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

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

3.2. خوارزمية الطريقة البسيطة.

دعونا نفكر في حل ZLP باستخدام الطريقة البسيطة ونقدمه فيما يتعلق بمشكلة التعظيم.

1. بناء على شروط المشكلة يتم تجميع نموذجها الرياضي.

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

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

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

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

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

5. يتم فحص خطة الدعم الأولية التي تم العثور عليها للتأكد من أنها مثالية:

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

ب) إذا ج
– يوجد عنصر سلبي واحد على الأقل في الصف، وهو ما يتوافق مع عمود من العناصر غير الإيجابية
;

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

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

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

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

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

2) تكوين علاقات عناصر عمود المصطلحات الحرة بالعناصر المقابلة لعمود الحل التي لها نفس العلامات (العلاقات البسيطة)؛

3) اختر أصغر العلاقات البسيطة. سيحدد هذا سلسلة التمكين. فليكن مثلا ر-خط؛

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

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

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

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

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

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

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

تعمل الطريقة البسيطة على حل مشكلة LP بالشكل القياسي.

تصغير (تكبير) الوظيفة في ظل الظروف x > 0؛ الفأس = ب.

المصفوفة A حقيقية ولها البعد ت×" والرتبة ت.

يمكن أيضًا كتابة مشكلة LP المصاغة في النموذج

وبناء على تسجيل مسألة LP بالشكل (8Л)، يمكننا القول بأن المصفوفة الموسعة

أبعاد (ر + 1) (ن + 2) يتوافق مع الحلول[x/] t.

لنمثل المصفوفة A كمجموعة من الأعمدة

بما أن المصفوفة A لها رتبة تي،ثم سيكون هناك تالأعمدة المستقلة خطيًا للمصفوفة A، على سبيل المثال (a U1،...,a U/u فكر في المتجه x° > 0، بحيث تكون جميع عناصره ص - رالعناصر هي 0 و Ax° = b. لتكن هذه عناصر ذات أرقام..., أنا ن _ م .لنفترض أيضًا أن موقع الأعمدة المستقلة خطيًا للمصفوفة A يتوافق مع موقع العناصر غير الصفرية في المتجهات 0. هندسيًا، وفقًا للبيان 3 من الفقرة 6.7، هذا يعني أن x° هي قمة (زاوية) ODR، بالإضافة إلى أنها تلبي شروط معينة. ويسمى هذا الحل حل أساسي مقبولزوايا المجموعة المسموح بها هي الحلول الأساسية المقبولة

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

وبالتالي، يمكن كتابة أي متجه x مشابه لـ x° بالشكل

أين × في- متجه تتوافق عناصره مع أعمدة المصفوفة A المستقلة خطيًا؛ xF -ناقلات مع صفر العناصر.

دعونا نحدد المتجهات بالمثل

المتغيرات التي هي عناصر المتجهات س في,وتسمى المتغيرات الأساسية, والمتغيرات التي هي عناصر المتجه س فوتسمى حر (المتغيرات غير الأساسية).

لأن س° ف=0، فإن قيمة الدالة الهدف للمتجه الأولي x° ستكون مساوية لـ

حيث /° هي قيمة / عند النقطة x°.

يسمى الحل (8.1) من الصيغة [x°/°]t لـ x > 0 حل واضح (صريح).وبالتالي، إذا جعلنا المتغيرات غير الأساسية مساوية للصفر، فسنحصل على حل واضح.

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

هنا تتوافق المصفوفة B تأعمدة مستقلة خطيا له البعد رسالة قصيرةوالرتبة تي،والمصفوفة F

يكون تكساس (ع - ر)مصفوفة. نظرًا لأن المصفوفة B تتكون من أعمدة مستقلة خطيًا، فإنها تحتوي على معكوس B -1 وdetB φ 0. لاحظ أنه لتكوين المصفوفة B يمكنك اختيار أي منها تالأعمدة المستقلة خطيًا للمصفوفة A.

دعونا نمثل المشكلة (8.1) مع الأخذ في الاعتبار الترميز المقدم

هذا التمثيل يتوافق مع المصفوفة الموسعة

من أين يتبع

إذا كان المتجه x الخامسسيكون حلا للنظام Bx d = b، فيكون الحل الأساسي. إذا استمر عدم المساواة الخامس= ب -1 ب > يا إذن × فيسيكون حلا مقبولا.

وبالتالي فإن الحل الحالي يحقق المعادلة التالية:

لنفكر في المصفوفة (8.4). سيتم عرض المتغيرات الأساسية بشكل صريح إذا استبدلنا المصفوفة B بمصفوفة الهوية I. بضرب الصف الأول من المصفوفة (8.4) على اليسار بـ B~ 1، نحصل على

حيث B_1 ب > O، أي تالعناصر العلوية في العمود الأيمن غير سالبة وتمثل القيمة الحالية للمتغيرات.

على الجانب الأيسر السطر العلويوالنتيجة هي مصفوفة الوحدة: B -1 B = I. هذا العرضمريحة للغاية، منذ الضرب بالمتجه × فيسيكون كل متغير على سطر منفصل.

هكذا، الحل الأساسي، والتي سنعتبرها مقبولة ومتوافقة مع الأساس B، هي x m = [x in 0]، حيث س في == ب_1 ب. الحل الأساسي ينتج عن افتراض ذلك س ف = 0. ومع ذلك، إذا xF* 0، فيمكن حساب x^ كـ x 5 = = B~"b - B^"Fx/r. باستبدال هذا التعبير في الدالة الهدف (دالة التكلفة)، نحصل على

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

أين هي قيمة الوظيفة الموضوعية للقرن الأولي

الحيد × 0 من (8.3).

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

باستخدام جدول بسيط، من السهل رؤية حل صالح. المتغيرات س F تتوافق مع المصفوفة الفرعية الصفرية والمتغيرات × في- مصفوفة الوحدة:

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

ثم - حل المشكلة (8.1). لذا

مثل b > أوه، هذا حل أساسي مقبول.

دعونا نقدم المصفوفة (8.9) في شكل أكثر ملاءمة، مع الحفاظ على الترميز الأساسي:

دعونا نفكر بشكل منفصل في مشاكل التعظيم والتقليل.

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

مع نالمتغيرات و مقيود المساواة، والمعروفة باسم الطريقة البسيطة.

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

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

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

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

اتضح أن مثل هذا الاستبدال هندسيًا يؤدي إلى الانتقال من نقطة زاوية إلى نقطة مجاورة (مجاورة) مرتبطة بها النقطة السابقةالحافة المشتركة.

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

يتكون المخطط العام للطريقة البسيطة من الخطوات الرئيسية التالية.

· الخطوة 0. تحديد الأساس الأولي ونقطة الزاوية الأولية المقابلة (خط الأساس).

· الخطوة 1. التحقق من خط الأساس الحالي لتحقيق الأمثل . إذا تم استيفاء معيار المثالية، الذي - التي الخطة مثالية والحل كامل. خلاف ذلكانتقل إلى الخطوة 2.

· الخطوة 2. العثور على المتغير الذي تم إدخاله في المتغيرات الأساسية. (من شرط زيادة الدالة الموضوعية).

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

· خطوة 4 . إيجاد إحداثيات خط الأساس الجديد (نقطة الزاوية المجاورة). انتقل إلى الخطوة 1.

تشكل الخطوات المتكررة 1-4 تكرارًا واحدًا للطريقة البسيطة.

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

تعريف. سنقول أن مشكلة LP الأساسية لها "نموذج مفضل" إذا

1. الطرف الأيمن من المعادلات، .

2. تحتوي مصفوفة الحالة على مصفوفة وحدة فرعية للحجم

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

مثال 2.1.

مصفوفة الحالة أومتجه الجوانب اليمنى للقيود بيبدو مثل

أ ناقلات الهدفج = (1، -3، 0، 4، 2).

مصفوفة أساس واحدة واضحة على الفور: مع ناقلات الوحدة للشروط.

ولذلك، اختيار كمتغيرات أساسية س 1 , س 3 ,س 5 , ووضع نظام المعادلات س 2 = س 4 = 0 (المتغيرات غير الأساسية) , نجدها على الفور س 1 = 10,س 3 = 20,س 5 = 8، وبالتالي فإن خط الأساس الأولي س 0 = (10, 0, 20, 0, 8). نرى أن قيم المتغيرات الأساسية تساوي الجانب الأيمن من القيود. ومن هذا يتضح أن الأطراف اليمنى يجب أن تكون إيجابية ب أنا .

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

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

س ب = ب.

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

? ي = < с ب ، أ ي > - ج ي ، ي = 1،...،ن،(2.1)

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

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

دعونا نطبق هذا المعيار للتحقق من سلامة الخطة الأساسية س 0 = (10، 0، 20، 0، 8) من المثال 2.1.

لأنه في هذا الصدد ناقلات المتغيرات الأساسية س ب =(س 1 , س 3 ,س 5 )، الذي - التي مع ب = (ج 1 , ج 3 ,ج 5 ) = (1, 0, 2).

لذلك،

? 1 = < с ب ، أ 1 > - ج 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- ج2 = 1 3 + 0 1 + 2 2 - (-3) = 10،

? 3 = < с ب ، أ 3 > - ج 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с ب ، أ 4 > - ج 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с ب ، أ 5 > - ج 5 = 1 0 + 0 0 + 2 1 - 2= 0.

منذ التقييم ? 4 < 0, то базисный план س 0 ليس الأمثل. لاحظ أن التقديرات البسيطة المقابلة للمتغيرات الأساسية تساوي دائمًا الصفر، لذا يكفي التحقق من التقديرات غير الأساسية فقط.

فكرة الطريقة البسيطة

طريقة سيمبلكس

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

دع المضلع ABCDEFGH يمثل مجموعة الحلول المقبولة لـ PLP بمتغيرين، والمتجه – التدرج من وظيفة الهدف.

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

تشكل فكرة التحسين المتسلسل للحل أساس الطريقة العالمية لحل مشاكل البرمجة الخطية – طريقة بسيطة.

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

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

تتكون الطريقة البسيطة من ثلاثة عناصر رئيسية.