Solving Linear Programming problems in python PulP

Click For Summary
SUMMARY

This discussion focuses on solving linear programming (LP) problems using the Python library PuLP. The objective function is defined as 30LADA + 40LAHO + 50SADA + 40SAHO + 110DANY + 125DACH + 105HONY + 115HOCH, with constraints on supply and demand. The user seeks clarification on the concept of dummy demand due to an imbalance between total supply and demand, specifically a surplus of 33,500 units. The conversation emphasizes the importance of simplifying the LP model by eliminating variables through derived equations, ultimately reducing the problem to a manageable four-variable LP.

PREREQUISITES
  • Understanding of linear programming concepts
  • Familiarity with Python programming
  • Knowledge of the PuLP library for optimization
  • Basic grasp of supply and demand principles in operations research
NEXT STEPS
  • Learn how to implement linear programming models using PuLP in Python
  • Study the concept of dummy variables in linear programming
  • Explore methods for simplifying LP problems by reducing variables
  • Investigate how to interpret and analyze LP solutions effectively
USEFUL FOR

This discussion is beneficial for data scientists, operations researchers, and anyone involved in optimization problems using linear programming techniques in Python.

alpha
Messages
9
Reaction score
1
Okay so far I have come up with the following:
The objective function is:
30LADA + 40LAHO + 50SADA + 40SAHO + 110DANY + 125DACH + 105HONY + 115HOCH (to read this please see the table above as I have just used the first two letters of each except NY which I have represented by NY). In these I have also added in the additional cost of $90 from Houston and $70 from Houston. Since that should be covered in the cost matrix (I think?)

My constraints are:
1. all variables must be >= 0
2. SADA + SAHO <= 55,500
3. LADA + LAHO <= 50000
4. DACH + HOCH <= 27000
5. DANY + HONY <= 45000
6. LADA + SADA - DANY - DACH = 0
7. LAHO + SAHO - HONY - HOCH = 0

Now what I don't understand is constraints 6 and 7. I have gone over a few books that talk about dummy demand since this is clearly not a balanced question (demand = 72000, supply = 105500) with the difference being 33500. So I noticed in similar questions people using dummy demand. Would appreciate some help in explaining what dummy demand is and how I would allocate the 33500 since I am not entirely sure how to split it.

From there I get the following table:


DallasHoustonNYChicagoDummySupply
LA
30​
40​
0​
50000​
SD
50​
40​
0​
55500​
Dallas
110​
125​
0​
Houston
105​
115​
0​
Demand
45000​
27000​
33500​

Now I know my dummy demand column is wrong but I am not too sure about the rest either. Can someone please give me some guidance on this? I am yet to export this to PuLp on python and solve it since I have to formulate the table first. Thank you!
 
Last edited:
Technology news on Phys.org
I don't know about dummy demand but it seems to me you can simplify the problem to have fewer variables. I think of constraints as being inequalities like items 1-5 whereas equations ('equalities') like 6-7 allow us to just remove variables from the calc and thus simplify it.
Before proceeding, note that, since you are required to meet demand, you should replace the <= sign in 4 and 5 by an = sign.
Hence we have eight unknown variables and four equations 4-7, which allows us to eliminate four variables, expressing them in terms of the remaining four variables.
We need to exercise judgement in which variables to eliminate. For instance we can't eliminate the four refiners to consumer variables, since that leaves only three variables, since the four producer-to-refinery variables must add to 27000+45000. We need to leave uneliminated at least one producer-to-refinery and oner refinery-to-consumer variable.

So let's eliminate one producer-to-refiner variable (say SADA) and three refiner-to-consumer variables (say all except HONY).

That will leave us with four unknown variables saho, lada, laho and hony

You get the other four variables by the derived equations:
1. dany = 45k - hony
2. sada = (45k + 27k) - (saho + lada + laho)
3. dach = lada + sada - (45k - hony)
4. hoch = 27k - dach

Substitute those in your objective function to get a function that only uses the four unknown variables

You have ten inequalities, being the requirement that each of the eight variables be >= 0, and the two producer inequalities (limits of 55.5k for San Diego and 50k for LA). Where eliminated variables occur in those inequalities, substitute for them using the above to obtain inequalities in terms of the four unknown variables.

So now you have a much simpler 4-variable LP problem instead of an 8-variable one.

Principle: use all available equations to reduce the number of variables, before you start linear programming.