1
$\begingroup$

Given the following system :

\begin{align*} \text{minimise } z = &2x_1 &+ 3x_2 &+ 3x_3 &+ x_4 &- 2x_5& \\ \end{align*}

Subject to \begin{align*} & x_1 &+ 3x_2 & &+x_4 &+ x_5 &= 2 \\ & x_1 &+ 2x_2 & &- 3x_4 &+ x_5 &= 2 \\ - &x_1 &- 4x_2 & +x_3 & & &= 1 \\ \end{align*}

with $x_1, x_2, x_3, x_4, x_5 \geq 0$

There should be Phase I and then Phase II of the simplex method.


Q1 - how to explain why Phase I is required here

Q2 - how to know which rows should have artificial variables added


For question 1, the objective function can be written as

\begin{align*} -z + 2x_1 + 3x_2 + 3x_3 + x_4 - 2x_5 = 0\\ \end{align*}

The way that the system is initially set up has basic variables $x_3$ and non-basic variables $x_1,x_2,x_4,x_5 = 0$.

Meaning the objective function is

\begin{align*} -z + 3x_3 = 0\\ \end{align*}

Or

\begin{align*} z = 3x_3 \end{align*}

Why is this an issue?

For Question 2 I'm not sure what to consider.

$\endgroup$
  • 1
    $\begingroup$ 1. You need 3 basic variables to start; 2. Your starting point does not satisfy the constraints. 3. Is there no nonnegativity constraint? $\endgroup$ – LinAlg Feb 22 at 1:50
  • $\begingroup$ @LinAlg (1) why do I need three variables to start (because that's the dimension of the row-space and solution?) (2) what do you mean? That my starting point is $x_3 = 1$, and if all other $x_i=0$ the second (and first) equalities (constraints) are false (3) There is - I'll add that $\endgroup$ – baxx Feb 22 at 2:30
  • 1
    $\begingroup$ 1. since you have 3 constraints; 2. 'are false': that is not ok. You need basic feasible solutions in every iterate (so basic AND feasible; you have neither) $\endgroup$ – LinAlg Feb 22 at 2:46
0
$\begingroup$

Point (2) in OP's comment is very near to the an answer.

For each of the first two constraints, there's no decision variable

  • which has nonzero coefficient, and
  • which doesn't appear in the other two rows.

For a concrete counterexample, you may consider the third row, in which $x_3$

  • has coefficient one
  • doesn't appear in the first two constraints.

Therefore, in general, the first two rows need artificial coefficients.

Remarks: Observe that $\begin{vmatrix} 1 & 3 & 0 \\ 1 & 2 & 0 \\ -1 & -4 & 1 \end{vmatrix} \ne 0$ and $\begin{vmatrix} 0 & 1 & 1 \\ 0 & -3 & 1 \\ 1 & 0 & 0 \end{vmatrix} \ne 0$, so you may actually solve it as in in exams/tests so save the trouble of doing phase I. However, finding initial BFS like this is never a general method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.