Linear Programming Virtual Lab

by Kardi Teknomo


How to use LP virtual Lab

1. Input Syntax Guide

Enter your optimization problem using standard math notation.

  • Variables: x1, x2, x, y, etc. (Case sensitive)
  • Constraints: Use <=, >=, or =. End each line with ;
  • Non-Negativity: Non-negativity (x >= 0) is assumed automatically.

Input Format

Maximize: 3x + 4y
Subject to:
x + y <= 10;
2x - y >= 5;

2. How to use this Virtual Lab

This tool uses the Simplex Algorithm to solve problems instantly.

Step A: Define Variables

You can use standard variable names like x, y, z or indexed names like x1, x2. Variable names are case-sensitive.

Step B: Input Syntax

Objective: 
3x + 4y
Constraints (End with ;): 
x + y <= 10;
2x - y >= 5;
x = 3;

Note: Non-negativity constraints (x >= 0, y >= 0) are added automatically by the solver, so you don't need to type them unless you want to be explicit.

3. Understanding the Results

  • Optimal Solution: The specific values for your variables that produce the best Z value.
  • Feasible Region: (2D only) The grey polygon on the chart represents all possible "legal" solutions that satisfy your constraints. The optimal solution is always at one of the corner points.
  • Shadow Price (Duals): Tells you the "marginal value" of a resource. If a constraint has a shadow price of 5, getting 1 more unit of that resource will increase your profit by 5.

4. How to Read the Tableau

The "Simplex Iterations" panel shows the math step-by-step:

  • Rows: Each row represents a constraint equation. The bottom row is the Objective (Z).
  • Columns: Represent your variables (x, y, s1, a1...).
  • Solution Column (RHS): The current value of the basic variables.
  • Goal: The algorithm swaps variables in and out of the "Basis" until no more improvements can be made to Z.
Note on Visualization: The graph/chart is strictly limited to 2 Dimensions (2 Variables). If your problem has 3 or more variables (e.g., x, y, z), the chart will not appear, as it is impossible to draw a 4D+ shape on a standard screen.
Understanding Linear Programming

1. What is Linear Programming (LP)?

Linear Programming is a mathematical method used to determine the best possible outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. It is widely used in business, economics, and engineering for resource allocation.

2. The Three Components of an LP Problem

  • Decision Variables (x, y, x1, etc.): The unknown quantities you want to determine.
    Example: Let x = number of Tables to build, y = number of Chairs to build.
  • Objective Function (Z): The mathematical formula you want to Maximize (profit) or Minimize (cost).
    Example: Maximize Z = 50x + 30y (Profit is \$50 per table, \$30 per chair).
  • Constraints: The limitations or restrictions on resources (time, money, materials).
    Example: 2x + y <= 100 (You only have 100 hours of labor).

3. Key Concepts & Terminology

  • Decision Variables (x, y): The unknown quantities you want to decide (e.g., how many items to produce).
  • Objective Function (Z): The formula to maximize or minimize (e.g., `Max Z = 5x + 3y`).
  • Basis (Basic Variables): In the Simplex method, the "active" variables that have non-zero values. If you have 3 constraints, you will always have 3 basic variables. All other variables are non-basic (set to 0).
  • Slack Variables (s): Added to <= constraints. They represent unused resources. (e.g., if Labor <= 100 and you use 90, Slack = 10).
  • Surplus Variables (s): Subtracted from >= constraints. They represent the amount exceeding the minimum requirement.
  • Artificial Variables (a): Temporary mathematical tools added to = or >= constraints to help the solver find a starting point. They must be zero in the final real solution.
The "Standard Form" Trick

Computers cannot solve inequalities (<=). They can only solve algebraic equations (=). To use the Simplex method, we must convert the problem into Standard Form.

1. Slack Variables (+s)

Used for <= constraints. It represents "unused resources".

            Original:  2x + y <= 10  (Labor limit)
            Standard:  2x + y + s1 = 10
            If x=2, y=2, then 4+2=6. So s1=4 (4 hours of idle time).

2. Surplus Variables (-e)

Used for >= constraints. It represents "excess over minimum".

            Original:  x + y >= 20   (Minimum production)
            Standard:  x + y - e1 = 20

3. Artificial Variables (a)

These are "mathematical crutches" added to = or >= constraints to help the computer find a valid starting point. They have a huge penalty cost (Big M) so the solver tries to get rid of them immediately.

Simplex vs. Interior Point (Karmarkar)

The "Dark Room" Analogy

Imagine you are in a pitch-black room filled with obstacles, and your goal is to find the highest point in the room (the optimal solution).

1. The Simplex Method (The Wall Follower)

  • Strategy: You walk until you hit a wall (constraint). Then, you feel your way along the wall until you hit a corner. You then switch to a new wall that goes "uphill." You keep moving from corner to corner until no path goes up anymore.
  • Visuals: In the chart, you will see the path jump from one vertex (corner) of the polygon to the next.
  • Pros: It yields an exact solution and provides sensitivity analysis (Shadow Prices).
  • Cons: In massive problems (millions of variables), checking every corner takes too long.

2. Interior Point / Karmarkar's Method (The Path Finder)

  • Strategy: Instead of hugging the walls, you start in the exact center of the room. You calculate the gradient (the direction of steepest ascent) and take a step through the open space. You use a mathematical "barrier" to ensure you never crash into a wall, but get infinitely close to the best corner.
  • Visuals: In the chart, you will see a curved line cutting through the middle of the grey polygon, landing near the optimal corner.
  • Pros: Extremely fast for huge problems.
  • Cons: The solution is often approximate (e.g., 3.99999 instead of 4), and it doesn't naturally provide Shadow Prices.
Reading the Sensitivity Report

Real-world numbers (prices, costs, available hours) change constantly. The Sensitivity Report tells you how stable your solution is before you need to re-calculate everything.

1. Adjustable Cells (Objective Coefficients)

This analyzes your profit margins or costs (e.g., "Profit per Unit").

  • The Question: "How much can the price change before I need to change what I build?"
  • Allowable Increase/Decrease: The range in which the Optimal Basis (the mix of x, y variables) stays exactly the same.
  • Example: If Profit = $50 and Allowable Decrease = $5:
    • If profit drops to $46 ($4 drop): Keep building the same number of units. Your total money drops, but the plan is still the best one possible.
    • If profit drops to $40 ($10 drop): The range is broken. You must re-solve; you likely need to stop making this product.

2. Constraints (RHS Ranges)

This analyzes your resources (e.g., "Total Labor Hours").

  • The Question: "How far does the Shadow Price hold true?"
  • Allowable Increase/Decrease: The range in which the Shadow Price remains constant.
  • Example: If Labor Shadow Price = $15 and Allowable Increase = 10 hours:
    • If you buy 5 extra hours: You gain exactly 5 * $15 = $75.
    • If you buy 20 extra hours: You exceed the range. The bottleneck will shift (maybe you run out of wood instead), and the extra hours will be worth less than $15 (or $0).
LP Real-World Applications

Linear Programming is the "invisible engine" behind modern efficiency. It is used whenever you have limited resources and a clear goal.

🚚 Logistics & Routing

Problem: Amazon or UPS delivering packages.
Goal: Minimize fuel cost & time.
Constraints: Truck capacity, driver hours, delivery windows.

🏭 Manufacturing (Product Mix)

Problem: A factory makes Phones and Tablets.
Goal: Maximize Profit.
Constraints: Available chips, screens, and assembly workers.

🍎 Diet & Blending

Problem: Creating cattle feed or metal alloys.
Goal: Minimize Cost.
Constraints: Must meet minimum nutritional (protein/vitamins) or chemical specifications.

⚡ Energy Grid

Problem: Power plants generating electricity.
Goal: Minimize generation cost.
Constraints: Power demand, transmission line limits, green energy quotas.

When LP is NOT Suitable (Limitations)

The Three "Linear" Assumptions

If your problem breaks these rules, you cannot use standard Linear Programming.

1. Linearity (No "Economies of Scale")

LP assumes that if 1 unit costs \$10, then 10 units cost \$100.
Failure case: Bulk discounts. If buying 1000 units drops the price to \$8/unit, the relationship is non-linear. You need Non-Linear Programming (NLP).

2. Divisibility (No "Half-Cars")

LP assumes variables can be decimals. The solver might tell you to build 3.5 bridges or hire 10.2 people.
Failure case: If you need whole numbers (integers), you cannot just round the result (rounding can make the solution infeasible). You need Integer Linear Programming (ILP).

3. Certainty (No "Maybe")

LP assumes constraints are fixed facts (e.g., "Demand is exactly 100").
Failure case: If demand fluctuates or stock prices are random, you need Stochastic Programming.

A Brief History of Linear Programming

1. The Birth of Simplex (1947)

George Dantzig developed the Simplex Algorithm shortly after World War II to solve logistics planning problems for the US Air Force.

  • The Concept: Dantzig realized that the optimal solution to a linear problem always lies at a "corner" (vertex) of the feasible region.
  • The Algorithm: Simplex works by starting at one corner and "walking" along the edges to adjacent corners, improving the result with every step until the peak is reached.
  • Impact: It became one of the most important algorithms of the 20th century, enabling modern supply chains and industrial planning.

2. The Klee-Minty Cube (1972)

For decades, Simplex seemed unbeatable. However, in 1972, mathematicians Victor Klee and George Minty published a paper that shattered the assumption of perfection.

  • The Counter-Example: They constructed a specific problem (a "deformed hypercube") that forced the Simplex algorithm to visit every single corner of the shape before finding the answer.
  • The Result: They proved that in the worst-case scenario, Simplex has exponential time complexity. If you double the variables, the time to solve could double repeatedly, making massive problems theoretically unsolvable by Simplex.

3. Karmarkar & Wall Street (1984)

The search for a faster, "Polynomial Time" algorithm concluded at Bell Labs with Narendra Karmarkar.

  • Interior Point Method: Unlike Simplex, which hugs the outer edges of the shape, Karmarkar's algorithm cuts through the interior (the middle) of the feasible region.
  • Performance: It was proven to solve problems in polynomial time ($O(n^{3.5})$), meaning it scales far better for massive datasets than the worst-case Simplex.
  • The "Black Box": The algorithm was so efficient that it was quickly adopted by Wall Street for portfolio optimization and by airlines for crew scheduling. It was even patented, creating a "black box" solver that gave proprietary advantages to financial firms in the 80s.
LPv4.3

Problem Setup