# Simpleg Algorithm LP trouble.

• Apr 16th 2012, 08:24 PM
linalg123
Simpleg Algorithm LP trouble.
Vinery 1 can produce 30 boxes per day.
Vinery 2 can produce 20 boxes per day.
Fred's needs at least 20 boxes a day.
Kevin's needs at least 18 boxes a day.
Mark's Needs only 5 boxes a day.

COSTS: Fred's Kevin's Mark's
Vinery 1 35 62 65
Vinery 2 28 36 33

Determine min cost delivery scheme that satisfies needs of bottle shops and does not exceep production capacities.

I have defined my decision variables:
X1= number of boxes from Vinery 1 to Fred's
X2= number of boxes from Vinery 2 to Fred's
X3= number of boxes from Vinery 1 to Kevin's
X4= number of boxes from Vinery 2 to Kevin's
X5= number of boxes from Vinery 1 to Mark's
X6= number of boxes from Vinery 2 to Mark's

Objective function:
min Z = 35X1 + 28X2 + 62X3 + 36X4 + 65X5 + 33X6

and my constraints:
X1 + X2 >= 20
X3 + X4 >= 18
X5+ X6 = 5
X1 + X3 + X5 <= 30
X2 + X4 + X6 <= 20
X1,X2,X3,X4,X5,X6 >= 0

Question: Are these the right variables and constraints, and how do i proceed from here?
• Apr 17th 2012, 02:45 AM
Bingk
Re: Simpleg Algorithm LP trouble.
I think you'd get more responses if you posted this in the business math sub-forum.

In any case, it seems like what you have is correct so far. I'm pretty sure there are other ways to do this (and I may be wrong), but here's what I got for x1,x2,...,x6: 20,0,3,15,0,5 respectively.

I started with X5+X6=5. Just considering Mark, the minimum cost will be if all 5 come from Vin2 and none from Vin1. Now, if we get 1 from Vin1, the cost increases by 65-33 = 32. But it's not possible to get a combination (considering Fred and Kevin as well) that will save at least that much, so X5=0 and X6=5.

Now, looking at X1 to X4, delivering to Kevin from Vin2 instead of Vin1 will save 62-36 = 26, whereas delivering to Fred from Vin2 instead of Vin1 will save 35-28 = 7. So, send the most you can to Kevin from Vin2, this gives us X4 = 15 (since 5 of the 20 from Vin 2 goes to Mark), and X3 = 3 (so that Kevin gets his minimum 18).

That leaves us with 20 going to Fred from Vin1, and none going to Fred from Vin2.

After that, I just played around abit with the numbers and saw that what I got gives the minimum ... so I may be wrong :D