中南大学线性规划课件4

2-1线性规划的对偶理论例2.1生产计划问题（资源利用问题）

胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？数学模型

maxg=50x1+30x2s.t.4x1+3x2120(2.1)2x1+x250x1,x20

如果我们换一个角度，考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？

假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：

mins=120y1+50y2目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。

该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：

4y1+2y2503y1+y230y1,y20

得到另外一个数学模型：

mins=120y1+50y2s.t.4y1+2y250(2.2)3y1+y230y1,y20模型(2.1)和模型(2.2)

既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型(2.1)称为原问题，则模型(2.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。例2.2营养配餐问题

假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表序号食品名称热量(千卡)蛋白质(克)钙(毫克)价格(元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，

x3，x40

(2.3)该问题的对偶问题：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314(2.4)800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30该问题的对偶问题(2.4)经济意义可解释为：市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。线性规划的对偶关系：（I）MaxS=CtXs.t.AXbX0(II)Ming=Ybs.t.YACY0（2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。(2.3)(2.4)

a11a12….a1nb1A=a21a22….a2nb

=

b2

。。。。。。。。。。。。。。。

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=Yt=……………..…..cnxn0ym原始问题maxs=CtXs.t. AX≤b X≥0对偶问题ming=Ybs.t.YA≥C Y≥0≤maxbACtCAtbt≥minmnmn例2-3：写出下列线性规划问题的对偶问题minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

22x1+2x2+4x43x1，x2，

x3，x40minS=12x1+8x2+16x3+12x4

s.t.2x1+x2+4x3

2

y1

2x1+2x2+4x43

y2

x1，x2，

x3，x40min

S=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

2

y1

2x1+2x2+4x4

3

y2

x1,x2,

x3,

x40解：该问题的对偶问题：

maxg=2y1+3y2

s.t.

2y1+2y212y1+2y284y1164y212

y1,y20例2-4：写出下列线性规划问题的对偶问题maxS=10x1+x2+2x3s.t.X1+x2+2x3

10y14x1+2x2-x320

y2

x1，x2，

x30解：该问题的对偶问题：

ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y2

0maxS=10x1+x2+2x3s.t.X1+x2+2x3

10y14x1+2x2-x320y2

x1,x2,

x30例2-5：写出下列线性规划问题的对偶问题

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

3x1+x2+7x33x1，x2，

x30解：用（-1）乘以第二个约束方程两边

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

y1

-3x1-x2-7x3-3y2x1，x2，

x30该问题的对偶问题：

maxg=2y1-3y2s.t.2y1-3y213y1-y225y1-

7y23y1，y20例2-6：写出下列线性规划问题的对偶问题

minS=2x1+3x2-5x3s.t.x1+x2-x3

5

2x1

+x3=4

x1，x2，

x30解：将原问题的约束方程写成不等式约束形式：

minS=2x1+3x2-5x3

x1+x2-x3

5

y1

2x1

+x34

y2’

-2x1

-x3-4y2”

x1,x2,

x30引入变量y1,y2’，y2”

写出对偶问题

maxg=5y1+4y2’-4y2”

s.t.y1+2y2’-2y2”

2y1

3-y1+y2’-y2”

-5y1，y2’，y2”

0令y2=y2’-y2”

得到

maxg=5y1+4y2s.t.y1+2y22y1

3-y1+y2-5y10，y2无非负约束此类问题称为非对称型对偶问题。前面的问题称为对称型对偶问题。原问题:2x1+x3=4根据对偶规划的对称性,若原规划某个变量无非负限制,则与之对应的对偶约束为等式约束.若原规划中有等式约束,则与之对应的对偶变量无非负限制.例2-7：写出下列线性规划问题的对偶问题

minS=3x1-2x2+x3s.t.x1+2x2=1

2x2

-x3-2

2x1+x33x1-2x2+3x34x1，x20

，

x3无非负限制不等式两边乘(-1)

ming=3x1-2x2+x3s.t.

x1+2x2=1

y1

-2x2+x32y22x1+x33y3x1-2x2+3x34y4x1，x20

，

x3无非负限制解:

综合运用对偶原则得到

maxZ=y1+2y2+3y3+4y4s.t.y1+2y3+y43x12y1-2y2-2y4-2x2

y2+y3+3y4=1

x3y2,y3,y40，y1无非负约束x3

无非负限制x1+2x2=1对偶问题的基本定理定理2.0:(对称性定理)

对偶问题的对偶就是原问题.minz’=-CTXs.t.-AX≥-b

X≥0maxg’=-Ybs.t.-YA≤-C Y≥0ming=Ybs.t.YA≥C Y≥0maxz=CTXs.t.AX≤

b

X≥0对偶的定义对偶的定义定理2.1:(弱对偶定理)

对于互为对偶问题(I)(II)中的任意的可行解X(0),Y(0),都有

CTX(0)≤Y(0)b

用非线性函数马鞍面说明定理的含义（鞍点）。但是线性规划是线性函数。马鞍面z=x2/4-y2/6鞍点YZXZYX在Y=0的平面上鞍点是z=f(0,y)的极大值点XYZ在X=0的平面上鞍点是z=f(0,y)的极小值点马鞍面z=x2/4-y2/6鞍点YZX对偶问题的基本定理推理一:对偶问题中,任意一个可行解,都产生了另一个问题的目标函数的界。推理二:若原问题和对偶问题都有可行解,则它们都有最优解。推理三:若互为对偶问题中任意一个有可行解,但无最优解,则另一个就无可行解。对偶问题的基本定理定理2.2(最优准则)

若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解.对偶问题的基本定理定理2.3(对偶定理)

若原问题有最优解,则对偶问题也有最优解,且最优值相等.对偶问题的基本定理定理2.3(对偶定理)

若原问题有最优解,则对偶问题也有最优解,且最优值相等。推理:对偶问题的最优解为原问题最优表中,相应的松驶变量检验数的相反数。定理2.3(互补松弛性)maxz=CTXs.t.AX+XS=bX,XS≥0ming=Ybs.t.YA-YS=CY,YS≥0maxz

=

CTXs.t.AX≤bX≥0ming=Ybs.t.YA≥CY≥0对偶引进松弛变量引进松弛变量XTYS=0YTXS=0互补松弛关系X，XsY，Ysmaxz=CTXs.t. AX+XS=b X,XS≥0ming=Ybs.t.YA-YS=C Y,YS

≥0XTYS=0YTXS=0mn=YYSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数

y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量

原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0原问题与对偶问题解的对应关系2-2对偶解的经济解释

如果把线性规划的约束看成广义资源约束，右边项则代表某种资源的可用量。对偶解的经济含义是资源的单位改变量引起目标函数值的改变量。通常称为影子价格。影子价格表明对偶解是对系统内部资源的客观估计，又表明它是一种虚拟的价格而不是真实价格。原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格(ShadowPrice)原始和对偶问题都取得最优解时，最大利润maxz=ming0yyyyyycyyayayacyyayayacyyayaya.t.sybybybgminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211³=-++=-++=-++++=++++++LLLLLLLLLLLLay1y2ym产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源0xxxxbxaxaxaxabxaxaxaxabxaxxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211³£+++£+++£++++++=LLLLLLLLLLLLLLLLL机会成本利润差额成本产品的差额成本（ReducedCost）差额成本=机会成本-利润影子价格的特征：影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋于资源这种价值。因此，也称为最优价格。影子价格的特征：影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为最优价格。影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。系统内部资源数量和价格的变化，它是一种动态的价格体系。影子价格的特征：对偶解——影子价格的大小客观反映了资源在系统内的稀缺程度。如果某资源在系统内供大于求，尽管它有市场价格，但它的影子价格等于零。增加这种资源的供应不会引起系统目标的任何变化。如果某资源是稀缺资源，其影子价格必然大于零。影子价格越高，这种资源在系统中越稀缺。影子价格的特征：影子价格是一种边际价值，它与经济学中边际成本的概念相同。因而在经济管理中有十分重要的价值。企业管理者可以根据资源在企业内部影子价格的大小决定企业的经营策略。例2-13：某企业生产A，B二种产品。A产品需要消耗2个单位原料和1个小时人工；B产品需要消耗3个单位原料和2个小时人工；A产品销售价格23元，B产品销售价格40元。该企业每天可利用生产原料25单位和15个人工。每单位原料的采购成本为5元，每小时人工工资为10元。问该企业如何组织生产才能使销售利润最大？解：（模型一）目标函数系数直接使用计算好的销售利润，成本数据不直接反映在模型中。

maxg=3x1+5x2s.t.2x1+3x225x1+2x215x1,x20最优解X=（5,5）最优值Z=40对偶解Y=（1,1）解：（模型二）目标函数系数使用未经过处理的数据，成本数据直接反映在模型中。

maxg=23x1+40x2-5

x3-10x4s.t.2x1+3x2-x3=0x1+2x2-x4=0x325x415x1,x2,

x3,

x40（模型二）最优解X=(5,5,0,0)最优值Z=40对偶解Y=(6,11,1,1)一般来讲，如果模型显性地处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。一般来讲，如果模型显性地处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。一般来讲，如果模型显性地处理所有资源的成本计算（模型二）则对偶解与影子价格相等，我们按以下原则考虑企业的经营策略：如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。如果某资源的影子价格等于市场价格，表明该资源在系统内处于平衡状态，既不用买入，也不必卖出该资源。一般来讲，如果模型隐性地处理所有资源的成本计算（模型一）则影子价格应等于对偶解与资源的成本之和，我们按以下原则考虑企业的经营策略：如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。一般来讲，如果模型隐性地处理所有资源的成本计算（模型一）则影子价格应等于对偶解与资源的成本之和，我们按以下原则考虑企业的经营策略：如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。如果某资源的对偶解小于零，表明该资源在系统内无获利能力，应卖出该资源。一般来讲，如果模型隐性地处理所有资源的成本计算（模型一）则影子价格应等于对偶解与资源的成本之和，我们按以下原则考虑企业的经营策略：如果某资源的对偶解大于零，表明该资源在系统内有获利能力，应买入该资源。如果某资源的对偶解小于零，表明该资源在系统内无获利能力，应卖出该资源。如果某资源的对偶解等于零，表明该资源在系统内处于平衡状态，既不用买入，也不必卖出。2-3对偶单纯形法原始单纯形法其基本思路：在换基迭代过程中，始终保持基变量值非负，逐步使检验数变成非正，最后求得最优解或判断无最优解。对偶单纯形法其基本思路：在换基迭代过程中，始终保持检验数非正，逐步使基变量值变成非负，最后求得最优解或判断无最优解。例2-9：用对偶单纯形法解下列线性规划问题

minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x4

2x1，x2，

x3，x40解：此题可用人工变量方法求，但也可用对偶单纯形法。

maxS’=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=

-2x1，x2，

x3，x4，x5

，x6

0计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。常数项是负数且最小，确定出基变量x5。用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1）主元运算：第一行乘（-1）主元运算：第二行加上第一行（-2）计算检验数确定出基变量X6确定进基变量X3，主元（-2）主元运算：第二行乘（-1/2）主元运算：第一行加第二行计算检验数：全为非正。但此时常数b已全大于零,最优解=（7,0,4,0