1

Let,

$\begin{array}{lcl}Min: z =10x_{1}+5x_{2} \\ \\ 20x_{1}+50x_{2} \geq 200 \\ 50x_{1}+10x_{2} \geq 150 \\30x_{1}+30x_{2} \geq 210 \\x_{1},x_{2} \geq 0\end{array}$

a linear programming problem.

In standart form one have,

$\begin{array}{lcl}Min: z =10x_{1}+5x_{2} \\ \\ 20x_{1}+50x_{2}+s_{1} = 200 \\ 50x_{1}+10x_{2}+s_{2} = 150 \\30x_{1}+30x_{2}+s_{3} = 210 \\x_{1},x_{2},s_{1},s_{2},s_{3} \geq 0\end{array}$

The previous form is associate to the basic feasible solution, $\left( 0,0,200,150,210\right)$.

Because the goal is to minimize $z$, let $x_{2}$ increase. Because the slack variables have to be positive, one have:

$\begin{array} \\200-50x_{2}\geq0 \\150-10x_{2}\geq0 \\210-30x_{2}\geq0 \end{array}$

Solving the previous system, one get that the maximum value of $x_{2}$ is $4$. When $x_{2}=4$ one get $s_{1}=0$.

The new basic feasible solution is $\left( 0,4,0,110,90\right)$. And, by making $x_{2}=4-\frac{2}{5}x_{1}-\frac{1}{50}s_{1}$, the standart form associated is,

$\begin{array}{lcl}Min: z =20 +8x_{1}-\frac{1}{10}s_{1} \\ \\ \frac{2}{5}x_{1}+x_{2}+\frac{1}{50}s_{1} = 4 \\ 46x_{1}-\frac{1}{5}s_{1}+s_{2} = 110 \\18x_{1}-\frac{3}{5}s_{1}+s_{3} = 90 \\x_{1},x_{2},s_{1},s_{2},s_{3} \geq 0\end{array}$

Now, and because the goal still is minimize $z$, let $s_{1}$ increase. But by the first restrition, if $s_{1}$ increase (and because $x_{1}=0$) $x_{2}$ will decrease and one would get back to the first basic feasible solution.

What is wrong with my thoughts? Thanks

1 Answers1

1

It should be:

$\begin{array}{lcl}Min: z =10x_{1}+5x_{2} \\ \\ 20x_{1}+50x_{2}-s_{1} = 200 \\ 50x_{1}+10x_{2}-s_{2} = 150 \\30x_{1}+30x_{2}-s_{3} = 210 \\x_{1},x_{2},s_{1},s_{2},s_{3} \geq 0\end{array}$

Mary Star
  • 13,956
  • 1
    By seeking on the Google, I've saw that a minimization problem can't be solve directly with the simplex method as it would if it was a maximization problem. First it must be convert to a maximization problem by a process called DUAL, that I didn't yet learn! Thanks for you answer. –  May 01 '14 at 22:24
  • 1
    To convert it into a maximization problem you have to take into consideration that: $$\ min{f(x)}=- \max{f(-x)}$$ So the minimization problem becomes: $$\begin{array}{lcl}\max: -z =-10x_{1}-5x_{2} \ \ 20x_{1}+50x_{2}-s_{1} = 200 \ 50x_{1}+10x_{2}-s_{2} = 150 \30x_{1}+30x_{2}-s_{3} = 210 \x_{1},x_{2},s_{1},s_{2},s_{3} \geq 0\end{array}$$ – Mary Star May 02 '14 at 01:09