2
$\begingroup$

I have to find a maximum and minimum of this linear programming problem.

$$\begin{align} max\quad x_1+x_2 \end{align}$$

Constrains $$\begin{align*} x_1+x_2+x_3 =3 \\ -2x_1+x_2+x_4=5 \\ x_2+x_5=7\\ x_1+x_6=6 \end{align*} \\ x_i \geq 0 $$

Origin simplex-table will be:

\begin{bmatrix}&x1&x2&x3&x4&x5&x6&B\\C_1&1&1&1&0&0&0&3\\C_2&-2&1&0&1&0&0&5\\C_3&0&1&0&0&1&0&7\\C_4&1&0&0&0&0&1&6\\-F&-1&-1&0&0&0&0&0\end{bmatrix} Where $C_i$ is constraint i.
To find an optimal solution, which is maximum, we need to take the minimal value in -F row, excluding B column (leading column). I'll take x1 column and mark this column as $x_r$.

To find the leading row we need to calculate $\frac{B_i}{x_r}$ and the row, where this fraction is minimal (including 0) becomes the leading row. If $x_r<0$ we skip this row automatically.

The element that is at the intersection of leading row and leading column is leading element.

The leading column, which represents a variable, moves to basis using Jordan-Gauss elimination.

According to this table, the leading column is $x_1$ column, leading row is $C_1$ and the leading element is 1. Moving this variable to basis we got the next simplex-table:

\begin{bmatrix}1&1&1&0&0&0&3\\0&3&2&1&0&0&11\\0&1&0&0&1&0&7\\0&-1&-1&0&0&1&3\\0&0&1&0&0&0&3\end{bmatrix}

F-row has no negative values, the solution is optimal. Yes, it's optimal, but for a different problem, where F looks like this:

$$\begin{align} max\quad x_1-x_2 \end{align}$$

MathCad solution x1-x2

MathCad solution x1+x2

I can achieve the true result choosing x2 as leading column instead of x1. But I'm working on inplementation of simplex-method and it's takes the 1st column if the minimal value in F row is not alone.

How can i achieve the true result, according to MathCad.

Second problem is if i have to find a minimum: $$\begin{align} min\quad x_1+x_2 \end{align}$$

How can i transform max problem into min problem? I know about min(F) = -max(F). But when i write down a simplex-table, I need to write F row with opposite signs, so i got an origin problem.

I have a problem (and my programm) solving min problems at all. What is the main steps to transform a min problem into max problem? How to check if solution is optimal ?

$\endgroup$
2
  • $\begingroup$ Wouldn't you minimize $x_1+x_2$ by maximizing $-x_1-x_2$? $\endgroup$ Commented Apr 11, 2021 at 21:02
  • $\begingroup$ @RobertShore Yes, i would maximize. But i still need to write down F row with opposite signs. And if i follow the algorithm of choosing leading element, the minimal value in -F row will be 0 (--1 --1 0 0 0 0) and this step will change nothing $\endgroup$ Commented Apr 12, 2021 at 12:23

1 Answer 1

Reset to default
1
$\begingroup$

On the first pivot the entering variable (nonbasic -> basic) is $x_1$ and the leaving variable (basic -> nonbasic) is $x_3$. So doing this pivot by hand you get:

$x_3 = 3 - x_1 - x_2 \implies x_1 = 3 - x_2 - x_3$

This is what the first row of the tableau is saying.

and so the objective is rewritten:

$\max (x_1 + x_2) \\ \implies \max ((3 - x_2 - x_3) + x_2) \\ \implies \max (3 - x_3)$

This corresponds to the final row of the tableau (before and after pivot).

No positive coefficients on objective remain, so an optimal solution is basic variable $x_1 = 3$ and nonbasic variable $x_2 = 0$. (Recall that we set all nonbasic variables to zero and so all basic variables just equal the constant, which is the final column of the tableau, usually called $b_i$)

Notice how if you increase $x_2$ then you have to decrease $x_1$ by an equal amount because of the first constraint $x_1 + x_2 \le 3$, and so $x_1 + x_2$ remains unchanged. That's why the coefficient in the objective becomes $0$ for $x_2$, even though its a nonbasic variable, and nonbasic variables usually have nonzero coefficients in the objective.

The geometric interpretation here is that an entire edge of the simplex is optimal. In particular the edge corresponding to $x_1 = 3-k$ and $x_2 = k$. For that entire edge $x_1 + x_2 = 3$. The simplex algorithm has found its way to one of the two vertices of that edge, and so it stops.

So I think the algorithm is working correctly. I think you've just made a mental error in thinking its optimizing a different problem.

I would study the mapping between the algebraic form I use here and the tableau. Each row of the tableau corresponds to an algebraic equation as shown here.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.