Example: The Lego Production Problem

• Linear Programming

A Production Problem

• Weekly supply of raw materials:

• 6 Large Bricks

• 8 Small Bricks

• Products:

• Table Chair
• Profit = $20/Table Profit = $15/Chair

Linear Programming

• Linear programming uses a mathematical model to find the best allocation of scarce resources to various activities so as to maximize profit or minimize cost.

• 0

• 0

• Tables

• Chairs

• 15 * (2 chairs) + 20 * (0 Tables) = $ 30.00

• 15 * (2 chairs) + 20 * (2 Tables) = $ 70.00

Components of a Linear Program

• Decision variables
• Changing cells
• Objective function
• Target cell
• Constraints

Four Assumptions of Linear Programming

• Linearity
• Divisibility
• Certainty
• Nonnegativity

Why Use Linear Programming?

• Linear programs are easy (efficient) to solve
• The best (optimal) solution is guaranteed to be found (if it exists)
• Useful sensitivity analysis information is generated
• Many problems are essentially linear

Mathematical Statement of a Linear Programming Problem

• In symbolic form, the linear programming model is:
• Choose values of the decision variables x1, x2, … , xn to

• for known parameters c1, … , cn ; a11, … , amn ; b1, … , bm.

The Graphical Method for Solving Linear Programs

• Formulate the problem as a linear program
• Plot the constraints
• Identify the feasible region
• Draw an imaginary line parallel to the objective function (Z=a)
• Find the optimal solution