# Solving linear programming with bounds by simplex algorithm

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.

• @Jean-ClaudeArbaut There is nothing wrong with capitalization in titles. There is no reason to change this to lower case, exctept the preposition "By". – miracle173 Jun 3 '18 at 12:26
• @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. – Jean-Claude Arbaut Jun 3 '18 at 12:32
• 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. – miracle173 Jun 3 '18 at 12:32
• 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$$ – miracle173 Jun 3 '18 at 12:55

## 1 Answer

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