Linear Programming: Standard Form

Slides

View slides in full screen / PDF

In-class activity

Use the JuMP modeling language to solve a linear program. \[ \begin{array}{ll} \min_{x} & c^T x\\ \text{st} & Ax \le b, \ x \geq 0 \end{array} \]

  • \(x_j\) represents how many servings of food \(j\) to eat
  • \(c_j\) gives cost of 1 serving of food \(j\)
  • \(a_{ij}\) gives amount of nutrient \(i\) in 1 serving of food \(j\)
  • \(b_i\) gives minimum amount of nutrient \(i\) required
  • \(x \geq 0\) since you can’t eat negative food

Here’s some data:

# Foods and their costs per unit
foods = ["Rice", "Beans", "Broccoli"]
costs = Dict("Rice" => 0.5, "Beans" => 0.8, "Broccoli" => 0.3)

# Nutrients required
nutrients = ["Calories", "Protein"]
requirements = Dict("Calories" => 2000, "Protein" => 50)

# Nutrient content for each food
# Structured as Dict{food, Dict{nutrient, amount}}
food_nutrients = Dict(
  "Rice" => Dict("Calories" => 130, "Protein" => 3),
  "Beans" => Dict("Calories" => 120, "Protein" => 10),
  "Broccoli" => Dict("Calories" => 35, "Protein" => 2.5)
);

Import packages.

using JuMP, GLPK, DataFrames, PrettyTables

Here’s some starter code to define the variables and the objective function.

# Initialize model
model = Model(GLPK.Optimizer)

# Variables
@variable(model, food_qty[foods] ≥ 0);

Complete the code below to define the objective and constraints.

# Objective: Minimize total cost
@objective(model, Min, # complete... 

# Constraints: Ensure nutritional requirements are met
for n in nutrients
    @constraint(model, # complete...
end

Solve the model.

optimize!(model)
Code for printing the solution table 
function print_sensitivity_report(model)
    # Get sensitivity report
    report = lp_sensitivity_report(model)
    
    # Extract variable data
    data = [(
        name = name(xi),
        value = value(xi),
        reduced_cost = reduced_cost(xi),
        obj_coefficient = coefficient(objective_function(model), xi),
        allowed_decrease = report[xi][1],
        allowed_increase = report[xi][2],
        lower_bound = has_lower_bound(xi) ? lower_bound(xi) : -Inf,
        upper_bound = has_upper_bound(xi) ? upper_bound(xi) : Inf,
    ) for xi in all_variables(model)]
    
    # Create DataFrame
    df = DataFrame(data)
    
    # Format with PrettyTables
    pretty_table(df, 
        header = ["Variable", "Value", "Reduced Cost", "Obj Coef", "Allow Decrease", "Allow Increase", "Lower Bound", "Upper Bound"],
        formatters = (v,i,j) -> j ∈ [2:6...] ? round(v, digits=4) : v,
        alignment = [:l, :r, :r, :r, :r, :r, :r, :r],
        crop = :none
    )
    
    return df
end;

Print the solution table, including sensitivity analysis.

print_sensitivity_report(model);
┌────────────────────┬─────────┬──────────────┬──────────┬────────────────┬────────────────┬─────────────┬─────────────┐
│ Variable           │   Value │ Reduced Cost │ Obj Coef │ Allow Decrease │ Allow Increase │ Lower Bound │ Upper Bound │
├────────────────────┼─────────┼──────────────┼──────────┼────────────────┼────────────────┼─────────────┼─────────────┤
│ food_qty[Rice]     │ 14.8936 │          0.0 │      0.5 │          -0.26 │         0.3667 │         0.0 │         Inf │
│ food_qty[Beans]    │  0.5319 │          0.0 │      0.8 │        -0.3385 │         0.3682 │         0.0 │         Inf │
│ food_qty[Broccoli] │     0.0 │       0.0862 │      0.3 │        -0.0862 │            Inf │         0.0 │         Inf │
└────────────────────┴─────────┴──────────────┴──────────┴────────────────┴────────────────┴─────────────┴─────────────┘

What does this report tell you about the sensitivity of the solution as the price of Broccoli changes? How much cheaper can broccoli get before the solution changes? How much more expensive can broccoli get before the solution changes?