Simplex Linear Programming Question

Simplex Linear Programming Question

Postby sirooseven7 » Thu Mar 17, 2016 5:35 pm


I am currently trying to solve a system of equations with numerous constraints by using the simplex linear programming method. I have 6 variables (x1 to x6) and 22 total constraints. The constraints are base on 11 variables (y1 to y11) that are dependent on x1 through x6. Each of the y has a lower and an upper bound which create 2 inequality constraints.

upper:
y1 = a1x1 + a2x2 + ... + a(n)x(n) <= A

lower:
y1 = a1x1 + a2x2 + ... + a(n)x(n) >= B

My objective is to maximize E = c1x1 + c2x2 + ... + c(n)xn
where c can be negative constants.

To fully understand this problem, I start with just the first 2 constraints for y1 and ran the simplex algorithm that I wrote. The solution satisfy the bounds for y1.
I then add the constraints for y2 and run the problem with 4 total constraints. Again, the result satisfy the bounds for y1, and y2.
The process is repeated until I reach y7. The simplex method found an answer; however, one of my previous constraints is no longer satisfy. I tried running this same problem in the Excel Simplex LP Solver and the results satisfy all of my constraints (y1 to y7).

Without going into the details of the problem, does any of you have experience in troubleshooting this issue? There is obviously a correct answer since excel simplex solver is able to get it. I am trying to understand why I am having trouble getting my simplex model to do so.

Thank you,
sirooseven7
 
Posts: 3
Joined: Thu Mar 17, 2016 5:13 pm
Reputation: 0

Re: Simplex Linear Programming Question

Postby Guest » Sat Mar 19, 2016 7:22 am

Without seeing the code you wrote it is unlikely anyone will be able to help you.

Linear programs don't necessarily have unique solutions for example "maximize x+y given x+y<=5". Any solution of the form (x,5-x) will work. So it is possible for your program and the excel solver to differ in the exact solution they return (however, the objective value should be the same in both cases, even if the variable values are different).

Having said that, it sounds like you have a bug. Common bugs in numerical solvers usually involve not dealing with floating point numbers correctly/robustly (you can't just compare numbers without taking rounding errors into account). Check out the errors section in:
http://floating-point-gui.de/

I suggest trying out lots of small examples and finding one which your code doesn't match the excel solver, then walking through each line of your code for that example and seeing where it went wrong.

Hope this helped,

R. Baber.
Guest
 

Re: Simplex Linear Programming Question

Postby sirooseven7 » Thu Mar 31, 2016 3:00 pm

Dear Baber,

Thank you for your insight. I'll take a look at that as soon as I get a chance. I have attached a copy of my matrix here in case if the simplex LP experts would like to give it a shot.

Thank you,
Attachments
Capture.JPG
Capture.JPG (142.4 KiB) Viewed 971 times

sirooseven7
 
Posts: 3
Joined: Thu Mar 17, 2016 5:13 pm
Reputation: 0

Re: Simplex Linear Programming Question

Postby Guest » Sat Apr 02, 2016 6:22 am

I don't think many people will be willing to type the data by hand. I suggest trying to post a txt file with the data in (I'm not sure if the forum allows that though). Also it would be useful if you could label the row/columns, I can probably guess that the last column is the constant, and the last row is the objective, but it would be nice to specify that. Also I assume each row (except for the last) represents [tex]a_1 x_1+a_2 x_2+\ldots = a_n[/tex] rather than [tex]\leq a_n[/tex] or something. Are you maximizing or minimizing the objective?

Having a quick look at the values, I suggest normalizing the rows (before adding the slack variables), having very large entries and very small entries usually isn't a good idea. Also it might be worth checking if your data is well conditioned
https://www.youtube.com/watch?v=JODxbi9B3tg
It may be the case that your data is ill conditioned and so prone to small errors making a huge difference in the output.

Hope this helped,

R. Baber.
Guest
 


Return to Simultaneous Equations, Systems of Equations/Inequalities



Who is online

Users browsing this forum: No registered users and 1 guest