Linear programming (linprog) in SciPy

Introduction

Linear programming helps find the best solution when you want to maximize or minimize something, like cost or profit, under certain limits.

Planning how to spend a budget to get the most benefit

Deciding how much of each product to make to maximize profit

Scheduling tasks to finish work in the shortest time

Allocating resources like workers or machines efficiently

Optimizing diet plans to meet nutrition needs at lowest cost

Syntax

SciPy

from scipy.optimize import linprog

result = linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='highs')

c is the coefficients of the objective function to minimize.

A_ub and b_ub define inequality constraints (A_ub * x ≤ b_ub).

Examples

Minimize -x - 2y without constraints (unbounded problem).

SciPy

from scipy.optimize import linprog

c = [-1, -2]
result = linprog(c)

Minimize -x - 2y with constraints 2x + y ≤ 20 and x + y ≤ 16.

SciPy

c = [-1, -2]
A_ub = [[2, 1], [1, 1]]
b_ub = [20, 16]
result = linprog(c, A_ub=A_ub, b_ub=b_ub)

Minimize 3x + 2y with x + y = 10 and x,y ≥ 0.

SciPy

c = [3, 2]
A_eq = [[1, 1]]
b_eq = [10]
bounds = [(0, None), (0, None)]
result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=bounds)

Sample Program

This program finds the values of x and y that minimize the cost 3x + 4y while keeping within the limits 2x + y ≤ 14 and x + 2y ≤ 14, with x and y not negative.

SciPy

from scipy.optimize import linprog

# Objective: minimize cost = 3x + 4y
c = [3, 4]

# Constraints:
# 2x + y <= 14
# x + 2y <= 14
A_ub = [[2, 1], [1, 2]]
b_ub = [14, 14]

# x and y must be >= 0
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

if result.success:
    print(f"Optimal value: {result.fun}")
    print(f"x = {result.x[0]}")
    print(f"y = {result.x[1]}")
else:
    print("No solution found")

Important Notes

Always check result.success to confirm a solution was found.

Use bounds to set limits on variables, like non-negativity.

The method='highs' is recommended for better performance and accuracy.

Summary

Linear programming finds the best solution under limits.

Use linprog from scipy.optimize to solve these problems.

Define the objective, constraints, and variable bounds clearly.