Nicht zulässige Basislösung bestimmen

Question

ich habe ein folgendes Problem:

Gegeben sei $$\max_{x\in P} 2x_1+2x_2 $$, wobei P das Polyeder ist. Dann habe ich die Nebenbedingungen aus einer gegebenen Abbildung bestimmt:

$$\begin{aligned} \frac{1}{4}x_1+x_2 &\leq 3 \\ 2x_1+x_2&\leq 6\\ x_1+x_2&\leq 4. \end{aligned}$$

Dann habe ich mithilfe der Schlupfvariablen $$s_1,s_2,s_3\in\mathbb{R}_+$$ die Simplex-Standardform gebildet:

$$A=\begin{pmatrix} 0.25 & 1 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0\\1&1&0&0&1\end{pmatrix}, b = \begin{pmatrix} 3\\6\\4\end{pmatrix}.$$

Meine Aufgabe lautet jetzt, eine zulässige und eine nicht zulässige Basislösung zu finden. Eine zulässige habe ich gefunden:

$$\bar{x}=(0,0,3,6,4)^T.$$

Wie kann ich jetzt eine nicht zulässige Basislösung bestimmen?

Answer 1

Ich glaube, dass du nur einfach eine negative Komponente in einer

Basislösung.

Also zum Beispiel die 2. 3. und 4. Spalte bilden eine Basis

und die zugehörige Basislösung wäre

x = ( 0 ; 4 ; -1 ; 2 ; 0 ) ^T

Die ist nicht zulässig, weil 3. Komponente negativ.

Answer 2

Mal so zur Diskussion gestellt:$$\vec Z_{max}(x_1,x_2) = \begin{pmatrix} 2\\2\\8 \end{pmatrix} + \lambda \cdot \begin{pmatrix} -\frac23\\\frac23\\0 \end{pmatrix}$$ für
$$0 \le \lambda \le 1 $$