管理运筹学：管理科学方法（第3版）

线性规划的一般模型

2.物资运输问题3个供货源A1,A2,A34个需求市场B1,B2,B3,B4产量、销量、单位运费如表统一筹划运销的最小运费方案

销地货源地R1R2R3产量A134515A22235销量5105(1)决策变量：设从Wi到Rj的运输量为xij，(2)最小运费：minZ=3x11+4x12+5x13+2x21+2x22+3x23(3)产销平衡：供应平衡x11+x12+x13=15x21+x22+x23=5销售平衡x11+x21=5x12+x22=10x13+x23=5非负性约束

xij≥0(i=1,2；j=1,2,3)

三、线性规划模型的特征

第一节

线性规划的一般模型

1.模型隐含假定（1）线性化假定

函数关系式f(x)=c1x1+c2x2+…+cnxn，称线性函数。

建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定

决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。

（4）连续性假定

决策变量取值连续。（5）确定性假定

所有参数都是确定的，不包含随机因素。三、线性规划模型的特征

第一节

线性规划的一般模型

2.一般数学模型

用一组非负的决策变量表示决策问题

存在一组等式或不等式的线性约束条件

有一个目标为决策变量的极值线性函数四、线性规划的图解方法

第一节

线性规划的一般模型

1.线性规划的可行域可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。maxZ=3x1+5x2

2x1≤162x2≤10

3x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD2x1=162x2=10x1x248103583x1+4x2

=320ABCD四、线性规划的图解方法

第一节

线性规划的一般模型

2.线性规划的最优解目标函数

Z=3x1+5x2

代表以

Z为参数的一族平行线。Z=30Z=37Z=15五、线性规划解的可能性第一节

线性规划的一般模型

1.唯一最优解：只有一个最优点2.多重最优解：无穷多个最优解当市场价格下降到74元，其数学模型变为

2x1=162x2=103x1+4x2

=32x1x248102580ABCDZ=24Z=32Z=12五、线性规划解的可能性第一节

线性规划的一般模型

3.无界解：可行域无界，目标值无限增大

(缺乏必要约束)原因在于：建模时遗漏了主要条件

（生产资源、市场需要、技术标准…）五、线性规划解的可能性第一节

线性规划的一般模型

4.没有可行解：线性规划问题的可行域是空集

(约束条件相互矛盾)技术冲突利害冲突强冲突弱冲突原因：舍去其一，保留另一个：限制其一，另一个最优：经济补偿一、线性规划的标准型式

1、标准型表达方式(1)代数式

(2)向量式

(3)矩阵式

A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。第二节

线性规划的单纯型法

一、线性规划的标准型式

2、标准型转换方法第二节

线性规划的单纯型法

(1)极小化目标：minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)某一资源：bi<0：则以－1乘该约束两端，使之满足非负性的要求(3)对于≤约束：则在左端加上一个非负松弛变量，使其为等式(4)对于≥约束：则在左端减去一个非负剩余变量，使其为等式

(5)无非负约束：令xk=x'k-x"k

，(x'k≥0,x"k≥0)二、线性规划之解的概念

基矩阵：一个非奇异的子矩阵（线性无关）。矩阵A中任意m列的线性无关子矩阵B

，称为一个基。组成基B的列为基向量，用Pj表示(j=1,2,…,n)。基变量：与基向量Pj相对应的m个变量xj称为基变量其余的n-m个变量为非基变量1、线性规划解之关系

基解：令所有非基变量等于零，得出基变量的唯一解

。x3x4x5基变量是x3,x4,x5非基变量是x1,x2令非基变量x1=x2=0，得到一个基解x3=16，x4=10，x5=32第二节

线性规划的单纯型法

二、线性规划之解的概念

1、线性规划解之关系

可行解：满足约束条件AX=b,X≥0的解。

可行基：可行解对应的基矩阵。

基可行解：满足非负性约束的基解称为基可行解。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解基可行解第二节

线性规划的单纯型法

二、线性规划之解的概念

2、线性规划基本原理定理1.

若线性规划问题存在可行域，则其可行域一定是凸集。定理2.

线性规划问题的基可行解对应可行域的顶点。定理3.

若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。定理4.

线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。第二节

线性规划的单纯型法

二、线性规划之解的概念

3、线性规划解题思路先找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。如果是最优解，就得到这个线性规划问题的最优解；如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直到得到最优解。

第二节

线性规划的单纯型法

三、单纯形法原理－代数法

1.代数解法

2x1+x3

=162x2+x4

=10

3x1+4x2+x5=32-Z+3x1

+5x2+0x3

+0x4+0x5=0x1x2x3x4x5x3x4x5非奇异子阵作为一个基基变量x3,x4,x5非基变量x1,x2三、单纯形法原理－代数法

将基变量用非基变量线性表示，即x3=16-2x1

x4

=10-2x2

x5=32-3x1-4x2

令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2

=0，x3=16，x4=10，x5

=32一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0

。（1）求初始基可行解

三、单纯形法原理－代数法

确定进基变量

2x1+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0

从目标函数-Z+3x1+5x2+0x3+0x4+0x5=0可知：非基变量x1，x2的系数为正数，生产哪种产品都会增加利润。因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品。（2）第一次迭代

三、单纯形法原理－代数法

确定离基变量基变量用非基变量线性表示x3=16–2x1x4=10－2x2

x5=32-3x1-4x2保持原非基变量x1=0，x2变成基变量时应保证

x3,x4,,x5非负，即有（2）第一次迭代（续）

x3=16≥0

x4=10-2x2≥0

x5=32-4x2≥0x2≤10/2x2≤32/4三、单纯形法原理－代数法

（2）第一次迭代（续）主行主列主元

2x1+0x2+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0进基变量所在列为主列，离基变量所在行为主行三、单纯形法原理－代数法

基变换进行初等变换，变主元为1，主列为单位列向量。（2）第一次迭代（续）

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+5x2+0x3+0x4+0x5=0

2x1+0x2+x3=162x2+x4=10

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0

2x1+x3=16

x2+1/2x4=5

3x1+4x2+x5=32-Z+3x1+5x2+0x3+0x4+0x5=0三、单纯形法原理－代数法

（2）第一次迭代（续）将基变量用非基变量线性表示，即x3=16–2x1x2=5-1/2x4

x5=12-3x1+4x4令非基变量x1=0，x4=0，找到另一个基可行解x1=0，x2=5，x3=16，x4=0，x5=12目标函数Z=25三、单纯形法原理－代数法

确定进基变量（3）第二次迭代

第一次迭代结果

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25目标函数-Z+3x1+0x2+0x3–5/2x4+0x5=-25，非基变量x1的系数σ1=3（检验数）为正数，确定x1为进基变量。三、单纯形法原理－代数法

确定离基变量（3）第二次迭代

（续）x3=16-2x1≥0x2=5≥0

x5=12-3x1≥0x1≤16/2x1≤12/3基变量用非基变量线性表示

x3=16–2x1x2=5-1/2x4

x5=12-3x1+4x4保持原非基变量x4=0，x1变成基变量时应保证

x2,x3,,x5非负，即

三、单纯形法原理－代数法

基变换变主元为1，主列为单位列向量。（3）第二次迭代（续）

2x1+x3=16

x2+1/2x4=5

x1+-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

x3+4/3x4-2/3x5=8

x2+1/2x4=5x1-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-25

x3+4/3x4-2/3x5=8

x2+1/2x4=6x1+-2/3x4+1/3x5=4

-Z+0x1+0x2+0x3-1/2x4-x5=-37

2x1+x3=16

x2+1/2x4=5

3x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-25三、单纯形法原理－代数法

（3）第二次迭代（续）将基变量用非基变量线性表示，即x3=8–4/3x4+2/3x5x2=5-1/4x4

x1=4+2/3x4-1/3x5

令非基变量x4=0，x5=0，又找到一个基可行解

目标函数

-Z+0x1+0x2+0x3-1/2x4-x5=-37

x1=4，x2=5，x3=8，x4=0，x5=0Z=37检验数σj非正，得最优解X*=(4,5,8,0,0)T，Z*=37三、单纯形法原理－表格法

对代数法步骤进行具体化、表格化2.单纯形法表CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1nθ1CB2xB2b2a21a22…a2j…a2nθ2………………………CBnxBnbmam1am2…amj…amnθm检验数σj-Zσ1σ2…σj…σn三、单纯形法原理－表格法

①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数σj=Cj-CBPj′，若所有σj≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个σk所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{σj｜σj＞0}=σk原则，确定xk为换入变量(进基变量)，再按θ规则计算：θ=min{bi′/aik′|aik′＞0}=bl′/aik′

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③步。

单纯形法的计算步骤

举例-Z+3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32

Cj比值CBXBb检验数σjx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8三、单纯形法原理－表格法

162010050101/2012300-21x3x2x5050300-5/208-4Cj比值CBXBb检验数σjx1x2x3x4x535000检验数σj80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解:X*=(4,5,8,0,0)T，Z*=37三、单纯形法原理－表格法

3.单纯形法的矩阵计算

数学模型

maxZ=CX

AX=b

X≥0A中线形无关的子矩阵B为基矩阵

，即A→(B,N)与基矩阵对应的变量XB，其余变量为非基变量XN变形XB用XN线形表示左乘B-1代入整理令XN=0检验数三、单纯形法原理－矩阵法

4、单纯形法的管理启示

2x1=162x2=103x1+4x2

=32x1x24812590ABC(4,5)DX0=(0,0,16,10,32)TX1=(0,5,16,0,12)TX2=(4,5,8,0,0)T企业管理过程也是如此：

把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求完美。三、单纯形法原理

四、人工变量问题

用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。1.人工变量

采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有两种：大M法两阶段法四、人工变量问题没有单位矩阵，不符合构造初始基的条件，需加入人工变量

。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。

大M法例如

S.t.3x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0maxZ=

3x1-x2-2x3四、人工变量问题按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：

maxZ=3x1-x2-2x3-Mx4-Mx5

3x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数σjx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00x4x5-M-M24四、人工变量问题Cj比值CBXBb检验数σjx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24检验数σj212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1检验数σj31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2四、人工变量问题没有单位矩阵，不符合构造初始基的条件，需加入人工变量

。人工变量最终必须等于0才能保持原问题性质不变。利用两阶段法求解该问题。第一阶段：单独求解人工变量最小化的目标函数；第二阶段：将第一阶段结果带入第二阶段，求解原目标函数。两阶段法例如

S.t.x1-x2+6x3-x4=2x1+x2+2x3–x5=1xi≥0,i=1,2,3,4,5minZ=

5x1+21x2四、人工变量问题首先，引入人工变量x6,x7构建模型：

minZ’=

x6+x7x1-x2+6x3-x4+x6=2x1+x2+2x3–x5+x7=1xi≥0,i=1,2,3,4,5,6,7Cj比值CBXBbσjx6x7-1-11/31/2

s.t.x1x2x3x4x5x6x700000-1-1211-1[6]-10101120-101208-1-100四、人工变量问题Cj比值CBXBbσjx3x200x1x2x3x4x5x6x700000-1-13/81/41/401-1/8-1/81/81/81/2101/4-3/4-1/43/400000-1-1Cj比值CBXBbσjx3x2-2103/21/2x1x2x3x4x5-50-21003/81/41/401-1/8-1/8[1/2]101/4-3/41/400-21/8-21/8第二阶段，删除人工变量x6,x7，将结果带入原目标函数四、人工变量问题Cj比值CBXBbσjx3x2-2103/21/2x1x2x3x4x5-50-21003/81/41/401-1/8-1/8[1/2]101/4-3/41/400-21/8-21/8Cj比值CBXBbσjx3x1-210x1x2x3x4x5-50-21001/41/20-1/210-1/41201/2-3/20-1/20-11/4-9/4得到最优解:(1/2,0,1/4,0,0)T五、单纯形法补遗进基变量相持：单纯形法运算过程中，同时出现多个相同的σj最大。在符合要求的σj(目标为max：σj＞0，min：σj＜0)中，选取下标最小的非基变量为换入变量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小θ值。继续迭代，便有基变量为0，称这种情况为退化解。选取其中下标最大的基变量做为换出变量。多重最优解：最优单纯形表中，存在非基变量的检验数σj=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：大于0的检验数中，若某个σk所对应的系数列向量Pk′≤0，则解无界。无可行解：最终表中存在人工变量是基变量。五、单纯形法补遗－无界解例如S.t.标准化

maxZ=

3x1+2x2-2x1+x2+x3=2x1-3x2+x4=3x1,x2,x3,x4≥0Cj比值CBXBb检验数σjx1x2x3x432002-211031-301x3x40003200-3检验数σj80-512x3x103--31-301-90110-3此时，检验数σ2=11＞0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界θ值不存在，有进基变量但无离基变量。maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1,x2≥0第三节

线性规划的建模技巧计件工资maxZ=66x1+89x2+70x3

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0岗位工资

总收入=173x1+233x2+170x3

原料费=65x1+95x2+65x3，营运费=11000maxZ=108x1+138x2+105x3-11000

x1≤40

x2≤80

x3≤40

x1,x2,x3≥0计时工资：maxZ=108x1+138x2+105x3-11000

0x1+30x2+15x3≤2400

10x1+20x2+0x3≤240031x1+21x2+21x3≤4800

31x1+13x2+24x3≤4800

x1

≤40x2

≤80x3≤40x1,x2,x3≥0目标函数的灵活性MMCCGGWB资源G15C12M20B14B28M7C10C9G4$30ABCDEFG5$35$65$30C6M18W9裝配B6W8裝配G15C15C18M20原料二、线性规划的适用层次计划链的层次

粗能力计划定单可行不可行CRP主生产计划MPS物料需求计划MRP能力需求计划车间作业计划产品分销计划可行否作业统计与控制物料清单库存管理采购计划供应商生产计划大纲预测当前条件企业经营计划

产值计划

或

利润计划

绝对数量

或

增长幅度

期限:年度

单位:万元

产品销售收入或台套

确定产品品种和数量

期限:年度

单位:万台

具体产品具体

时段出产计划

合同单,预测转换为生产任务

将产品出产计划转换成物料需求表

大类产品年度生产计划

品种和数量的最优组合

期限:年度

单位:万台独立需求：需求量

和时间与其它物料

没直接关系来自企业外部市场,

数量和时间取决于

企业外部需求订单和预测确定相关需求：需求量

和时间则取决于

另一物料制造过程的材料、

毛坯、零件需求BOM,产量和交期

计算—MRP第四节

线性规划的典型案例_

配送中心选择

供货源S1(产地)的供货能力5万台/月新增供货源S2可以满足市场需求且两个货源的价格相同目标市场(销地)的需求量5,10,5万台/月分销渠道中拟定在2个地点中选址设立分销中心转运产品决策变量：设从供货源到分销中心的运输量yij从分销中心到需求市场的运输量xjk选址规划在于二者的实际取值：若y11+y21=0,则不设分销中心W1；反之设置W1规模y11+y21若y12+y21=0,则不设分销中心W2；反之设置W2规模y12+y21目标函数：各路段上的实际运量×单位物流运费之和最小，即第四节

线性规划的典型案例供应能力平衡约束：市场需求平衡约束配送中心不存留产品所有变量大于等于零第四节

线性规划的典型案例_

库存控制某帆船公司需确定年内四个季度的生产计划安排，根据历史数据做出市场预测：一季度市场需求为30艘,二季度60艘,三季度75艘,四季度25艘。需求必须被满足季度期初生产：每季度最大产能是40艘,所需成本为400元/艘。若加班生产,则加班生产的数量不能超过20艘,加班生产的单位成本是450元/艘。如果没有销售出去,每艘帆船每季度的库存持有成本是20元。年度生产计划该如何安排才能实现生产成本和库存成本的最小化？

(1)决策变量:每个季度,必须确定正常生产和加班生产的帆船数量,因此定义如下决策变量：xi=第i季度正常生产帆船的数量(i=1,2,3,4)yi=第i季度加班生产帆船的数量(i=1,2,3,4)si=第i季度末的帆船库存量(i=1,2,3,4）(2)目标函数:优化目标是追求总成本最小化,因此目标函数是：

(3)约束条件:库存守恒：第(i-1)季度末的库存量+第i季度的生产量=第i季度的需求量+第i季度末的库存量库存平衡约束：si-1+(xi+yi)=di+si(i=1,2,3,4)生产能力约束：xi<=40,yi<=20(i=1,2,3,4)非负约束：xi≥0,yi≥0,si≥0(i=1,2,3,4)

最优解：Z=78850,x1=x2=x3=40,x4=25,y1=5,y2=y3=20,y4=0

s1=s2=15,s3=s4=0第四节

线性规划的典型案例_

合理下料某建筑公司要用铝型材作为构架，制作100个铝合金窗子，每个窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根，原材料每根6米。怎样下料才能使余料最少?

(1)决策变量:无法直接定义，应列选可行方案。如方案1为：2.8米1根，1.8米1根，1.17米1根，0.6米0根，合计5.77米，余料0.23(2)目标函数和约束条件:第四节

线性规划的典型案例_

营养配餐假定一个成年人每天需要从食物中摄取3000千卡的热量、55克的蛋白质和800毫克的钙。如果市场上只有4种食品可供选择(当然可以扩充到n种食品),它们每千克所含的热量、营养成分和市场价格见表1-13。如何选择才能在满足营养的前提下使购买食品的费用最小?

(1)决策变量:设变量为每种食品每天的购入量。(2)目标函数和约束条件:第四节

线性规划的典型案例_

产品混合新时代制药公司利用4种化学原料A，B，C，D来生产一种新药，新药的产量必须达到每天1000公斤以上。新药中含有3种有效成分甲、乙、丙，它们的含量分别不低于8%，4%，2%。每公斤原料的价格和所含有效成分的比例如表1-14所示。如何选择才能在满足营养的前提下使购买食品的费用最小?

(1)决策变量:设变量为每种化学原料的投入量。(2)目标函数和约束条件:第2章

对偶规划Subtitle第一节

对偶规划的数学模型

对偶问题的提出

对偶规划的性质

第二节

对偶规划的经济解释

影子价值的内涵

影子价值的应用第三节

资源的参数变动分析第四节资源定价的决策案例学习要点思考一个案例根据第一章中的引入案例，该汽车制造厂的主营业务为机动汽车的生产加工制造，并且为了扩大市场占有率而实行资产经营。随着该厂业务量的提升，为了满足更高的需求，该制造厂希望能扩展业务范围、增加业务种类，不仅局限于生产制造环节，而是通过产业升级获得更多的利润。因此,汽车制造环节的设备产生冗余，为了避免设备闲置带来的损失，该厂计划将制造设备和技术人员等资源出租，从而获取一定的利润。如果你是该部门主管，会怎样制定出租计划、选择出租单位?生产不同型号汽车的设备中哪些属于紧缺设备,哪些存在冗余呢?而当进口生产成本、工人费用等条件发生变化时,应该如何调整生产计划来应对复杂的变化?（从企业管理或者运筹学角度想一想）第2章

对偶规划第一节

对偶规划的数学模型一、对偶问题的提出产品平销是否做代工：设备台时的最低价码？谈判时衡量对方出价面临着两种选择：自行生产或代加工①合理安排生产的利润?②利润不降低的资源转让最低价？资源出让模型(对偶问题)A,B,C工时出让利润y1,y2,y3minw=16y1+10y2+32y3

2y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1,y2,y3≥0

最优解

y1=0,y2=1/2,y3=1,w*=37生产计划模型(原问题)

假设甲乙产量x1,x2

maxZ=

3x1+5x2

2x1≤162x2≤103x1+4x2≤32x1

,x2

≥0最优解

x1=4,x2=5,Z*=37第一节

对偶规划的数学模型二、对偶规划的性质1.对称性定理

对偶问题的对偶问题是原问题。

根据对偶规划，很容易写出对偶问题的对偶问题模型。2.最优性定理

设

，

分别为原问题和对偶问题的可行解，且

则

，

分别为各自的最优解。3.对偶性定理

若原问题有最优解，那么对偶问题也有最优解，而且

两者的目标函数值相等。4.互补松弛性

最优解的充分必要条件

，第二节

对偶规划的经济解释

影子价值的内涵左边是资源bi每增加一个单位对目标函数Z的贡献；yi在经济上表示原问题第i种资源的边际价值。第二节

对偶规划的经济解释影子价格不是资源的实际价格，反映资源配置结构其它数据固定，某资源增加一单位导致目标函数的增量若原问题价值系数Cj表示单位产值，则yi称影子价格若原问题价值系数Cj表示单位利润，则yi称影子利润影子价格=资源成本+影子利润对资源i总存量的评估：购进

or出让对资源i分配量的评估：增加

or减少影子利润说明增加哪种资源对经济效益最有利影子价格告知以怎样的代价去取得紧缺资源影子价格是机会成本，提示资源出租/转让的基价利用影子价格分析新品的资源效果：定价决策利用影子价格分析现有产品价格变动的资源紧性可以帮助分析工艺改变后对资源节约的收益可以预知哪些资源是稀缺资源而哪些资源不稀缺第三节

资源的参数变动分析参数变动分析的必要性环境和条件处在不断的变化中模型参数的值是通过估计或预测得到的,带有一定的不确定性价值系数的变动分析非基变量xj的价值系数cj变动

只要σj'=cj+Δcj-CBB-1Pj≤0，最优基不变基变量xBi的价值系数cBi的改变

基变量的检验数σB=CB+ΔCB-(CB+ΔCB)B-1B=0,不受变动影响;非基变量的检验数变为:σj’=cj-(CB+ΔCB)B-1Pj=cj-CBB-1Pj-ΔCBB-1Pj=σj-ΔCBB-1Pj资源限量的变动分析考察b的变化分析

不影响检验数,只影响XB=B-1b考察b的变化范围

br的增量为Δbr,其他数据不变。新的基解为:XB’=B-1(b+Δb)只要XB'≥0,则可保持最优基不变。第四节

资源定价的决策案例案例：甲乙生产工艺如图，试确定获利最大的生产计划?材料A材料AD

10材料BD15裝配裝配D

20C8甲D15D25C12C28乙产品