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$ Commented Jun 3, 2018 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$ Commented Jun 3, 2018 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$ Commented Jun 3, 2018 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$ Commented Jun 3, 2018 at 12:55

1 Answer 1

Reset to default
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$

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.