Chapter 02 Linear Programing

一、Matlab在线性规划中的应用Linear Programing, 又叫线性最优化(Linear Optimization)1、(1)线性规划首先要有一个目标函数(2)要有一组控制变量(或叫决策变量),且目标函数必须是控制变量的线性组合（即只能是一个线性方程）.(3)需要一组约束条件(等式、不等式约束，特别注意这些变量是否大于0或变量的可能的取值范围) (要尽可能挖掘出所有的条件) （4）线性规划的目标是控制变量在满足约束条件下使目标函数达到最大或最小值。

1、线性规划问题即线性方程求最小值----有一个万能函数fmincon（当目标函数为多元一次方程时，它的最小值可以用此求，但有个万能的命令的fmincon）---且不能带常数项2、线性规划的函数为linprog此函数只能（只能线性方程（每项最多只有一次的多项式），n元-----------(即n元一次方程)完全可以用(因fmincon可以用来求任意方程的最小值)（任意方程，任意n元----任意条件）完全可以用代替（即可以不学linprog）两个函数都只能求最小值，（条件都只能是<=）（什么都是“小”）如要求最大值，两个函数都必须前后两次取反(1)使用格式为:x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,l,u)x=linprog(f,A,b,Aeq,beq,l,u,x0)（参数个数为：3/5/7/8, 少了X0或让其置于末尾）不要编程序，用向量f来表示目标方程（同线性代数中的线性方程）(2)左边还可为:[x,fval]=……[x,fval,exitflag]=……[x,fval,exitflag,output]=……[x,fval,exitflag,output,lambda]=其中lambda表示拉格朗日乘子的内容所以最好是用三个返回结果，最后要根据exitflag判断结果的有效性(用法与fmincon把函数换成了系数向量(不要编程)(2)x0不要或置于末尾---因为没有额外编写程序)(3)x0为初始向量,一般不要使用f为目标函数的系数向量A*x<=b 构成了线性不等式条件Aeq*x=beq 构成了线性等式条件l<=x<=u 构成了上下限(4)注意:A:如要求最大值,则必须对目标函数取反,转化为先求出最小值,最后再将函数值取反即为所求的最大值.B:不等式约束条件是<=,如果为>=,则必须两边乘以-1,C:如前面的某些项没有使用,必须用空矩阵[ ]d:有3、5、7个等参数线性方程中不能有常数项，如有，先不要考虑，最后在结果上再加（或减）去该常数。

ASSUMPTIONS OF LINEAR PROGRAMMING •from a mathematical viewpoint, the assumptions simply are that the model must have a linear objective function subject to linear constraints.•However, from a modeling viewpoint, these mathematical properties of a linear programming model imply that certain assumptions must hold about the activities and data of the problem being modeled, including assumptions about the effect of varying the levels of the activities.•Proportionality •Additivity •Divisibility •CertaintyProportionality assumptioncosts•This case would arise if there were start-up costs associated with initiating the production of product 1. For example, there might be costs involved with setting up the production facilities. There might also be costs associated with arranging the distribution of the new product. Because these are one-time costs, they would need to be amortized on a per-week basis to be commensurable with Z (profit in thousands of dollars per week).costs•Suppose that this amortization were done and that the total start-up cost amounted to reducing Z by 1, but that the profit without considering the start-up cost would be 3x1. This would mean that the contribution from product 1 to Z should be 3x1-1 for x1 > 0, whereas the contribution would be 3x1 0 when x1 0 (no start-up cost). This profit function,3 which is given by the solid curve in Fig., certainly is not proportional to x1.increasing marginal return•the slope of the profit function for product 1 keeps increasing asx 1is increased. This violation of proportionality might occurbecause of economies of scale that can sometimes be achieved at higher levels of production, e.g., through the use of more efficient high-volume machinery, longer production runs, quantity discounts for large purchases of raw materials, and the learning-curve effect whereby workers become more efficient as they gain experience with a particular mode of production.As the incremental cost goes down, the incremental profit will go up (assuming constant marginal revenue).decreasing marginal return•the slope of the profit function for product 1 keeps decreasing as xis increased.1decreasing marginal return•the marketing costs need to go up more than proportionally to attain increases in the level of sales . For example, it might be possible to sell product 1 at the rate of 1 per week (x 1=1) with no advertising, whereas attaining sales to sustain a production rate of x 1=2 might require a moderate amount of advertising, x 1=3might necessitate an extensive advertising campaign, and x 1=4 might require also lowering the price•The conclusion was that proportionality could indeed be assumed without serious distortion.•what happens when the proportionality assumption does not hold even as a reasonable approximation? In most cases, this means you must use nonlinear programming instead• a certain important kind of nonproportionality can still be handled by linear programming by reformulating the problem appropriately.•Furthermore, if the assumption is violated only because of start-up costs, there is an extension of linear programming (mixed integer programming) that can be usedAdditivity•Although the proportionality assumption rules out exponents other than 1, it does not prohibit cross-product terms (terms involving the product of two or more variables).•Additivity assumption: Every function in a linear programming model (whether the objective function or the function on the left-hand side of a functional constraint) is the sum of the individual contributions of the respective activities•this case corresponds to an objective function of Z =3x1+5x2+x1x2, so that Z =3+ 5+ 1= 9 for (x1, x2) (1, 1), thereby violating the additivity assumption that Z =3+5.•The proportionality assumption still is satisfied since after the value of one variable is fixed, the increment in Z from the other variable is proportional to the value of that variable. This case would arise if the two products were complementary in some way that increases profit.•For example, suppose that a major advertising campaign would be required to market either new product produced by itself, but that the same single campaign can effectively promote both products if the decision is made to produce both. Because a major cost is saved for the second product, their joint profit is somewhat more than the sum of their individual profits when each is produced by itself.•Case 2 also violates the additivity assumption because of the extra term in the corresponding objective function, Z =3x 1+5x 2-x 1x 2, so that Z=3+5-1= 7 for (x 1, x 2) (1, 1). As the reverse of the first case, Case 2 would arise if the two products were competitive in some way that decreased their joint profit.•For example, suppose that both products need to use the same machinery and equipment . If either product were produced by itself, this machinery and equipment would be dedicated to this one use. However, producing both products would require switching the production processes back and forth, with substantial time and cost involved in temporarily shutting down the production of one product and setting up for the other.Affect the additivity of the constraint functions•Affect the additivity of the constraints function•For example, consider the third functional constraint of the Wyndor Glass Co. problem: 3x1+2x2<=18. (This is the only constraint involving both products.)•3x1+2x2+0.5x1x2<=18•namely, extra time is wasted switching the production processes back and forth between the two products. The extra cross-product term (0.5x1x2) would give the production time wastedin this way. (Note that wasting time switching between products leads to a positive cross-product term here, where the total function is measuring production time used, whereas it led to a negative cross-product term for Case 2 because the total function there measures profit.)•For Case 4 the function for production time used is 3x1+2x2-0.1x21x2, so the function value for (x1, x2)=(2, 3) is 6+6-1.2=10.8. This case could arise in the following way.•As in Case 3, suppose that the two products require the same type of machinery and equipment. But suppose now that the time required to switch from one product to the other would be relatively small.•occasional idle periodsDivisibility•Divisibility assumption: Decision variables in a linear programming model are allowed to have any values, including noninteger values, that satisfy the functional and nonnegativityconstraints. Thus, these variables are not restricted tojust integer values. Since each decision variable represents the level of some activity, it is being assumed that the activities can be run at fractional levels.Certainty•Certainty assumption: The value assigned to each parameter of a linear programming model is assumed to be a known constant •Linear programming models usually are formulated to select some future course of action. Therefore, the parameter values used would be based on a prediction of future conditions, which inevitably introduces some degree of uncertainty.•sensitivity analysis to identify the sensitive parameters•other ways of dealing with linear programming under uncertainty•It is very common in real applications of linear programming that almost none of the four assumptions hold completely. Except perhaps for the divisibility assumption, minor disparities are to be expected.This is especially true for the certainty assumption, so sensitivity analysis normally is a must to compensate for the violation of this assumption•A disadvantage of these other models is that the algorithms available for solving them are not nearly as powerful as those for linear programming, but this gap has been closing in some cases. For some applications, the powerful linear programming approach is used for the initial analysis, and then a more complicated model is used to refine this analysisThe Simplex MethodTHE ESSENCE OF THE SIMPLEX METHOD •The simplex method is an algebraic procedure. However, its underlying concepts are geometric.•Before delving into algebraic details, we focus in this section on the big picture from a geometric viewpoint.•each constraint boundary is a line that forms the boundary of what is permitted by the corresponding constraint. The points of intersection are the corner-point solutions of the problem. The five that lie on the corners of the feasible region—(0, 0), (0, 6), (2, 6), (4, 3), and (4, 0)—are the cornerpoint feasible solutions (CPF solutions). [The other three—(0, 9), (4, 6), and (6, 0)—are called corner-point infeasible solutions.]•In this example, each corner-point solution lies at the intersection of two constraint boundaries.•For a linear programming problem with n decision variables, each of its cornerpoint solutions lies at the intersection of n constraint boundaries.•Certain pairs of the CPF solutions share a constraint boundary, and other pairs do not.•For any linear programming problem with n decision variables, two CPF solutions are adjacent to each other if they share n-1 constraint boundaries. The two adjacent CPF solutions are connected by a line segment that lies on these same shared constraint boundaries. Such a line segment is referred to as an edge of the feasible region•Since n=2 in the example, two of its CPF solutions are adjacent if they share one constraint boundary; for example, (0, 0) and (0, 6) are adjacent because they share the x1=0 constraint boundary. The feasible region in Fig has five edges, consisting of thefive line segments forming the boundary of this region. Note that two edges emanate from each CPF solution. Thus, each CPF solution has two adjacent CPF solutions•Optimality test: Consider any linear programming problem that possesses at least one optimal solution. If a CPF solution has no adjacent CPF solutions that are better (as measured by Z), thenit must be an optimal solutionSolving the Example -Wyndor Glass Co. Problem•Initialization: Choose (0, 0) as the initialCPF solution to examine. (This is aconvenient choice because no calculationsare required to identify this CPF solution.)•Optimality Test: Conclude that (0, 0) is notan optimal solution. (Adjacent CPFsolutions are better.)•Iteration 1: Move to a better adjacent CPFsolution, (0, 6), by performing the followingthree steps.•1. Considering the two edges of the feasible region that emanate from (0, 0), choose to move along the edge that leads up the x 2axis. (With an objective function of Z=3x 1+5x 2, moving up the x 2axis increases Z at afaster rate than moving along the x 1axis.)•2. Stop at the first new constraint boundary:2x 2=12. [Moving farther in the directionselected in step 1 leaves the feasible region; e.g., moving to the second new constraint boundary hit when moving in that direction gives (0, 9), which is a corner-point infeasible solution.]•3. Solve for the intersection of the new set of constraint boundaries: (0, 6). (The equations for these constraint boundaries, x 1=0 and 2x 2=12, immediately yield this solution.)•Optimality Test: Conclude that (0, 6) is not an optimal solution. (An adjacent CPF solution is better.)•Iteration 2: Move to a better adjacent CPF solution, (2, 6), by performing the following three steps•1. Considering the two edges of the feasible region that emanate from (0, 6), choose tomove along the edge that leads to the right. (Moving along this edge increases Z, whereas backtracking to move back down the x2axis decreases Z.)2. Stop at the first new constraint boundary encountered when moving in that direction:3x1+2x2=12. (Moving farther in the direction selected in step 1 leaves the feasibleregion.)3. Solve for the intersection of the new set of constraint boundaries: (2, 6). (The equations for these constraint boundaries, 3x1+2x2=18 and2x2=12, immediately yield this solution.)•Optimality Test: Conclude that (2, 6) is an optimal solution, so stop. (None of the adjacent CPF solutions are better.)The Key Solution Concepts•Solution concept 1: The simplex method focuses solely on CPF solutions. For any problem with at least one optimal solution, finding one requires only finding•The only restriction is that the problem must possess CPF solutions. This is ensured if the feasible region is bounded.•Solution concept 2: The simplex method is an iterative algorithm (a systematic solution procedure that keeps repeating a fixed series of steps, called an iteration, until a desired result has been obtained) with the following structure.•Solution concept 3: Whenever possible, the initialization of the simplex method chooses the origin (all decision variables equal to zero) to be the initial CPF solution. When there are too many decision variables to find an initial CPF solution graphically, this choice eliminates the need to use algebraic procedures tofind and solve for an initial CPF solution•Solution concept 4: Given a CPF solution, it is much quicker computationally to gather information about its adjacent CPF solutions than about other CPF solutions. Therefore, each time the simplex method performs an iteration to move from the current CPF solution to a better one, it always chooses a CPF solution that is adjacent to the current one. No other CPF solutions are considered. Consequently, the entire path followed to eventually reach an optimal solution is alongthe edges of the feasible region.•Solution concept 5: After the current CPF solution is identified, the simplex method examines each of the edges of the feasibleregion that emanate from this CPF solution. Each of theseedges leads to an adjacent CPF solution at the other end, but the simplex method does not even take the time to solve for theadjacent CPF solution. Instead, it simply identifies the rate of improvement in Z that would be obtained by moving along the edge. Among the edges with a positive rate of improvement in Z, it then chooses to move along the one with the largest rate of improvement in Z. The iteration is completed by first solving for the adjacent CPF solution at the other end of this one edge and then relabeling this adjacent•Solution concept 6: Solution concept 5 describes how the simplex method examines each of the edges of the feasible region that emanate from the current CPF solution. This examination of an edge leads to quickly identifying the rate of improvement in Z that would be obtained by moving along the edge toward theadjacent CPF solution at the other end. A positive rate of improvement in Z implies that the adjacent CPF solution is better than the current CPF solution, whereas a negative rate of improvement in Z implies that the adjacent CPF solution is worse. Therefore, the optimality test consists simply of checking whether any of the edges give a positive rate of improvement in Z. If none do, then the current CPF solution is optimalSETTING UP THE SIMPLEX METHOD•The algebraic procedure is based on solving systems of equations. Therefore, the first step in setting up the simplex method is to convert the functional inequality constraints to equivalent equality constraints. (The nonnegativity constraints are left asinequalities because they are treated separately.) This conversion is accomplished by introducing slack variables.•Although both forms of the model represent exactly the same problem, the new form is much more convenient for algebraic manipulation and for identification of CPF solutions.•We call this the augmented form of the problem because the original form has been augmented by some supplementary variables neededto apply the simplex method.。

LINEAR PROGRAMMINGA Concise IntroductionThomas S.FergusonContents1.Introduction (3)The Standard Maximum and Minimum Problems (4)The Diet Problem (5)The Transportation Problem (6)The Activity Analysis Problem (6)The Optimal Assignment Problem (7)Terminology (8)2.Duality (10)Dual Linear Programming Problems (10)The Duality Theorem (11)The Equilibrium Theorem (12)Interpretation of the Dual (14)3.The Pivot Operation (16)4.The Simplex Method (20)The Simplex Tableau (20)The Pivot Madly Method (21)Pivot Rules for the Simplex Method (23)The Dual Simplex Method (26)5.Generalized Duality (28)The General Maximum and Minimum Problems (28)Solving General Problems by the Simplex Method (29)Solving Matrix Games by the Simplex Method (30)6.Cycling (33)A Modification of the Simplex Method That Avoids Cycling (33)7.Four Problems with Nonlinear Objective Function (36)Constrained Games (36)The General Production Planning Problem (36)Minimizing the Sum of Absolute Values (37)Minimizing the Maximum of Absolute Values (38)Chebyshev Approximation (39)Linear Fractional Programming (39)Activity Analysis to Maximize the Rate of Return (40)8.The Transportation Problem (42)Finding a Basic Feasible Shipping Schedule (44)Checking for Optimality (45)The Improvement Routine (47)9.Solutions to the Exercises (50)Related Texts (65)LINEAR PROGRAMMING1.Introduction.A linear programming problem may be defined as the problem of maximizing or min-imizing a linear function subject to linear constraints.The constraints may be equalitiesor inequalities.Here is a simple example.Find numbers x1and x2that maximize the sum x1+x2subject to the constraintsx1≥0,x2≥0,andx1+2x2≤44x1+2x2≤12−x1+x2≤1In this problem there are two unknowns,andfive constraints.All the constraints areinequalities and they are all linear in the sense that each involves an inequality in some linear function of the variables.Thefirst two constraints,x1≥0and x2≥0,are special. These are called nonnegativity constraints and are often found in linear programmingproblems.The other constraints are then called the main constraints.The function to bemaximized(or minimized)is called the objective function.Here,the objective function isx1+x2.Since there are only two variables,we can solve this problem by graphing the set of points in the plane that satisfies all the constraints(called the constraint set)and thenfinding which point of this set maximizes the value of the objective function.Each inequality constraint is satisfied by a half-plane of points,and the constraint set is the intersection of all the half-planes.In the present example,the constraint set is thefive-sidedfigure shaded in Figure1.We seek the point(x1,x2),that achieves the maximum of x1+x2as(x1,x2)ranges over this constraint set.The function x1+x2is constant on lines with slope−1,for example the line x1+x2=1,and as we move this line further from the origin up and to the right,the value of x1+x2increases.Therefore,we seek the line of slope−1that is farthest from the origin and still touches the constraint set.This occurs at the intersection of the lines x1+2x2=4and4x1+2x2=12,namely,(x1,x2)=(8/3,2/3).The value of the objective function there is(8/3)+(2/3)=10/3.Exercises1and2can be solved as above by graphing the feasible set.It is easy to see in general that the objective function,being linear,always takes onits maximum(or minimum)value at a corner point of the constraint set,provided thex2x1Figure1.constraint set is bounded.Occasionally,the maximum occurs along an entire edge or face of the constraint set,but then the maximum occurs at a corner point as well.Not all linear programming problems are so easily solved.There may be many vari-ables and many constraints.Some variables may be constrained to be nonnegative and others unconstrained.Some of the main constraints may be equalities and others inequal-ities.However,two classes of problems,called here the standard maximum problem and the standard minimum problem,play a special role.In these problems,all variables are constrained to be nonnegative,and all main constraints are inequalities.We are given an m-vector,b=(b1,...,b m)T,an n-vector,c=(c1,...,c n)T,and anm×n matrix,A=⎛⎜⎜⎝a11a12 (1)a21a22 (2)............a m1a m2···a mn⎞⎟⎟⎠of real numbers.The Standard Maximum Problem:Find an n-vector,x=(x1,...,x n)T,to maximizec T x=c1x1+···+c n x nsubject to the constraintsa11x1+a12x2+···+a1n x n≤b1a21x1+a22x2+···+a2n x n≤b2...a m1x1+a m2x2+···+a mn x n≤b m(or Ax≤b)andx1≥0,x2≥0,...,x n≥0(or x≥0).The Standard Minimum Problem:Find an m-vector,y=(y1,...,y m),to minimizey T b=y1b1+···+y m b msubject to the constraintsy1a11+y2a21+···+y m a m1≥c1y1a12+y2a22+···+y m a m2≥c2(or y T A≥c T)...y1a1n+y2a2n+···+y m a mn≥c nandy1≥0,y2≥0,...,y m≥0(or y≥0).Note that the main constraints are written as≤for the standard maximum problem and≥for the standard minimum problem.The introductory example is a standard maximum problem.We now present examples of four general linear programming problems.Each of these problems has been extensively studied.Example1.The Diet Problem.There are m different types of food,F1,...,F m, that supply varying quantities of the n nutrients,N1,...,N n,that are essential to good health.Let c j be the minimum daily requirement of nutrient,N j.Let b i be the price per unit of food,F i.Let a ij be the amount of nutrient N j contained in one unit of food F i. The problem is to supply the required nutrients at minimum cost.Let y i be the number of units of food F i to be purchased per day.The cost per day of such a diet isb1y1+b2y2+···+b m y m.(1) The amount of nutrient N j contained in this diet isa1j y1+a2j y2+···+a mj y mfor j=1,...,n.We do not consider such a diet unless all the minimum daily requirements are met,that is,unlessa1j y1+a2j y2+···+a mj y m≥c j for j=1,...,n.(2) Of course,we cannot purchase a negative amount of food,so we automatically have the constraintsy1≥0,y2≥0,...,y m≥0.(3) Our problem is:minimize(1)subject to(2)and(3).This is exactly the standard minimum problem.Example 2.The Transportation Problem.There are I ports,or produc-tion plants,P1,...,P I,that supply a certain commodity,and there are J markets, M1,...,M J,to which this commodity must be shipped.Port P i possesses an amount s i of the commodity(i=1,2,...,I),and market M j must receive the amount r j of the commodity(j=1,...,J).Let b ij be the cost of transporting one unit of the commodity from port P i to market M j.The problem is to meet the market requirements at minimum transportation cost.Let y ij be the quantity of the commodity shipped from port P i to market M j.The total transportation cost isI i=1Jj=1y ij b ij.(4)The amount sent from port P i is Jj=1y ij and since the amount available at port P i iss i,we must haveJj=1y ij≤s i for i=1,...,I.(5)The amount sent to market M j is Ii=1y ij,and since the amount required there is r j,we must haveIi=1y ij≥r j for j=1,...,J.(6) It is assumed that we cannot send a negative amount from P I to M j,we havey ij≥0for i=1,...,I and j=1,...,J.(7) Our problem is:minimize(4)subject to(5),(6)and(7).Let us put this problem in the form of a standard minimum problem.The number of y variables is IJ,so m=IJ.But what is n?It is the total number of main constraints. There are n=I+J of them,but some of the constraints are≥constraints,and some of them are≤constraints.In the standard minimum problem,all constraints are≥.This can be obtained by multiplying the constraints(5)by−1:Jj=1(−1)y ij≥−s j for i=1,...,I.(5 )The problem“minimize(4)subject to(5 ),(6)and(7)”is now in standard form.In Exercise3,you are asked to write out the matrix A for this problem.Example3.The Activity Analysis Problem.There are n activities,A1,...,A n, that a company may employ,using the available supply of m resources,R1,...,R m(labor hours,steel,etc.).Let b i be the available supply of resource R i.Let a ij be the amountof resource R i used in operating activity A j at unit intensity.Let c j be the net value to the company of operating activity A j at unit intensity.The problem is to choose the intensities which the various activities are to be operated to maximize the value of the output to the company subject to the given resources.Let x j be the intensity at which A j is to be operated.The value of such an activity allocation isnj=1c j x j.(8)The amount of resource R i used in this activity allocation must be no greater than the supply,b i;that is,j=1a ij x j≤b i for i=1,...,m.(9) It is assumed that we cannot operate an activity at negative intensity;that is,x1≥0,x2≥0,...,x n≥0.(10) Our problem is:maximize(8)subject to(9)and(10).This is exactly the standard maximum problem.Example4.The Optimal Assignment Problem.There are I persons available for J jobs.The value of person i working1day at job j is a ij,for i=1,...,I,and j=1,...,J.The problem is to choose an assignment of persons to jobs to maximize the total value.An assignment is a choice of numbers,x ij,for i=1,...,I,and j=1,...,J,where x ij represents the proportion of person i’s time that is to be spent on job j.Thus,Jj=1x ij≤1for i=1,...,I(11)Ii=1x ij≤1for j=1,...,J(12)andx ij≥0for i=1,...,I and j=1,...,J.(13) Equation(11)reflects the fact that a person cannot spend more than100%of his time working,(12)means that only one person is allowed on a job at a time,and(13)says that no one can work a negative amount of time on any job.Subject to(11),(12)and(13),we wish to maximize the total value,I i=1Jj=1a ij x ij.(14)This is a standard maximum problem with m =I +J and n =IJ .Terminology.The function to be maximized or minimized is called the objective function .A vector,x for the standard maximum problem or y for the standard minimum problem,is said to be feasible if it satisfies the corresponding constraints.The set of feasible vectors is called the constraint set .A linear programming problem is said to be feasible if the constraint set is not empty;otherwise it is said to be infeasible .A feasible maximum (resp.minimum)problem is said to be unbounded if the ob-jective function can assume arbitrarily large positive (resp.negative)values at feasible vectors;otherwise,it is said to be bounded .Thus there are three possibilities for a linear programming problem.It may be bounded feasible,it may be unbounded feasible,and it may be infeasible.The value of a bounded feasible maximum (resp,minimum)problem is the maximum (resp.minimum)value of the objective function as the variables range over the constraint set.A feasible vector at which the objective function achieves the value is called optimal .All Linear Programming Problems Can be Converted to Standard Form.A linear programming problem was defined as maximizing or minimizing a linear function subject to linear constraints.All such problems can be converted into the form of a standard maximum problem by the following techniques.A minimum problem can be changed to a maximum problem by multiplying the objective function by −1.Similarly,constraints of the form n j =1a ij x j ≥b i can be changed into the form n j =1(−a ij )x j ≤−b i .Two other problems arise.(1)Some constraints may be equalities.An equality constraint n j =1a ij x j =b i maybe removed,by solving this constraint for some x j for which a ij =0and substituting this solution into the other constraints and into the objective function wherever x j appears.This removes one constraint and one variable from the problem.(2)Some variable may not be restricted to be nonnegative.An unrestricted variable,x j ,may be replaced by the difference of two nonnegative variables,x j =u j −v j ,where u j ≥0and v j ≥0.This adds one variable and two nonnegativity constraints to the problem.Any theory derived for problems in standard form is therefore applicable to general problems.However,from a computational point of view,the enlargement of the number of variables and constraints in (2)is undesirable and,as will be seen later,can be avoided.Exercises.1.Consider the linear programming problem:Find y1and y2to minimize y1+y2 subject to the constraints,y1+2y2≥32y1+y2≥5y2≥0.Graph the constraint set and solve.2.Find x1and x2to maximize ax1+x2subject to the constraints in the numerical example of Figure1.Find the value as a function of a.3.Write out the matrix A for the transportation problem in standard form.4.Put the following linear programming problem into standard form.Find x1,x2, x3,x4to maximize x1+2x2+3x3+4x4+5subject to the constraints,4x1+3x2+2x3+x4≤10x1−x3+2x4=2x1+x2+x3+x4≥1,andx1≥0,x3≥0,x4≥0.2.Duality.To every linear program there is a dual linear program with which it is intimately connected.We first state this duality for the standard programs.As in Section 1,c and x are n -vectors,b and y are m -vectors,and A is an m ×n matrix.We assume m ≥1and n ≥1.Definition.The dual of the standard maximum problemmaximize c T xsubject to the constraints Ax ≤b and x ≥0(1)is defined to be the standard minimum problemminimize y T bsubject to the constraints y T A ≥c T and y ≥0(2)Let us reconsider the numerical example of the previous section:Find x 1and x 2to maximize x 1+x 2subject to the constraints x 1≥0,x 2≥0,andx 1+2x 2≤44x 1+2x 2≤12−x 1+x 2≤ 1.(3)The dual of this standard maximum problem is therefore the standard minimum problem:Find y 1,y 2,and y 3to minimize 4y 1+12y 2+y 3subject to the constraints y 1≥0,y 2≥0,y 3≥0,and y 1+4y 2−y 3≥12y 1+2y 2+y 3≥1.(4)If the standard minimum problem (2)is transformed into a standard maximum prob-lem (by multiplying A ,b ,and c by −1),its dual by the definition above is a standard minimum problem which,when transformed to a standard maximum problem (again by changing the signs of all coefficients)becomes exactly (1).Therefore,the dual of the stan-dard minimum problem (2)is the standard maximum problem (1).The problems (1)and(2)are said to be duals.The general standard maximum problem and the dual standard minimum problem may be simultaneously exhibited in the display:x 1x 2···x n y 1a 11a 12···a 1n ≤b 1y 2a 21a 22···a 2n ≤b 2...............y m a m 1a m 2···a mn ≤b m ≥c 1≥c 2···≥c n (5)Our numerical example in this notation becomesx1x2y112≤4(6)y242≤12y3−11≤1≥1≥1The relation between a standard problem and its dual is seen in the following theorem and its corollaries.Theorem1.If x is feasible for the standard maximum problem(1)and if y is feasible for its dual(2),thenc T x≤y T b.(7)Proof.c T x≤y T Ax≤y T b.Thefirst inequality follows from x≥0and c T≤y T A.The second inequality follows from y≥0and Ax≤b.Corollary1.If a standard problem and its dual are both feasible,then both are bounded feasible.Proof.If y is feasible for the minimum problem,then(7)shows that y T b is an upper bound for the values of c T x for x feasible for the maximum problem.Similarly for the converse.Corollary2.If there exists feasible x∗and y∗for a standard maximum problem(1)and its dual(2)such that c T x∗=y∗T b,then both are optimal for their respective problems.Proof.If x is any feasible vector for(1),then c T x≤y∗T b=c T x∗.which shows that x∗is optimal.A symmetric argument works for y∗.The following fundamental theorem completes the relationship between a standard problem and its dual.It states that the hypothesis of Corollary2are always satisfied if one of the problems is bounded feasible.The proof of this theorem is not as easy as the previous theorem and its corollaries.We postpone the proof until later when we give a constructive proof via the simplex method.(The simplex method is an algorithmic method for solving linear programming problems.)We shall also see later that this theorem contains the Minimax Theorem forfinite games of Game Theory.The Duality Theorem.If a standard linear programming problem is bounded feasible, then so is its dual,their values are equal,and there exists optimal vectors for both problems.There are three possibilities for a linear program.It may be feasible bounded (f.b.),feasible unbounded (f.u.),or infeasible (i).For a program and its dual,there are therefore nine possibilities.Corollary 1states that three of these cannot occur:If a problem and its dual are both feasible,then both must be bounded feasible.The first conclusion of the Duality Theorem states that two other possiblities cannot occur.If a program is feasible bounded,its dual cannot be infeasible.The x’s in the accompanying diagram show the impossibilities.The remaining four possibilities can occur.Standard Maximum Problemf.b. f.u.i.f.b.x xDual f.u.x xi.x(8)As an example of the use of Corollary 2,consider the following maximum problem.Find x 1,x 2,x 2,x 4to maximize 2x 1+4x 2+x 3+x 4,subject to the constraints x j ≥0for all j ,andx 1+3x 2+x 4≤42x 1+x 2≤3x 2+4x 3+x 4≤3.(9)The dual problem is found to be:find y 1,y 2,y 3to minimize 4y 1+3y 2+3y 3subject to the constraints y i ≥0for all i ,andy 1+2y 2≥23y 1+y 2+y 3≥44y 3≥1y 1+y 3≥1.(10)The vector (x 1,x 2,x 3,x 4)=(1,1,1/2,0)satisfies the constraints of the maximum prob-lem and the value of the objective function there is 13/2.The vector (y 1,y 2,y 3)=(11/10,9/20,1/4)satisfies the constraints of the minimum problem and has value there of 13/2also.Hence,both vectors are optimal for their respective problems.As a corollary of the Duality Theorem we haveThe Equilibrium Theorem.Let x ∗and y ∗be feasible vectors for a standard maximum problem (1)and its dual (2)respectively.Then x ∗and y ∗are optimal if,and only if,y ∗i =0for all i for which n j =1a ij x ∗j <b i (11)andx ∗j =0for all j for whichmi =1y ∗i a ij>c j(12)Proof.If:Equation (11)implies that y ∗i=0unless there is equality inja ij x ∗j ≤b i .Hencem i =1y ∗i b i =m i =1y ∗i n j =1a ij x ∗j =mi =1n j =1y ∗i a ij x ∗j .(13)Similarly Equation (12)impliesm i =1n j =1y ∗i a ij x ∗j =n j =1c j x ∗j .(14)Corollary 2now implies that x ∗and y ∗are optimal.Only if:As in the first line of the proof of Theorem 1,n j =1c j x ∗j ≤m i =1n j =1y ∗i a ij x ∗j ≤m i =1y ∗i b i .(15)By the Duality Theorem,if x ∗and y ∗are optimal,the left side is equal to the right sideso we get equality throughout.The equality of the first and second terms may be written as n j =1c j −mi =1y ∗i a ij x ∗j =0.(16)Since x ∗and y ∗are feasible,each term in this sum is nonnegative.The sum can be zero only if each term is zero.Hence ifm i =1y ∗i a ij >c j ,then x ∗j =0.A symmetric argument shows that if nj =1a ij x ∗j <b i ,then y ∗i =0.Equations (11)and (12)are sometimes called the complementary slackness con-ditions .They require that a strict inequality (a slackness)in a constraint in a standard problem implies that the complementary constraint in the dual be satisfied with equality.As an example of the use of the Equilibrium Theorem,let us solve the dual to the introductory numerical example.Find y 1,y 2,y 3to minimize 4y 1+12y 2+y 3subject to y 1≥0,y 2≥0,y 3≥0,andy 1+4y 2−y 3≥12y 1+2y 2+y 3≥1.(17)We have already solved the dual problem and found that x ∗1>0and x ∗2>0.Hence,from (12)we know that the optimal y ∗gives equality in both inequalities in (17)(2equations in 3unknowns).If we check the optimal x ∗in the first three main constraints of the maximum problem,we find equality in the first two constraints,but a strict inequality inthe third.From condition (11),we conclude that y ∗3=0.Solving the two equations,y 1+4y 2=12y 1+2y 2=1we find (y ∗1,y ∗2)=(1/3,1/6).Since this vector is feasible,the “if”part of the Equilibrium Theorem implies it is optimal.As a check we may find the value,4(1/3)+12(1/6)=10/3,and see it is the same as for the maximum problem.In summary,if you conjecture a solution to one problem,you may solve for a solution to the dual using the complementary slackness conditions,and then see if your conjecture is correct.Interpretation of the dual.In addition to the help it provides in finding a solution,the dual problem offers advantages in the interpretation of the original,primal problem.In practical cases,the dual problem may be analyzed in terms of the primal problem.As an example,consider the diet problem,a standard minimum problem of the form (2).Its dual is the standard maximum problem (1).First,let us find an interpretation of the dual variables,x 1,x 2,...,x n .In the dual constraint,n j =1a ij x j ≤b i ,(18)the variable b i is measured as price per unit of food,F i ,and a ij is measured as unitsof nutrient N j per unit of food F i .To make the two sides of the constraint comparable,x j must be measured in of price per unit of food F i .(This is known as a dimensional analysis .)Since c j is the amount of N j required per day,the objective function, n1c j x j ,represents the total price of the nutrients required each day.Someone is evidently trying to choose vector x of prices for the nutrients to maximize the total worth of the required nutrients per day,subject to the constraints that x ≥0,and that the total value of the nutrients in food F i ,namely, n j =1a ij x j ,is not greater than the actual cost,b i ,of that food.We may imagine that an entrepreneur is offering to sell us the nutrients without the food,say in the form of vitamin or mineral pills.He offers to sell us the nutrient N j at a price x j per unit of N j .If he wants to do business with us,he would choose the x j so that price he charges for a nutrient mixture substitute of food F i would be no greater thanthe original cost to us of food F i .This is the constraint,(18).If this is true for all i ,we may do business with him.So he will choose x to maximize his total income, n1c j x j ,subject to these constraints.(Actually we will not save money dealing with him since the duality theorem says that our minimum, m 1y i b i ,is equal to his maximum, n 1c j x j .)The optimal price,x j ,is referred to as the shadow price of nutrient N j .Although no such entrepreneur exists,the shadow prices reflect the actual values of the nutrients as shaped by the market prices of the foods,and our requirements of the nutrients.Exercises.1.Find the dual to the following standard minimum problem.Find y 1,y 2and y 3to minimize y 1+2y 2+y 3,subject to the constraints,y i ≥0for all i ,andy 1−2y 2+y 3≥2−y 1+y 2+y 3≥42y 1+y 3≥6y 1+y 2+y 3≥2.2.Consider the problem of Exercise 1.Show that (y 1,y 2,y 3)=(2/3,0,14/3)is optimal for this problem,and that (x 1,x 2,x 3,x 4)=(0,1/3,2/3,0)is optimal for the dual.3.Consider the problem:Maximize3x1+2x2+x3subject to x1≥0,x2≥0,x3≥0, andx1−x2+x3≤42x1+x2+3x3≤6−x1+2x3≤3x1+x2+x3≤8.(a)State the dual minimum problem.(b)Suppose you suspect that the vector(x1,x2,x3)=(0,6,0)is optimal for the maximum e the Equilibrium Theorem to solve the dual problem,and then show that your suspicion is correct.4.(a)State the dual to the transportation problem.(b)Give an interpretation to the dual of the transportation problem.3.The Pivot Operation.Consider the following system of equations.3y 1+2y 2=s 1y 1−3y 2+3y 3=s 25y 1+y 2+y 3=s 3(1)This expresses dependent variables,s 1,s 2and s 3in terms of the independent variables,y 1,y 2and y 3.Suppose we wish to obtain y 2,s 2and s 3in terms of y 1,s 1and y 3.We solve the first equation for y 2,y 2=12s 1−32y 1,and substitute this value of y 2into the other equations.y 1−3(12s 1−32y 1)+3y 3=s 25y 1+(12s 1−32y 1)+y 3=s 3.These three equations simplified become−32y 1+12s 1=y 2112y 1−32s 1+3y 3=s 272y 1+12s 1+y 3=s 3.(2)This example is typical of the following class of problems.We are given a system of n linear functions in m unknowns,written in matrix form asy T A =s T(3)where y T =(y 1,...,y m ),s T =(s 1,...,s n ),andA =⎛⎜⎜⎝a 11a 12...a 1n a 21a 22...a 2n ............a m 1a m 2...a mn⎞⎟⎟⎠.Equation (3)therefore represents the systemy 1a 11+···+y i a i 1+···+y m a m 1=s 1.........y 1a 1j +···+y i a ij +···+y m a mj =s j .........y 1a 1n +···+y i a in +···+y m a mn =s n .(4)In this form,s 1,...,s n are the dependent variables,and y 1,...,y m are the independent variables.Suppose that we want to interchange one of the dependent variables for one of the independent variables.For example,we might like to have s 1,...,s j −1,y i ,s j +1,...,s n in terms of y 1,...,y i −1,s j ,y i +1,...,y m ,with y i and s j interchanged.This may be done if and only if a ij =0.If a ij =0,we may take the j th equation and solve for y i ,to findy i =1a ij(−y 1a 1j −···−y i −1a (i −1)j +s j −y i +1a (i +1)j −···−y m a mj ).(5)Then we may substitute this expression for y i into the other equations.For example,the k th equation becomesy 1 a 1k −a ik a 1j a ij +···+s j a ika ij +···+y m a mk −a ik a mj a ij=s k .(6)We arrive at a system of equations of the formy 1ˆa 11+···+s j ˆa i 1+···+y m ˆa m 1=s 1.........y 1ˆa 1j +···+s j ˆa ij +···+y m ˆa mj =y i .........y 1ˆa 1n +···+s j ˆa in +···+y m ˆa mn =s n .(7)The relation between the ˆa ij ’s and the a ij ’s may be found from (5)and (6).ˆa ij =1a ij ˆa hj =−a hj a ij for h =iˆa ik =a ik a ijfor k =j ˆa hk=a hk −a ik a hja ijfor k =j and h =i .Let us mechanize this procedure.We write the original m ×n matrix A in a display with y 1to y m down the left side and s 1to s n across the top.This display is taken to represent the original system of equations,(3).To indicate that we are going to interchange y i and s j ,we circle the entry a ij ,and call this entry the pivot .We draw an arrow to thenew display with y i and s j interchanged,and the new entries of ˆaij ’s.The new display,of course,represents the equations (7),which are equivalent to the equations (4).s 1···s j ···s n y 1a 11···a 1j ···a 1n............y i a i 1··· a ij ···a in ............y ma m 1···a mj···a mn−→s 1···y i···s ny 1ˆa 11···ˆa 1j ···ˆa 1n............s j ˆa i 1···ˆa ij ···ˆa in ............y mˆa m 1···ˆa mj ···ˆa mnIn the introductory example,this becomess1s2s3y1315 y2 2−31 y3031−→y2s2s3y1−3/211/27/2s11/2−3/21/2y3031(Note that the matrix A appearing on the left is the transpose of the numbers as they appear in equations(1).)We say that we have pivoted around the circled entry from the first matrix to the second.The pivoting rules may be summarized in symbolic notation:p r c q −→1/p r/p−c/p q−(rc/p)This signifies:The pivot quantity goes into its reciprocal.Entries in the same row as the pivot are divided by the pivot.Entries in the same column as the pivot are divided by the pivot and changed in sign.The remaining entries are reduced in value by the product of the corresponding entries in the same row and column as themselves and the pivot,divided by the pivot.We pivot the introductory example twice more.y2s2s3y1−3/211/27/2 s11/2−3/21/2 y303 1−→y2s2y3y1−3/2 −5−7/2s11/2−3−1/2s3031−→y2y1y3s2.3−.2.7s11.4−.61.6s3−.9.6−1.1The last display expresses y1,y2and y3in terms of s1,s2and s3.Rearranging rows and columns,we canfind A−1.y1y2y3s1−.61.41.6 s2−.2.3.7 s3.6−.9−1.1so A−1=⎛⎝−.61.41.6−.2.3.7.6−.9−1.1⎞⎠The arithmetic may be checked by checking AA−1=I.Exercise.Solve the system of equations y T A=s T,s1s2s3s4y1 1102y202−11y3−1103y41−221。

Chapter 2: Introduction to Linear ProgrammingYou may recall unconstrained optimization from your high school years: the idea is to find the highest point (or perhaps the lowest point) on an objective function (see Figure2.1). For optimization to be required, there must be more than one solution available. In Figure 2.1, any point on the function is asolution, and because the single variable is real-valued, there are an infinite number ofprocess is then required in order to choose the very best solution from among thoseavailable. What is meant by best dependson the problem at hand: it might mean thesolution that provides the most profit, or that consumes the least of some limited resource,e.g. area in computer chip design, or fuel in delivery route design. commonly applied form of constrained optimization . Constrained optimization is much harder than unconstrained optimization: you still have to find the best point of the function, but now you also have to respect various constraints while doing so. For example, you must guarantee that the optimum point does not have a value above or below a prespecified limit when substituted into a given constraint function. The constraints usually relate to limited resources. The simple methods you used in high school to find peaks and valleys won’t work anymore: now the best solution (the optimum point ) may not occur at the top of a peak or at the bottom of a valley. The best solution might occur half way up a peak when a constraint prohibits movement farther up.The main elements of any constrained optimization problem are:• Variables (also called decision variables ). The values of the variables are notknown when you start the problem. The variables usually represent things that you can adjust or control, for example the rate at which to manufacture items. The goal is to find values of the variables that provide the best value of the objective function.• Objective function. This is a mathematical expression that combines thevariables to express your goal. It may represent profit, for example. You will be required to either maximize or minimize the objective function.• Constraints. These are mathematical expressions that combine the variables toexpress limits on the possible solutions. For example, they may express the idea that the number of workers available to operate a particular machine is limited, or that only a certain amount of steel is available per day.•Variable bounds. Only rarely are the variables in an optimization problem permitted to take on any value from minus infinity to plus infinity. Instead, the variables usually have bounds. For example, zero and 1000 might bound the production rate of widgets on a particular machine.In linear programming (LP), all of the mathematical expressions for the objective function and the constraints are linear. The programming in linear programming is an archaic use of the word “programming” to mean “planning”. So you might think of linear programming as “planning with linear models”. You might imagine that the restriction to linear models severely limits your ability to model real-world problems, but this isn’t so. An amazing range of problems can be modeled using linear programming, everything from airline scheduling to least-cost petroleum processing and distribution. LP is very widely used. For example, IBM estimated that in 1970, 25% of all scientific computation was devoted to linear programming.Linear programming is by far the most widely used method of constrained optimization. The largest optimization problems in the world are LPs having millions of variables and hundreds of thousands of constraints. With recent advances in both solution algorithms and computer power, these large problems can be solved in practical amounts of time.Of course, there are also many problems for which LP is not appropriate, and part of the job for this textbook is to help you decide when to use LP and the other techniques covered here, and when not to use them.A Prototype Example: The Acme Bicycle CompanyIt’s time now to introduce you to a small example that we will be visiting numerous times throughout the book: the Acme Bicycle Company (ABC). The name follows the time-honored tradition in optimization and operations research texts of inventing bogus companies such as the “Wyndor Glass Company” (which, oddly, makes glass windows and doors), or the “Nori and Leets” Iron and Steel Company.The Acme Bicycle Company produces two kinds of bicycles by hand: mountain bikes and street racers. Acme wishes to determine the rate at which each type of bicycle should be produced in order to maximize the profits on the sales of the bicycles. Acme assumes that it can sell all of the bicycles produced.The physical data on the production process is available from the company engineer. A different team produces each kind of bicycle, and each team has a different maximum production rate: 2 mountain bikes per day and 3 racers per day, respectively. Producing a bicycle of either type requires the same amount of time on the metal finishing machine (a production bottleneck), and this machine can process at most a total of 4 bicycles per day, of either type. The company accountant estimates that mountain bikes are currently generating a profit of around $15 per bicycle, and racers a profit of around $10 per bicycle.This problem is small enough to solve without using LP, just the straightforward application of common sense. To maximize profit, start by producing the maximum number possible of the higher-profit mountain bikes and use any leftover production capacity to produce racers for additional profit. This would mean a production rate of 2 mountain bikes per day, which is the limit of the mountain bike team, yet leaves spare capacity on the metal finishing machine. This remaining capacity can be used to produce 2 racers per day, which is below the capacity of the racer production team. The total profit would then be 2×$15+2×$10=$50 per day.We will be formulating and solving the Acme problem as a linear program, but there is an important lesson here: the results returned by a mathematical program should always be compared to the results predicted by common sense. If the two are in conflict, investigate. You will discover either a modeling or data error, or will learn more about the underlying process, thereby sharpening your intuition. The LP solution of the Acme problem had better turn up a daily profit of at least $50!The first step in formulating the ABC problem as a linear program is to identify the variables. These are the items whose values you can set or otherwise control. The Acme variables are the production rates of mountain bikes (call this x1) and racers (call this x2). Note any bounds on the variables:•variable nonnegativity: x1≥0, x2≥0Using these variables, next write the objective function:•maximize daily profit: maximize Z=15x1+10x2(in $ per day)It’s a convention to represent the value of the objective function by Z.Use the variables to write the constraints as well:•mountain bike production limit: x1≤2 (in bikes per day)•racer production limit: x2≤3 (in bikes per day)•metal finishing machine production limit: x1+x2≤4 (in bikes per day)The first two constraints are normally considered variable bounds, but we will treat them as general constraints for now.Note that it is customary to write LP constraints with all of the variables on the left hand side of the relationship, and the constant value on the right hand side (rhs). As in all LPs, all of the relationships (constraints and objective) are linear.On a superficial level, you now have all that you need to apply a linear programming solver: a set of linear constraints (≥ type, ≤ type, or = type) and a linear objective, and some variable bounds. LP solvers are not hard to find: several are available for free via the World Wide Web, and an LP solver is even included in the Microsoft Excelspreadsheet software for PCs. For this reason, many people with only very limited understanding of LP are formulating and solving them. The difficulty arises when unexpected results are returned: then a deeper understanding of LP is essential.Cornerpoints are ImportantBecause there are only two variables in the Acme Bicycle Company formulation, the problem can be sketched on the plane, as shown in Figure 2.2. The limiting value of each of the constraints is shown as a line. Each constraint eliminates part of the plane. For example, the vertical line labeled “x 1=2” is the limiting value of the inequality x 1≤2 and all points to the right of the line violate the constraint (i.e. are infeasible ). The areas eliminated by the constraints are shaded. The unshaded area represents points that are not eliminated by any constraint, and is called the feasible region . Points in the feasible region (which includes the bordering lines) satisfy all of the constraints.Figure 2.2 is to find the point in the value of the objective function. One(silly) way to do this is to randomlychoose feasible points and to calculate the value of the objective function at those points, keeping the point that gives the best value of the objective. Becausethere are an infinite number of points ineffective! There is no guarantee that the best point will be found, or even that an objective function value that is close tothe best possible value will be found. We need a more efficient way of searching the feasible region.We can develop a more efficient search technique based on a couple of simpleobservations. First, let’s plot points in the 2-dimensional x 1×x 2 plane that have the same valueof the objective function. As shown in Figure 2.3,points having the same value of Z (value of theobjective function) form a line. This is easy tounderstand if we replace Z by the specific valuethat we want to plot, e.g. Z=15x 1+10x 2 becomesthe line 15x 1+10x 2=20 plotted in Figure 2.3.Figure 2.3 also shows that all of the constant-profit lines are parallel. This is because all of theconstant-profit line equations differ only by the selected value of Z . If you were to calculate the Figure 2.2: The feasible region for the Acme Bicycle Company problem. Figure 2.3: Some constant-profitlines for the ABC problem.slope of any constant-profit line, the Z constant disappears; hence the slopes of all of the constant-profit lines are the same. For the Acme Bicycle Company, all of the constant profit lines have the same slope, given by d x 2/d x 1 = -15/10 = -1.5.The third important observation is that the value of Z is higher for the constant-profit lines towards the upper right in Figure 2.3. We will revisit this property in more detail when we cover nonlinear programming, but for now accept that this is a property of linear functions because they have a constant gradient .Now we can view the linear programming problem in a different way. Picture the objective function as a constant-profit line that is floating upwards from the lower left to the upper right in Figure 2.3, increasing in value as it floats higher. Now the linear programming question is this: what is the last point in the feasible region that the objective function passes through as it floats up to infinity? From Figure 2.3 we see that the last point is (2,2) with Z =50. This is the solution to the LP: the feasible point that has the best value of the objective function! Another analogy is to imagine the objective function sinking from infinity in the upper right, decreasing in value until it first bumps into the feasible region. What is the first feasible point that it bumps into (which will give the best value of the objective function)? It is of course (2,2) with Z =50.Here is the final and most important observation. Because lines define the feasible region, all of its external edges (or faces ) are flat linear surfaces that join together at cornerpoints . Again imagine the objective function as a line sinking from infinity: where will it first bump into this feasible region defined by flat faces and cornerpoints? As you can see by inspection, the linear objective function will always first bump into the feasible region at a cornerpoint! This is because a cornerpoint “sticks out farthest” in the direction of the sinking objective function line, hence first contact will be at a cornerpoint, and this will define the optimum point.In some cases, the objective function has exactly thesame slope as a face of the feasible region and firstcontact is between the objective function and thisface, as in Figure 2.4. This means that all of the objective function, and all are optimum: i.e. there are multiple optima . Notice, though, that if a face hasfirst contact, then the cornerpoints of the face also have first contact. The important idea is that first cornerpoint. Hence, an optimum solution to the LP isalways at a cornerpoint.This observation drastically simplifies the search for the optimum point: we need to look only at the relatively small number of cornerpoints of the feasible region instead of randomly sampling the infinite number of points on the interior of the feasible region. Figure 2.4: The slope of the objective function exactly matches the slope of the face of the feasibleregion.This fact underlies the simplex method of linear programming, which we shall begin to address in the next chapter. For now just observe in Fig. 2.2 that there are only five feasible cornerpoints that need to be visited to find an optimum solution to the Acme Bicycle Company LP.It is also easy to identify when there are multiple optima just by looking at the feasible cornerpoints. In two dimensions, when two feasible cornerpoints have the same optimum value of the objective function, then all of the points on the line segment joining the two cornerpoints have the same optimum value. It’s worth knowing this because one of the intermediate optimum points may be preferable to the cornerpoints for nonquantifiable reasons. It is possible to have three or more feasible cornerpoints with the same optimum value of the objective function in a three dimensional problem. Imagine, for example, that the feasible region is defined by a three-dimensional tetrahedron and that the slope of the objective function plane is exactly equal to the slope of one of the faces of the tetrahedron. Now all three feasible cornerpoints of the triangular face of the tetrahedron, and all of the points on the face of the tetrahedron, will have the same optimum value of the objective function.The Underlying Assumptions in Linear ProgrammingThe inescapable underlying assumption that is made in modeling the real world via linear programming is that a linear model is suitable. Models constructed solely from linear relationships have certain limitations. The most obvious is that some real-world phenomena are poorly modeled by lines. Nonlinear relationships such as curves or step-functions may be needed instead. If such nonlinear or discontinuous relationships are not adequately approximated by linear relationships, then you must use a technique other than linear programming.The two linear properties of additivity and proportionality preclude curves or step-functions. The additivity property prohibits cross-product terms, e.g. 5x1x2, which might represent interaction effects between the variables. For example, Acme may discover that ordering materials for both bicycles together from the same supplier lowers costs, but this effect cannot be modelled using a linear relationship.The proportionality property requires that the value of each term in the linear function is strictly proportional to the value of the variable in the term. For example, the objective function cost of using a certain variable is always directly proportional to the level of use of the variable: it is not possible to include a start-up cost. In the Acme model, the proportionality assumption is violated if, for example, the production efficiency improves significantly as the rate of production increases.Linear programming assumes that the variables are real-valued, meaning that they can take on fractional values. In the Acme problem we are trying to determine the rate of production, which can take on fractional values, e.g. produce mountain bicycles at the rate of 1.5 per day. Fractional values are not suitable in some problems, such as determining the number of people to staff a set of restaurants or the number of ships to purchase. Where at least one variable is restricted to taking on an integer value, then youmust use the methods of integer programming, which are covered in a later chapter. For now, note that it is not acceptable to treat integer problems as linear problems and then just round the results to the closest integer. This may yield an infeasible solution. The true optimum in an integer programming problem can be very far away from the approximate solution obtained by linear programming.A weakness common to all of mathematical programming is the assumption that the input data are perfectly accurate. You are assuming that the objective function coefficients (profit per bicycle for Acme), the constraint coefficients, and the constraint right hand sides (e.g. maximum team daily production of mountain bikes) are all correct. In the real world, these numbers are seldom known with accuracy. For example, how does Acme really know how much profit it makes per bicycle of either type? In large companies such a number is generally produced by the Accounting department, which uses data about average amount of material used in each bicycle, average price paid for the materials, average worker wages, yearly depreciation estimates on machines, average selling prices, etc., to estimate the “profit per mountain bike sold”. The emphasis is on “estimate”.So how useful is the optimum result produced by the mathematical program if the input data is of poor quality? It can be extremely useful, but you have to be careful. First and foremost, don’t treat the output result as if it is “the” answer: you might arrive at quite different results just by using slightly different estimates of the input parameters. For example, will you get a different result if the profit per mountain bike is estimated at $14 instead of the present $15? This is where sensitivity analysis is applied: using various tests to determine how sensitive the optimum result is to small changes in the values of the input parameters. It turns out that Acme should still make two each of the racers and mountain bikes per day even if the profit per mountain bike is $1 lower than estimated, but of course the total rate of profit generation will be lower. If knowing the total profit generation rate is crucial to Acme, then it is worthwhile to analyze various scenarios of profit per bicycle.Formulation Practice: the Smalltime Mutual Funds Company Formulating LPs well takes practice. In a classroom situation you will often know in advance that you are formulating a linear program. In contrast, in the real world you normally don’t know the type of the problem when you begin studying it, and that makes formulation much more difficult. The only way to improve your skills in formulation is practice, practice, practice. So here’s another example. Try to formulate it before looking at the solution as give below.You are the investments manager for the Smalltime Mutual Funds Company, and are trying to determine how to invest a pool of $14 million released by cashing out some of the stock investments. Table 2.1 summarizes the information that you have about a set of five possible investments.To be as conservative as possible, you assume that in the event of a loss by the investment, you lose all of your money. This is a fairly serious assumption, since mostmutual fund investments are likely to lose some but not all of their value. On the other hand, you also assume that if there is not a loss, then the investment will grow by the growth rate shown.For policy reasons, there are limits on how you can invest the money. You must allocate at least 35% of the total funds available to the balanced and bond investments. Of all the money put into equity, special equity and foreign investments, at least half must be in the equity investment. Finally, the expected lost capital must be less than 10%. Of course, your overall objective is to maximize the return on the original pool of money.This is a textbook problem, so the data is stated much more succinctly and clearly than in real world problems, which are plagued by misleading, hidden, and spurious information. Still, extracting an LP formulation from even a textbook word problem can be harder than it seems. You can test yourself by trying to answer the questions posed in the next few paragraphs before reading the answers.The first thing to do in an LP formulation is to identify the decision variables. Ask yourself what it is that you can control in this problem, what quantities do you need to find values for? What are the decision variables?The most straightforward formulation of this problem chooses variables representing the amount of money put into each investment:•x1: millions of dollars put into equity investment,•x2: millions of dollars put into special equity investment,•x3: millions of dollars put into balanced investment,•x4: millions of dollars put into foreign investment,•x5: millions of dollars put into bond investment.It is also possible to formulate this problem using variables representing the fraction of the total money to be put into each kind of investment. It is an awkward approach, but the results are the same in the end.Now that you have selected variables, the second question is: what is the objective function? You are to “maximize the return on the money invested”, but what does this mean? Since some money is gained from interest on the investments and some money is lost, let’s say the net return is:(expected growth from good investments) minus (expected losses from bad investments).If you are not sure if this is what the managers at Smalltime mean by “maximizing the return on money invested”, then make sure you ask! Effective mathematical programming is not just about number-crunching, it’s about crunching the right numbers.Assuming we have the correct idea about the objective, let’s now write it out in terms of the decision variables:maximize Z = 0.15(1-.18)x1 + 0.21(1-.31)x2 + 0.11(1-.09)x3 + 0.19(1-.19)x4 +0.08(1-.03)x5 - 0.18x1- 0.31x2 - 0.09x3 - 0.19x4 - 0.03x5The pattern is simple: the first five terms represent the income due to annual growth on the investments that do not lose money, and the second five terms represent the capital losses on the investments that lose money (remember that we assume you also get no interest on losing investments).Now we add the constraints. Scan the problem description. Can you identify all of the constraints? There are five:1.limit on proportion of total funds put into balanced and bond investments,2.limit on proportion of funds in the equity, special equity, and foreign investmentsthat goes into equity funds,3.limit on expected capital losses,And the two most frequently forgotten by students:4.limit on total funds available,5.nonnegativity constraints on the variables.Now we can write out these constraints.Limit on proportion of total funds put into balanced and bond investments:(x3+x5)/14 ≥ 0.35 ⇒x3+x5≥ 4.9Limit on proportion of funds in the equity, special equity, and foreign investments that goes into equity funds:x1/(x1+x2+x4) ≥ 0.5 ⇒−0.5x1 + 0.5x2 + 0.5x4≤ 0Limit on expected capital losses. We will interpret this to mean (expected capital loss)/(total capital invested), so:(0.18x1 + 0.31x2 + 0.09x3 + 0.19x4 + 0.03x5)/(x1 + x2 + x3 + x4 + x5) ≤ 0.1⇓0.08x1 + 0.21x2 – 0.01x3 + 0.09x4 – 0.07x5≤ 0Limit on total funds available (remember that the variables are in units of millions of dollars):(x 1 + x 2 + x 3 + x 4 + x 5) ≤ 14Nonnegativity of the variables:x 1, x 2, x 3, x 4, x 5 ≥ 0Are the assumptions inherent in any LP model appropriate for this model? The additivity and proportionality assumptions are likely correct here. Strictly speaking, the restriction to real numbers does not hold because you can’t subdivide a penny, but when dealing with very large numbers, this rounding to the nearest penny is negligible. The worst assumption here is that the parameters are known for certain. Both the annual growth rate and the probability of loss are educated guesses at best. Since $14 million depends on this decision, you should very carefully examine how changes in those numbers affect your solution. You will need to do some sensitivity analysis , a topic addressed later in this book.Another unrealistic assumption is that you lose all of your capital if the mutual fund loses value. There is an old saying that “the map is not the territory”, or to paraphrase for applied optimization “the model is not the real world”. You must be aware of the losses in accuracy inherent in the assumptions that you make during modeling. Always check any assumptions with the client to make sure they are appropriate for the task at hand. The Standard Form LPLinear programs can have objective functions that are to be maximized or minimized, constraints that are of three types (≤, ≥, =), and variables that have upper and lower bounds. An important subset of the possible LPs is the standard form LP . A standard form LP has these characteristics:• the objective function must be maximized,• all constraints are ≤ type,• all constraint right hand sides are nonnegative,• all variables are restricted to nonnegativity.A standard form LP is the simplest form of linearprogram, so we will begin our study of how to solveLPs using them. The most significant property of astandard form LP is that the origin (all variables setto zero) is always a feasible cornerpoint. This isbecause all standard form LPs have the kind ofshape illustrated in Figure 2.5. Knowing this initialfeasible cornerpoint greatly simplifies the search forthe optimum. After studying how to solve standard optimizing LPs that are not in standard form. In an algebraic representation, a standard form LPhaving m functional constraints and n variables looks like this:Figure 2.5: The origin is always a feasible cornerpoint in a standard form LP.•Objective function: maximize Z = c1x1 + c2x2 + … + c n x nwhere the c j, the coefficients in the objective function, represent the increase ordecrease in Z, the objective function value, per unit increase in x j. For the AcmeBicycle Company, Z is the daily profit, and the c i are the contributions to profitmade by the mountain bikes (c1) and the racers (c2).•m functional constraints, so called because they take a functional form:a11x1 + a12x2 + … + a1n x1n≤b1a12x1 + a22x2 + … + a2n x2n≤b2Ma m1x1 + a m2x2 + … + a mn x n≤b mwhere the b i are the resource limits, and the a ij are the coefficients of the functional constraint equations, expressing the usage resource i consumed by activity j. For the Acme Bicycle Company, the b i are limits on mountain bike production (b1), on racer production (b2) and on the metal finishing machine (b3).•n nonnegativity constraints: x1≥ 0, x2≥ 0, …, x n≥ 0.Don’t forget to explicitly include the nonnegativity constraints when writing out a problem formulation. You don’t want to allow negative values for the variables accidentally: in the Acme example, this would mean that you could perhaps make money by disassembling bicycles and selling the materials back to the suppliers! Fortunately, most commercial LP solvers will assume nonnegativity if you don’t mention it, but while you are learning the subject, show that you have considered the variable bounds by explicitly writing them out. There are some formulations in which negative variables are allowed, for example when the variable represents change from the current level, as in the level of water in a reservoir.In PracticeIt is easy to get started using linear programming on real problems. Modern LP solvers are generally coupled with a user-friendly front-end which permits easy input of the model and browsing of the results. The solvers use a variety of input formats, so choose a solver that includes an input format that suits the way you work:• A straight algebraic representation of the problem, with each constraint written out explicitly, such as in this book.• A spreadsheet representation, generally with columns for the variables and rows for the constraints.•An algebraic language that allows use of summations and indices to write the model very compactly. One statement in the algebraic language may generate numerous individual constraints for submission to the solver.• A proprietary input format.Algebraic modeling languages are the best developed input format, and are most used in practice. The ability to use summations and indices means that large industrial-scale models can be written in a concise form that is easier to debug. Many of the languages。

COBRA 安装指南1、安装这一系列软件时，要注意版本之间的兼容性否则...........可能现在的CORBRA版本只能用libSBML3.41及更低的版本，SBMLtoolbox的版本兼容性不知道2、安装软件的时候，先要搞清楚这些软件之间的依赖性。

在Windows XP 环境下，安装过程如下：步骤一，Install your LP solver of choice following the instructions for each solver. Test the functionality of the solver using examples provided with the solver and add the relevant folders to your Matlab path.首先，要下载线性规划（Linear Programing）的解题器（Solver），我是用glpk solver的。

* Download the precompiled version of glpkmex下载glpkmex 网址是/* Unzip the files to a folder of your choice解压下载的文件夹到目的文件夹* Add this folder to your matlab path添加目的文件夹到Matlab路径* Test with the examples that come with glpkmex (glpktest1.m,glpktest2.m)测试glpkmex（有两个demo包括glpktest1,glpktest2）步骤二，Install the SBML Toolbox following the instructions included in the installation package. Test the functionality of the Toolbox and add the relevant folders to your Matlab path.首先要安装libXML，然后安装SBML 工具箱，将文件夹添加到Matlab路径。