数据模型决策01线性规划2

1、线性规划的对偶问题例例1：某公司利用现有三条生产线生产两种：某公司利用现有三条生产线生产两种 产品，有关数据产品，有关数据 如下表：如下表：设设 产量产量 产量产量1x2x 0, 1823 122 4 53max 21212121xxxxxxs.t.xxz问如何安排生产，使获利最多？问如何安排生产，使获利最多？产品甲产品甲产品乙产品乙每周可用量每周可用量生产线一104小时生产线二0212小时生产线三3218小时产品利润3百元5百元一、对偶问题的提出一、对偶问题的提出例2.1* 有一个中间商接到一批加工定单，需用到该公司的三条生产线,有意租用该公司的三条生产线全部可用时间，问中间商应如何出价，才

2、能使公司觉得有利可图肯把设备出租，又使自己付出的租金最少？ 中中间间商商 付出的代价最小付出的代价最小出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。对方能接受对方能接受公公司司生产线一生产线一生产线二生产线二生产线三生产线三利润（百元）利润（百元）时时12时时 18时时D 公司能接受的条件：公司能接受的条件： 中间商的意愿：中间商的意愿：32118124minyyyw出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。3331yy0,y 522 33.3213231yyyyyyts32118124mi

3、nyyyw设：生产线一设：生产线一 Y1Y1百元时百元时, ,生产线二生产线二 y2百元百元时时, ,生产线三生产线三y y3 3百元百元时时5232 yy 0, 1823 122 4 53max 21212121xxxxxxs.t.xxz0,y 522 33.3213231yyyyyyts32118124minyyyw对对偶偶问问题题原原问问题题中中间间商商公公司司一对对偶问题一对对偶问题设原线性规划问题为：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx则称下面的线性规划问题：mm

4、ybybybW2211minnmmnnnmmmmcyayayacyayayacyayayats22112222211211221111.称为对偶变量myyy,21为其对偶规划，0,21myyy二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系1：定义myyy21nxxx21mnmmnnaaaaaaaaa212222111211mbbb21nccc21nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxxmmybybybW2211minnmmnnnmmmmcyayayacyayaya

5、cyayayats22112222211211221111.0,21myyy表中间的数(aij)的每一行与xj对应地乘起来相加后不大于这一行右边的数bi，就是原问题的一个约束条件。最后一行cj 与xj 对应地乘起来相加就是原问题的目标函数。类似地，把(aij)的每一列与yi 对应地乘起来相加后不小于cj 就是对偶问题的一个约束条件。最后一列与yj 对应地乘起来相加就是目标函数。321x4x3x2Zmax1的对偶问题：求下列线性规划问题例0,45643732532.321321321321321xxxxxxxxxxxxxxxt s321432maxxxxZ0,45643732532.321321

6、321321321xxxxxxxxxxxxxxxt s所求对偶问题为：43214532minyyyyS232.4321yyyyt s3434321yyyy46754321yyyy0,4321yyyy4321yyyy321xxx111641713532453243244332211xcxcxcxczmaxP2）为：原问题（例343433323213124243232221211414313212111.bxaxaxaxabxaxaxaxabxaxaxaxats0,0,4321xxxx无符号限制，11bb033333 xxxxx，令0444xxx，则取) 1(443332211maxxcxxcxc

7、xczP ）（）的化为则原问题（ 34343333232131242433232221211414331321211114143313212111)()()()(.bxaxxaxaxabxaxxaxaxabxaxxaxaxabxaxxaxaxats0,43321 xxxxx化为定义中的形式) 1(443332211maxxcxxcxcxczP ）（）原问题（ 34343333232131242433232221211414331321211114143313212111)()()()(.bxaxxaxaxabxaxxaxaxabxaxxaxaxabxaxxaxaxats0,43321 xxxx

8、x4433332211maxxcxcxcxcxcz 即 3434333333232131242432332322212114143133132121111414313313212111.bxaxaxaxaxabxaxaxaxaxabxaxaxaxaxabxaxaxaxaxat s0,43321 xxxxx3211yyyy 4433332211maxxcxcxcxcxczP ）为即原问题（ 3434333333232131242432332322212114143133132121111414313313212111.bxaxaxaxaxabxaxaxaxaxabxaxaxaxaxabxaxax

9、axaxats0,43321 xxxxx32 11yyyy4 3321xxxxx3433333231242323222114131312111413131211aaaaaaaaaaaaaaaaaaaa3211bbbb43321ccccc32 11yyyy4 3321xxxxx3433333231242323222114131312111413131211aaaaaaaaaaaaaaaaaaaa3211bbbb43321ccccc对偶规划问题（D）为33221111minybybybybS 1331221111111.cyayayayats2332222112112cyayayaya 33332

10、23113113cyayayaya 3333223113113cyayayaya 4334224114114cyayayaya 03211 yyyy，对偶规划问题（D）为33221111minybybybybS 1331221111111.cyayayayats2332222112112cyayayaya 3333223113113cyayayaya 3333223113113cyayayaya 4334224114114cyayayaya 03211 yyyy，211yyy取33yy取) 1() 1(对偶规划问题（D）为：332211minybybybS1331221111.cyayayat

11、s2332222112cyayaya3333223113cyayaya4334224114cyayaya00321yyy，无符号限制，44332211maxxcxcxcxczP）为原问题（343433323213124243232221211414313212111.bxaxaxaxabxaxaxaxabxaxaxaxats0,0,4321xxxx无符号限制，对偶规划问题（D）为：332211minybybybS1331221111.cyayayats2332222112cyayaya3333223113cyayaya4334224114cyayaya00321yyy，无符号限制，原问题（P）

12、对偶问题（D）minmax变量约束：方程约束：变量方程变量无限制方程=变量方程方程约束：变量约束：方程=变量无限制方程变量方程变量重要结论、若原问题存在最优解，则其对偶问题一定存若原问题存在最优解，则其对偶问题一定存在最优解，且有相同的最优值在最优解，且有相同的最优值1、对偶问题的对偶就是原问题对偶问题的对偶就是原问题。 （即互为对偶规划） 0, 1823 122 4 53max 21212121xxxxxxs.t.xxz0,y 522 33.3213231yyyyyyts32118124minyyyw练习：4321532max1xxxxZ题、求下列问题的对偶问无限制4321432142143

13、21, 0, 0643247235234.xxxxxxxxxxxxxxxts4321532min2xxxxZ题、求下列问题的对偶问无限制432143214214321, 0, 0643247235234.xxxxxxxxxxxxxxxt s（P）与(D)的关系对应表： 原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵AA系数矩阵321645minyyyS无限制32132131321321,0,01725433322234.yyyyyy

14、yyyyyyyyts321645maxyyyS无限制32132131321321, 0, 01725433322234.yyyyyyyyyyyyyyts对偶解的经济意义 -影子价格资源的合理利用问题：资源单位消费产品mAAA21nBBB21mnmmnnaaaaaaaaa212222111211资源限制mbbb21单位利润nccc21nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx的总利润最大？利用现有资源，使获得排生产计划，才能充分下表，问如何安件产品可获得的利润如资源的数量限制以及每

15、所消费的资源数、每种种资源，已知每件产品，耗种产品，要消，周期内生产某厂计划在下一个生产mnAAABBB2121), 2 , 1njBxjj（的产量表示产品解：设还有现金，问应该投资何种资源？决策依据：比较第i种资源增加一个单位，其余资源不增加时利润的增加值是否为正。nnxcxcxcz2211max对mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21nxxx决策依据：在取得最优方案的前提下比较第i种资源增加一个单位，其余资源不增加时利润的增加值设 是最优解，Z*是最优值mmybybybwD2211min)(nmmnnnmmmm

16、cyayayacyayayacyayayat s22112222211211221111.0,21myyy设其最优解*2*1,nxxx*2*1,myyy最优值为*则Z*2211mmybybybmyyy21nxxx21mnmmnnaaaaaaaaa212222111211mbbb21nccc21nnxcxcxcz2211maxmnmnmmininiinnnnbxaxaxabxaxaxabxaxaxabxaxaxat s2211221122222121112121111.0,21nxxx其余不变时，当, 1iibb此时原问题变为最优值为*此时目标函数的增量是*-*miyyy.1n21x.xxmnm

17、miniiiinaaaaaaaaaaa.21432111211nibbb.1.1n21c.ccmmiiybybybybw) 1(min2211nmmnnnmmmmcyayayacyayayacyayayat s22112222211211221111.0,21myyy此时由于该对偶问题可行域没发生变化，目标函数中第i个系数改变很小，所以可以假设其最优解没有变化，则还是最优解，设此时最优值为*2*1,myyy则 Z* *此时对偶问题变为*) 1(*11mmiiybybyb*iyZZZZ*2211mmybybyb第i种资源增加一个单位，其余资源不增加时利润的增加值正好是原问题的对偶问题最优解的第i

18、个分量对偶价格对偶价格.i*y*ZbiPDPii个约束条件的对偶价格称为第的改变量题目标函数最优值单位时，所引起的原问增加一个个约束条件的右端常数）的第（）中，）和（问题（对偶价格：在一对对偶边际价格1、对偶价格的定义个分量的第）的最优解对偶问题（iYDyi* 对偶价格也称为影子价格影子价格，在用lingo软件求解原问题时，程序的输出结果会给出所有的对偶价格润最大？，使获得的总利才能充分利用现有资源问如何安排生产计划，得的利润如下表，限制以及每件产品可获源数、每种资源的数量产品所消费的资时三种资源，已知每件耗钢材、煤炭、设备台两种产品，要消生产周期内生产甲、乙例：某厂计划在下一个资源单位消费产

19、品甲乙资源限制钢材52170煤炭23100设备台时15150单位利润（万元）1018211810maxxxz求0,15051003217025.21212121xxxxxxxxt s表示产品乙的产量表示产品甲的产量解：设21xx最优解X*=(50/7，200/7)最优值Z*=4100/7Y*=(0，32/7,6/7)对偶价格0,15051003217025.21212121xxxxxxxxts对偶价格（影子价格）Y*=(0，32/7,6/7)211810max)(xxzP求钢材煤炭设备台时，钢材的影子价格0*1y732*2y煤炭的影子价格76*3y设备台时的影子价格即再增加1吨钢材，利润不会增

20、加即再增加1吨煤炭，利润增加3/7万元即再增加1个台时，利润增加6/7万元例例:某公司利用现有三条生产线生产两种某公司利用现有三条生产线生产两种 产品，有产品，有关数据如下表：关数据如下表：问如何安排生产，使获利最多？问如何安排生产，使获利最多？产品甲产品甲产品乙产品乙每周可用量每周可用量资源单位成本资源单位成本生产线一104小时1百元/小时生产线二0212小时1百元/小时生产线三3218小时1百元/小时产品售价7百元9百元数学模型一：设甲产量 x1 乙产量x2则生产一个单位甲产品获利润711313（百元）则生产一个单位乙产品获利润921215（百元）4x112x220 x0 x21 ，21x5x3zmaxts.18x2x321最优解X*=(2，6)最优值Z*=36Y*=(0,1.5,1)对偶价格