Example: stock market

Linear programming 1 Basics - MIT Mathematics

Lecture notesMarch 17, 2015 Linear programmingLecturer: Michel Goemans1 BasicsLinear Programmingdeals with the problem of optimizing a linearobjective functionsubject tolinear equality and inequalityconstraintson thedecision variables. Linear programming has manypractical applications (in transportation, production planning, ..). It is also the building block forcombinatorial optimization. One aspect of Linear programming which is often forgotten is the factthat it is also a useful proof technique. In this first chapter, we describe some Linear programmingformulationsfor some classical problems. We also show that Linear programs can be expressed in avariety of equivalent The Diet ProblemIn the diet model, a list of available foods is given together with the nutrient content and the costper unit weight of each food.

Suppose a company manufacturing widgets has two factories located at cities F1 and F2 and three retail centers located at C1, C2 and C3. The monthly demand at the retail centers are (in thousands of widgets) 8, 5 and 2 respectively while the monthly supply at the factories are 6 and 9 respectively. Notice that the total supply equals the total ...

Tags:

  Programming, Linear programming, Linear, Factories

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Linear programming 1 Basics - MIT Mathematics

1 Lecture notesMarch 17, 2015 Linear programmingLecturer: Michel Goemans1 BasicsLinear Programmingdeals with the problem of optimizing a linearobjective functionsubject tolinear equality and inequalityconstraintson thedecision variables. Linear programming has manypractical applications (in transportation, production planning, ..). It is also the building block forcombinatorial optimization. One aspect of Linear programming which is often forgotten is the factthat it is also a useful proof technique. In this first chapter, we describe some Linear programmingformulationsfor some classical problems. We also show that Linear programs can be expressed in avariety of equivalent The Diet ProblemIn the diet model, a list of available foods is given together with the nutrient content and the costper unit weight of each food.

2 A certain amount of each nutrient is required per day. For example,here is the data corresponding to a civilization with just two types of grains (G1 and G2) and threetypes of nutrients (starch, proteins, vitamins):Starch Proteins VitaminsCost ($/kg) content and cost per kg of requirement per day of starch, proteins and vitamins is 8, 15 and 3 respectively. The problemis to find how much of each food to consume per day so as to get the required amount per day ofeach nutrient at minimal trying to formulate a problem as a Linear program, the first step is to decide whichdecision variablesto use. These variables represent the unknowns in the problem. In the dietproblem, a very natural choice of decision variables is: x1: number of units of grain G1 to be consumed per day, x2: number of units of grain G2 to be consumed per next step is to write down theobjective function.

3 The objective function is the function to beminimized or maximized. In this case, the objective is to minimize the total cost per day which isgiven byz= + (the value of the objective function is often denoted byz).Finally, we need to describe the differentconstraintsthat need to be satisfied of all,x1andx2must certainly satisfyx1 0 andx2 0. Only nonnegative amounts ofLP-1food can be eaten! These constraints are referred to asnonnegativity constraints. Nonnegativityconstraints appear in most Linear programs. Moreover, not all possible values forx1andx2giverise to a diet with the required amounts of nutrients per day. The amount of starch inx1units ofG1 andx2units of G2 is 5x1+ 7x2and this amount must be at least 8, the daily requirement ofstarch.

4 Therefore,x1andx2must satisfy 5x1+ 7x2 8. Similarly, the requirements on the amountof proteins and vitamins imply the constraints 4x1+ 2x2 15 and 2x1+x2 diet problem can therefore be formulated by the following Linear program:Minimizez= + to:5x1+ 7x2 84x1+ 2x2 152x1+x2 3x1 0,x2 more terminology. Asolutionx= (x1,x2) is said to befeasiblewith respect to the abovelinear program if it satisfies all the above constraints. The set of feasible solutions is called thefeasible spaceorfeasible region. A feasible solution isoptimalif its objective function value is equalto the smallest valuezcan take over the feasible The Transportation ProblemSuppose a company manufacturing widgets has two factories located at cities F1 and F2 and threeretail centers located at C1, C2 and C3.

5 The monthly demand at the retail centers are (in thousandsof widgets) 8, 5 and 2 respectively while the monthly supply at the factories are 6 and 9 that the total supply equals the total demand. We are also given the cost of transportationof 1 widget between any factory and any retail C2 C3F1553F2641 Cost of transportation (in $/widget).In thetransportation problem, the goal is to determine the quantity to be transported from eachfactory to each retail center so as to meet the demand at minimum total shipping order to formulate this problem as a Linear program, we first choose the decision (i= 1,2 andj= 1,2,3) be the number of widgets (in thousands) transported from factoryFito city Cj. Given thesexij s, we can express the total shipping cost, the objective functionto be minimized, by5x11+ 5x12+ 3x13+ 6x21+ 4x22+ now need to write down the constraints.

6 First, we have the nonnegativity constraints sayingthatxij 0 fori= 1,2 andj= 1,2,3. Moreover, we have that the demand at each retail centermust be met. This gives rise to the following constraints:x11+x21= 8,LP-2x12+x22= 5,x13+x23= , each factory cannot ship more than its supply, resulting in the following constraints:x11+x12+x13 6,x21+x22+x23 inequalities can be replaced by equalities since the total supply is equal to the total Linear programming formulation of this transportation problem is therefore given by:Minimize5x11+ 5x12+ 3x13+ 6x21+ 4x22+x23subject to:x11+x21= 8x12+x22= 5x13+x23= 2x11+x12+x13= 6x21+x22+x23= 9x11 0,x21 0,x31 0,x12 0,x22 0,x32 these 5 equality constraints, one isredundant, it is implied by the other constraintsor, equivalently, it can be removed without modifying the feasible space.

7 For example, by addingthe first 3 equalities and substracting the fourth equality we obtain the last equality. Similarly, byadding the last 2 equalities and substracting the first two equalities we obtain the third Representations of Linear ProgramsA Linear program can take many different forms. First, we have a minimization or a maximizationproblem depending on whether the objective function is to be minimized or maximized. Theconstraints can either be inequalities ( or ) or equalities. Some variables might be unrestrictedin sign ( they can take positive or negative values; this is denoted by 0) while others mightbe restricted to be nonnegative. A general Linear program in the decision variablesx1,..,xnistherefore of the following form:Maximize or Minimizez=c0+c1x1+.

8 +cnxnsubject to:ai1x1+ai2x2+..+ainxn =bii= 1,..,mxj{ 0 0j= 1,.., problem data in this Linear program consists ofcj(j= 0,..,n),bi(i= 1,..,m) andaij(i= 1,..,m,j= 1,..,n).cjis referred to as the objective function coefficient ofxjor, moreLP-3simply, thecost known as theright-hand-side(RHS) of equationi. Noticethat the constant termc0can be omitted without affecting the set of optimal Linear program is said to be instandard formif it is a maximization program, there are only equalities (no inequalities) and all variables are restricted to be matrix form, a Linear program in standard form can be written as:Maxz=cTxsubject to:Ax=bx ,b= ,x= are column vectors,cTdenote the transpose of the vectorc, andA= [aij] is them nmatrixwhosei,j element Linear program can in fact be transformed into an equivalent Linear program in standardform.}

9 Indeed, If the objective function is to minimizez=c1x1+..+cnxnthen we can simply maximizez = z= c1x1 .. cnxn. If we have an inequality constraintai1x1+..+ainxn bithen we can transform it into anequality constraint by adding aslackvariable, says, restricted to be nonnegative:ai1x1+..+ainxn+s=biands 0. Similarly, if we have an inequality constraintai1x1+..+ainxn bithen we can transform itinto an equality constraint by adding asurplusvariable, says, restricted to be nonnegative:ai1x1+..+ainxn s=biands 0. Ifxjis unrestricted in sign then we can introduce two new decision variablesx+jandx jrestricted to be nonnegative and replace every occurrence ofxjbyx+j x example, the Linear programMinimizez= 2x1 x2subject to:x1+x2 23x1+ 2x2 4x1+ 2x2= 3x1 0,x2 equivalent to the Linear programMaximizez = 2x+1+ 2x 1+x2subject to:x+1 x 1+x2 x3= 23x+1 3x 1+ 2x2+x4= 4x+1 x 1+ 2x2= 3x+1 0,x 1 0,x2 0,x3 0,x4 decision variablesx+1,x 1,x2,x3,x4.

10 Notice that we have introduced different slack or surplusvariables into different some cases, another form of Linear program is used. A Linear program is incanonical formifit is of the form:Maxz=cTxsubject to:Ax bx Linear program in canonical form can be replaced by a Linear program in standard form by justreplacingAx bbyAx+Is=b,s 0 wheresis a vector of slack variables andIis them midentity matrix. Similarly, a Linear program in standard form can be replaced by a Linear programin canonical form by replacingAx=bbyA x b whereA =[A A]andb =(b b).2 The Simplex MethodIn 1947, George B. Dantzig developed a technique to solve Linear programs this technique isreferred to as thesimplex Brief Review of Some Linear AlgebraTwo systems of equationsAx=band Ax= bare said to be equivalent if{x:Ax=b}={x: Ax= b}.


Related search queries