导读：第二章线性规划的对偶问题，2.1写出下列线性规划问题的对偶问题，2.2已知线性规划问题maxz＝CX，其对偶问题的解的变化：，（1）问题的第k个约束条件乘上常数λ（λ≠0），2.3已知线性规划问题minz＝8x1＋6x2＋3x3＋6x4，(1)写出其对偶问题，(2)已知原问题最优解为x*＝（1，直接求出对偶问题的最优解，2.4已知线性规划问题minz＝2x1＋x2＋5x3＋6x4对偶变量，其对第二章 线性规划的对偶问题 第二章 线性规划的对偶问题 习题
2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋ x2＋2x3
(2) max z ＝2x1＋ x2＋3x3＋ x4 st.
x1＋ x2＋2 x3≤10
x1＋ x2＋ x3 ＋ x4 ≤5 4x1＋ x2＋ x3≤20
2x1－ x2＋3x3
＝－4 xj ≥0
（j＝1,2,3）
－ x3＋ x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4
(4) min z ＝－5 x1－6x2－7x3 st.
x1－2x2＋3x3＋4x4≤3
－x1＋5x2－3x3 ≥15 x2＋3x3＋4x4≥－5
－5x1－6x2＋10x3 ≤20
2x1－3x2－7x3 －4x4＝2＝
x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3 无约束
x1≤0， x2≥0，x3 无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3x'1代换。 2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4 st.
＋ x4≥3 3x1＋ x2＋ x3＋ x4≥6 x3 ＋ x4＝2
xj≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题 min z＝2x1＋x2＋5x3＋6x4
对偶变量 st. 2x1
＋x3＋ x4≤8
y1 2x1＋2x2＋x3＋2x4≤12
xj≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。
４７ 第二章 线性规划的对偶问题 2.5 考虑线性规划问题
max z＝2x1＋4x2＋3x3
3x1＋4 x2＋2x3≤60 2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 xj≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。 2.6 已知线性规划问题
max z＝10x1＋5x2 st.
3x1＋4x2≤9 5x1＋2x2≤8 xj≥0（j＝1,2） 用单纯形法求得最终表如下表所示：
x2 x1 x1 0 1 0 x2 1 0 0 x3 x4 b ?j=cj-Zj 5 141― 75― 143 142 725― 14―3 21
试用灵敏度分析的方法分别判断： （1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变； （2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变； （3）问题的目标函数变为max z ＝12x1＋4x2时上述最优解的变化； （4）约束条件右端项由????时上述最优解的变化。 ???变为?2.7 线性规划问题如下： max z＝―5x1＋5x2＋13x3
―x1＋x2＋3x3≤20
① 12x1＋4x2＋10x3≤90
② ?9??8??11??19?xj≥0 （j＝1,2,3） 先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？ （1） 约束条件①的右端常数由20变为30； ４８ 第二章 线性规划的对偶问题 （2） （3） （4） （5） 约束条件②的右端常数由90变为70； 目标函数中x3的系数由13变为8； TTx1的系数列向量由（―1，12）变为（0，5）； 增加一个约束条件③：2x1＋3x2＋5x3≤50； （6） 将原约束条件②改变为：10x1＋5x2＋10x3≤100。 2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下： cj a b 基变量 c d ?j=cj-Zj 50 x1 0 1 0 40 x2 1 0 0 10 x3 60 x4 1 2 f S 6 4 g 1 21 4e （1）给出a，b，c，d，e，f，g的值或表达式； （2）指出原问题是求目标函数的最大值还是最小值； （3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。 2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸坯纸1040千克，每打日记本用白坯纸千克，每箱练习本用白3380千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生3产一箱练习本获利1元。试确定： （1）现有生产条件下获利最大的方案； （2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？ 2.10 某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。 产品原料 A B 销售价（元） 甲 2 3 13 乙 4 2 16 可用量（千克） 原料成本（元/千克） 160 180
（1）请构造数学模型使该厂利润最大，并求解。
４９ 第二章 线性规划的对偶问题 （2）原料A、B的影子价格各为多少。 （3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。 （4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？ 2.11 某厂生产A、B两种产品需要同种原料，所需原料、工时和利润等参数如下表： 单位产品 原料（千克） 工时（小时） 利润（万元） A 1 2 4 B 2 1 3 可用量（千克） 200 300
（1） 请构造一数学模型使该厂总利润最大，并求解。 （2） 如果原料和工时的限制分别为300公斤和900小时，又如何安排生产？ （3） 如果生产中除原料和工时外，尚考虑水的用量，设两A，B产品的单位产品分别需要水4吨和2吨，水的总用量限制在400吨以内，又应如何安排生产？
复习思考题
2.12 试从经济上解释对偶问题及对偶变量的含义。 2.13 根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。 2.14 什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。 2.15 试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。 2.16 将aij，b，c的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自将会出现什么变化，有多少种不同情况以及如何去处理。 2.17 判断下列说法是否正确 (a)任何线性规划问题存在并具有唯一的对偶问题； (b)对偶问题的对偶问题一定是原问题； (c)根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解； (d)若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k； (e)应用对偶单纯形法计算时，若单纯形表中某一基变量xi<0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解； (f)若线性规划问题中的bi，c,值同时发生变化，反映到最终单纯形表中，不会出５０ 第二章 线性规划的对偶问题 现原问题与对偶问题均为非可行解的情况； (g)在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。
５１ 包含总结汇报、办公文档、人文社科、考试资料、教学教材、经管营销以及线性规划的对偶问题等内容。
相关内容搜索(window.slotbydup=window.slotbydup || []).push({
id: '2014386',
container: s,
size: '234,60',
display: 'inlay-fix'
&&|&&2次下载&&|&&总25页&&|
您的计算机尚未安装Flash，点击安装&
阅读已结束，如需下载到电脑，请使用积分（）
下载：10积分
1人评价26页
0人评价45页
0人评价5页
0人评价78页
0人评价49页
所需积分：（友情提示：大部分文档均可免费预览！下载之前请务必先预览阅读，以免误下载造成积分浪费！）
（多个标签用逗号分隔）
文不对题，内容与标题介绍不符
广告内容或内容过于简单
文档乱码或无法正常显示
文档内容侵权
已存在相同文档
不属于经济管理类文档
源文档损坏或加密
若此文档涉嫌侵害了您的权利，请参照说明。
我要评价：
下载：10积分温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
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 to decrease by 10 units in a maximization problem and/or increase by 10 units in a minimization problem for 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 &= 50;
2. 在菜单LINGO下选Genertate -& Dual Model 即可生成原线性规划的对偶问题，结果如下
&MODEL:& MIN= 120 * _2 + 50 * _3;&[X1] 4 * _2 + 2 * _3 &= 50;&&&&! 我以前不知道[X1]原来是行号&[X2] 3 * _2 + _3 &= 30;&END
例2& 某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：
现有资源总数
若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？
用DESKS、TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。
max=60*desks+30*tables+20*
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.000000&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& TABLES&&&&&&& 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行松驰变量 = 5
If 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 model—a model for which there doesn’t 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 &= 21 时，目标函数值 = 280 +10 = 290。对第4行也类似。
对于非紧约束（如本例中第2、5行是非紧约束），DUAL PRICE 的值为0, 表示对应约束中不等式右端项的微小扰动不影响目标函数。有时, 通过分析DUAL PRICE, 也可对产生不可行问题的原因有所了解。灵敏度分析操作流程：菜单lingo--&options--&general solver--&dual computations:prices & ranges--&ok. 菜单lingo--&range& 灵敏度分析：如果做敏感性分析，则系统报告当目标函数中的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中INFINITY表示正无穷。1） 如本例目标函数为： max=60*desks+30*tables+20* 目标函数中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&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2&&&&&&&& 48.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:&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&& Variable&&&&&&&&&& Value&&&&&&& Reduced Cost
&&&&&&&&&&&&&&&&&&&&&&&&&&&& X1&&&&&&& 20.00000&&&&&&&&&&& 0.000000
&&&&&&&&&&&&&&&&&&&&&&&&&&&& X2&&&&&&& 30.00000&&&&&&&&&&& 0.000000
&&&&&&&&&&&&&&&&&&&&&&&&&&& Row&&& Slack or Surplus&&&&& Dual Price
&&&&&&&&& &&&&&&&&&&&&&&&&&&&&1&&&&&&& &&&&&&&&&&& 1.000000&& ! 注意第一行为目标函数，目标函数加1则目标值加1
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2&&&&&&& 0.000000&&&&&&&&&&& 48.00000
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3&&&&&&& 0.000000&&&&&&&&&&& 2.000000
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 4&&&&&&& 40.00000&&&&&&&&&&& 0.000000
Ranges in which the basis is unchanged:
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Objective Coefficient Ranges
&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Current&&&&&&& Allowable&&&&&&& Allowable
Variable&&&&& 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系数变为30×3=90，在允许范围内，所以不应改变生产计划，但最优值变为90×20+64×30=3720。
下面对“资源”的影子价格作进一步的分析。影子价格的作用（即在最优解下“资源”增加1个单位时“效益”的增量）是有限制的。每增加1桶牛奶利润增长48元（影子价格），但是，上面输出的CURRENT RHS 的ALLOWABLE INCREASE 和 ALLOWABLE DECREASE 给出了影子价格有意义条件下约束右端的限制范围： milk）原料最多增加10（桶牛奶），time）劳动时间最多增加53（小时）。现在可以回答附加问题1）的第2问：虽然应该批准用35元买1桶牛奶的投资，但每天最多购买10桶牛奶。顺便地说，可以用低于每小时2元的工资聘用临时工人以增加劳动时间，但最多增加53.3333小时。
需要注意的是：灵敏性分析给出的只是最优基保持不变的充分条件，而不一定是必要条件。比如对于上面的问题，“原料最多增加10（桶牛奶）”的含义只能是“原料增加10（桶牛奶）”时最优基保持不变，所以影子价格有意义，即利润的增加大于牛奶的投资。反过来，原料增加超过10（桶牛奶），影子价格是否一定没有意义？最优基是否一定改变？一般来说，这是不能从灵敏性分析报告中直接得到的。此时，应该重新用新数据求解规划模型，才能做出判断。所以，从正常理解的角度来看，我们上面回答“原料最多增加10（桶牛奶）”并不是完全科学的。
In conclusion:
1）Reduce Cost 和 Dual Price 实际上反应了约束条件LHS和RHS微小扰动1个单位对Objective Value产生的影响
2）Reduced Cost 表示约束条件LHS的变量x1的最优解增加1个单位(扰动)后Objective Value的变化量。第一种解释：为了使某个变量在解x1中的数值的基础上增加1(如x1=0,变成x1=1)目标函数值Objective Value必须付出的代价; 第二种解释：Reduced Cost= 10表示max问题中x1前面的系数a减小10个单位，即将a*x1变成(a-10)*x1可以使x1变成基变量，其Reduced Cost可以变成0
3）Dual Price 表示约束条件RHS的值增加1个单位(扰动)后，Objective Value增加的数量。比如某一行约束的Dual Price = -1，表示Objective Value要减1
4）当REDUCE COST 或DUAL PRICE& 的值为０。表示当微小扰动不影响目标函数。
最后看一个Lingo求解非线性优化问题的Demo
model:min=(x1-1)^2+(x2-2)^2;x2-1=1;x1+x2&=2;end
&Local optimal solution found.& Objective value:&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 1.000000& Infeasibilities:&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 0.000000& Extended solver steps:&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 1& Total solver iterations:&&&&&&&&&&&&&&&&&&&&&&&&&&&& 4
& Model Class:&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& NLP
& Total variables:&&&&&&&&&&&&&&&&&&&&&&&& 1& Nonlinear variables:&&&&&&&&&&&&&&&&& 1& Integer variables:&&&&&&&&&&&&&&&&&&&&& 0
& Total constraints:&&&&&&&&&&&&&&&&&&&&& &2& Nonlinear constraints:&&&&&&&&&&&&&&& 1
& Total nonzeros:&&&&&&&&&&&&&&&&&&&&&&&&& 2& Nonlinear nonzeros:&&&&&&&&&&&&&&&&&& 1
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Variable&&&&&&&&&& Value&&&&&&& Reduced Cost&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& X1&&&&&&& 0.000000&&&&&&&&&&& 0.000000&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& X2&&&&&&& 2.000000&&&&&&&&&&& 0.000000
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Row&&& Slack or Surplus&&&&& Dual Price&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 1&&&&&&& 1.000000&&&&&&&&&& -1.000000&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2&&&&&&& 0.000000&&&&&&&&&& -2.000244&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3&&&&&&& 0.000000&&&&&&&&&&& 2.000000
阅读(16449)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'Lingo solution report中各项的含义',
blogAbstract:'
即以此功德，庄严佛净土。上报四重恩，下救三道苦。惟愿见闻者，悉发菩提心。在世富贵全，往生极乐国。
（一）优化模型的组成
优化模型包括以下3部分：
l Objective Function：目标函数是一个能准确表达所要优化问题的公式。
l Variables：Decision variables（决策变量），在模型中所使用的变量。
l Constraints：约束条件。
blogTag:'lingo,optimum,theory',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:4,
publishTime:9,
permalink:'blog/static/',
commentCount:3,
mainCommentCount:3,
recommendCount:9,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:true,
hostIntro:'人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}