1
$\begingroup$

I want to solve the following simplex algorithm :

Maximize $$z =x_1+x_2+2x_3-2x_4$$ Subject to $$ x_1+2x_3 \le 700 $$ $$ 2x_2-8x_3 \le 0 $$ $$ x_2-2x_3+2x_4 \ge 1 $$ $$ x_1+x_2+x_3+x_4 = 10 $$ where $$ 0 \le x_1 \le 10$$ $$ 0 \le x_2 \le 10$$ $$ 0 \le x_3 \le 10$$ $$ 0 \le x_4 \le 10$$

I know that the standard simplex problem has following form :

Maximize $$z=c_1x_1+c_2x_2+ \ldots + c_n+x_n$$ Subject to $$a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n \le b1$$ $$a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n \le b2$$ Subject to $$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots $$ $$a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n \le bm$$

where $$ x_j \ge 0 , j=1,2,3,\ldots,n$$

How can I convert my problem to standard form ? How can I solve my problems by simplex algorithm ?

My attempt:

I have replaced $0 \le x_1 \le 10 $ by two separate constraints $ 0 \le x_1 $ and $ x_1 \le 10 $. But after that, I can't reach to optimal solution although the problem has basic feasible solution.

$\endgroup$
4
  • $\begingroup$ @Jean-ClaudeArbaut There is nothing wrong with capitalization in titles. There is no reason to change this to lower case, exctept the preposition "By". $\endgroup$ – miracle173 Jun 3 '18 at 12:26
  • $\begingroup$ @miracle173 The link you give mentions that the rule "can vary according to a particular style guide" I don't know if there is an explicit rule on MSE, however it seems to me the current practice is to not capitalize. But I won't argue about this if someone decides that he prefers capitals. $\endgroup$ – Jean-Claude Arbaut Jun 3 '18 at 12:32
  • 1
    $\begingroup$ This is neither a simplex problem nor a simplex algorithm but a linear programming problem or linear optimization problem. You can use the simplex algorithm to solve such problems. $\endgroup$ – miracle173 Jun 3 '18 at 12:32
  • $\begingroup$ Did you notice that $$x_1 \le 10$$ is an inequality of type $$a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n \le bm$$ $\endgroup$ – miracle173 Jun 3 '18 at 12:55
0
$\begingroup$

Some software packages offer Linear Programming solvers. Each package has a typical formatting rules so for instance in MATHEMATICA we have the solver format

LinearProgramming[c, M, b]

in which the problem should be submitted as

$$ \max c x = c_1x_1+\cdots + c_n x_n\\ \mbox{subject to}\\ M x \ge b\\ x \ge 0 $$

with

$$ M = \left( \begin{array}{cccc} -1 & 0 & -2 & 0 \\ 0 & -2 & 8 & 0 \\ 0 & 1 & -2 & 2 \\ 1 & 1 & 1 & 1 \\ -1 & -1 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{array} \right), b = \left( \begin{array}{c} -700 \\ 0 \\ 1 \\ 10 \\ -10 \\ -10 \\ -10 \\ -10 \\ -10 \\ \end{array} \right), c = (1,1,2,-2) $$

and the result is

$$ x_0 = (0,0,0,10) $$

NOTE

The equality

$$ x_1+x_2+x_3+x_4 = 10 $$

is handled as

$$ x_1+x_2+x_3+x_4 \ge 10\\ x_1+x_2+x_3+x_4 \le 10 $$

$\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.