Linear programming (linprog) in SciPy - Step-by-Step Execution

Concept Flow - Linear programming (linprog)

Define objective function coefficients c

↓

Define inequality constraints A_ub and b_ub

↓

Define equality constraints A_eq and b_eq (optional)

↓

Call linprog solver with inputs

↓

Solver finds optimal solution x

↓

Check solver success and output results

Linear programming solves a problem by defining an objective and constraints, then finding the best solution using linprog.

Execution Sample

SciPy

from scipy.optimize import linprog
c = [-1, -2]
A = [[2, 1], [1, 1]]
b = [20, 16]
res = linprog(c, A_ub=A, b_ub=b)
print(res.x)

This code finds values for two variables that maximize the objective under given constraints.

Execution Table

Step	Action	Input/Condition	Result/Output
1	Define objective coefficients c	c = [-1, -2]	Objective: minimize -1*x1 - 2*x2
2	Define inequality constraints A_ub and b_ub	A = [[2,1],[1,1]], b = [20,16]	Constraints: 2x1 + x2 <= 20, x1 + x2 <= 16
3	Call linprog solver	linprog(c, A_ub=A, b_ub=b)	Solver starts optimization
4	Solver iterates to find feasible solution	Checking constraints and objective	Intermediate solutions tested
5	Solver finds optimal solution	Optimal x found	x = [0.0, 16.0]
6	Check solver success	res.success == True	Optimization successful
7	Print solution	print(res.x)	[0.0, 16.0]
8	Exit	Optimization complete	Best solution found within constraints

💡 Solver stops after finding optimal solution that satisfies all constraints.

Variable Tracker

Variable	Start	After Step 3	After Step 5	Final
c	[-1, -2]	[-1, -2]	[-1, -2]	[-1, -2]
A	[[2,1],[1,1]]	[[2,1],[1,1]]	[[2,1],[1,1]]	[[2,1],[1,1]]
b	[20,16]	[20,16]	[20,16]	[20,16]
res.x	None	None	[0.0, 16.0]	[0.0, 16.0]
res.success	None	None	True	True

Key Moments - 3 Insights

Why are the coefficients in c negative when we want to maximize?

linprog only minimizes, so to maximize we minimize the negative of the objective. See Step 1 and Step 3 in execution_table.

What does A_ub and b_ub represent in the problem?

They represent inequality constraints of the form A_ub * x <= b_ub. This is shown in Step 2 where constraints are defined.

How do we know the solver found a valid solution?

res.success is True as shown in Step 6, indicating the solver found a solution meeting all constraints.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the value of res.x?

A [10.0, 5.0]

B [0.0, 16.0]

C [8.0, 8.0]

D [5.0, 10.0]

💡 Hint

Check the 'Result/Output' column at Step 5 in execution_table.

At which step does the solver confirm the optimization was successful?

A Step 6

B Step 4

C Step 3

D Step 7

💡 Hint

Look for 'res.success == True' in the execution_table.

If we change c to [1, 2] instead of [-1, -2], what happens to the optimization goal?

A It still maximizes the original objective

B It maximizes the negative objective

C It minimizes the original objective

D It minimizes the negative objective

💡 Hint

Recall linprog minimizes the objective; changing sign changes maximize to minimize.

Concept Snapshot

Linear programming with linprog:
- Define objective coefficients c (minimize c·x)
- Define inequality constraints A_ub·x <= b_ub
- Optionally define equality constraints A_eq·x = b_eq
- Call linprog(c, A_ub=A_ub, b_ub=b_ub)
- Check res.success and res.x for solution
- To maximize, minimize negative objective

Full Transcript

Linear programming uses linprog to find the best values for variables that minimize an objective function while respecting constraints. We start by defining the objective coefficients as c, constraints as A_ub and b_ub, then call linprog. The solver tries different values to find the minimum of c·x that satisfies constraints. Since linprog only minimizes, to maximize we use negative coefficients. The solver returns res.x with the best solution and res.success to confirm success. This step-by-step process helps understand how linprog works.