Linear Programming

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

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

report = lp_sensitivity_report(model)
function variable_report(xi)
    return (
        name = name(xi),
        lower_bound = has_lower_bound(xi) ? lower_bound(xi) : -Inf,
        value = value(xi),
        upper_bound = has_upper_bound(xi) ? upper_bound(xi) : Inf,
        reduced_cost = reduced_cost(xi),
        obj_coefficient = coefficient(objective_function(model), xi),
        allowed_decrease = report[xi][1],
        allowed_increase = report[xi][2],
    )
end
function print_solution_table(model)
    variable_df =
        DataFrames.DataFrame(variable_report(xi) for xi in all_variables(model))
    return variable_df
end;

Print the solution table, including sensitivity analysis.

print_solution_table(model)

3×8 DataFrame

Row	name	lower_bound	value	upper_bound	reduced_cost	obj_coefficient	allowed_decrease	allowed_increase
	String	Float64	Float64	Float64	Float64	Float64	Float64	Float64
1	food_qty[Rice]	0.0	14.8936	Inf	0.0	0.5	-0.26	0.366667
2	food_qty[Beans]	0.0	0.531915	Inf	0.0	0.8	-0.338462	0.368182
3	food_qty[Broccoli]	0.0	0.0	Inf	0.0861702	0.3	-0.0861702	Inf

Other Formats