MthSc 440, H440, 640 – Linear Programminginstructor: Dr. Douglas ShierMartin Hall, O-120phone: (864) 656-1100office hrs: M 1:25-2:25, Tu 12:30-1:30,W 11:15-12:15, or by appointmentemail: [email protected] from the SyllabusHomework: 25%Hour Tests (2): 40%Final exam: 35% (May 3)Learning and practice materials:IClass Notes: MTHSC 440, Linear Programming, CampusCopy Shop.ISupplementary Handouts: formulation andcomputational exercisesCourse OutlineIFormulationsILinear Programming modelsIOptimality conditionsIThe Simplex algorithmIRefinementsIDuality theoryIKKT conditionsISensitivity analysisIDual Simplex algorithmINetwork flow modelsOptimization modelsIare used to find the best configuration of processes,systems, products, etc.Irely on a theory developed primarily in the past 50 yearsIhave been applied to many industrial, financial, biological,and military problems:- refining processes- crew scheduling- forest management- law enforcementIyield a more efficient use of budget/resources or a higherrevenueSuccess storiesSource: http://www.informs.com(see also http://www.ScienceOfBetter.org)Year Company Resulta86 Eletrobras (hydroelectric energy) 43M$ saved90 Taco Bell (human resources) 7.6M$ saved92 Harris semicond. prod. planning 50% → 95% orders “on time”95 GM – Car Rental +50M$96 HP printers — re-designed prod. 2x production99 IBM — supply chain 750M$ saved00 Syngenta — corn production 5M$ saved01 Ford — vehicle prototypes 250M$ savedA simple exampleIYou work at a company that sells food in tin cans and arecharged with designing the next generation can, which is acylinder made of tin.IThe can must contain V = 20 cu. inches of liquid.ICut and solder tin to produce cylindrical cans.ITin is expensive, so we want to use as little as possible.⇒ Design a cylinder with volume V using as little tin (i.e.,total area) as possible.ExamplepfhpfrIf we knew radius r and height h,Ithe volume would be πr2hIqty of tin would be 2πr2+ 2πrhπr2h must be V = 20in3⇒ h =Vπr2Rewrite the quantity of tin as Q(r) = 2πr2+ 2πrVπr2, orQ(r) = 2πr2+2Vr⇒ Find the minimum of Q(r) — a calculus problem!Minimize the quantity of tin0 1 2 3 4 5 6050100150200250pfminalupfradiuspfqalupfinsqr = 1.471 in h =Vπ(1.471)2= 2.942 inYour first optimization modelVariables r: radius of the can’s baseh: height of the canObjective 2πrh + 2πr2(minimize)Constraints πr2h = Vh ≥ 0r ≥ 0Optimization models, in general, haveVariables: Height and radius, number of trucks, etc.— the unknowns of the problem.Constraints: Physical, explicit (V = 20in3), imposed byphysical laws, budget limits, . . .They define all and the only values of the variables thatgive possible solutions.Objective function: what the boss really cares about.Quantity of tin, total cost of trucks, total estimatedrevenue, . . . — a function of the variables.The general optimization problemConsider a vector x ∈ Rnof variables.An optimization problem can be expressed as:P : minimize f0(x)subject to f1(x) ≤ b1f2(x) = b2...fm(x) ≥ bmIn this class we concentrate on linear optimization problems(linear