《1.线性规划和lingo初步》由会员分享，可在线阅读，更多相关《1.线性规划和lingo初步（35页珍藏版）》请在金锄头文库上搜索。
1、线性规划, 线性规划问题及其数学模型 问题的提出 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示,数学模型,x1, x2 :决策变量,max（或min）,目标函数,约束条件,非负约束,线性规划linear programming(LP) 模型三要素：决策变量 Decision variables ，目标函数Objective function，约束条件Constraints.,max（或min）,目标函数,约束条件,规划(优化)模型三要素：决策变量 Decision variables ，目标函数Objective function，约束
2、条件Constraints.,决策变量,图解法用图解法求解。max z = 2x1 + 3x2x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0,解：(1)建立x1 - x2坐标；,(2)约束条件的几何表示；,(3)目标函数的几何表示；,z = 2x1 + 3x2,首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。,可见，在Q2点z取到最大值。因此， Q2点所对应的解为最优解。Q2点坐标为(4，2)。即: x1 = 4，x2 = 2 由此求得最优解：x1* = 4 x2* = 2最大值：max z = z* = 2x1 + 3x2 = 14(元),4,3,1.建
3、立平面直角坐标系。 2.对约束条件加以图解，找出可行域。 3.画出目标函数等值线。 4.移动目标函数求出最优解。,图解法步骤：,关键：(1)每个约束条件的半平面判断(2)目标函数直线的移动方向,如何处理决策变量个数大于2的情况？,exa001,Soluting Report,几点说明,1.目标函数以“max=”或“min=”开头 2.每个表达式以分号“；”结束 3.变量名不区分大小写，第一个字符必须是字母 4.不区分“=”和“” 若要在LINGO中表示严格大于(小于)，该怎么处理？,Lingo无严格小于，欲使ab，可以适当选取小的正常数e，表示成a+eb，,几点说明,5.注释用“！”和“；”
4、6.决策变量默认为非负实数 如何对决策变量进行简单限制 gin(x) 限制x为整数 bin(x) 限制x为0或1 bnd(L,x,U) 限制LxU free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数,几点说明,7.LINGO中的算术运算符有以下5种： +（加法）， （减法或负号）， *（乘法）， /（除法）， (求幂)。,线性规划,Lingo代码,Min=-3*x1+x2+x3; X1-2*x2+x3=3; -2*x1+x3=1;,非线性规划,Lingo代码,Min=-3*x13+x22+x3; X1-2*x2+x3=3; -2*x1+x3=1;,练习,某昼夜公交路线不用时段
5、所需司机人数如下表。设每位司机每天连续工作两班，问该路线至少需要多少司机？,规划问题建模的步骤,1、分析实际问题，弄清需要确定的未知量，在此基础上假定自变量（决策变量）。 2、认清决策者想要达到的主要目标，据此列出目标函数。 3、分析并汇总问题的限制条件，写出约束条件。 4、写出完整的规划数学模型。,max（或min）,目标函数,约束条件,规划(优化)模型三要素：决策变量 Decision variables ，目标函数Objective function，约束条件Constraints.,决策变量,影子价格和灵敏度分析,50桶牛奶,时间480h,至多加工100kgA1,制订生产计划，使每天获
6、利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/kg，应否改变生产计划？,每天：,问题,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480h,至多加工100kgA1,基本模型,模型求解,软件实现,LINGO,model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,Glob
7、al optimal solution found.Objective value: 3360.000Total solver iterations: 2Variable Value Reduced Cost X1 20.00000 0.000000X2 30.00000 0.000000Row Slack or Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.000000 2.000000CPCT 40.00000 0.000000,20桶牛奶生产A1, 30桶生产A2，利润3360元.,结果解释,Globa
8、l optimal solution found.Objective value: 3360.000Total solver iterations: 2Variable Value Reduced CostX1 20.00000 0.000000X2 30.00000 0.000000Row Slack or Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.000000 2.000000CPCT 40.00000 0.000000,model: max = 72*x1+64*x2; milk x1 + x250
9、; time 12*x1+8*x2480; cpct 3*x1100; end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,Global optimal solution found.Objective value: 3360.000Total solver iterations: 2Variable Value Reduced CostX1 20.00000 0.000000X2 30.00000 0.000000Row Slack or Surplus Dual Price1 3360.000 1.000000MILK 0.000000 48.00000TIME 0.
10、000000 2.000000CPCT 40.00000 0.000000,最优解下“资源”增加1单位时“效益”的增量,影子价格,35元可买到1桶牛奶，要买吗?,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元?,2元！,影子价格(Shadow price),原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格,灵敏度分析,以前讨论线性规划问题时，假定系数都是常数。但实际上这些系数往往是估计值和预测值。 因此提
11、出这样两个问题： (1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化； (2)或者这些系数在什么范围内变化时，线性规划问题的最优解不变。,灵敏度分析,灵敏度分析的内容： 目标函数系数在什么范围变化时（此时假定其它系数保持不变），最优解不变化 约束右端项在什么范围变化时（此时假定其它系数保持不变），对应项约束的对偶价格不变。,Ranges in which the basis is unchanged:Objective Coefficient RangesCurrent Allowable Allowable Variable Coefficient Increa
12、se DecreaseX1 72.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase DecreaseMILK 50.00000 10.00000 6.666667TIME 480.0000 53.33333 80.00000CPCT 100.0000 INFINITY 40.00000,目标函数系数在此变化范围内，最优解不变,敏感性分析 (“LINGO|Ranges” ),x1系数范围(64,96),x2系数范围
13、(48,72),A1获利增加到 30元/kg，应否改变生产计划?,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,Ranges in which the basis is unchanged:Objective Coefficient RangesCurrent Allowable Allowable Variable Coefficient Increase DecreaseX1 72.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase DecreaseMILK 50.00000 10.00000 6.666667TIME 480.0000 53.33333 80.00000CPCT 100.0000 INFINITY 40.00000,
