Linear Programming

Definition

Linear Programming is a mathematical technique used to find the best possible outcome in a given mathematical model where the requirements are represented by linear relationships. The word linear simply means that all the equations involve straight-line graphs, and programming means planning or allocating resources.

Expert Definitions:

• H.A. Taha: Linear Programming is a technique that helps in resource allocation decisions through the use of mathematical models, aiming to maximize or minimize a linear objective function subject to linear constraints.
• George B. Dantzig (Father of Linear Programming): An efficient procedure for choosing the best option out of a massive set of possible alternatives when the problem can be expressed using linear inequalities.

Explanation

• At its core, linear programming takes a real-world problem, translates it into math, and solves it. It always involves two main ingredients: something you want to optimize (like maximizing profit or minimizing cost) and limits or restrictions that you must obey (like running out of raw materials or labor hours).
• The relationships between variables must always be linear, meaning they form straight lines on a graph.
• There is always a clear goal, known as optimization, and limiting factors, known as constraints.
• Solutions must always be non-negative because you cannot produce a negative number of items.

Examples

• A furniture maker wants to decide how many tables and chairs to build to maximize profit, given limited wood and working hours.
• A shipping company wants to determine the cheapest route to deliver packages across five cities while respecting delivery time windows.

Real-Life Uses

• Logistics and Delivery Planning: Major shipping companies like FedEx or Amazon use linear programming every single day to optimize delivery truck routes by factoring in traffic, package weights, fuel costs, and delivery time limits.
• Diet and Nutrition Planning: Hospitals and school cafeterias use linear programming to design meal plans that provide maximum nutrition at the minimum possible cost.

Common Misconceptions and Corrections

• Misconception: Linear programming is only useful for large factories and businesses.
  Correction: While corporations use it heavily, the same logic applies to personal budgeting, studying schedules, and daily time management.
• Misconception: The word programming means writing software code.
  Correction: In this context, programming comes from military logistics planning from the mid-twentieth century, meaning schedule or plan.

Concise Takeaway

Linear programming is simply smart resource planning using straight-line math to get the best result within strict limits.

Definition

Constraints are the restrictions, limits, or boundaries placed on a problem that limit how far you can push your goal.

Expert Definitions:

• Kanti Swarup: Constraints are mathematical inequalities or equations that represent the physical limitations of resources available to the decision-maker.
• Richard Bronson: Constraints are conditions that must be satisfied by the solution of an optimization problem.

Explanation

• Think of constraints as the rules of a game. In real life, if you only have ten hours to study for two exams, your total available study time is a constraint.
• They are usually written as mathematical inequalities using symbols like less than or equal to ($\le$), or greater than or equal to ($\ge$).
• They define what is physically or practically possible, including non-negativity restrictions.

Examples

• The total hours spent cutting and painting wood cannot exceed forty hours a week.
• You cannot use more than two hundred kilograms of flour per day.

Real-Life Uses

• Manufacturing Capacity: An automobile factory has only one assembly line that can run for a maximum of sixteen hours a day. That daily time limit is a physical constraint that stops them from producing an infinite number of cars.

Common Misconceptions and Corrections

• Misconception: Constraints can always be broken if you try hard enough.
  Correction: Mathematical constraints represent absolute physical or financial walls that cannot be crossed.

Concise Takeaway

Constraints are your boundaries and limitations.

Definition

The objective function is a linear mathematical expression that describes the goal of the problem, which is either to be maximized or minimized.

Expert Definitions:

• Handy A. Taha: The objective function is the linear function of the decision variables that represents the performance measure, such as profit or cost, to be optimized.
• Sharma: The objective function is a mathematical representation of the goal of the decision maker in terms of the decision variables.

Explanation

• This is your ultimate target. If you run a business, your objective function is your profit equation. If you run a transport network, your objective function is your total cost equation.
• It contains decision variables multiplied by their respective coefficients and is usually labeled with the letter $Z$.

Examples

• $Z = 50X + 80Y$, representing total profit where $X$ and $Y$ are the numbers of items produced.
• $Z = 10X + 15Y$, representing total shipping costs.

Real-Life Uses

• Financial Investment Portfolios: Investment firms use an objective function to maximize total expected portfolio return while keeping risk below a certain threshold.

Common Misconceptions and Corrections

• Misconception: You can have multiple objective functions in standard linear programming.
  Correction: Standard linear programming solves for one specific objective at a time.

Concise Takeaway

The objective function is the math equation for your main goal.

Definition

Optimization is the act of finding the best possible solution from all the feasible alternatives.

Expert Definitions:

• Hillier and Lieberman: Optimization refers to the process of finding the conditions that give the maximum or minimum value of a function.
• Winston: Optimization is the analytical methodology used to select the best course of action among several choices.

Explanation

• Optimization means refusing to settle for just okay. It means finding the absolute peak of a mountain or the lowest point of a valley.
• It involves either maximization or minimization, relying completely on the objective function and constraints working together.

Examples

• Finding the exact airplane seating arrangement that maximizes airline revenue per flight.
• Finding the exact chemical mix that minimizes production waste.

Real-Life Uses

• Smart Grid Energy Distribution: Power companies use optimization algorithms to route electricity from solar, wind, and coal plants to neighborhoods in real-time, matching supply with demand at the lowest operational cost.

Common Misconceptions and Corrections

• Misconception: Optimization always means making things as large as possible.
  Correction: Optimization often means minimizing costs, travel times, or errors.

Concise Takeaway

Optimization means achieving the absolute best outcome.

Definition

Mathematical formulation is the process of translating a real-world word problem into a structured system of mathematical equations and inequalities.

Expert Definitions:

• Gass: Mathematical formulation is the translation of verbal descriptions of a problem into a precise mathematical format consisting of an objective function and constraints.
• Taha: Formulation is the art of building a mathematical model that adequately represents the core aspects of a real-life situation.

Explanation

• This is where you act like a translator, converting a story problem about a farmer into variables, an objective function, and constraint inequalities.
• Steps include: identifying decision variables ($X, Y$), writing the objective function, writing constraints, and including non-negativity restrictions.

Examples

• Converting a word problem about baking cakes and cookies into $Z = 5X + 4Y$ subject to $2X + Y \le 10$.

Real-Life Uses

• Urban City Planning: City planners formulate traffic flow problems mathematically to decide where to install new traffic lights to minimize congestion.

Common Misconceptions and Corrections

• Misconception: Formulation is just guessing numbers until something fits.
  Correction: Formulation is a rigid, systematic translation of English sentences into algebraic logic.

Concise Takeaway

Formulation turns word problems into math equations.

Definition

The graphical method is a visual technique used to solve linear programming problems that involve only two decision variables by drawing lines on a coordinate plane.

Expert Definitions:

• Render and Stair: The graphical method is a visual approach to finding the optimal solution to a two-variable linear programming problem by plotting constraint lines on a graph.
• Kapoor: Graphical representation allows the decision-maker to see the feasible region and inspect corner points to find the optimal solution visually.

Explanation

• If your problem only has two variables ($X$ and $Y$), you can draw it on graph paper. Each constraint becomes a shaded line. Where all overlapping regions meet is your playground of valid choices.
• Limited strictly to problems with two (or sometimes three) variables.

Examples

• Solving a manufacturing problem involving tables and chairs on a standard coordinate grid.

Real-Life Uses

• Small Business Production Planning: A local print shop owner with two types of printing machines uses a quick sketch on a whiteboard to figure out how many posters and flyers to print each day.

Common Misconceptions and Corrections

• Misconception: You can use the graphical method for problems with five or ten different variables.
  Correction: You cannot draw graphs in more than three dimensions, so the graphical method stops working past two or three variables.

Concise Takeaway

The graphical method lets you draw and see the solution on a flat plane.

Definition

The feasible region is the area on a graph where all constraints are satisfied simultaneously, while the infeasible region is any area that violates at least one constraint.

Expert Definitions:

• Hamdy Taha: The feasible region consists of all the points that satisfy all the constraints of the linear programming model, including non-negativity.
• Bazaraa: The set of all feasible solutions defines the feasible region or constraint set of the mathematical program.

Explanation

• The feasible region is the safe zone where all rules are followed. The infeasible region is outside the boundary lines where you get disqualified.
• Can be bounded (closed shape) or unbounded (stretches infinitely). Infeasible problems have no overlapping region.

Examples

• On a graph of work hours and material limits, the shaded triangle where all lines cross is the feasible region.

Real-Life Uses

• Airspace Sector Management: Air traffic controllers define geographical flight corridors. Planes must stay within these designated spatial corridors, which represent the feasible region of the sky.

Common Misconceptions and Corrections

• Misconception: The optimal solution can lie anywhere in the infeasible region.
  Correction: Solutions outside the feasible region break the rules and are totally useless.

Concise Takeaway

Feasible means allowed; infeasible means forbidden.

Definition

A feasible solution is any single combination of variables that satisfies all constraints, whereas the optimal solution is that one special feasible solution that gives the absolute best value for the objective function.

Expert Definitions:

• Anderson, Sweeney, and Williams: A feasible solution is any set of decision variables that satisfies all the constraints, and the optimal solution is the feasible solution that provides the most favorable value for the objective function.
• Hadley: Any vector satisfying the constraints is a feasible solution, and one that optimizes the objective function is an optimal solution.

Explanation

• A feasible solution is any job offer that pays your bills. The optimal solution is the single best job offer that pays the highest salary.
• The optimal solution always lies on one of the corner points of the feasible region.

Examples

• Making three tables and four chairs is a feasible solution. Making five tables and two chairs is the optimal solution that yields maximum profit.

Real-Life Uses

• Supply Chain Warehouse Placement: Every single location meeting zoning laws is a feasible solution. The one specific city location that minimizes total shipping costs is the optimal solution.

Common Misconceptions and Corrections

• Misconception: The optimal solution is always right in the exact middle of the feasible region.
  Correction: The optimal solution almost always sits right on the boundary edge or a corner point of the feasible region.

Concise Takeaway

Many choices are feasible, but only one is optimal.

Problem 1

A toy company manufactures two types of toys: Car ($X$) and Train ($Y$). Each Car takes 2 hours of machine time and 1 hour of finishing time. Each Train takes 1 hour of machine time and 3 hours of finishing time. The total available machine time per day is 100 hours, and the total available finishing time per day is 90 hours. The company makes a profit of $4 on each Car and $3 on each Train. Find the number of Cars and Trains the company should produce to maximize total profit.

Step-by-Step Solution

• Step 1: Identify the Decision Variables
  Let $X$ be the number of Cars produced.
  Let $Y$ be the number of Trains produced.
• Step 2: Write down the Objective Function
  Maximize $Z = 4X + 3Y$
• Step 3: Write down the Constraints
  Machine time constraint: $2X + Y \le 100$
  Finishing time constraint: $X + 3Y \le 90$
  Non-negativity constraints: $X \ge 0, Y \ge 0$
• Step 4: Convert Inequalities to Equations to Find Intercepts
  - For $2X + Y = 100$: If $X=0 \implies Y=100$ $(0, 100)$; If $Y=0 \implies X=50$ $(50, 0)$.
  - For $X + 3Y = 90$: If $X=0 \implies Y=30$ $(0, 30)$; If $Y=0 \implies X=90$ $(90, 0)$.
• Step 5: Find the Intersection Point of the Two Lines
  Solve simultaneous equations:
  1) $2X + Y = 100$
  2) $X + 3Y = 90 \implies 2X + 6Y = 180$
  Subtracting equations: $5Y = 80 \implies Y = 16$.
  Substitute $Y = 16$ into Equation 1: $2X + 16 = 100 \implies 2X = 84 \implies X = 42$.
  Intersection point is $(42, 16)$.
• Step 6: Evaluate the Objective Function at All Corner Points
  Corner points: $(0, 0)$, $(50, 0)$, $(0, 30)$, and $(42, 16)$.
  - At $(0, 0)$: $Z = 4(0) + 3(0) = 0$
  - At $(50, 0)$: $Z = 4(50) + 3(0) = 200$
  - At $(0, 30)$: $Z = 4(0) + 3(30) = 90$
  - At $(42, 16)$: $Z = 4(42) + 3(16) = 168 + 48 = 216$
• Step 7: Conclusion
  The maximum profit is $216, which occurs when producing 42 Cars and 16 Trains.

Formulas and Equations

Objective Function: Z = c₁X₁ + c₂X₂ + ... + cₙXₙ
General Constraint: aᵢ₁X₁ + aᵢ₂X₂ + ... + aᵢₙXₙ ≤ (or ≥, =) bᵢ
Non-negativity condition: Xⱼ ≥ 0 for all j
        

Overview

GreenLeaf Organic Juice produces two flagship drinks: Berry Blast ($X$) and Citrus Sun ($Y$). Maximize profit $Z = 5X + 4Y$ subject to apple juice constraint ($2X + Y \le 300$), spring water constraint ($X + 2Y \le 400$), machine hours ($0.5X + Y \le 150$), and non-negativity ($X \ge 0, Y \ge 0$).

Solution & Findings

Using optimization software, the corner points of the feasible region are tested: $(0, 0)$, $(150, 0)$, $(0, 200)$, and $(100, 100)$.

• At $(0, 0)$: Profit = $0
• At $(150, 0)$: Profit = $750
• At $(0, 200)$: Profit = $800
• At $(100, 100)$: Profit = $900

Conclusion: The optimal solution is to produce 100 liters of Berry Blast and 100 liters of Citrus Sun daily, yielding a maximum daily profit of $900.

Modern Tools & Industry Applications

• Python: Utilizing SciPy, PuLP, and Google OR-Tools.
• Microsoft Excel Solver: Built-in spreadsheet optimization.
• IBM ILOG CPLEX: Enterprise-grade logistics software.
• MATLAB Optimization Toolbox: Used by engineers for complex design.

1. What does the term linear mean in linear programming?
   A) The variables are squared
   B) The relationships form straight lines
   C) The problem is solved using computers
   D) There are no constraints
   Answer: B
   Explanation: Linear relationships mean that equations and inequalities graph as straight lines on a coordinate plane.
2. Which of the following represents an objective function?
   A) $2X + 3Y \le 50$
   B) $X \ge 0$
   C) $Z = 10X + 20Y$
   D) $Y = 5$
   Answer: C
   Explanation: An objective function specifies the goal, such as maximizing or minimizing a quantity labeled Z, composed of decision variables.
3. Constraints in a linear programming problem represent:
   A) The ultimate profit goal
   B) Limitations and restrictions on resources
   C) The graphical coordinates
   D) Random guessing values
   Answer: B
   Explanation: Constraints act as boundaries or limits, such as maximum available hours or raw materials.
4. The feasible region is defined as:
   A) The area where all constraints are violated
   B) The area outside the graph axes
   C) The set of all points that satisfy all constraints simultaneously
   D) The point of maximum cost
   Answer: C
   Explanation: The feasible region is the overlapping zone where every single constraint inequality is satisfied.
5. Where does the optimal solution of a linear programming problem always lie?
   A) In the exact center of the graph
   B) At one of the corner points of the feasible region
   C) In the infeasible region
   D) Always at the origin $(0,0)$
   Answer: B
   Explanation: Due to the geometry of linear inequalities, the maximum or minimum value of a linear objective function always occurs at a vertex or corner point.
6. Who is known as the father of linear programming?
   A) Isaac Newton
   B) George B. Dantzig
   C) Albert Einstein
   D) Pythagoras
   Answer: B
   Explanation: George B. Dantzig developed the simplex method and foundational theories of linear programming.
7. Non-negativity constraints mean that:
   A) Variables can be any negative number
   B) Variables must be greater than or equal to zero
   C) Profit must be negative
   D) Equations must be multiplied by zero
   Answer: B
   Explanation: In real-world applications, you cannot produce a negative number of physical items.
8. If a linear programming problem has no feasible region because constraints contradict, it is called:
   A) Unbounded
   B) Infeasible
   C) Optimal
   D) Redundant
   Answer: B
   Explanation: When constraints cannot all be satisfied at once, no feasible region exists.
9. Which modern tool is commonly used to solve linear programming problems in spreadsheets?
   A) Microsoft Word
   B) Microsoft Excel Solver
   C) Adobe Photoshop
   D) Notepad
   Answer: B
   Explanation: Microsoft Excel Solver is a built-in optimization tool designed for linear programming models.
10. In a maximization problem, if the feasible region stretches infinitely without a boundary, the problem is:
    A) Infeasible
    B) Unbounded
    C) Closed
    D) Complete
    Answer: B
    Explanation: An unbounded problem means constraints do not close the region, allowing the objective value to grow infinitely.

1. Define Linear Programming and state its three basic components.
   Answer: Linear Programming is a mathematical technique used to optimize a linear objective function subject to a set of linear constraints and non-negativity restrictions. Its three basic components are decision variables, the objective function, and constraints.
2. Explain why the optimal solution always occurs at a corner point of the feasible region.
   Answer: Because the objective function is linear, its value changes at a constant rate across the coordinate plane. The extreme value on a flat, sloped plane bound by straight constraint lines will always be found at one of the extreme vertices or corner points.
3. What is the difference between a feasible solution and the optimal solution?
   Answer: A feasible solution is any combination of variables that satisfies all constraints (a legal choice). The optimal solution is the specific feasible solution that achieves the absolute best value for the objective function.
4. State two major real-world industry applications of linear programming.
   Answer: Airline crew and flight scheduling to minimize operational costs, and supply chain logistics to find the shortest delivery routes between warehouses and retail stores.
5. What does an infeasible linear programming problem indicate?
   Answer: It indicates that the constraints contradict each other, meaning there is no single point on the graph satisfying all rules simultaneously.
6. Why are non-negativity restrictions essential in mathematical formulation?
   Answer: Decision variables represent physical quantities such as units of products, hours of labor, or quantities of ingredients, none of which can logically be negative.
7. Can the graphical method be used to solve a problem with five decision variables? Why or why not?
   Answer: No. The graphical method is limited to two or three variables because humans cannot draw or visualize four-dimensional or higher-dimensional geometric graphs on a flat 2D surface.
8. What is an objective function in a minimization problem? Provide an example.
   Answer: An objective function in a minimization problem is a linear equation representing a cost or waste metric to be reduced. Example: Minimize $C = 12X + 15Y$.
9. Explain what a redundant constraint is.
   Answer: A redundant constraint is a restriction that does not affect the shape of the feasible region because stricter constraints already cover its limits.
10. How do modern software tools handle linear programming problems with thousands of variables?
    Answer: Modern software uses advanced algorithms like the Simplex method or Interior-Point methods executed on computers to navigate corner points and matrix calculations instantly.

• Linear Programming: Resource planning using straight-line math.
• Constraints: Physical/financial limits and boundaries ($\le, \ge$).
• Objective Function: The main goal equation ($Z = c_1X_1 + c_2X_2$).
• Optimization: Achieving the absolute peak (max) or valley (min).
• Feasible Region: The safe, overlapping zone where all constraints hold true.
• Corner Point Theorem: The optimal solution always sits at a vertex of the feasible region.

Mnemonic for LP Steps (COFE):
C - Constraints (Know your limits)
O - Objective (Know your goal)
F - Formulate (Translate words into math)
E - Evaluate (Test corner points for the optimal answer)

Frequently Confused Concepts:
- Feasible Region vs. Feasible Solution: The region is the entire neighborhood of allowed choices; a feasible solution is one specific house inside that neighborhood.
- Maximization vs. Minimization: Maximization aims for highest profit, while minimization aims for lowest cost/waste.