النقطة المتطرفة Extreme Point

– 4 – 6 النقطة المتطرفة Extreme Point أي نقطة (u) في المجموعة المحدبة (c) هي نقطة متطرفة أذا (u) لا يمكن التعبير عنها كتوافيق محدبة لأية نقطتين في (c).
نظرية (2 – 1):
أي نقطة تقع على الخط الواصل بين نقطتين في المجال (E_n), يمكن التعبير عنها كتوافيق محدبة لهاتين النقطتين.


البرهان:
نفرض أن النقطتان هما (u,v) ونفرض أن (w) هي النقطة التي تقع على الخط الواصل بين النقطتان (u,v) وأن هذا الخط يكون موازي إلى الخط المعٌرف بالمتجه (u-v), وباستخدام قوانين جمع المتجهات ولقيم (0???1), فأن:
v+?(u-v)=w (2.13)
أو
(1-?)v+?u=w (2.14)
والذي يعبر كتوافيق محدب للنقطتين (u) و (v).
نظرية (2 – 2):
المجموعة لكل الحلول المقبولة لمسألة البرمجة الخطية هي مجموعة محدبة.
البرهان:
نبرهن أن أي توافيق محدب لحلين مقبولين هو أيظاً حل مقبول نفترض بأن هناك على الأقل حلين هما (x_1) و (x_2).
Ax_1=b x_1?0
Ax_2=b x_2?0
x=?x_1+(1-?) x_2 0???1
حيث (x) توافيق محدبة للحلين (x_1) و (x_2).
Ax=A[?x_1+(1-?) x_2]
Ax=?Ax_1+Ax_2-?Ax_2
Ax=?b+b-?b
Ax=b (2.15)
من هنا يتبين أن (x) هو حل مقبول.
نظرية (2 – 3):
إذا كانت المتجهات {p_1,p_2,…,p_k (k?m)} بحيث أن:
?x_1 p?_1+?x_2 p?_2+?+x_k p_k=p_0
فأن النقطة (x) ستكون نقطة متطرفة لمجموعة الحلول المقبولة المحدبة, حيث:
x=(x_1,x_2,…,x_k,0,…,0)
البرهان:
لنفرض أن (x) ليس نقطة متطرفة, ولكن بسبب كون (x) حل مقبول فأنه يمكن كتابته كتوافيق محدب لأي نقطتان في المتجه (k) لنفرض أن هاتان النقطتان هما (x_1) و (x_2).
x=?x_1+(1-?) x_2 0???1
وبسبب كون جميع عناصر (x_i) في (x) عناصر غير سالبة وبسبب (0???1) فأن (n-k) من العناصر الأخيرة في (x_1) و (x_2) يجب أن تساوي صفر, أي أن:
x_1=(x_1^((1)),x_2^((1)),…,x_k^((1)),0,…,0)
x_2=(x_1^((2)),x_2^((2)),…,x_k^((2)),0,…,0)
وبسبب كون (x_1) و (x_2) حلول مقبولة, فأن:
Ax_1=b
Ax_2=b (2.16)
وبإعادة كتابة هذه المعادلات برموز متجهات, نحصل:
x_1^((1)) p_1+x_2^((1)) p_2+?+x_k^((1)) p_k=p_0
x_1^((2)) p_1+x_2^((2)) p_2+?+x_k^((2)) p_k=p_0 (2.17)
ولكن (p_1,p_2,…,p_k) مستقلة خطياً (بالفرض) وأن (p_0) يمكن التعبير عنها كتوافيق خطية الى (p_1,p_2,…,p_k) وهذا يتضمن بأن (x_i=x_i^((1))=x_i^((2))) لذا فأن (x) لا يمكن التعبير عنها كتوافيق محدبة لنقطتان في (k), ويجب أن تكون نقطة متطرفة في (k).