Solving LPP using Simplex Method with variables subject to a range

Question

I am currently working on a problem which can be solved using linear programming according to the research I have done here, on YouTube and on other websites. I have familiarized myself with the so called Simplex Method and it’s variations, like – Big M, Dual SM, but still I can’t find any examples that resemble the formulation of my problem and respectively its solution.

My question would be: how to convert the program in standard form?

I think both minimization and maximization should work but let’s do it with minimization.

I am using ‘n’ as a denotation that as input there may be ‘n’ number of variables, ie. sometimes there will be 10, sometimes - 60, yeah ..that many. But if there is a way to solve it it should work for any number of variables, I guess.

To minimize:
Z = a1*x1 + a2*x2 + .. + an*xn, where a1 .. an are just random coefficients, all positive.

Subject to: (here is the part where I am not sure if it could be done like that)

N1 ≤ b1*x1 + b2*x2 + .. + bn*xn ≤ N2<br>
M1 ≤ c1*x1 + c2*x2 + .. + cn*xn ≤ M2<br>
O1 ≤ d1*x1 + d2*x2 + .. + dn*xn ≤ O2

where N1, N2, M1, M2, O1 & O2 are natural numbers, > 0, e.g 101, 155, 6433, etc.
and of course N1 < N2, M1 < M2, O1 < O2
where b1 .. bn, c1 .. cn, d1 .. dn are just random coefficients, all positive

Also each unknown variable – x1, x2 .. xn is bounded like so:

X1-min ≤ x1 ≤ X1-max
X2-min ≤ x2 ≤ X2-max
..
Xn-min ≤ xn ≤ Xn-max

Of course all mins and maxes are known, positive, where Xmin < Xmax and > 0.
X1..n must always be > 0 and between its min/max.

I know about adding slack, surplus, artificial variables but I am not 100% sure if it is as simple as that. My initial thoughts were to split every inequality into two and depending on its sign add either the slack or the surplus + artificial variables and continue with the tables.

Hopefully I managed to explain my problem well enough although I am still a bit confused on how to approach it.

Thanks in advance! Hope you guys have a nice day!

And what is your question? Theory of preprocessing to standard-form or How to solve it (most libs don't need Standard-form)? Yes, looks like a LP which can be solved by Simplex or IPMs. — sascha
My question would be how rearrange the constraint inequalities in order to create the first iteration of the SM tableau. — Dizarb
Then maybe describe how that tableau should look like. Which kind of standard-form? — sascha
It may be easier just to use a bounded variable revised simplex method instead of a tableau method. — Erwin Kalvelagen
The title seems to indicate this is about the revised simplex method. There is a natural extension to handle lower and upper bounds on variables (and slacks). Not sure if this is discussed. From your comments it looks you have very little background in linear programming. In that case it may be much better not to implement things yourself but rather use an existing solver. — Erwin Kalvelagen

strubbly strubbly · Accepted Answer · 2017-10-25T07:40:36

You have both greater than and less than constraints. You need to convert these into a pair of constraints, with the same form of inequality by multiplying through by minus one:

N1 ≤ b1*x1 + b2*x2 + .. + bn*xn ≤ N2

goes to

 b1*x1 + b2*x2 + .. + bn*xn ≤ N2
-b1*x1 - b2*x2 - .. - bn*xn ≤ -N1

You can do this also for the variable bounds (it's just that the coefficients there have one 1 and the rest zero). And then you're done: this is a fairly standard form.

Unless I'm missing something?

Solving LPP using Simplex Method with variables subject to a range

1 Answers