Lingo solution report中各项的含义.docx

即以此功德，庄严佛净土。上报四重恩，下救三道苦。惟愿见闻者，悉发菩提心。在世富贵全，往生极乐国。（一）优化模型的组成优化模型包括以下3部分：lObjective Function：目标函数是一个能准确表达所要优化问题的公式。lVariables：Decision variables（决策变量），在模型中所使用的变量。lConstraints：约束条件。（二）Lingo软件使用的注意事项（1）LINGO中不区分大小写字母，变量（和行名）可以使用不超过32个字符表示，且必须以字母开头。（2）在命令方式下（Command Window中），必须先输入MODEL：表示开始输入模型。LINGO中模型以“MODEL:”开始，以“END”结束。对简单的模型，这两个语句也可以省略。（3）LINGO中的语句的顺序是不重要的，因为LINGO总是根据“MAX=”或“MIN=”语句寻找目标函数，而其它语句都是约束条件（当然注释语句和TITLE除外）。（4）LINGO模型是由一系列语句组成，每个语句以分号“;”结束。（5）LINGO中以感叹号“!”开始的是说明语句（说明语句也需要以分号“;”结束）。（6）LINGO中解优化模型时假定所有变量非负（除非用限定变量取值范围的函数free或sub或slb另行说明）。（7）当您要判断表达式输入是否有错误时，也可以使用菜单“Lingo“的”Picture“选项。(8) 用命令BND(下界, 变量名, 上界)设置变量的上界和下界(9) 用命令free(x1)取消变量x1的非负限制，x1可以取正实数和负实数(10)一般整数变量可以用GIN(变量名)来标识，0-1型变量可以用BIN(变量名)来标识（三）Solution Report各项的含义例1 将以下模型粘贴到Lingo中求解，其中第一行MODEL和最后一行END在Lingo Model 窗口下可以不要。MODEL:min = 2*x1 + 3*x2;x1 + x2 = 350;x1 = 100;2*x1 + x2 = 600;END得到如下的结果报告Global optimal solution found. Objective value: 800.0000 Infeasibilities: 0.000000 ！指矛盾约束的数目； Total solver iterations: 2 Model Class: LP Total variables: 2 Nonlinear variables: 0 Integer variables: 0 Total constraints: 4 Nonlinear constraints: 0 Total nonzeros: 7 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 250.0000 0.000000 X2 100.0000 0.000000 Row Slack or Surplus Dual Price 1 800.0000 -1.000000 2 0.000000 -4.000000 ! 模型第一行表示目标函数，第二行对应第一个约束; 3 150.0000 0.000000 4 0.000000 1.000000下面对Solution Report（LINGO的结果报告窗口）的各个部分进行说明： Global optimal solution found 表示全局最优解找到. Objective value: 800.0000 表示最优目标值为800.0000. Total solver iterations: 2 表示用单纯行法进行了两次迭代. Variable 表示变量, 此问题中有两个变量X1, X2. Value 给出最优解中各变量(Variable)的值: X1=250.0000, X2=100.0000.Reduced Cost 实际上是与最优单纯形表中的检验数相差一个负号的一个数，以前没有注意到检验数就是非基变量前面的系数啊。我以前没有注意到最优单纯形表中的各个检验数就是与之对应的非基向量前的系数！ Reduced Cost指为了使某个变量在解中的数值增加一个单位，目标函数值必须付出的代价。如果一个变量的Reduced Cost值为8，为了使该变量增加一个单位，在最大化（最小化）问题中，目标函数值将减少（增大）8个单位。 The reduced cost of a variable may be interpreted as the amount of penalty you would have to pay tointroduceone unitof that variable into the solution. Again, if you have a variable with a reduced cost of 10, you would have to pay a penalty of 10 units to introduce the variable into the solution. In other words, the objective value would fall by 10 units in a maximization model or increase by 10 units in a minimization model. 在一个最大值的模型中，Reduced Cost 对应的非基变量增加一个单位，目标值会有减少Reduced Cost；在一个最小值模型中，Reduced Cost对应的非基变量增加一个单位，目标值会增大Reduced Cost。Reduced Cost它也可以认为是：在最优化问题中，要使某个变量进入基，该变量在目标函数中的该变量前的系数应该改变的数量。(在Min问题中要选单纯形表最后一行中最大的正的判别数对应的列为主列此列对应的变量是进基变量，其目标是使所有的判别数都非正；在Max问题中要选单纯形表最后一行最小的负数对应的变量作为进基变量，其目标是使所有的判别数都非负)例如：在一个最大化（最小化）问题中，如果一个变量的Reduced Cost值为8，则为了使该变量进基，目标函数中该变量前的系数就必须减小（增加）8个单位(已经经过试验验证,该变量进基后Reduced Cost = 0)。 For example, if a variable had a reduced cost of 10, the objective coefficient of that variable would have todecrease by 10 units in a maximizationproblem and/orincrease by 10 units in a minimization problemfor the variable to become an attractive alternative to enter into the solution.非基向量要进入基必须将它对应的检验数消为0，直观的将该非基向量的检验数取个负号加到最后一行即可，对应在方程上实际上是此检验数乘以该非基变量后的结果加到最后一行，所以前边有了系数这一说。Reduced Cost 给出最优的单纯形表中目标函数行中变量对应的系数. 其中基变量的Reduced Cost值一定为0;对于非基变量(非基变量本身的取值一定为0)和max问题,相应的Reduced Cost值表示当该非基变量增加一个单位(其它非基变量保持不变)时目标函数的减少的量。这估计也是Reduced Cost的reduced 所在，很直观。在这个例子中最优解中两个变量都是基向量, 因此对应的Reduced Cost的值都为0.Slack or Surplus表示接近等于的程度。在约束条件是=中，通常叫过剩变量。如果约束条件是=，则Slack or Surplus为0，该约束是个紧约束(或有效约束)。如果一个约束条件错误，作为一个不可行解，Slack or Surplus为负数。Slack or Surplus表示的是：约束离相等还差多少。如果一个约束是矛盾的（模型无可行解），则Slack or surplus的值是负数。知道这些，可以帮助我们发现在一个不可实行的模型（指没有存在同时满足所有约束条件的变量集合）中的错误的约束条件。第2和第4行松弛变量均为0,说明对于最优解来讲,两个约束(第2和4行)均取等号,即都是紧约束.Dual Price (Shadow price)给出对偶价格的值。表示每增加一个单位(约束右边的常数)，目标值改变的数量（在最大化问题中目标函数值是增加，在最小化问题中目标函数值是减少）。比如，在上一个Min模型中第四行的1，表示2*x1 + x2 = 600增加一个单位到2*x1 + x2 = 601，可以使目标值增加-1(因为第一行是目标函数的Dual Price是-1)，即Objective value = 799; 增加-1个单位到599会使目标值增加到801。You can interpret the dual price as the amount that the objective would improve as the right-hand side, or constant term, of the constraint is increased by one unit. Notice that improve is a relative term. In a maximization problem, improve means the objective value would increase. However, in a minimization problem, the objective value would decrease if you were to increase the right-hand side of a constraint with a positive dual price.对偶价格补充一例：max=100*x+150*y;!约束条件;x=80;y=100;x*2+y=180; Global optimal solution found. Objective value: 19000.00 Infeasibilities: 0.000000 Total solver iterations: 1 Model Class: LP Total variables: 2 Nonlinear variables: 0 Integer variables: 0 Total constraints: 4 Nonlinear constraints: 0 Total nonzeros: 6 Nonlinear nonzeros: 0 Variable Value Reduced Cost X 40.00000 0.000000 Y 100.0000 0.000000 Row Slack or Surplus Dual Price 1 19000.00 1.000000! 注意第一行为目标函数，目标函数加1则目标值加1 2 40.00000 0.000000 3 0.000000 100.0000 4 0.000000 50.00000对偶变量值也叫影子价格，这是由于它们表示可以用多大的价格去购买（租用）单位资源。上面的模型显示，某人最多愿意花100元购买（租用）一个Y。对偶问题其实可以在Lingo中自动生成，这可以采用以下两步实现1. 以上原始线性规划问题输入到Lingo中max = 50*x1 + 30*x2;4*x1 + 3*x2 = 120;2*x1 + x2 Dual Model 即可生成原线性规划的对偶问题，结果如下MODEL: MIN= 120 * _2 + 50 * _3;X1 4 * _2 + 2 * _3 = 50;! 我以前不知道X1原来是行号X2 3 * _2 + _3 = 30;END例2 某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？用DESKS、TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。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;求解这个模型，查看报告窗口（Reports Window）:Global optimal solution found. Objective value: 280.0000 Infeasibilities: 0.000000 Total solver iterations: 2 Model Class: LP Total variables: 3 Nonlinear variables: 0 Integer variables: 0 Total constraints: 5 Nonlinear constraints: 0 Total nonzeros: 13 Nonlinear nonzeros: 0 Variable Value Reduced Cost DESKS 2.000000 0.000000TABLES 0.000000 5.000000 !Tables加1时,Objective value要reduce 5变为275 CHAIRS 8.000000 0.000000 ! 验证方法是将 tables = 5 改为 tables =1 Row Slack or Surplus Dual Price 1 280.0000 1.000000 ! 注意第一行为目标函数，目标函数加1则目标值加1 2 24.00000 0.000000 3 0.000000 10.00000 4 0.000000 10.00000 5 5.000000 0.000000“Objective value:280.0000”表示最优目标值为280。 “Value”给出最优解中各变量的值：造2个书桌（desks）, 0个餐桌（tables）, 8个椅子（chairs）。所以desks、chairs是基变量（非0），tables是非基变量（0）。观察单纯性表的最后一行(f行)，当所有的检验数都非负，单纯形表左侧的行基向量对应的主列确实是非零的。 还要注意最优解的基变量中无松弛变量（松弛变量的引入将不等式变为等式约束）“Slack or Surplus”给出松驰变量的值：第1行松驰变量 = 280（模型第一行表示目标函数，所以第二行对应第一个约束）第2行松驰变量 = 24第3行松驰变量 = 0第4行松驰变量 = 0第5行松驰变量 = 5If a constraint is exactly satisfied as an equality, the slack or surplus value will be zero. If a constraint is violated, as in an infeasible solution, the slack or surplus value will be negative. Knowing this can help you find the violated constraints in an infeasible modela model for which there doesnt exist a set of variable values that simultaneously satisfies all constraints.“Reduced Cost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时, 目标函数的变化率。其中基变量的reduced cost值应为0， 对于非基变量 Xj, 相应的 reduced cost值表示当某个变量Xj 增加一个单位时目标函数减少的量( max型问题)。本例中：变量tables对应的reduced cost值为5，表示当非基变量tables的值从0变为 1时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值 = 280 - 5 = 275。“DUAL PRICE”（对偶价格）表示当对应约束有微小变动时, 目标函数的变化率。输出结果中对应于每一个约束有一个对偶价格。 若其数值为p，表示对应约束中不等式右端项若增加1 个单位，目标函数将增加p个单位（max型问题）。显然，如果在最优解处约束正好取等号（也就是“紧约束”，也称为有效约束或起作用约束），对偶价格值才可能不是0。本例中：第3、4行是紧约束，对应的对偶价格值为10，表示当紧约束 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20 变为 4 DESKS + 2 TABLES + 1.5 CHAIRS options-general solver-dual computations:prices & ranges-ok. 菜单lingo-range 灵敏度分析：如果做敏感性分析，则系统报告当目标函数中的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中INFINITY表示正无穷。1） 如本例目标函数为： max=60*desks+30*tables+20*chairs; 目标函数中DESKS的变量前面的系数为60，当它在60 - 4,60 + 20= 56, 80 变化时，最优基保持不变 。2）如本例约束条件为：8*desks+6*tables+chairs = 48;4*desks+2*tables+1.5*chairs = 20;2*desks+1.5*tables+.5*chairs = 8;tables = 5; 第一个约束右端项为48，当它在48 - 24, 48 + INFINITY=24, INFINITY 范围变化时，最优基保持不变 。其他约束的灵敏度分析这里就不再赘述，道理是一样的！灵敏度分析的结果是Ranges in which the basis is unchanged: Objective Coefficient Ranges: Current Allowable Allowable Variable Coefficient Increase Decrease DESKS 60.00000 20.00000 4.000000 TABLES 30.00000 5.000000 INFINITY CHAIRS 20.00000 2.500000 5.000000 Righthand Side Ranges: Current Allowable Allowable Row RHS Increase Decrease 248.00000 INFINITY 24.00000 3 20.00000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000目标函数中DESKS变量原来的费用系数为60，允许增加（Allowable Increase）=20、允许减少（Allowable Decrease）=4，说明当它在60-4，60+20 = 56，80范围变化时，最优基保持不变。对TABLES、CHAIRS变量，可以类似解释。由于此时约束没有变化（只是目标函数中某个费用系数发生变化），所以最优基保持不变的意思也就是最优解不变（当然，由于目标函数中费用系数发生了变化，所以最优值会变化）。第2行约束中右端项（Right Hand Side，简写为RHS）原来为48，当它在48-24，48+ = 24，范围变化时，最优基保持不变。第3、4、5行可以类似解释。不过由于此时约束发生变化，最优基即使不变，最优解、最优值也会发生变化。灵敏性分析结果表示的是最优基保持不变的系数范围。由此，也可以进一步确定当目标函数的费用系数和约束右端项发生小的变化时，最优基和最优解、最优值如何变化。下面我们通过求解一个实际问题来进行说明。例3： 一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1） 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3） 由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？解：模型代码如下max = 72*x1+64*x2;x1+x2 = 50;12*x1+8*x2 = 480;3*x1 = 100;求解这个模型并做灵敏性分析，结果如下。 Global optimal solution found at iteration: 0 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 ! 注意第一行为目标函数，目标函数加1则目标值加1 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 ! 我以前不知道Coefficient是目标函数中X1,X2之前的系数X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 ! 以前不知道这些是约束条件右手边的值 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000结果告诉我们：这个线性规划的最优解为x1=20，x2=30，最优值为z=3360，即用20桶牛奶生产A1, 30桶牛奶生产A2，可获最大利润3360元。输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3个附加问题给予说明。 3个约束条件的右端不妨看作3种“资源”：原料、劳动时间、车间甲的加工能力。输出中Slack or Surplus给出这3种资源在最优解下是否有剩余：原料、劳动时间的剩余均为零，车间甲尚余40（公斤）加工能力。 目标函数可以看作“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长。输出中DUAL PRICES 给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量：原料增加1个单位（1桶牛奶）时利润增长48（元），劳动时间增加1个单位（1小时）时利润增长2（元），而增加非紧约束车间甲的能力显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，车间甲的影子价格为零。读者可以用直接求解的办法验证上面的结论，即将输入文件中原料约束milk）右端的50改为51，看看得到的最优值（利润）是否恰好增长48（元）。用影子价格的概念很容易回答附加问题1）：用35元可以买到1桶牛奶，低于1桶牛奶的影子价格48，当然应该作这项投资。回答附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单地回答。上面输出给出了最优基不变条件下目标函数系数的允许变化范围：x1的系数为（72-8，72+24）=（64，96）；x2的系数为（64-16，64+8）=（48，72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题3）：若每公斤A1的获利增加到30元，则x1系数变为303=90，在允许范围内，所以不应改变生产计划，但最优值变为9020+6430=3720。下面对“资源”的影子价格作进一步的分析。影子价格的作用（即在最优解下“资源”增加1个单位时“效益”的增量）是有限制的。每增加1桶牛奶利润增长48元（影子价格），但是，上面输出的CURRENT RHS 的ALLOWABLE INCREASE 和 ALLOWABLE DECREASE 给出了影子价格有意义条件下约束右端的限制范围： milk）原料最多增加10（桶牛奶），time）劳动时间最多增加53（小时）。现在可以回答附加问题1）的第2问：虽然应该批准用35元买1桶牛奶的投资，但每天最多购买10桶牛奶。顺便地说，可以用低于每小时2元的工资聘用临时工人以增加劳动时间，但最多增加53.3333小时。需要注意的是：灵敏性分析给出的只是