Degeneriert Ecken und die dazu gehörigen Basen bestimmen

Question

Aufgabe:

Der zulässige Bereich wird durch folgende Ungleichungen definiert
x1 + x2 + 2x3 ≤ 8
x2 + 6x3 ≤ 12
x1 ≤ 4
x2 ≤ 6
x1, x2, x3 ≥ 0
Welche von den Ecken A = (2, 6, 0), B = (4, 0, 2) sind degeneriert? Welche
Basen gehören zu diesen Ecken?

Problem/Ansatz:

Hallo,
Wie gehe ich so ein Beispiel am Besten an?

Schritt 1: Ungleichungen in Normalform bringen
x1 + x2 + 2x3 + u1 = 8

x2 + 6x3 + u2= 12

x1  + u3 = 4

x2 + u4= 6

x1, x2, x3, 2 ≥ 0

Schritt 2 : Basislösung ermitteln
ab da habe ich Schwierigkeiten. Ich weiß, dass u1, u2, u3, u4 Basisvariablen sind. Aber wie komme ich zu den Schluss welche Ecken degeneriert sind und welche Basen zu diesen Ecken gehören?

Answer 1

Als degenerierte Ecke bezeichnet man eine Ecke auf der der Simplex—Algorithmus hängen bleibt.

Eine sehr anschauliche Darstellung finde ich bei Peter Buchholz:

//

Extrempunkte können u.U. auch durch weniger als $\mathrm{m}(=\text { Anzahl Zeilen von A und } \operatorname{rang}(\mathrm{A}))$ positive Elemente charakterisiert sein
$$\left(\begin{array}{lllll} 2 & 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 2 & 5 & 0 & 0 & 1 \end{array}\right)\left(\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}\right)=\left(\begin{array}{l} 4 \\ 3 \\ 7 \end{array}\right)$$
mit der Lösung $(1,1,0,0,0)^{\mathrm{T}}$
Man spricht dann von einer degenerierten Ecke

//

Anschaulich wird im Fall n=2 eine Ecke durch den Schnittpunkt 2er NB-Geraden bestimmt. In dem Fall oben (degenerierte Ecke) sind 3 Schlupfvariablen=0, d.h. dort schneiden sich 3 NB-Geraden.

Rechnung

m=Rang(A)=4

A (x1,x2,x3,s1,s2,s3,s4)^T = b

$\small \left(\begin{array}{rrrrrrr}1&1&2&1&0&0&0\\0&1&6&0&1&0&0\\1&0&0&0&0&1&0\\0&1&0&0&0&0&1\\\end{array}\right) \cdot \left(\begin{array}{r}2\\6\\0\\0\\6\\2\\0\\\end{array}\right)= \left(\begin{array}{r}8\\12\\4\\6\\\end{array}\right)$

===> nicht degeneriert: Lösung hat 4 Komponenten=m. Ecke wird beschrieben durch s1=s4=x3=0 (Schnittpunkt 3 Ebenen)

$\small \left(\begin{array}{rrrrrrr}1&1&2&1&0&0&0\\0&1&6&0&1&0&0\\1&0&0&0&0&1&0\\0&1&0&0&0&0&1\\\end{array}\right) \cdot \left(\begin{array}{r}4\\0\\2\\0\\0\\0\\6\\\end{array}\right)= \left(\begin{array}{r}8\\12\\4\\6\\\end{array}\right)$

===> degeneriert: Lösung hat 3 Komponenten<m. Ecke wird beschrieben durch s1=s2=s3=0 Schnitpunkt 3er NB-Ebenen und x2=0  (Schnittpunkt 4 Ebenen)

Answer 2

Nach Betrachtung von

https://de.wikipedia.org/wiki/Simplex-Verfahren#Basen,_Basislösungen…

habe ich den Eindruck, dass man nur die Koordinaten der Ecken für x1,x2,x3

einsetzen muss und die Werte von u1,u2,u3 damit bestimmen.

Das gibt bei der 1. Ecke 0,6,2,0

und bei der 2. Ecke 0,0,0,6.

Also hat man bei beiden Ecken  "weniger als m

Nicht-Null-Einträge" ; denn hier ist ja m=4 die

Anzahl der Schlupfvariablen. Also wären beide

Ecken degeneriert.