Linear Programming¶

Linear programming problems are a special class of optimization problem. They involve finding the maximum (or minimum) of some linear objective function $f(x)$ of a vector $x = (x_1 , x_2 , \ldots, x_n )$ , subject to a set of linear equality constraints $A_{eq} \cdot x = b_{eq}$ and inequality constraints $A_{ub} \cdot x \leq b_{ub}$ . The online class notes give a more detailed description on page 66.

Report Description¶

Model the pipelines problem in Python using linprog from the scipy.optimize package.
Use linprog to find the maximum possible flow through the pipelines using the “simplex” algorithm. This is the default method used by linprog.
Give full details of your solution, clearly identifying the flow through each pipeline.
Suggest a way to increase the maximum flow by at least 3 units for as little cost as possible.
Confirm that the suggested change is successful.

Tip

Describing the pipelines problem as a linear programming problem means first answering the following key questions before starting to code:

What are the variables?
What are the bounds on each variable?
What is the objective function?
What are the inequality constraints?
What are the equality constraints?