### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# LINEAR OPTIMIZATION MATH 407

UW

GPA 3.76

### View Full Document

## 40

## 0

## Popular in Course

## Popular in Mathematics (M)

This 14 page Class Notes was uploaded by Addison Beer on Wednesday September 9, 2015. The Class Notes belongs to MATH 407 at University of Washington taught by James Burke in Fall. Since its upload, it has received 40 views. For similar materials see /class/192060/math-407-university-of-washington in Mathematics (M) at University of Washington.

## Reviews for LINEAR OPTIMIZATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/09/15

Math 407 7 Linear Optimization 1 Introduction 11 What is optimization A mathematical optimization problem is one in which some function is either maximized or minimized relative to a given set of alternatives The function to be minimized or maximized is called the objective function and 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 R real n dimensional space and the objective function is a function from R to R We further restrict the class of optimization problems that we consider to linear program ming problems or LPs An LP is an optimization problem over R wherein the objective function is a linear function that is the objective has the form 01 C z Cnxn for some 0 E R i 1 n and the feasible region is the set of solutions to a nite number of linear inequality and equality constraints of the form ai1iai2239amn bi 1778 and anxiai2x2amxnbi is1m Linear programming is an extremely powerful tool for addressing a wide range of applied optimization problems A short list of application areas is resource allocation produc tion scheduling warehousing layout transportation scheduling facility location ight crew scheduling portfolio optimization parameter estimation 12 An Example To illustrate some of the basic features of LP we begin with a simple two dimensional example In modeling this example we will review the four basic steps in the development of an LP model H Identify and label the decision variables 3 Determine the objective and use the decision variables to write an expression for the objective function 00 Determine the eaplicit constraints and write a functional expression for each of them 4 Determine the implicit constraints PLASTIC CUP FACTORY A local family owned plastic cup manufacturer wants to optimize their production mix in order to maximize their pro t They produce personalized beer mugs and champaign glasses The pro t on a case of beer mugs is 25 while the pro t on a case of champaign glasses is 20 The cups are manufactured with a machine called a plastic extruder which feeds on plastic resins Each case of beer mugs requires 20 lbs of plastic resins to produce while champaign glasses require 12 lbs 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 the family wants to limit their work day to 8 hours We will model the problem of maximizing the pro t for this company as an LP The rst step in our modeling process is to identify and label the decision variables These are the variables that represent the quanti able decisions that must be made in order to determine the daily production schedule That is we need to specify those quantities whose values completely determine a production schedule and its associated pro t In order to determine these quantities one can ask the question If I were the plant manager for this factory what must I know in order to implement a production schedule77 The best way to identify the decision variables is to put oneself in the shoes of the decision maker and then ask the question What do I need to know in order to make this thing work7 In the case of the plastic cup factory everything is determined once it is known how many cases of beer mugs and champaign glasses are to be produced each day Decision Variables B of cases of beer mugs to be produced daily 0 of cases of champaign glasses to be produced daily You will soon discover that the most dif cult part of any modeling problem is identifying the decision variables Once these variables are correctly identi es then the remainder of the modeling process usually goes smoothly After identifying and labeling the decision variables one can now specify the problem objective That is one can write an expression for the objective function Objective Function Maximize pro t where pro t 25B 200 The next step in the modeling process is to express the feasible region as the solution set of a nite collection of linear inequality and equality constraints We separate this process into two steps 1 determine the explicit constraints and 2 determine the implicit constraints The explicit constraints are those that are explicitly given in the problem statement In the problem under consideration there are explicit constraints on the amount of resin and the number of work hours that are available on a daily basis Emplicit Constraints resin constraint 20B 120 S 1800 work hours constraint B 0 3 8 This problem also has other constraints called implicit constraints These are constraints that are not explicitly given in the problem statement but are present nonetheless Typically these constraints are associated with natural77 or common sense77 restrictions on the deci sion variable In the cup factory problem it is clear that one cannot have negative cases of beer mugs and champaign glasses That is both E and 0 must be non negative quantities Implicit Constraints 0 S B 0 S O The entire model for the cup factory problem can now be succinctly stated as 73 max 25B 200 subject to 20B 120 3 1800 3 T150 8 0 S B O l Since it is an introductory example the Plastic Cup Factory problem is particularly easy to model As the course progresses you will be asked to model problems of increasing dif culty and complexity In this regard let me emphasize again that the rst step in the modeling process identi cation of the decision variables is always the most dif cult In addition the 4 step modeling process outlined above is not intended a process that one steps through in a linear fashion As the model unfolds it is often necessary to revisit earlier steps for example by adding in more decision variables a very common requirement Cycling through these steps several times is often required before the model is complete In this process the greatest stumbling block experienced by students is the overwhelming desire to try to solve the problem as it is being modeled lndeed every student who has taken this course over the last 20 years has made this error and on occasion I continue to make this error myself Perhaps the most common error in this regard is to try to reduce the total number of decision variables required This often complicates the modeling process blocks the ability to fully characterize all of the variability present makes it dif cult to interpret the solution and understand its robustness and makes it dif cult to modify the model as it evolves Never be afraid to add more decision variables either to clarify the model or to improve its exibility Modern LP software easily solves problems with tens of thousands of variables and in some cases tens of millions of variables It is more important to get a correct easily interpretable and exible model then to provide a compact minimalist model 3 We now turn to solving the Plastic Cup Factory problem Since this problem is two dimensional it is possible to provide a graphical representation and solution The rst step is to graph the feasible region To do this7 rst graph 15 20B 120 1800 W 12 7 objective normal 71 solution 45 optimal value 2625 feasible region 1 1 7 2 W MEBE078 1 lllllllll l lllllB 12 3 4 5 6 7 89101 12131415 the line associated with each of the linear inequality constraints Then determine on which side of each of these lines the feasible region must lie dont forget the implicit constraintsl To determine the correct side7 locate a point not on the line that determines the constraint for exarnple7 the origin is often not on the line7 and it is particularly easy to use Plug this point in and see if it satis es the constraint If it does7 then it is on the correct side of the line If it does not7 then the other side of the line is correct Once the correct side is determined put little arrows on the line to remind yourself of the correct side Then shade in the resulting feasible region which is the set of points feasible for all of the linear inequalities The next step is to draw in the vector representing the gradient of the objective function This vector may be placed anywhere on your graph7 but it is often convenient to draw it emanating from the origin Since the objective function has the form f9617 962 01961 02962 the gradient of f is the same at every point in R2 mexz Cl 02 4 Recall from calculus that the gradient always points in the direction of increasing function values Moreover since the gradient is constant on the whole space the level sets of f associated with different function values are given by the lines perpendicular to the gradient Consequently to obtain the location of the point at which the objective is maximized we simply set a ruler perpendicular to the gradient and then move the ruler in the direction of the gradient until we reach the last point or points at which the line determined by the ruler intersects the feasible region In the case of the cup factory problem this gives the solution to the LP as g 71 We now recap the steps followed in the solution procedure given above Step 1 Graph each of the linear constraints indicating on which side of the constraint the feasible region must lie with an arrow Don7t forget the implicit constraints Step 2 Shade in the feasible region Step 3 Draw the gradient vector of the objective function Step 4 Place a straight edge perpendicular to the gradient vector and move the straight edge either in the direction of the gradient vector for maximization or in the oppo site direction of the gradient vector for minimization to the last point for which the straight edge intersects the feasible region The set of points of intersection between the straight edge and the feasible region is the set of solutions to the LP The solution procedure described above for two dimensional problems reveals a great deal about the geometric structure of LPs that remains true in 71 dimensions We will explore this geometric structure more fully as the course evolves For the moment note that the solution to the Plastic Cup Factory problem lies at a corner point of the feasible region Indeed it is easy to convince oneself that every 2 dimensional LP has an optimal solution that is such a corner point The notion of a corner point can be generalized to n dimensional space where it is refered to as a vertex These vertices play a big role in understanding the geometry of linear programming Before leaving this section we make a nal comment on the modeling process described above We emphasize that there is not one and only one way to model the Cup Factory problem or any problem for that matter In particular there are many ways to choose the decision variables for this problem Clearly it is suf cient for the shop manager to know how many hours each day should be devoted to the manufacture of beer mugs and how many hours to champaign glasses From this information everything else can be determined For example the number of cases of beer mugs that get produced is 15 times the number of hours devoted to the production of beer mugs However in the end they should all point to the same optimal process 13 Sensitivity Analysis One of the most important things to keep in mind about real world77 LPs is that the input data associated with the problem speci cation can change over time is subject to mea surernent error and is often the product of educated guesses another name for fudging For example in the case of the cup factory the pro t levels for both beer mugs and charn paign glasses are subject to seasonal variations Prior to the New Year the higher demand for charnpaign glasses forces up the sale price and consequently their pro tability As St Patricks Day approaches the demand for charnpaign glasses drops but the demand for beer rnugs soars In June demand for charnpaign glasses again rises due to the increase in rnar riage celebrations Then just before the Fourth of July the demand for beer rnugs returns These seasonal uctuations may effect the optimal solution and the optimal value A natural question to ask in this regard is What is the smallest pro t level required for charnpaign glasses remain in the optimal production rniX7 or equivalently What is the smallest pro t level at which rnanufacturing charnpaign glasses rernains e cient The lowest level of pro tability for charnpaign glasses to remain in the optimal production mix is called the break even pro t77 for charnpaign glasses Correspondingly the lowest sale price for charnpaign glasses to remain in the optimal production mix is called the break even sale price77 for charnpaign glasses 131 Breakeven Prices The break even price for charnpaign glasses is easily computed Recall that the optimal solu tion is obtained by holding a ruler perpendicular to the objective gradient and then moving the ruler in the direction of the objective gradient to the furthest point at which the line determined by the ruler and the feasible region intersect Thus to determine the break even price for charnpaign glasses we need to determine the smallest tilt of the objective gradi ent for which the optimal solution changes from producing both beer mugs and charnpaign glasses to producing just beer rnugs This occurs when the objective gradient is parallel to any normal to the constraint line associated with the resin bound That is if the objective is fBO a3 60 then we want 04 7 20 B T E where the numbers 20 and 12 are coef cients in the resin constraint Holding 04 xed at 25 we get 12 7 25 15 B 20 That is the break even price for charnpaign glasses is 15 a case Similarly one computes the break even price for beer rnugs by considering the labor hours constraint and arrives at 20 per case of beer rnugs Observe that if we set the per case pro tability of champaign glasses to 15 while keeping the pro tability of beer mugs xed we nd that every point on the line segment connecting the two points and 30 is optimal for the new LP Thus the set of optimal solutions to an LP can be in nite 132 Marginal Values Next we consider the effect of uctuations in the availability of resources on both the optimal solution and the optimal value In the case of the cup factory there are two basic resources consumed by the production process plastic resin and labor hours In order to analyze the behavior of the problem as the value of these resources is perturbed we rst observe a geometric property of the optimal solution namely that the optimal solution lies at a corner point77 or vertex of the feasible region More will be made of the notion of a vertex later but for the moment suf ce it to say that if an optimal solution to an LP exists then there is at least one optimal solution that is a vertex of the feasible region Next note that as the availability of a resource is changed the constraint line associated with that resource moves in a parallel fashion along a line normal to the constraint Thus at least for a small range of perturbations to the resources the vertex associated with the current optimal solution moves but remains optimal We caution that this is only a generic property of an optimal vertex and there are examples for which it fails For example the feasible region can be made empty under arbitrarily small perturbations of the resources These observations lead us to conjecture that the solution to the LPs l6162 max 25B 200 subject to 20B 120 3 1800 61 1 1 EB 0 E 9 62 0 g B 0 lies at the intersection of the two lines 20B 120 1800 61 and 1175B 0 8 62 for small values of 61 and 62 namely B 4576261 C 75 77562 7 el and 06162 2625 62 261 It can be veri ed by direct computation that this indeed yields the optimal solution for small values of 61 and 62 Next observe that the value 161 62 can now be viewed as a function of 61 and 62 and that this function is differentiable at g with WWW 3392 l 39 7 The number 2 is called the marginal value of the resin resource at the optimal solution 2 71 and the number L5 is called the marginal value of the labor time resource at the optimal solution We have the following interpretation for these marginal values each additional pound of resin beyond the base amount of 1800 lbs contributes 2 to the pro t and each additional hour of labor beyond the base amount of 8 hours contributes to the pro t Using this information one can answer certain questions concerning how one might change current operating limitations For example7 if we can buy additional resin from another supplier7 how much more per pound are we willing to pay than we are currently paying Answer 2 per pound is the most we are willing to pay beyond what we now pay7 why Or7 if we are willing to add overtime hours7 what is the greatest overtime salary we are willing to pay Of course7 the marginal values are only good for a certain range of uctuation in the resources7 but within that range they provide valuable information 14 Duality Theory We now brie y discuss the economic theory behind the marginal values and how the hidden hand of the market place77 gives rise to them This leads in a natural way to a mathematical theory of duality for linear programming Think of the cup factory production process as a black box through which the resources ow Raw resources go in one end and exit the other When they come out the resources have a different form7 but whatever comes out is still comprised of the entering resources However7 something has happened to the value of the resources by passing through the black box The resources have been purchased for one price as they enter the box and are sold in their new form as they leave The difference between the entering and exiting prices is called the pro t Assuming that there is a positive pro t the resources have increased in value as they pass through the production process The marginal value of a resource is precisely the increase in the per unit value of the resource due to the production process Let us now consider how the market introduces pressures on the pro tability and the value of the resources available to the market place We take the perspective of the cup factory vs the market place The market place does not want the cup factory to go out of business On the other hand7 it does not want the cup factory to see a pro t It wants to keep all the pro t for itself and only let the cup factory just break even It does this by setting the price of the resources available in the market place That is7 the market sets the price for plastic resin and labor and it tries to do so in such a way that the cup factory sees no pro t and just breaks even Since the cup factory is now seeing a pro t7 the market must gure out by how much the sale price of resin and labor must be raised to reduce this pro t to zero This is done by minimizing the value of the available resources over all price increments that guarantee that the cup factory either loses money or sees no pro t from both of its products If we denote the per unit price increment for resin by R and that for labor by L7 then the pro t for beer mugs is eliminated as long as 1 20B 7L gt 25 15 7 since the left hand side represents the increased value of the resources consumed in the production of one case of beer mugs and the right hand side is the current pro t on a case of beer mugs Similarly7 for champaign glasses7 the market wants to choose R and L so that 1 12B 7L gt 20 15 7 Now in order to maintain equilibrium in the market place7 that is7 not drive the cup factory out of business since then the market realizes no pro t at all7 the market chooses R and L so as to minimize the increased value of the available resources That is7 the market chooses R and L to solve the problem D minimize 1800B 8L subject to 20R L 25 12B L 2 20 0 3 R7 L l V This is just another LP It is called the dual77 to the LP 73 in which the cup factory tries to maximize pro t Observe that if is feasible for 73 and is feasible for D7 then 25B 200 3 20B LlB 12R Ljo R2OB 120 L B 0 1800B 8L Thus7 the value of the objective in 73 at a feasible point in 73 is bounded above by the objective in D at any feasible point for D In particular7 the optimal value in 73 is bounded above by the optimal value in D The strong duality theorem77 states that if either of these problems has a nite optimal value7 then so does the other and these values coincide ln addition7 we claim that the solution to D is given by the marginal values for 73 That is7 1 32 is the optimal solution for D In order to show this we need only show that R7 58ii R7 58 L i 3752 is feasible for D and that the value ofthe objective in D at L i 3752 coincides with the value of the objective in 73 at First we check feasibility K o 8 7 2 20 7LEgt25 8 15 2 5 1 375 12777220 8 15 2 Next we check optimality 5 375 254520752625 1800 87 This is a most remarkable relationship We have shown that the marginal values have three distinct and seemingly disparate interpretations H The marginal values are the partial derivatives of the value function for the LP with respect to resource availability7 D The marginal values give the per unit increase in value of each of the resources that occurs as a result of the production process7 and C40 The marginal values are the solutions to a dual LP7 D 15 LPS in Standard Form and Their Duals Recall that a linear program is a problem of maximization or minimization of a linear func tion subject to a nite number of linear inequality and equality constraints This general de nition leads to an enormous variety of possible formulations In this section we propose one xed formulation for the purposes of developing an algorithmic solution procedure and developing the theory of linear programming We will show that every LP can be recast in this one xed form We say that an LP is in standard form if it has the form 73 maximize mm ngg cnzn subject to ailzl aigzg amzn lt bl forz3917277m 0 zj forj17277n Using matrix notation7 we can rewrite this LP as 73 maximize cTz subject to Az S b 0 S x 7 where c 6 R72 b 6 RT A E Rm and the inequalities Az S b and 0 S x are to be interpreted componentwise Following the results of the previous section on LP duality7 we claim that the dual LP to 73 is the LP D minimize blyl bzyz bnym subjectto a1jy1azjy2amjym Z ijOFj17277n 0 yiforz3917277m7 10 or equivalently using matrix notation we have D minimize bTy subject to ATy 2 c 0 S y Just as for the cup factory problem the LPs 73 and D are related via the Weak Duality Theorem for linear programming THEOREM WEAK DUALITY Ifz E R is feasible for andy E R is feasible for D then ch S yTA S bTy Thus if is unbounded then D is necessarily infeasible and ifD is unbounded then 73 is necessarily infeasible Moreover if cTi bTy with i feasible for 73 and y feasible for D then i must solve 73 and y must solve D PROOF Let x E R be feasible for 73 and y E R be feasible for D Then CT 1 Ci 1 x H m m since 0 3 7 and 07 3 Z aijyi so cjxj S aijyi jl i1 i1 l 1M 4M3 s s S F yTAz m 1 XXX ai alyz i1 11 m 1 7L 2 biyl lSinCe 0 S in and bi E Z ai j SO biyi S ai j il i1 11 11 bTy To see that cTi bTy plus 737D feasibility implies optimality simply observe that for every other 737D feasible pair Ly we have ch S bTy cTi S bTy I We caution that the infeasibility of either 73 or D does not imply the unboundedness of the other Indeed it is possible for both 73 and D to be infeasible as is illustrated by the following example EXAMPLE maximize 2x1 7 2 1 7 2 S 1 1 2 S 2 0 S 1 2 151 Transformation to Standard Form Every LP can be transformed to an LP in standard form This process usually requires a transformation of variables and occasionally the addition of new variables In this section we provide a step by step procedure for transforming any LP to one in standard form minimization a maximization To transform a minimization problem to a maximization problem just multiply the objective function by 71 linear inequalities If an LP has an equality constraint of the form a 1 al z cumin 2 bi This inequality can be transformed to one in standard form by multiplying the inequal ity through by 71 to get aiih ai z 39 39 39 am n S ibi linear equation The linear equation 011 1min bi can be written as two linear inequalities duh quot39 1min lt bi and ai i am n Z bi The second of these inequalities can be transformed to standard form by multiplying through by 71 variables with lower bounds If a variable al has lower bound ll which is not zero li 3 07 one obtains a non negative variable wl with the substitution In this case7 the bound li 3 x1 is equivalent to the bound 0 S w variables with upper bounds If a variable x has an upper bound ul S one obtains a non negative variable iv with the substitution i u 7 wi In this case the bound z lt u is equivalent to the bound 0 S w variables with iriterval bounds An interval bound of the form Z 3 z lt U can be transformed into one non negativity constraint and one linear inequality constraint in standard form by making the substi tution In this case the bounds l g z lt u are equivalent to the constraints 0 3 iv and w 3 iii 7 li free variables Sometimes a variable is given without any bounds Such variables are called free vari ables To obtain standard form every free variable must be replaced by the difference of two non negative variables That is if z is free then we get M u 7 Ni with 0 3 iii and 0 3 vi To illustrate the ideas given above we put the following LP into standard form minimize 3x1 7 2 subject to 7z1 6x2 7 3 4 2 73 72 4 5 3 4 S 2 71 23 572 4 2 The hardest part ofthe translation to standard form or at least the part most susceptible to error is the replacement of existing variables with non negative variables For this reason I usually make the translation in two steps In the rst step I make all of the changes that do not involve variable substitution and then in the second step I start again and do all of the variable substitutions Following this procedure let us start with all of the transformations that do not require variable substitution First turn the minimization problem into a maximization problem by rewriting the objective as maximize 7 3x1 m Next we replace the rst inequality constraint by the constraint 1762374 The equality constraint is replaced by the two inequality constraints 7 4 S 5 772 7 4 S Finally7 the double bound 72 3 x4 3 2 indicates that we should group the upper bound with the linear inequalities All of these changes give the LP maximize 73m 2 subject to 1 7 6x2 3 7 x4 3 3 7M 4 S 5 7 72 7 4 S 75 3 4 S 2 4 S 2 71 S 273 S 5772 S 4 We now move on to variable replacement Observe that the variable 1 is free7 so we replace it by zlzf7zf with0 2170 zf The variable 2 has a non zero lower bound so we replace it by 22z21 or 22271 with 0 22 The variable 3 is bounded above7 so we replace it by 2357z3 or 35723 with 0 23 The variable 5 is bounded below7 so we replace it by 24z42 or 4z472 with 0 z4 After making these substitutions7 we get the following LP in standard form maximize 732r 32 22 subjectto 2f 7 2f 7 622 7 23 7 24 S 710 722 24 S 14 7 722 7 24 S 714 7 23 24 S 71 24 S 4 0 3 21721722723724 14

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.