Linear programming: A method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships.
- Identify the decision variables
- Translate constraints into inequalities
- Formulate the system of inequalities
- Find a feasible solution
- Verify the solution
Let x = number of croissants, y = number of muffins
Croissants need 0.2 hours, muffins need 0.1 hours
Total labor: 0.2x + 0.1y ≤ 10
Croissants need 0.1 kg, muffins need 0.15 kg
Total flour: 0.1x + 0.15y ≤ 8
Total pastries: x + y ≥ 20
x ≥ 0 and y ≥ 0 (can't make negative pastries)
Test (30, 20):
Labor: 0.2(30) + 0.1(20) = 6 + 2 = 8 ≤ 10 ✓
Flour: 0.1(30) + 0.15(20) = 3 + 3 = 6 ≤ 8 ✓
Total: 30 + 20 = 50 ≥ 20 ✓
The constraints are: 0.2x + 0.1y ≤ 10, 0.1x + 0.15y ≤ 8, x + y ≥ 20, x ≥ 0, y ≥ 0. A possible plan is 30 croissants and 20 muffins.
• Resource Constraints: Total usage must not exceed availability
• Minimum Requirement: Total production must meet minimum demand
• Non-negativity: Physical quantities cannot be negative
Nutrition constraints: Inequalities that represent minimum nutritional requirements and maximum serving limits.
Let a = servings of food A, b = servings of food B
Food A: 100 cal/serving, Food B: 50 cal/serving
Total calories: 100a + 50b ≥ 400
Food A: 5g/serving, Food B: 8g/serving
Total protein: 5a + 8b ≥ 30
Total servings: a + b ≤ 6
a ≥ 0 and b ≥ 0
Calories: 100(3) + 50(2) = 300 + 100 = 400 ≥ 400 ✓
Protein: 5(3) + 8(2) = 15 + 16 = 31 ≥ 30 ✓
Servings: 3 + 2 = 5 ≤ 6 ✓
Yes, the meal with 3 servings of food A and 2 servings of food B satisfies all nutritional and serving constraints.
• Minimum Requirements: Nutritional needs must be met
• Maximum Limits: Total servings cannot exceed capacity
• Feasibility: Solution must satisfy ALL constraints
Manufacturing constraints: Inequalities that represent limitations on production capacity and minimum output requirements.
Let x = units of product X, y = units of product Y
Product X: 2 hrs, Product Y: 1 hr
Machine A time: 2x + y ≤ 40
Product X: 1 hr, Product Y: 3 hrs
Machine B time: x + 3y ≤ 30
x ≥ 5 (at least 5 units of X)
y ≥ 3 (at least 3 units of Y)
Minimum Y: y = 3
From machine B constraint: x + 3(3) ≤ 30 → x ≤ 21
From machine A constraint: 2x + 3 ≤ 40 → x ≤ 18.5
So x ≤ 18 (since x must be integer)
Machine A: 2(18) + 3 = 39 ≤ 40 ✓
Machine B: 18 + 3(3) = 27 ≤ 30 ✓
Min X: 18 ≥ 5 ✓
Min Y: 3 ≥ 3 ✓
The factory can produce a maximum of 18 units of product X while meeting all constraints (producing 3 units of Y).
• Capacity Constraints: Resource usage must not exceed availability
• Minimum Requirements: Production must meet minimum demands
• Optimization: Maximize one variable while satisfying all constraints
Feasible region: The set of all points that satisfy all constraints in the system.
Linear constraints: Inequalities of the form ax + by ≤ c, ax + by ≥ c, etc.
Objective function: The function to be maximized or minimized in an optimization problem.
Corner point: A vertex of the feasible region where constraints intersect.
- Define variables: Assign symbols to unknown quantities
- Identify constraints: List all limitations and requirements
- Formulate system: Write all constraints as inequalities
- Graph solution: Visualize the feasible region
- Solve: Find solutions that satisfy all constraints
- Optimize: If applicable, find optimal values
Business planning: Resource allocation, production scheduling, budget constraints.
Nutrition planning: Meeting dietary requirements within caloric limits.
Manufacturing: Production optimization under capacity constraints.
Transportation: Routing and scheduling under time and capacity limits.
- Graphical method: Plot constraints and find feasible region
- Algebraic method: Solve system of inequalities
- Corner point method: Evaluate objective at vertices
- Substitution method: Reduce to single variable
• Feasibility: Solution must satisfy ALL constraints simultaneously
• Convexity: Feasible region is always a convex polygon
• Corner Points: Optimal solutions occur at vertices
• Consistency: All constraints must be compatible
Definitions of Key Concepts:
Inequality System: A set of two or more inequalities that must be satisfied simultaneously by the same set of variables.
Feasible Region: The set of all points that satisfy all constraints in the system simultaneously; the intersection of all individual solution regions.
Constraint: A condition or limitation that restricts the possible solutions to a problem; typically expressed as an inequality.
Linear Programming: A mathematical method to optimize a linear objective function subject to linear inequality constraints.
Optimal Solution: The best possible solution that maximizes or minimizes the objective function while satisfying all constraints.
Core Rules and Principles:
Simultaneous Satisfaction: A feasible solution must satisfy ALL constraints in the system simultaneously, not just some of them.
Convexity Principle: The feasible region of a linear inequality system is always a convex polygon (or convex unbounded region).
Optimality at Corners: For linear objective functions, optimal solutions (if they exist) occur at corner points of the feasible region.
Constraint Interaction: Adding more constraints shrinks the feasible region or leaves it unchanged (never expands it).
Step-by-Step Methods and Procedures:
- Problem Analysis: Read the problem carefully and identify all constraints and objectives.
- Variable Definition: Assign variables to unknown quantities with clear definitions.
- Constraint Identification: Identify all limitations and requirements in the problem.
- Mathematical Formulation: Translate each constraint into an inequality using the defined variables.
- System Formation: Combine all constraints into a system of inequalities.
- Graphical Solution: Graph each constraint and find the feasible region (intersection of all solution regions).
- Optimization: If applicable, find the optimal solution by evaluating the objective function at corner points.
- Verification: Check that the solution satisfies all original constraints.
Examples from Simple to Advanced:
Simple Example: A person has $20 to spend on apples ($2 each) and oranges ($1 each). Write constraints for the purchase.
Variables: a = apples, o = oranges
System: a ≥ 0, o ≥ 0, 2a + o ≤ 20
Intermediate Example: A company produces products A and B. A requires 2 hours labor and B requires 1 hour. Total labor available is 100 hours. Also, they must produce at least 20 units of A and 10 of B.
Variables: a = units of A, b = units of B
System: 2a + b ≤ 100, a ≥ 20, b ≥ 10
Advanced Example: A nutritionist wants to create a meal plan with at least 50g protein, 40g carbs, and 20g fat, using foods X and Y with different nutrient contents and cost $3 and $2 per serving respectively, with a maximum of 8 servings total. Minimize cost.
Variables: x = servings of X, y = servings of Y
System: nutrients ≥ requirements, x + y ≤ 8, x ≥ 0, y ≥ 0
Objective: Minimize 3x + 2y
Tips, Tricks, and Common Pitfalls:
Tips:
- Always include non-negativity constraints (x ≥ 0, y ≥ 0) for physical quantities
- Look for key phrases like "at least" (≥), "at most" (≤), "no more than" (≤), "minimum" (≥)
- Organize constraints in a table for complex problems
- Draw a rough sketch of the feasible region to visualize the problem
- Check corner points when optimizing linear functions
Common Pitfalls:
- Forgetting to include all constraints from the problem statement
- Misinterpreting inequality directions (≥ vs ≤)
- Not checking that solutions are feasible for all constraints
- Arithmetic errors when solving systems of inequalities
- Overlooking the need for integer solutions in counting problems
Tricks:
- For maximization, try extreme values within constraints
- For minimization, start with minimum required values
- Use substitution to reduce the number of variables when possible
- Verify solutions by substituting back into all original constraints
Key Notes for Memorization:
Constraint Types: Resource limits (≤), minimum requirements (≥), maximum limits (≤), non-negativity (≥)
Feasible Region: Always convex, intersection of all individual solution regions
Optimization: Linear objectives optimized at corner points of feasible region
Verification: Always substitute solution back into all constraints
Learning Strategies:
Start with simple problems that have 2-3 constraints to understand the basic concepts. Practice translating word problems into mathematical inequalities. Focus on visualizing the feasible region by graphing constraints. Work on problems from various application areas (business, nutrition, manufacturing) to see the versatility of the method.
Pay attention to the relationship between constraints and how they interact. Practice identifying corner points and understanding why optimal solutions occur there. Connect the mathematical solution to the real-world context of the problem.
Questions & Answers
Question: How do I know if a system of inequalities has a feasible solution?
Answer: A system of inequalities has a feasible solution if there exists at least one point that satisfies ALL inequalities simultaneously. Here's how to check:
- Graphical method: Plot all constraints. If there's any region where all constraints overlap, the system is feasible.
- Algebraic method: Try to find a point that satisfies all constraints. If you can find even one such point, the system is feasible.
- Check for contradictions: Look for conflicting constraints (e.g., x ≥ 10 and x ≤ 5).
For example, the system {x ≥ 0, y ≥ 0, x + y ≤ 5, x ≥ 10} is infeasible because no point can satisfy both x ≥ 10 and x + y ≤ 5 when y ≥ 0.
If constraints are too restrictive, no feasible region exists. If they're too loose, the feasible region might be unbounded.
Question: What happens if the feasible region is unbounded? Can I still find an optimal solution?
Answer: Whether you can find an optimal solution depends on what you're optimizing:
- Minimization with unbounded region: May have an optimal solution. For example, minimizing cost with constraints like x ≥ 5, y ≥ 3 has an optimal solution at (5, 3).
- Maximization with unbounded region: Often has no optimal solution. For example, maximizing profit with only minimum constraints like x ≥ 0, y ≥ 0 allows for unlimited growth.
The key is whether the objective function is "pulled" toward a boundary of the feasible region. If the objective function increases indefinitely in the direction the region extends, no maximum exists. However, if it decreases in that direction, a minimum might exist.
In real-world problems, physical constraints usually bound the region, preventing infinite solutions.
Question: Why do optimal solutions occur at corner points of the feasible region?
Answer: This is due to the geometry of linear functions and the properties of convex sets:
- Linear objective function: Its level curves (points of equal value) are straight lines
- Convex feasible region: Any line segment connecting two points in the region lies entirely within the region
- Optimization direction: The objective function increases or decreases most rapidly in a particular direction
When optimizing a linear function over a convex polygon, the function value changes linearly along any edge. Since the function can't have a local optimum in the interior of an edge (due to linearity), optimal values must occur at vertices.
Intuitively, if you imagine sliding a straight line (level curve) in the direction of improvement, it will eventually touch the feasible region only at a corner point, which represents the optimal solution.
This is formalized in the Fundamental Theorem of Linear Programming.