Linear Programming Basics

What is Linear Programming?

Linear programming: Optimization method for problems with linear constraints

Components:

1. Objective function: What to maximize or minimize
2. Constraints: Linear inequalities that restrict solutions
3. Feasible region: Set of all points satisfying constraints
4. Optimal solution: Point that maximizes or minimizes objective function

Key theorem: Optimal solution occurs at a vertex (corner) of feasible region

Graphing Linear Inequalities

Review: Graphing inequality in two variables

Steps:

1. Graph boundary line (use = instead of ≤ or ≥)
2. Dashed line for < or >
3. Solid line for ≤ or ≥
4. Shade appropriate region (test point)

Example: Graph Inequality

Graph: 2x + y ≤ 6

Boundary line: 2x + y = 6

• Intercepts: (3, 0) and (0, 6)
• Solid line (includes boundary)

Test (0, 0):

2(0) + 0 ≤ 6
0 ≤ 6 ✓

Shade region containing origin

Feasible Region

Feasible region: Intersection of all constraint regions

Graph all inequalities on same axes

Region where all shadings overlap

Example: Find Feasible Region

Constraints:

x + y ≤ 8
2x + y ≤ 10
x ≥ 0
y ≥ 0

Graph each:

1. x + y ≤ 8: Below line through (8,0) and (0,8)
2. 2x + y ≤ 10: Below line through (5,0) and (0,10)
3. x ≥ 0: Right of y-axis
4. y ≥ 0: Above x-axis

Feasible region: Quadrilateral in first quadrant

Finding Vertices

Vertices: Corner points of feasible region

Find by:

• Solving pairs of boundary equations
• Finding intersections
• Including intercepts and origin (if feasible)

Example: Find Vertices

Constraints from previous:

x + y = 8
2x + y = 10
x = 0
y = 0

Vertices:

Origin: (0, 0) ✓

x-axis intercept of 2x + y = 10: (5, 0) ✓

y-axis intercept of x + y = 8: (0, 8) ✓

Intersection of x + y = 8 and 2x + y = 10:

2x + y = 10
x + y = 8
_____________
Subtract: x = 2
Then: y = 6

Vertex: (2, 6) ✓

Four vertices: (0,0), (5,0), (2,6), (0,8)

Objective Function

Objective function: What we want to optimize

Form: P = ax + by (linear expression)

Maximize: Find largest P value in feasible region

Minimize: Find smallest P value in feasible region

Example: Evaluate Objective Function

Objective: P = 3x + 2y

At each vertex:

• (0, 0): P = 3(0) + 2(0) = 0
• (5, 0): P = 3(5) + 2(0) = 15
• (2, 6): P = 3(2) + 2(6) = 18
• (0, 8): P = 3(0) + 2(8) = 16

Maximum: 18 at (2, 6)

Minimum: 0 at (0, 0)

Complete Linear Programming Problem

Typical problem structure:

1. Read problem
2. Define variables
3. Write constraints
4. Write objective function
5. Graph feasible region
6. Find vertices
7. Evaluate objective at each vertex
8. Identify optimal solution

Example: Manufacturing Problem

Problem: Factory makes tables and chairs.

Constraints:

• Table needs 4 hours labor, chair needs 2 hours
• 40 hours labor available
• Table needs 3 units wood, chair needs 1 unit
• 24 units wood available
• Make at least 2 tables

Profit: $60 per table, $30 per chair

Maximize profit.

Solution:

Variables: x = tables, y = chairs

Constraints:

4x + 2y ≤ 40  (labor)
3x + y ≤ 24   (wood)
x ≥ 2         (minimum tables)
x ≥ 0, y ≥ 0  (non-negative)

Objective: P = 60x + 30y

Simplify first constraint:

2x + y ≤ 20

Find vertices:

Intersection of x = 2 and y = 0: (2, 0)

Intersection of x = 2 and 2x + y = 20:

2(2) + y = 20 → y = 16

Vertex: (2, 16)

Intersection of 2x + y = 20 and 3x + y = 24:

3x + y = 24
2x + y = 20
___________
x = 4, y = 12

Vertex: (4, 12)

Intersection of 3x + y = 24 and y = 0:

3x = 24 → x = 8

Vertex: (8, 0)

Evaluate objective:

• (2, 0): P = 60(2) + 30(0) = 120
• (2, 16): P = 60(2) + 30(16) = 600
• (4, 12): P = 60(4) + 30(12) = 600
• (8, 0): P = 60(8) + 30(0) = 480

Maximum profit: $600

Achieved at (2, 16) or (4, 12) (tie!)

Answer: Make 2 tables and 16 chairs, OR 4 tables and 12 chairs**

Unbounded Regions

Sometimes feasible region extends infinitely

Unbounded: At least one constraint creates open region

Maximum might not exist (P can grow without bound)

Minimum often still exists

Example: Unbounded Problem

Constraints:

x + y ≥ 5
x ≥ 1
y ≥ 2

Feasible region extends to infinity (upper right)

If maximizing: No maximum (unbounded)

If minimizing: Minimum exists at some vertex

No Feasible Solution

Sometimes constraints are contradictory

Empty feasible region

No solution exists

Example: Impossible Constraints

Constraints:

x + y ≤ 5
x + y ≥ 10

No region satisfies both (no solution)

Real-World Applications

Business: Production planning, resource allocation

Transportation: Shipping routes, delivery scheduling

Agriculture: Crop selection, land use

Nutrition: Diet planning (minimize cost, meet requirements)

Finance: Investment portfolios

Example: Diet Problem

Problem: Minimize cost while meeting nutrition requirements

Variables: x = servings of food A, y = servings of food B

Constraints:

• Minimum calories
• Minimum protein
• Maximum fat
• Non-negative

Objective: Minimize cost C = price_A · x + price_B · y

Special Cases

Multiple optimal solutions: Objective function parallel to constraint

Unique optimal solution: Most common case

Unbounded: Objective can increase/decrease without limit

No solution: Empty feasible region

Practice