Lingo案例分析-供参考

1、最小费用运输问题单位 销地运价产地B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338280/302i.e:model:!6发点8收点运输问题;sets: warehouses/wh1.wh6/: capacity; vendors/v1.v8/: demand; links(warehouses,vendors): cost, volume;endsets!目标函数; min=sum(links: cost*volume);!需求

2、约束; for(vendors(J): sum(warehouses(I): volume(I,J)=demand(J);!产量约束; for(warehouses(I): sum(vendors(J): volume(I,J)=0, FLOOR returns the largest integer, I, such that I =X.LGM( X)This returns the natural (base e) logarithm of the gamma function of X (i.e., log of (X - 1)!). It is extended to noninteg

3、er values of X by linear interpolation.Note:伽玛方程表达式为：(x)=e(-t)*t(x-1)dt (积分的下限式0,上限式+) 利用分部积分法(integration by parts)我们可以得到 (x)=（x-1)*(x-1) LOG( X)This returns the natural logarithm of X.MOD( X,Y)This returns the value of X modulo Y, or, in other words, the remainder of an integer divide of X by Y.PO

4、W( X,Y) This returns the value of X rasied to the Y power.SIGN( X)This returns -1 if X =Staff required today, for each day of the weekThe right-hand side of this expression, Staff required today, is easy to calculate. It is simply the quantity REQUIRED( I). The left-hand side, Staff on duty today, i

5、s a bit trickier to compute. Given that all employees are on a five day on, two day off schedule, the number of employees working today is:Number working today = Number starting today + Number starting 1 day ago + Number starting 2 days ago + Number starting 3 days ago + Number starting 4 days ago.I

6、n other words, to compute the number of employees working today, we sum up the number of people starting today plus those starting over the previous four days. The number of employees starting five and six days back dont count because they are on their days off. So, using mathematical notation, what

7、 one might consider doing is adding the constraint:= j-4, j STARTi ?REQUIRED j , for j?DAYS Translating into LINGO notation, we can write this as:FOR( DAYS( J): SUM( DAYS( I) | I #LE# 5: START( J - I + 1) = REQUIRED( J);In words, the LINGO statement says, for each day of the week, the sum of the emp

8、loyees starting over the five day period beginning four days ago and ending today must be greater-than-or-equal-to the required number of staff for the day. This sounds correct, but there is a slight problem. If we try to solve our model with this constraint we get the error message:To see why we ge

9、t this error message, consider what happens on Thursday. Thursday has an index of 4 in our set DAYS. As written, the staffing constraint for Thursday will be:START( 4 - 1 + 1) + START( 4 - 2 + 1) + START( 4 - 3 + 1) + START( 4 - 4 + 1) + START( 4 - 5 + 1) = REQUIRED( 4);Simplifying, we get:START( 4)

10、 + START( 3) + START( 2) + START( 1) + START( 0) = REQUIRED( 4);The START( 0) term is the root of our problem. START is defined for days 1 through 7. START( 0) does not exist. An index of 0 on START is considered out of range. We would like to have any indices less-than-or-equal-to 0 wrap around to

11、the end of the week. Specifically, 0 would correspond to Sunday (7), -1 to Saturday (6), and so on. LINGO has a function that does just this called WRAP. The WRAP function takes two argumentscall them INDEX and LIMIT. Formally speaking, WRAP returns J such that J = INDEX - K * LIMIT, where K is an i

12、nteger such that J is in the interval 1, LIMIT. Informally speaking, WRAP will subtract or add LIMIT to INDEX until it falls in the range 1 to LIMIT. Therefore, this is just what we need to wrap around an index in multiperiod planning models. Incorporating the WRAP function, we get the corrected, fi

13、nal version of our staffing constraint:FOR( DAYS( J): SUM( DAYS( I) | I #LE# 5: START( WRAP( J - I + 1, 7) = REQUIRED( J);The Solution：Below is our staffing model in its entirety:SETS: DAYS / MON TUE WED THU FRI SAT SUN/: REQUIRED, START;ENDSETSDATA: REQUIRED = 20 16 13 16 19 14 12;ENDDATAMIN = SUM(

14、 DAYS( I): START( I);FOR( DAYS( J): SUM( DAYS( I) | I #LE# 5: START( WRAP( J - I + 1, 7) = REQUIRED( J);Model: STAFFDEMSolving the model, we get the solution report:Optimal solution found at step: 8Objective value: 22.00000 Variable Value Reduced CostSTART( MON) 8.000000 0.0000000START( TUE) 2.00000

15、0 0.0000000START( WED) 0.0000000 0.0000000START( THU) 6.000000 0.0000000START( FRI) 3.000000 0.0000000START( SAT) 3.000000 0.0000000START( SUN) 0.0000000 0.0000000 Row Slack or Surplus Dual Price 1 22.00000 1.000000 2 0.0000000 -0.2000000 3 0.0000000 -0.2000000 4 0.0000000 -0.2000000 5 0.0000000 -0.

16、2000000 6 0.0000000 -0.2000000 7 0.0000000 -0.2000000 8 0.0000000 -0.2000000Solution to STAFFDEMThe objective value of 22 means we need to hire 22 workers. We start our workers according to the schedule:MonTueWedThuFriSatSunStart8206330If we look at the surpluses on our staffing requirement rows (ro

17、ws 2 - 7), we see that the slack values are 0 on all of the days. This means there are no more workers than required and we just meet staffing requirements on every day. Even though this is a small model, trying to come up with a solution this efficient by hand would be a difficult task.职员时序安排模型 一项工

18、作一周7天都需要有人（比如护士工作），每天（周一至周日）所需的最少职员数为20、16、13、16、19、14和12，并要求每个职员一周连续工作5天，试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。model:sets: days/mon.sun/: required,start;endsetsdata: !每天所需的最少职员数; required = 20 16 13 16 19 14 12; enddata!最小化每周所需职员数; min=sum(days: start); for(days(J): sum(days(I) | I #le# 5:start(wrap(J-I

19、+1,7) = required(J);end计算的部分结果为Global optimal solution found at iteration: 0 Objective value: 22.00000 Variable Value Reduced Cost REQUIRED( MON) 20.00000 0.000000 REQUIRED( TUE) 16.00000 0.000000 REQUIRED( WED) 13.00000 0.000000 REQUIRED( THU) 16.00000 0.000000 REQUIRED( FRI) 19.00000 0.000000 REQU

20、IRED( SAT) 14.00000 0.000000 REQUIRED( SUN) 12.00000 0.000000 START( MON) 8.000000 0.000000 START( TUE) 2.000000 0.000000 START( WED) 0.000000 0.3333333 START( THU) 6.000000 0.000000 START( FRI) 3.000000 0.000000 START( SAT) 3.000000 0.000000 START( SUN) 0.000000 0.000000每周最少:22个职员，周一:8人，周二:2人，周三:0人

21、，周四:6人，周五和周六:3人，周日:0人。用Matlab编程为：先建立一个M文件：fssp.m然后再建立：%fssp.mf=1,1,1,1,1,1,1; %A=-1,0,0,-1,-1,-1,-1; -1,-1,0,0,-1,-1,-1; -1,-1,-1,0,0,-1,-1; -1,-1,-1,-1,0,0,-1; -1,-1,-1,-1,-1,0,0; 0,-1,-1,-1,-1,-1,0; 0,0,-1,-1,-1,-1,-1;b=-20,-16,-13,-16,-19,-14,-12;l=0,0,0,0,0,0,0;xo,fo,exitflag=linprog(f,A,b,l)结果为

22、：xo = 8.0000 2.0000 0.0000 6.0000 3.0000 3.0000 0.0000fo = 22.0000exitflag = 13.7集循环函数（Set Looping Functions）Set looping functions operate over an entire set and, with the exception of the FOR function, produce a single result. The syntax for a set looping function is:function( setname ( set_index_l

23、ist) | conditional_qualifier : expression_list);function corresponds to one of the set looping functions listed below. setname is the name of the set you want to loop over. The set_index_list is optional and is used to create a list of indices, which correspond to the parent primitive sets that form

24、 the setname set. As LINGO loops through the members of the setname set, it will set the values of the indices in the set_index_list to correspond to the current member of the setname set. The conditional_qualifier is optional and may be used to limit the scope of the set looping function. When LING

25、O is looping over each member of the setname set, it evaluates the conditional_qualifier. If the conditional_qualifier evaluates to true, then function is performed for the set member. Otherwise, it is skipped. The expression_list is a list of expressions to be applied to each member of the setname

26、set. When using the FOR function, the expression_list may contain multiple expressions, separated by semicolons. These expressions will be added as constraints to the model. When using the remaining three set looping functions (SUM, MAX, and MIN), the expression_list must contain one expression only

27、. If the set_index_list is omitted, all attributes referenced in the expression_list must be defined on the setname set.The available set looping functions are listed below:集循环函数遍历整个集进行操作。其语法为function(setname(set_index_list)|conditional_qualifier:expression_list);function相应于下面罗列的四个集循环函数之一；setname是要遍

28、历的集；set_ index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式。如果省略set_index_list

29、，那么在expression_list中引用的所有属性的类型都是setname集。FOR( setname ( set_index_list) | cond_qualifier: exp_list)This generates the expressions contained in exp_list for all members of the setname set. FOR is used to generate constraints over all the members of a set, and is one of the most powerful features of L

30、INGO.MAX( setname ( set_index_list) | cond_qualifier: expression) This returns the maximum value of expression taken over the setname set.MIN( setname ( set_index_list) | cond_qualifier: expression) This returns the minimum value of expression taken over the setname set.PROD( setname ( set_index_lis

31、t) | cond_qualifier: expression) This returns the product of an expression over the setname set.SUM( setname ( set_index_list) | cond_qualifier: expression)This returns the sum of an expression over the setname set.Set looping functions are discussed in more detail in section Set Looping Functions i

32、n Chapter 2.3.8 辅助功能函数（Miscellaneous Functions）IF( logical_condition, true_result, false_result)The IF function evaluates logical_condition and, if true, returns true_result, otherwise it returns false_result. For example, consider the following simple model that uses IF to compute fixed production

33、costs:MIN = COST;COST = XCOST + YCOST;XCOST = IF( X #GT# 0, 100, 0) + 2 * X;YCOST = IF( Y #GT# 0, 60, 0) + 3 * Y;X + Y = 30;Model: IFCOSTWe produce two products梄 and Y. We want to minimize total cost, subject to producing at least 30 total units of X and Y. If we produce X, there is a fixed charge o

34、f 100 along with a variable cost of 2. Similarly, for Y, these respective values are 60 and 3. We use the IF function to determine if either of the products are being produced in order to apply the relevant fixed cost. This is accomplished by testing to see if their production levels are greater tha

35、n 0. If so, we return the fixed cost value, otherwise, we return zero.Experienced modelers know that, without the benefit of an IF function, modeling fixed costs requires invoking some tricks using binary integer variables. The resulting models are not as intuitive as models constructed using IF. Th

36、e caveat, however, is that the IF function is not a linear function. At best, the graph of an IF function will be piecewise linear. In our current example, the IF functions are piecewise linear with a discontinuous break at the origin. As we discuss in the chapter On Mathematical Modeling, it is alw

37、ays best to try and keep a model linear. Barring this, it is best for all functions in a nonlinear model to be continuous. Clearly, then, the IF function is a problem in that it violates both these conditions. Thus, models containing IF functions may be tough to solve to global optimality. Fortunate

38、ly, LINGO has two options that can help overcome the difficult nature of models containing IF functions條inearization and global optimization.To illustrate the difficulty in solving models with discontinuous functions such as IF, we will solve our example model with both linearization and global opti

39、mization disabled. When we do this, we get the following solution:Local optimal solution found at iteration: 42Objective value: 160.0000 Variable Value COST 160.0000 XCOST 160.0000 YCOST 0.000000 X 30.00000 Y 0.000000This solution involves producing only X at a total cost of 160. Clearly, this is me

40、rely a locally optimal point, given that producing only Y and not X will result in a lower total cost of 150. In order to find the globally optimal point we must resort to either the linearization or global optimization features in LINGO. Briefly, linearization seeks to reformulate a nonlinear model

41、 into a mathematically equivalent linear model. This is desirable for two reasons. First, and most important, linear models can always be solved to global optimality. Secondly, linear models will tend to solve much faster than equivalent nonlinear models. Unfortunately, linearization can抰 always tra

42、nsform a model into an equivalent linear state, in which case, it may be of no benefit. Fortunately, our sample model can be entirely linearized. To enable the linearization option, run the LINGO|Options command and set the Linearization Degree to High on the General Solver tab. Global optimization

43、breaks a model down into a series of smaller, local models. Once this series of local models has been solved, a globally optimal solution can be determined. To enable global optimization, run the LINGO|Options command, select the Global Solver tab, then click on the Global Solver checkbox. Note that

44、 the global solver is an add-on option to LINGO. The global solver feature will not be enabled for some installations. Run the Help|About LINGO command to determine if your installation has the global solver capability enabled.Regardless, whether using the linearization option or the global solver,

45、LINGO obtains the true, global solution:Global optimal solution found at iteration: 6Objective value: 150.0000 Variable Value COST 150.0000 XCOST 0.000000 YCOST 150.0000 X 0.000000 Y 30.00000Note:Starting with release 9.0, the false branch of the IF function may contain arithmetic errors without cau

46、sing the solver to trigger an error. This makes the IF function useful in avoiding problems when the solver strays into areas where certain functions become undefined. For instance, if your model involves division by a variable, you might use IF as follows: IF( X #GT# 1.E-10, 1/X, 1.E10).WARN( text,

47、 logical_condition)This function displays the message 憈ext?if the logical_condition is met. This feature is useful for verifying the validity of a models data. In the following example, if the user has entered a negative interest rate, the message INVALID營NTEREST燫ATE is displayed:! A model of a home

48、 mortgage;DATA:! Prompt the user for the interest rate, years, and value of mortgage. We will compute the monthly payment; YRATE = ?; YEARS = ?; LUMP = ?;ENDDATA! Number of monthly payment; MONTHS = YEARS * 12;! Monthly interest rate; ( 1 + MRATE) 12 = 1 + YRATE;! Solve next line for monthly payment

49、; LUMP = PAYMENT * FPA( MRATE, MONTHS);! Warn them if interest rate is negative WARN( INVALID INTEREST RATE, YRATE #LT# 0);USER( user_determined_arguments)The user can supply this in an external DLL or object code file. For a detailed example on the use of USER, see User Defined Functions.4.灵敏度分析i.e

50、：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables=5; Global

51、 optimal solution found. Objective value: 280.0000 Total solver iterations: 3 Variable Value Reduced Cost DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 Row Slack or Surplus Dual Price 1 280.0000 1.000000 2 24.00000 0.000000 3 0.000000 10.00000 4 0.000000 10.00000 5 5.0000

52、00 0.000000“Slack or Surplus”给出松驰变量的值：第1行松驰变量 =280（模型第一行表示目标函数，所以第二行对应第一个约束）第2行松驰变量 =24第3行松驰变量 =0第4行松驰变量 =0第5行松驰变量 =5“Reduced Cost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时, 目标函数的变化率。其中基变量的reduced cost值应为0， 对于非基变量 Xj, 相应的 reduced cost值表示当某个变量Xj 增加一个单位时目标函数减少的量( max型问题)。本例中：变量tables对应的reduced cost值为5，表示当非基变量

53、tables的值从0变为 1时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值 = 280 - 5 = 275。“DUAL PRICE”（对偶价格）表示当对应约束有微小变动时, 目标函数的变化率。输出结果中对应于每一个约束有一个对偶价格。 若其数值为p， 表示对应约束中不等式右端项若增加1 个单位，目标函数将增加p个单位（max型问题）。显然，如果在最优解处约束正好取等号（也就是“紧约束”，也称为有效约束或起作用约束），对偶价格值才可能不是0。本例中：第3、4行是紧约束，对应的对偶价格值为10，表示当紧约束 3) 4 DESKS + 2 TABLES

54、 + 1.5 CHAIRS = 20 变为 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS 1的正整数）：N点求解 Barrier: 障碍法 (即内点法)6.综合案例旅行售货员问题（Traveling Salesman Problem）有一个推销员，从城市1出发，要遍访城市2，3，n各一次，最后返回城市1。已知从城市i到j的旅费为，问他应按怎样的次序访问这些城市，使得总旅费最少？可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，引入一些0-1整数变量：其目标只是使为最小。这里有两个

55、明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。123456到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件。 为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线

56、都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有把这k个式子相加，有，矛盾！故假设不正确，结论（1）得证。下面证明（2），采用构造法。对于任意的总巡回，可取访问城市i的顺序数，取值范围为。因此，。下面来证明总巡回满足该约束条件。()总巡回上的边（）非总巡回上的边从而结论（2）得证。这样我们把TSP转化成了一个混合整数线性规划问题。显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发

57、现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。!旅行售货员问题;model:sets: city / 1. 5/: u; link( city, city): dist, ! 距离矩阵; x;endsets n = size( city);data: !距离矩阵，它并不需要是对称的; dist = 0 2 6 7 4 2 0 5 3 8 6 5 0 9 7 7 3 9 0 9 4 8 7 9 0 ; !随机产生，这里可改为你要解决的问题的数据;enddata !目标函数; min = sum( link: dist * x); FOR( city( K)

58、: !进入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保证不出现子圈; for(city(I)|I #gt# 1: for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1); ); !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解; for(city(I) | I #gt# 1: u(I)=n-2 ); !定义X为01变量; for( link: bin( x)

59、;endGlobal optimal solution found. Objective value: 25.00000 Extended solver steps: 0 Total solver iterations: 19 Variable Value Reduced Cost N 5.000000 0.000000 U( 1) 0.000000 0.000000 U( 2) 0.000000 0.000000 U( 3) 2.000000 0.000000 U( 4) 1.000000 0.000000 U( 5) 3.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 2.000000 0.000000 DIST( 1, 3) 6.000000 0.000000 DIST( 1, 4) 7.000000 0.000000 DIST( 1, 5) 4.000000 0.0000