线性规划问题的求解

线性规划问题的求解第一页，共六十八页，2022年，8月28日5.1一般线性规划模型的建立与求解5.1.1基本理论线性规划问题的标准形式是等约束的，用矩阵表示如下：一般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形式。线性规划模型的一般性质：(1)比例性，每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。(2)可加性，每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。(3)连续性，每个决策变量的取值都是连续的。比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质，连续性则允许得到决策变量的实数最优解。单纯形算法的实质：在保证可行(最小比值法则)的前提下，先在可行解上取一个顶点，判断是否达到最优解，如果没有，则通过一定的规则(入基，旋转等)到另一个更优第二页，共六十八页，2022年，8月28日的顶点，如此迭代下去直到最优，或者判断不可行或者判断无界为止。5.1.2应用举例例5-1(运输问题)两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大米分别为4t，8t，三个两站至少需要大米分别为2t,4t,5t，两个粮库到三个粮站的距离(km)如下表，求使运费最低。B1B2B3库存A1122484A23012248需求245解：(1)问题分析：总需求量为11t，小于总库存量12t，所以问题可行。(2)从线性规划的三个要素出发，决策变量：问题是各个粮仓向粮站调运了多少大米，此调运量就是决策变量。目标函数：运费和运量和距离有关系，即t*km最小，所以要将运量与相应的距离相乘然后使总和最小。约束条件：两个粮库的库存量限制和三个粮站需求量的限制。第三页，共六十八页，2022年，8月28日(3)建立模型，设A1,A2分别向B1,B2,B3运送大米x11,x12,x13,x21,x22,x23，则有：minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13<=4x21+x22+x23<=8x11+x21>=2x12+x22>=4x13+x23>=5x11,x12,x13,x21,x22,x23>=0(4)转化成对应的Lingo建模语言程序1，求解模型，结果如下页图示：第四页，共六十八页，2022年，8月28日第五页，共六十八页，2022年，8月28日通过选择Lingo|Generate|Displaymodel将模型展开，方便查看求解报告的第三部分。相应的添加的剩余变量或者松弛变量。第六页，共六十八页，2022年，8月28日程序改进一、上面解法是一种傻瓜式的直接输入法，适用于程序规模不大的问题，如果问题规模很大的话用这种方式很费力，可以使用矩阵生成器来编写程序2minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13+y1=4x21+x22+x23+y2=8x11+x21-y3=2x12+x22-y4=4x13+x23-y5=5x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5>=0转换成Lingo语言如下所示：第七页，共六十八页，2022年，8月28日第八页，共六十八页，2022年，8月28日注：1、写程序要习惯给程序用title命名2、为了方便查看报告，用行号区分约束3、此程序的格式可以固定为标准形式的求解模式。程序改进三：可以减少引入的变量个数，将模型修改为下面的形式minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13<=4x21+x22+x23<=8-x11-x21<=-2-x12-x22<=-4-x13-x23<=-5x11,x12,x13,x21,x22,x23>=0写成lingo语言如下所示：第九页，共六十八页，2022年，8月28日第十页，共六十八页，2022年，8月28日注：1、改程序把不等式约束全部转化为小于等于约束，是为了将约束可以写到一个循环语句中实现，如果还有等是约束的话，则要在写一个循环语句来控制约束。2、当程序比较大的时候，一般将约束按性质进行分类程序改进四：将约束进行分类，代码如下：第十一页，共六十八页，2022年，8月28日注：1、在进行调试程序时，可以用!号某些语句屏蔽，缩小寻找出错的范围。2、可以编写程序边运行，保证每行书写都是正确的3、常见的出错情况有：(1)定义了多个长度一样的集合，而在使用中区分不明确；(2)定义了同名的属性；(3)漏掉了括号；(4)分号不是英文半角；(5)使用的字母没有定义；(6)循环语句中元素下标颠倒或者不明；(7)约束错误变成不可行或者无界；(8)关系运算符误用成逻辑运算符；(9)函数调用错误等等…第十二页，共六十八页，2022年，8月28日例5-2（阶段生产问题）某公司产品最大生产能力为10000单位，每单位存储费2元，预定的销售量与单位成本如下表所示：月份单位成本销售量17060002717000380120004766000求一生产计划，使(1)满足需求；(2)不超过生产能力；(3)成本(生产成本与存储费之和最低)问题分析：这是一个多阶段生产计划问题，设计多阶段存储，只需要制定1~4月份的生产计划，不妨假定1月初无库存，4月底卖完，当月生产的不作为当月的库存，库存量无限制。模型建立（1）：设xi为第i月产量，di为销售量，ei为存储费，ci为单位成本，则目标生产成本为:第十三页，共六十八页，2022年，8月28日第j月到j+1月的库存量(记作第j+1月的库存量)应该是1月到j月的总产量减去1月到j月的总销售量，即：总的库存费用为：总成本为：即求总成本的最小值。约束条件1：如果每个月都有非负的存储量，显然满足要求，可用约束：第十四页，共六十八页，2022年，8月28日约束条件3：产量限制，0<=xi<=10000。综上，建立如下数学模型：约束条件2：4个月的总产量等于总需求量即：转成相应的Lingo语言如下：第十五页，共六十八页，2022年，8月28日第十六页，共六十八页，2022年，8月28日模型改进(2)：引入库存变量，再利用库存平衡方程使模型更加流畅简洁。设xi为第i个月的产量，di为销售量，ei为存储费，ci为单位成本，设第i个月的库存为si,则：程序编写如下：第十七页，共六十八页，2022年，8月28日模型改进(3)：将该模型转化成运输问题。设xij表示第i个月生产的产品在第j个月卖出去的数量，cij表示第i个月生产的产品在第j月卖出去时的生产成本与存储成本之和，第十八页，共六十八页，2022年，8月28日dj表示第j月的销售量，则生产月生产的产品在需求月卖出时单位总成本如下表所示：需求月1需求月2需求月3需求月4产量生产月17072747610000生产月271737510000生产月3808210000生产月47610000销量60007000120006000建立模型如下：第十九页，共六十八页，2022年，8月28日相应的Lingo程序如下：第二十页，共六十八页，2022年，8月28日例5-3（连续投资问题）某部门在今后5年内考虑给下列项目投资，已知：(1)项目A，从第1年到第4年每年初要投资，次年末回收本利1.15；(2)项目B，第3年初投资，到第5年末回收本利1.25，最大投资4万元;(3)项目C，第2年初投资，到第5年末回收本利1.40，最大投资3万元；(4)项目D，每年初购买国债，当年末回收本利1.06;该部门现有资金10万元，问应如何投资到第5年末总资本最大。问题分析：将可能的投资情况设为变量，如下表所示第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx3CDx1Dx2Dx3Dx4Dx5D因为具有项目D，所以可以认为该部门每年都把自己全部投出去，而且年末的总资本等于第二年初的总投资额。由此可建立模型如下：第二十一页，共六十八页，2022年，8月28日转换成Lingo程序如下所示：第二十二页，共六十八页，2022年，8月28日第二十三页，共六十八页，2022年，8月28日5.2灵敏性分析与影子价格5.2.1灵敏性分析例5-4(生产计划问题)某工厂计划安排生产III两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额见下表所示：产品I产品II最大资源量设备128台原材料A4016kg原材料B0412kg单位产品利润23求：(1)怎么样安排生产使得工厂利润最大？(2)产品I的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？(3)产品II的单位利润增大到5万元，要不要改变生产计划？(4)如果产品I,II的单位利润同时降低了1万元，要不要改变生产计划？第二十四页，共六十八页，2022年，8月28日建立模型：用x1,x2分别表示计划生产产品III的数量，可建立如下模型编写lingo程序如下：第二十五页，共六十八页，2022年，8月28日程序执行结果：通过执行结果对问题进行分析：问题1：安排生产产品I为4个单位，II为2个单位，最大利润为14万元。灵敏性分析：打开LINGO中的灵敏性分析开关，LINGO|Options|GeneralSolver|DualComputations|PricesandRanges分析结果通过点击Lingo|Range命令获得第二十六页，共六十八页，2022年，8月28日说明1、(1)红框内的部分是对目标函数进行的灵敏性分析，第一列是变量，第二列是对应的系数，第三列是允许增加量，第四列是允许减少量，允许增加和允许减少都是在当前系数基础上改变的。在其他变量系数都不变的情况下有：当x1在(2-0.5,2+∞)=(1.5,∞)之间变化时,最优解不变；当x2在(3-3,3+1)=(0,4)之间变化时，最优解不变。第二十七页，共六十八页，2022年，8月28日问题2：

产品I的单位利润降低到1.8万元，在(1.5,∞)之间，所以不改变生产计划；而降低到1万元，则需要重新制定生产计划；问题3：5万不在(0,4)范围内，故要重新制定生产计划。修改程序之后运行结果如下：问题4：

因为两个系数同时发生变化，所以只能更改程序的数据，重新运行。运行结果和灵敏性分析结果如下：第二十八页，共六十八页，2022年，8月28日第二十九页，共六十八页，2022年，8月28日说明2、

红框内所示为保持最优基不变的约束右端项的变化范围，即原材料A的量在(8-4，8+2)=(4,10)，原材料B的量在(16-8,16+16)=(8,32)，设备台时在(12-4,12+∞)=(8,∞)内变化时，最优基保持不变。第三十页，共六十八页，2022年，8月28日5.2.2对偶问题两个线性规划问题：称为对称形式的对偶问题(dualproblem),互为对偶问题的(I)和(II)一个称为原问题，一个称为原问题的对偶问题。称对偶问题的最优解为原问题约束条件的影子价格(shadowprice)1、一对对称形式的对偶问题有如下的对应关系：(1)若一个模型为目标求极大，约束为小于等于的不等式，则它的对偶模型为目标求极小，约束为大于等于的不等式，即”max<=”对应”min>=”第三十一页，共六十八页，2022年，8月28日(2)从约束系数的矩阵看，一个模型为A，一个模型为AT，一个模型为m个约束，n个变量，另一个则为n个约束，m个变量。(3)从数据b和c的位置看，在两个规划模型中两者互换。(4)两个模型中的变量皆非负。2、非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。第三十二页，共六十八页，2022年，8月28日下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价：则原规划模型可以写成如下形式：第三十三页，共六十八页，2022年，8月28日此时已转化为对称形式，可以直接写出其对偶问题：这里，把y1看作是y1=y1’-y1’’，于是y1没有非负限制，关系（2）的说明完毕。对偶定理：若互为对偶问题的线性规划问题(I)和(II)中有一个最优解，则另一个必有最优解，且目标函数值相同。第三十四页，共六十八页，2022年，8月28日例5-5(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)：产品I产品II产品III现有原料/t原料A2127原料B13211单位产品利润/万元231求：(1)若目前市场上原料A的实际价格为0.5万元/t，工厂应如何决策？(2)若目前市场上原料B的实际价格为0.8万元/t，工厂应如何决策？解：建立模型，设x1,x2,x3分别表示I，II，III的生产量，则模型如下：对偶问题第三十五页，共六十八页，2022年，8月28日模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y2≥2,也就是一定比生产产品I赚得多。产品II，III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。如果把资源A的量由7增加到8，会导致什么结果呢？影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。第三十六页，共六十八页，2022年，8月28日影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。程序编写：执行结果如下：第三十七页，共六十八页，2022年，8月28日说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。通过对右端项的灵敏性分析：第三十八页，共六十八页，2022年，8月28日在最优基不变时，A,B的右端项变化范围分别为(4.67,22)和(3.5,21)对问题(1)0.5<0.6,应该购进原料A，扩大生产能力，最大购进15t，利润增加(0.6-0.50*15=1.5万元对于问题(2),0.8>0.6，应该售出部分原料将使利润更大，最大售出量为3.33t,利润将会增加(0.8-0.6)*3.33=0.66万元第三十九页，共六十八页，2022年，8月28日例5-6(奶制品的加工问题)1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大(1)35元可买到1桶牛奶，买吗？若买，每天最多买多少?(2)可聘用临时工人，付出的工资最多是每小时几元?(3)A1的获利增加到30元/公斤，应否改变生产计划？每天：第四十页，共六十八页，2022年，8月28日1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天第四十一页，共六十八页，2022年，8月28日max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。模型求解第四十二页，共六十八页，2022年，8月28日模型求解reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量第四十三页，共六十八页，2022年，8月28日OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释第四十四页，共六十八页，2022年，8月28日OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000结果解释最优解下“资源”增加1单位时“效益”的增量时间加1单位,利润增2影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！

聘用临时工人付出的工资最多每小时几元？2元！第四十五页，共六十八页，2022年，8月28日RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释第四十六页，共六十八页，2022年，8月28日结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)注意:充分但可能不必要第四十七页，共六十八页，2022年，8月28日5.3整数线性规划例5-7(下料问题)做100套钢架，用长为2.9m,2.1m,1.5m的元钢各一根，已知原料长为7.4m，问如何下料，所用最省？问题分析：每一种下料方式用了多少根钢材，合理的下料方式是剩余料头的长度不能超过最短原料需求(1.5m)，可首先利用lingo搜索出全部的下料方式，然后从中筛选出符合条件的方式：模型建立：设xi为按第i种方式下料的根数，i=1,…,8，建立如下模型：x1x8第四十八页，共六十八页，2022年，8月28日说明：(1)目标函数有两种取法，一是剩余的料最少，二是所用原料的根数最少。(2)决策变量限制取整数。(3)这种全方式设变量的模型只适合小型下料问题，大型下料问题或者对下料方式有限制的问题将不再合适。程序编写：第四十九页，共六十八页，2022年，8月28日补充例5-7(下料问题2)问题1.如何下料最节省?问题2.客户增加需求：原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根第五十页，共六十八页，2022年，8月28日按照客户需要在一根原料钢管上安排切割的一种组合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根下料问题第五十一页，共六十八页，2022年，8月28日为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023下料问题1两种标准1.原料钢管剩余总余量最小第五十二页，共六十八页，2022年，8月28日xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量

目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12,x5=15,

其余为0；最优值：27整数约束：xi为整数第五十三页，共六十八页，2022年，8月28日当余料没有用处时，通常以总根数最少为目标目标2（总根数）下料问题1约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。xi为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比第五十四页，共六十八页，2022年，8月28日下料问题2对大规模问题，用模型的约束条件界定合理模式增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。决策变量xi~按第i种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量第五十五页，共六十八页，2022年，8月28日满足需求模式合理：每根余料不超过3米整数非线性规划模型下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数第五十六页，共六十八页，2022年，8月28日增加约束，缩小可行域，便于求解原料钢管总根数下界：

特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：31模式排列顺序可任定

下料问题2需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米第五十七页，共六十八页，2022年，8月28日LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。第五十八页，共六十八页，2022年，8月28日例5-8(选址问题)A