第三章 对偶规划

桂林电子科技大学商学院内容提要Sub title第一节对偶规划的数学模型✓对偶问题的提出✓对偶规划的性质第二节对偶规划的经济解释✓影子价值的内涵✓影子价值的应用第三节资源定价的决策案例对偶理论对偶问题对偶解的经济意义对偶理论对称性定理弱对偶定理对偶定理互补松弛定理对偶问题的解对偶解的经济意义边际贡献对偶问题实例应用对偶规划的数学模型对偶问题与原问题之间的关系引例——俩制造商间的对话：唉!我想租您的机器设备一用。

咋样？价格嘛……好说，肯定不会让您兄弟吃亏。

王老板做家电赚了大钱，可惜我老李有高科技产品，却苦于没有足够的机器设备咋办？只有租咯。

Hi ：王老板，听说近来家电生意好惨了，也帮帮兄弟我哦!家电生意还真赚钱，但是现在的手机生意这样好，不如干脆把我的机器设备租给他，又能收租金又可做生。

价格嘛……好商量，好商量。

只是…...王老板李老板一、对偶问题的提出●若例1中该厂的产品平销，现有另一企业想租赁其设备。

厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。

●在这个问题上厂长面临着两种选择：自行生产或出租设备。

首先要弄清两个问题：⏹①合理安排生产能取得多大利润?⏹②为保持利润水平不降低，资源转让的最低价格是多少？●问题①的最优解：x 1=4，x 2=5，Z *=37。

一、对偶问题的提出出让定价：●假设出让A 、B 、C 设备所得利润分别为y 1、y 2、y 3●原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。

于是有2y 1+0y 2+3y 3≥3●同理，对乙产品而言，则有0y 1+2y 2+4y 3≥5●设备台时出让的收益（希望出让的收益最少值）min 16y 1+10y 2+32y 3●显然还有y 1，y 2，y 3≥0一、对偶问题的提出例1的对偶问题的数学模型●对偶问题的最优解：y 1=0，y 2=1/2，y 3=1，W * =37●两个问题的目标函数值相等并非偶然●前者称为线性规划原问题，则后者为对偶问题，反之亦然。

●对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。

min =16y 1+10y 2+32y 32y 1+ 0y 2+ 3y 3≥30y 1+ 2y 2+ 4y 3≥5y 1，y 2，y 3≥0S.t.maxZ=3x 1+5 x 22x 1≤162x 2≤103x 1+4 x 2≤32x 1 , x 2 ≥0S.t.表3-1对偶关系第i个约束为=第i个变量无约束0,,0,148210561882794543213214243214321x x x x x x x x x x x x x x x x x MinZ 无约束【解】目标函数求最小值，应将表3-1的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3 个变量4个约束，对照表3-1的对应关系，对偶问题为：123131231312max 1810147226885w y y y y y y y yy y y y=≥≤≤1549 y 1≤0，y 2≥0，y 3无约束●1、写出下列问题的对偶问题Min Z=2x1-x2+2x3-x1+x2+x3=4-x1+x2-x3 6x1 0,x2 0, x3无限制●2、写出下列问题的对偶问题Max w=5x1+4x2+6x3x1+2x2≥2x1+ x3≤3-x1+x2+x3≤-5x1-x2+x3=1x1≥0, x2≤0, x3无约束二、对偶规划的性质1、对称性定理对偶问题的对偶问题是原问题。

根据对偶规划，很容易写出对偶问题的对偶问题模型。

2、最优性定理设，分别为原问题和对偶问题的可行解，且则，分别为各自的最优解。

3. 对偶性定理若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。

4. 互补松弛性最优解的充分必要条件是，X Y Y X C Tb X Y 0*s X Y 0* X Y s将互补松弛条件写成下式：*1*100i j miS i nS j j y x y x由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：(1)当y i *>0时，,反之当时y i *=0；0 iS x 0 iSx **(2)00,00j j S j jS y x x y 时反之当时利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。

【例33,2,1,0162210243321321321j x x x x x x x st x x x MaxZ j的最优解是运用互补松弛定理求对偶问题的最优解。

TX )0,2,6( 【解】对偶问题是,1422321610min 2121212121y y y y y y y y y y w 因为X 1≠0，X 2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即：422322121y y y y 解此线性方程组得y 1=1，y 2=1,从而对偶问题的最优解为Y =（1，1），最优值w =26。

●已知线性规划问题●已知其对偶问题的最优解为，z = 5。

试用对偶理论找出原问题的最优解。

5210 3 32 432 32532543215432154321,,,j ,x x x x x x x x x x x x x x x x min j 541/y * 532/y *(5) 3 3 (4) 2 (3) 532(2) 3 (1) 22 212121212121 y ,y y y y y y y y y y y 将*y 1,*y 2的值代入约束条件，得(2)，(3)，(4)为严格不等式；由互补松弛性得0432 ***x x x 。

因y 1，y 2 0；原问题的两个约束条件应取等式，故有3243 5151 ****x x x x求解后得到1151x ,x ；故原问题的最优解为X * = (1，0，0，0，1)T； * = 51、弱对偶性：设X °、Y °分别为LP(max)与DP(min)的可行解，则这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。

例：证明下列线性规划无最优解：补2：LP(max)的初始基变量的检验数的相反数对应于DP(min)的一组基本解。

bY CX003,2,1,0324min 32131321j x x x x x x xxxZ j题解的对应关系；表2－6也许对了解这些性质有帮助。

表2－6一、影子价值的内涵（Shadow price ）:n j mi i i j j y b x c Z 11i iy b Z ●左边是资源b i 每增加一个单位对目标函数Z 的贡献；●对偶变量y i 在经济上表示原问题第i 种资源的边际价值边际价值。

●对偶变量的值y i *表示第i 种资源的边际价值，称为影子价值影子价值。

⏹若原问题价值系数C j 表示单位产值，则y i 称为影子价格。

⏹若原问题价值系数C j 表示单位利润，则y i 称为影子利润。

⏹影子价格=资源成本+影子利润一、影子价值的内涵●影子价格不是资源的实际价格，反映了资源配置结构，⏹其它数据固定，某资源增加一单位导致目标函数的增量。

●对资源i总存量的评估：购进or 出让对资源i当前分配量的评估：增加or 减少⏹第一，影子利润说明增加哪种资源对经济效益最有利⏹第二，影子价格告知以怎样的代价去取得紧缺资源⏹第三，影子价格是机会成本，提示资源出租/转让的基价⏹第四，利用影子价格分析新品的资源效果：定价决策⏹第五，利用影子价格分析现有产品价格变动的资源紧缺性⏹第六，可以帮助分析工艺改变后对资源节约的收益⏹第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺例：某厂生产甲乙产品，（1）如何安排每周的利润为最大?（2）如果企业可以不生产，那资源出让如何定价？352390销售价格(元)360200300205014510943原材料(kg)设备(工时)电力(度)资源拥有量资源成本乙甲,3001032005436049s.t.127max 2121212121x x x x x x x x x x Z *T(20,24,84,0,0)X 一、最优生产决策二、资源获利决策如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。

123123123123min 3602003009437s.t.451012,,0w y y y y y y y y y y y y1*0y 2*1.36y 3*0.52y *428Z 45**0,0y y 设原材料的单位出让获利为y 1，设备工时的单位出让获利为y 2，电力的单位出让获利为y 3。

出让决策的线性规划模型：●假设资源市场上，原材料的价格为18元/公斤，设备工时价格为52元，电力资源成本为1.3元/度，企业是否应购进资源呢？●分析：由于原材料的资源成本为20元/公斤，设备工时的资源成本为50元，电力资源成本为1元/度，因此它们的影子价格分别20元/公斤、51.36元/小时、1.52元/度。

企业经营决策者可以在把本企业资源的影子价格与市场价格进行比较后，作出决策。

电力资源的影子价格高于市场价格，企业可以考虑购进资源，增大其持有量；而设备工时的影子价格低于市场价格，企业暂时不可购买；虽然原材料市场价格低于其影子价格，但它是非紧缺资源，则企业增加资源不但难以获利，还会增加库存成本。

设原问题是（记为LP ）：max X b AX CX Z 对偶问题是（记为DP ）：m in 0w Y b Y A C Y根据原问题和对偶问题之间的对称原理，可以构造一个求线性规划的另一种方法，即对偶单纯形法。

对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时，极小化问题时。

0 j0 j(1)将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数（max ）或（min ）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解b i <0，则进行换基计算；(2)先确定出基变量。

l 行对应的变量x 出基；min |0l i i ib b b ＝(3)再选进基变量。

求最小比值0|min lj lj j j k a a (4)求新的基本解，用初等变换将主元素a lk 化为l,k 列其它元素化为零，得到新的基本解，转到第一步重复运算。

0 j 0 j【例】用对偶单纯形法求解：0,,34534min 321321321321x x x x x x x x x x x x z 【解】先将约束不等式化为等式，再两边同乘以（－1），得到5,,2,1,034534min 53214321321 j x x x x x x x x x x x x z jx 4、x 5 为基变量，用对偶单纯形法，迭代过程如下表所示。