Linear Programming

Introduction To Linear Programming: 

Introduction To Linear Programming Today many of the resources needed as inputs to operations are in limited supply. Operations managers must understand the impact of this situation on meeting their objectives. Linear programming (LP) is one way that operations managers can determine how best to allocate their scarce resources .

Linear Programming (LP) in OM: 

Linear Programming (LP) in OM There are five common types of decisions in which LP may play a role Product mix Production plan Ingredient mix Transportation Assignment

LP Problems in OM: Product Mix: 

LP Problems in OM: Product Mix Objective To select the mix of products or services that results in maximum profits for the planning period Decision Variables How much to produce and market of each product or service for the planning period Constraints Maximum amount of each product or service demanded; Minimum amount of product or service policy will allow; Maximum amount of resources available

LP Problems in OM: Production Plan: 

LP Problems in OM: Production Plan Objective To select the mix of products or services that results in maximum profits for the planning period Decision Variables How much to produce on straight-time labor and overtime labor during each month of the year Constraints Amount of products demanded in each month; Maximum labor and machine capacity available in each month; Maximum inventory space available in each month

Recognising LP Problems: 

Recognising LP Problems Characteristics of LP Problems in OM A well-defined single objective must be stated. There must be alternative courses of action. The total achievement of the objective must be constrained by scarce resources or other restraints. The objective and each of the constraints must be expressed as linear mathematical functions.

Steps in Formulating LP Problems: 

Steps in Formulating LP Problems 1. Define the objective. (min or max) 2. Define the decision variables. 3. Write the mathematical function for the objective. 4. Write a 1- or 2-word description of each constraint. 5. Write the right-hand side (RHS) of each constraint. 6. Write < , =, or > for each constraint. 7. Write the decision variables on LHS of each constraint. 8. Write the coefficient for each decision variable in each constraint.

Example: LP Formulation: 

Cycle Trends is introducing two new lightweight bicycle frames, the Deluxe and the Professional, to be made from aluminum and steel alloys. The anticipated unit profits are Rs.10 for the Deluxe and Rs.15 for the Professional. The number of kilogram of each alloy needed per frame is summarized on the next slide. A supplier delivers 100 Kgs of the aluminum alloy and 80 Kgs of the steel alloy weekly. How many Deluxe and Professional frames should Cycle Trends produce each week? Example: LP Formulation

Example: LP Formulation: 

Aluminum Alloy Steel Alloy Deluxe 2 3 Professional 4 2 Example: LP Formulation Kilogram of each alloy needed per frame

Example: LP Formulation: 

Example: LP Formulation Define the objective Maximize total weekly profit Define the decision variables x 1 = number of Deluxe frames produced weekly x 2 = number of Professional frames produced weekly Write the mathematical objective function Max Z = 10x 1 + 15x 2

Example: LP Formulation: 

Example: LP Formulation Write a one- or two-word description of each constraint Aluminum available Steel available Write the right-hand side of each constraint 100 80 Write <, =, > for each constraint < 100 < 80

Example: LP Formulation: 

Example: LP Formulation Write all the decision variables on the left-hand side of each constraint x 1 x 2 < 100 x 1 x 2 < 80 Write the coefficient for each decision in each constraint + 2x 1 + 4x 2 < 100 + 3x 1 + 2x 2 < 80

Example: LP Formulation: 

Example: LP Formulation LP in Final Form Max Z = 10x 1 + 15x 2 Subject To 2x 1 + 4x 2 < 100 ( aluminum constraint) 3x 1 + 2x 2 < 80 ( steel constraint) x 1 , x 2 > 0 (non-negativity constraints)

Example: LP Formulation: 

Montana Wood Products manufacturers two-high quality products, tables and chairs. Its profit is Rs. 15 per chair and Rs.21 per table. Weekly production is constrained by available labour and wood. Each chair requires 4 labor hours and 8 sq. feet of wood while each table requires 3 labor hours and 12 Sq. feet of wood. Available wood is 2400 Sq.feet and available labor is 920 hours. Management also requires at least 40 tables and at least 4 chairs be produced for every table produced. To maximize profits, how many chairs and tables should be produced? Example: LP Formulation

Example: LP Formulation: 

Example: LP Formulation Define the objective Maximize total weekly profit Define the decision variables x 1 = number of chairs produced weekly x 2 = number of tables produced weekly Write the mathematical objective function Max Z = 15x 1 + 21x 2

Example: LP Formulation: 

Example: LP Formulation Write a one- or two-word description of each constraint Labor hours available Board feet available At least 40 tables At least 4 chairs for every table Write the right-hand side of each constraint 920 2400 40 4 to 1 ratio Write <, =, > for each constraint < 920 < 2400 > 40 4 to 1

Example: LP Formulation: 

Example: LP Formulation Write all the decision variables on the left-hand side of each constraint x 1 x 2 < 920 x 1 x 2 < 2400 x 2 > 40 4 to 1 ratio  x 1 / x 2 ≥ 4/1 Write the coefficient for each decision in each constraint + 4x 1 + 3x 2 < 920 + 8x 1 + 12x 2 < 2400 x 2 > 40 x 1 ≥ 4 x 2

Example: LP Formulation: 

Example: LP Formulation LP in Final Form Max Z = 15x 1 + 21x 2 Subject To 4x 1 + 3x 2 < 920 ( labor constraint) 8x 1 + 12x 2 < 2400 ( wood constraint) x 2 - 40 > 0 (make at least 40 tables) x 1 - 4 x 2 > 0 (at least 4 chairs for every table) x 1 , x 2 > 0 (non-negativity constraints)

Example: LP Formulation: 

A Concrete Company produces concrete. Two ingredients in concrete are sand (costs Rs.600 per ton) and gravel (costs Rs.800 per ton). Sand and gravel together must make up exactly 75% of the weight of the concrete. Also, no more than 40% of the concrete can be sand and at least 30% of the concrete be gravel. Each day 2000 tons of concrete are produced. To minimize costs, how many tons of gravel and sand should be purchased each day? Example: LP Formulation

Example: LP Formulation: 

Example: LP Formulation Define the objective Minimize daily costs Define the decision variables x 1 = tons of sand purchased x 2 = tons of gravel purchased Write the mathematical objective function Min Z = 600x 1 + 800x 2

Example: LP Formulation: 

Example: LP Formulation Write a one- or two-word description of each constraint 75% must be sand and gravel No more than 40% must be sand At least 30% must be gravel Write the right-hand side of each constraint .75(2000) .40(2000) .30(2000) Write <, =, > for each constraint = 1500 < 800 > 600

Example: LP Formulation: 

Example: LP Formulation Write all the decision variables on the left-hand side of each constraint x 1 x 2 = 1500 x 1 < 800 x 2 > 600 Write the coefficient for each decision in each constraint + x 1 + x 2 = 1500 + x 1 < 800 x 2 > 600

Example: LP Formulation: 

Example: LP Formulation LP in Final Form Min Z = 600x 1 + 800x 2 Subject To x 1 + x 2 = 1500 ( mix constraint) x 1 < 800 ( mix constraint) x 2 > 600 ( mix constraint ) x 1 , x 2 > 0 (non-negativity constraints)