Transcription
Linear ProgrammingLecture 2: Introduction to Linear ProgrammingLecture 2: Introduction to Linear ProgrammingLinear Programming1 / 46
1Math 407: Introduction2What is linear programming?3Applications of Linear Programing4Example: Plastic Cup Factory5Introduction to LP Modeling6Graphical Solution of 2D LPs7Introduction to Sensitivity Analysis8The Theory of Linear Economic ModelsProduction ModelsThe Optimal Value Function and Marginal ValuesDuality: The Hidden Hand of the Market Place9LP DualityThe Weak Duality Theorem of Linear ProgrammingLecture 2: Introduction to Linear ProgrammingLinear Programming2 / 46
What is optimization?Lecture 2: Introduction to Linear ProgrammingLinear Programming3 / 46
What is optimization?A mathematical optimization problem is one in which some function is eithermaximized or minimized relative to a given set of alternatives.Lecture 2: Introduction to Linear ProgrammingLinear Programming3 / 46
What is optimization?A mathematical optimization problem is one in which some function is eithermaximized or minimized relative to a given set of alternatives.The function to be minimized or maximized is called the objective function.Lecture 2: Introduction to Linear ProgrammingLinear Programming3 / 46
What is optimization?A mathematical optimization problem is one in which some function is eithermaximized or minimized relative to a given set of alternatives.The function to be minimized or maximized is called the objective function.The set of alternatives is called the feasible region (or constraint region).Lecture 2: Introduction to Linear ProgrammingLinear Programming3 / 46
What is optimization?A mathematical optimization problem is one in which some function is eithermaximized or minimized relative to a given set of alternatives.The function to be minimized or maximized is called the objective function.The set of alternatives is called the feasible region (or constraint region).In this course, the feasible region is always taken to be a subset of Rn (realn-dimensional space) and the objective function is a function from Rn to R.Lecture 2: Introduction to Linear ProgrammingLinear Programming3 / 46
What is linear programming (LP)?Lecture 2: Introduction to Linear ProgrammingLinear Programming4 / 46
What is linear programming (LP)?A linear program is an optimization problem in finitely many variableshaving a linear objective function and a constraint region determinedby a finite number of linear equality and/or inequality constraints.Lecture 2: Introduction to Linear ProgrammingLinear Programming4 / 46
What is linear programming (LP)?Lecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
What is linear programming (LP)?A linear program is an optimization problemLecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
What is linear programming (LP)?A linear program is an optimization problemin finitely many variablesLecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
What is linear programming (LP)?A linear program is an optimization problemin finitely many variableshaving a linear objective functionLecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
What is linear programming (LP)?A linear program is an optimization problemin finitely many variableshaving a linear objective functionand a constraint region determined by afinite number of constraintsLecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
What is linear programming (LP)?A linear program is an optimization problemin finitely many variableshaving a linear objective functionand a constraint region determined by afinite number of constraintsthat are linear equality and/or linear inequality constraints.Lecture 2: Introduction to Linear ProgrammingLinear Programming5 / 46
A linear function of the variables x1 , x2 , . . . , xn is any function f of the formf (x) c1 x1 c2 x2 · · · cn xnfor fixed ci R i 1, . . . , n.Lecture 2: Introduction to Linear ProgrammingLinear Programming6 / 46
A linear function of the variables x1 , x2 , . . . , xn is any function f of the formf (x) c1 x1 c2 x2 · · · cn xnfor fixed ci R i 1, . . . , n.A linear equality constraint is any equation of the forma1 x1 a2 x2 · · · an xn α,where α, a1 , a2 , . . . , an R.Lecture 2: Introduction to Linear ProgrammingLinear Programming6 / 46
A linear function of the variables x1 , x2 , . . . , xn is any function f of the formf (x) c1 x1 c2 x2 · · · cn xnfor fixed ci R i 1, . . . , n.A linear equality constraint is any equation of the forma1 x1 a2 x2 · · · an xn α,where α, a1 , a2 , . . . , an R.A linear inequality constraint is any inequality of the forma1 x1 a2 x2 · · · an xn α,ora1 x1 a2 x2 · · · an xn α,where α, a1 , a2 , . . . , an R.Lecture 2: Introduction to Linear ProgrammingLinear Programming6 / 46
Compact Representationmaximizec 1 x1 c 2 x2 · · · c n xnsubject toai1 xi ai2 x2 · · · ain xn αii 1, . . . , sbi1 xi bi2 x2 · · · bin xn βii 1, . . . , r .Lecture 2: Introduction to Linear ProgrammingLinear Programming7 / 46
Vector Inequalities: ComponentwiseLet x, y Rn . x x1x2.xn y y1y2.yn We write x y if and only ifxi yi , i 1, 2, . . . , n .Lecture 2: Introduction to Linear ProgrammingLinear Programming8 / 46
Matrix Notationc 1 x1 c 2 x2 · · · c n xn c T x c Lecture 2: Introduction to Linear Programmingc1c2.cn x Linear Programmingx1x2.xn 9 / 46
Matrix Notationai1 xi ai2 x2 · · · ain xn αi i 1, . . . , s Ax a A Lecture 2: Introduction to Linear Programminga11a21.a12a22.a1na2n.as1as2.asn Linear Programming a α1α2.αs 10 / 46
Matrix Notationbi1 xi bi2 x2 · · · bin xn βii 1, . . . , r Bx b B Lecture 2: Introduction to Linear Programmingb11b21.b12b22.b1nb2n.br 1br 2.brn Linear Programming b β1β2.βr 11 / 46
LP’s Matrix Notationmaximizesubject toLecture 2: Introduction to Linear ProgrammingcT xAx a and Bx bLinear Programming12 / 46
LP’s Matrix NotationcT xAx a and Bx bmaximizesubject to c1α1 . .c . , a .cnαs a11 . . . a1n .A , B.as1Lecture 2: Introduction to Linear Programming.asn β1 . , b . .βr b11 . . . b1n . .br 1 . . . brnLinear Programming 12 / 46
Applications of Linear ProgramingA very short list:Lecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousingLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designtransportation schedulingLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designtransportation schedulingfacility locationLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designtransportation schedulingfacility locationsupply chain managementLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designtransportation schedulingfacility locationsupply chain managementModel selectionLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationproduction schedulingwarehousinglayout designtransportation schedulingfacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingwarehousinglayout designtransportation schedulingfacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousinglayout designtransportation schedulingfacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designtransportation schedulingfacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingfacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingcurrency exchange arbitragefacility locationsupply chain managementModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingcurrency exchange arbitragefacility locationsupply chain managementcrop schedulingModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingcurrency exchange arbitragefacility locationsupply chain managementcrop schedulingdiet balancingModel selectionMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingcurrency exchange arbitragefacility locationsupply chain managementcrop schedulingModel selectionparameter estimationdiet balancingMachine LearningLecture 2: Introduction to Linear ProgrammingLinear Programming13 / 46
Applications of Linear ProgramingA very short list:resource allocationCompressed sensingproduction schedulingflight crew schedulingwarehousingportfolio optimizationlayout designcash flow matchingtransportation schedulingcurrency exchange arbitragefacility locationsupply chain managementcrop schedulingModel selectionparameter estimationMachine Learning.Lecture 2: Introduction to Linear Programmingdiet balancingLinear Programming13 / 46
Example: Plastic Cup FactoryA local family-owned plastic cup manufacturer wants to optimize their productionmix in order to maximize their profit. They produce personalized beer mugs andchampagne glasses. The profit on a case of beer mugs is 25 while the profit on acase of champagne glasses is 20. The cups are manufactured with a machinecalled a plastic extruder which feeds on plastic resins. Each case of beer mugsrequires 20 lbs. of plastic resins to produce while champagne glasses require 12lbs. per case. The daily supply of plastic resins is limited to at most 1800 pounds.About 15 cases of either product can be produced per hour. At the moment thefamily wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming14 / 46
Example: Plastic Cup FactoryA local family-owned plastic cup manufacturer wants to optimize their productionmix in order to maximize their profit. They produce personalized beer mugs andchampagne glasses. The profit on a case of beer mugs is 25 while the profit on acase of champagne glasses is 20. The cups are manufactured with a machinecalled a plastic extruder which feeds on plastic resins. Each case of beer mugsrequires 20 lbs. of plastic resins to produce while champagne glasses require 12lbs. per case. The daily supply of plastic resins is limited to at most 1800 pounds.About 15 cases of either product can be produced per hour. At the moment thefamily wants to limit their work day to 8 hours.Model this problem as an LP.Lecture 2: Introduction to Linear ProgrammingLinear Programming14 / 46
LP ModelingThe four basic steps of LP modeling.Lecture 2: Introduction to Linear ProgrammingLinear Programming15 / 46
LP ModelingThe four basic steps of LP modeling.1Identify and label the decision variables.Lecture 2: Introduction to Linear ProgrammingLinear Programming15 / 46
LP ModelingThe four basic steps of LP modeling.1Identify and label the decision variables.2Determine the objective and use the decision variables to write an expressionfor the objective function as a linear function of the decision variables.Lecture 2: Introduction to Linear ProgrammingLinear Programming15 / 46
LP ModelingThe four basic steps of LP modeling.1Identify and label the decision variables.2Determine the objective and use the decision variables to write an expressionfor the objective function as a linear function of the decision variables.3Determine the explicit constraints and write a functional expression for eachof them as a linear equation/inequality in the decision variables.Lecture 2: Introduction to Linear ProgrammingLinear Programming15 / 46
LP ModelingThe four basic steps of LP modeling.1Identify and label the decision variables.2Determine the objective and use the decision variables to write an expressionfor the objective function as a linear function of the decision variables.3Determine the explicit constraints and write a functional expression for eachof them as a linear equation/inequality in the decision variables.4Determine the implicit constraints and write them as a linearequation/inequality in the decision variables.Lecture 2: Introduction to Linear ProgrammingLinear Programming15 / 46
Decision VariablesDetermining the decision variables is the most difficult part of modeling.Lecture 2: Introduction to Linear ProgrammingLinear Programming16 / 46
Decision VariablesDetermining the decision variables is the most difficult part of modeling.To determining these variables it is helpful to put yourself in the shoes of thedecision maker, then ask What must he or she know to do their job.Lecture 2: Introduction to Linear ProgrammingLinear Programming16 / 46
Decision VariablesDetermining the decision variables is the most difficult part of modeling.To determining these variables it is helpful to put yourself in the shoes of thedecision maker, then ask What must he or she know to do their job.In the real world, the modeler often follows the decision maker around for days,weeks, even months at a time recording all of the actions and decisions thisperson must make.Lecture 2: Introduction to Linear ProgrammingLinear Programming16 / 46
Decision VariablesDetermining the decision variables is the most difficult part of modeling.To determining these variables it is helpful to put yourself in the shoes of thedecision maker, then ask What must he or she know to do their job.In the real world, the modeler often follows the decision maker around for days,weeks, even months at a time recording all of the actions and decisions thisperson must make.In this phase of modeling, it is very important to resist the temptation to makeassumptions about the nature of the solution.Lecture 2: Introduction to Linear ProgrammingLinear Programming16 / 46
Decision VariablesDetermining the decision variables is the most difficult part of modeling.To determining these variables it is helpful to put yourself in the shoes of thedecision maker, then ask What must he or she know to do their job.In the real world, the modeler often follows the decision maker around for days,weeks, even months at a time recording all of the actions and decisions thisperson must make.In this phase of modeling, it is very important to resist the temptation to makeassumptions about the nature of the solution.This last point cannot be over emphasized. Even the most experienced modelersoccasionally fall into this trap since such assumptions can enter in very subtleways.Lecture 2: Introduction to Linear ProgrammingLinear Programming16 / 46
Decision VariablesA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming17 / 46
Decision VariablesA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.B number of cases of beer mugs produced dailyLecture 2: Introduction to Linear ProgrammingLinear Programming17 / 46
Decision VariablesA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.B number of cases of beer mugs produced dailyC number of cases of champagne glasses produced dailyLecture 2: Introduction to Linear ProgrammingLinear Programming17 / 46
Objective FunctionA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming18 / 46
Objective FunctionA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Maximize Profit:Lecture 2: Introduction to Linear ProgrammingLinear Programming18 / 46
Objective FunctionA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Maximize Profit: Profit Revenue CostsLecture 2: Introduction to Linear ProgrammingLinear Programming18 / 46
Objective FunctionA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Maximize Profit: Profit Revenue CostsProfit 25B 20CLecture 2: Introduction to Linear ProgrammingLinear Programming18 / 46
Explicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming19 / 46
Explicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Resin:Lecture 2: Introduction to Linear ProgrammingLinear Programming19 / 46
Explicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Resin: 20B 12C 1800Lecture 2: Introduction to Linear ProgrammingLinear Programming19 / 46
Explicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Resin: 20B 12C 1800Labor:Lecture 2: Introduction to Linear ProgrammingLinear Programming19 / 46
Explicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Resin: 20B 12C 1800Labor: B/15 C /15 8Lecture 2: Introduction to Linear ProgrammingLinear Programming19 / 46
Implicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming20 / 46
Implicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Lecture 2: Introduction to Linear ProgrammingLinear Programming20 / 46
Implicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The cups are manufactured with a machine called a plasticextruder which feeds on plastic resins. Each case of beer mugs requires 20 lbs. of plasticresins to produce while champagne glasses require 12 lbs. per case. The daily supply ofplastic resins is limited to at most 1800 pounds. About 15 cases of either product can beproduced per hour. At the moment the family wants to limit their work day to 8 hours.Implicit Constraints:The decision variables are non-negative:Lecture 2: Introduction to Linear ProgrammingLinear Programming20 / 46
Implicit ConstraintsA local family-owned plastic cup manufacturer wants to optimize their production mix inorder to maximize their profit. They produce personalized beer mugs and champagneglasses. The profit on a case of beer mugs is 25 while the profit on a case ofchampagne glasses is 20. The
Lecture 2: Introduction to Linear Programming Linear Programming 3 / 46. What is linear programming (LP)? A linear program is an optimization problem in nitely many variables having a linear objective function and a constraint region determined by a nite number of linear equality and/or inequality constraints.
