数据模型决策01线性规划2（PPT30页)

线性规划的对偶问题例1：某公司利用现有三条生产线生产两种产品，有关数据如下表：设Ⅰ产量–––––Ⅱ产量–––––1x2x0,1823122453max21212121xxxxxxs.t.xxz问如何安排生产，使获利最多？产品甲产品乙每周可用量生产线一104小时生产线二0212小时生产线三3218小时产品利润3百元5百元一、对偶问题的提出例2.1*有一个中间商接到一批加工定单，需用到该公司的三条生产线,有意租用该公司的三条生产线全部可用时间，问中间商应如何出价，才能使公司觉得有利可图肯把设备出租，又使自己付出的租金最少？中间商付出的代价最小出让代价应不低于用同等数量的资源自己生产的利润。对方能接受公司生产线一生产线二生产线三利润（百元）１０３３０２２５４时12时18时ⅠⅡD•公司能接受的条件：•中间商的意愿：32118124minyyyw出让代价应不低于用同等数量的资源自己生产的利润。3331yy0,,y52233.3213231yyyyyyts32118124minyyyw设：生产线一—Y1百元／时,生产线二––y2百元／时,生产线三––y3百元／时5232yy0,1823122453max21212121xxxxxxs.t.xxz0,,y52233.3213231yyyyyyts32118124minyyyw对偶问题原问题中间商公司一对对偶问题设原线性规划问题为：nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,,21nxxx则称下面的线性规划问题：mmybybybW2211minnmmnnnmmmmcyayayacyayayacyayayats22112222211211221111.称为对偶变量myyy,,21为其对偶规划，0,,21myyy二、原问题与对偶问题的对应关系1：定义myyy21nxxx21mnmmnnaaaaaaaaa212222111211mbbb21nccc21nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,,21nxxxmmybybybW2211minnmmnnnmmmmcyayayacyayayacyayayats22112222211211221111.0,,21myyy表中间的数(aij)的每一行与xj对应地乘起来相加后不大于这一行右边的数bi，就是原问题的一个约束条件。最后一行cj与xj对应地乘起来相加就是原问题的目标函数。类似地，把(aij)的每一列与yi对应地乘起来相加后不小于cj就是对偶问题的一个约束条件。最后一列与yj对应地乘起来相加就是目标函数。321x4x3x2Zmax1的对偶问题：求下列线性规划问题例0,,45643732532.321321321321321xxxxxxxxxxxxxxxts321432maxxxxZ0,,45643732532.321321321321321xxxxxxxxxxxxxxxts所求对偶问题为：43214532minyyyyS232.4321yyyyts3434321yyyy46754321yyyy0,,,4321yyyy4321yyyy321xxx111641713532453243244332211xcxcxcxczmaxP2）为：原问题（例343433323213124243232221211414313212111.bxaxaxaxabxaxaxaxabxaxaxaxats0,0,4321xxxx无符号限制，11bb033333xxxxx，，令0444xxx，则取)1(443332211maxxcxxcxcxczP）（）的化为则原问题（34343333232131242433232221211414331321211114143313212111)()()()(.bxaxxaxaxabxaxxaxaxabxaxxaxaxabxaxxaxaxats0,,,,43321xxxxx化为定义中的形式)1(443332211maxxcxxcxcxczP）（）原问题（34343333232131242433232221211414331321211114143313212111)()()()(.bxaxxaxaxabxaxxaxaxabxaxxaxaxabxaxxaxaxats0,,,,43321xxxxx4433332211maxxcxcxcxcxcz即3434333333232131242432332322212114143133132121111414313313212111.bxaxaxaxaxabxaxaxaxaxabxaxaxaxaxabxaxaxaxaxats0,,,,43321xxxxx3211yyyy4433332211maxxcxcxcxcxczP）为即原问题（3434333333232131242432332322212114143133132121111414313313212111.bxaxaxaxaxabxaxaxaxaxabxaxaxaxaxabxaxaxaxaxats0,,,,43321xxxxx'32''1'1yyyy'4''3'321xxxxx3433333231242323222114131312111413131211aaaaaaaaaaaaaaaaaaaa3211bbbb43321ccccc'32''1'1yyyy'4''3'321xxxxx3433333231242323222114131312111413131211aaaaaaaaaaaaaaaaaaaa3211bbbb43321ccccc对偶规划问题（D）为33221111minybybybybS1331221111111.cyayayayats2332222112112cyayayaya3333223113113cyayayaya3333223113113cyayayaya4334224114114cyayayaya03211yyyy，，，对偶规划问题（D）为33221111minybybybybS1331221111111.cyayayayats2332222112112cyayayaya3333223113113cyayayaya3333223113113cyayayaya4334224114114cyayayaya03211yyyy，，，211yyy取33yy取)1()1(对偶规划问题（D）为：332211minybybybS1331221111.cyayayats2332222112cyayaya3333223113cyayaya4334224114cyayaya00321yyy，无符号限制，44332211maxxcxcxcxczP）为原问题（343433323213124243232221211414313212111.bxaxaxaxabxaxaxaxabxaxaxaxats0,0,4321xxxx无符号限制，对偶规划问题（D）为：332211minybybybS1331221111.cyayayats2332222112cyayaya3333223113cyayaya4334224114cyayaya00321yyy，无符号限制，原问题（P）对偶问题（D）minmax变量约束：方程约束：变量≥方程≥变量无限制方程=变量≤方程≤方程约束：变量约束：方程=变量无限制方程≤变量≥方程≥变量≤重要结论２、若原问题存在最优解，则其对偶问题一定存在最优解，且有相同的最优值．1、对偶问题的对偶就是原问题。（即互为对偶规划）0,1823122453max21212121xxxxxxs.t.xxz0,,y52233.3213231yyyyyyts32118124minyyyw练习：4321532max1xxxxZ题、求下列问题的对偶问无限制432143214214321,0,,0643247235234.xxxxxxxxxxxxxxxts4321532min2xxxxZ题、求下列问题的对偶问无限制432143214214321,0,,0643247235234.xxxxxxxxxxxxxxxts（P）与(D)的关系对应表：原问题对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵AA系数矩阵321645minyyyS无限制32132131321321,0,01725433322234.yyyyyyyyyyyyyyts321645maxyyyS无限制32132131321321,0,01725433322234.yyyyyyyyyyyyyyts对偶解的经济意义-------影子价格资源的合理利用问题：资源mAAA21nBBB21mnmmnnaaaaaaaaa212222111211资源限制mbbb21单位利润nccc21nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,,21nxxx的总利润最大？利用现有资源，使获得排生产计划，才能充分下表，问如何安件产品可获得的利润如资源的数量限制以及每所消费的资源数、每种种资源，已知每件产品，，，耗种产品，要消，，，周期内生产某厂计划在下一个生产mnAAABBB2121),,2,1njBxjj（的产量表示产品解：设还有现金，问应该投资何种资源？决策依据：比较第i种资源增加一个单位