运筹学课件 (2)教材

第一章绪论1.1题解

Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究——历史渊源OR11绪论1.2运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮

Erlang1917排队论

Harris1920存储论

Levinson1930零售贸易

康脱洛维奇1939LP

OR12OR13OR14OR15OR16OR17OR18OR19绪论1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett

运输船编队空袭逃避深水炸弹轰炸机编队OR110绪论1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题

OR1111.3学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。OR1121.4定性与定量例：店主进货两者都是常用的决策方法定性是基础，定量是工具，定量为定性服务。定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。OR1131.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、系统结构。形象模型：如地球仪、沙盘、风洞模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk)G(xi,yj,uk)≥0OR1141.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划图论与网络存储论排队论决策论对策论计算机仿真OR1151.7运筹学的工作步骤确定问题搜集数据建立模型检验模型求解模型结果分析结果实施OR1161.8运筹学与计算机计算机为运筹学提供解题工具。本书有现成的程序可以利用要学会解题的思路与方法，建立模型很重要。OR117第二章线性规划与单纯形法2.1LP(linearprogramming)的基本概念

LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。

OR1182.1.1LP的数学模型

例题1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120OR119例题1建模问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360

设备约束4X1+5X2

≤200

原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥0OR120例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR121例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5≥700营养要求：

x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非负性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0OR122例题3：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6OR123例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x6+x1≥60非负性约束：xj

≥0,j=1,2,…6OR124归纳：线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn约束条件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1

a21x1+a22x2+a23x3+…+a2nxn

≤(=≥)b2

…………am1x1+am2x2+am3x3+…+amnxn

≤(=≥)bn非负性约束：x1

≥0,x2≥0,…,xn

≥0OR1252.1.2线性规划图解法由中学知识可知：y=ax+b是一条直线，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线，以Z为参数的一族等值线。

9x1+4x2

≤360→x1≤360/9-4/9x2

是直线

x1=360/9-4/9x2

下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR126例1图示.9080604020

020406080100x1

x29x1+4x2

≤3604x1+5x2

≤200

3x1+10x2

≤300ABCDEFGHIZ=70x1+120x2OR127概念概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR128结论可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形OR1292.1.3线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,nOR130线性规划的标准型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,m

xj≥0

j=1,2,…,nj=1nnj=1OR131线性规划的标准型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1OR132线性规划的标准型矩阵式：maxZ=CXAX=bX≥0

其中：

b=(b1,b2,…,bm)T

a11

a12….a1nA=a21

a22…a2n………

am1

am2…amnOR133标准型的特征目标函数极大化约束条件为等式决策变量非负OR134非标准型转化为标准型目标函数极小化转为极大化：

minZ=－max(－Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：∑aijxj≤bi

加入松弛变量

∑aijxj≥bi

减去剩余变量非正变量：即xk

≤0则令x’k=－xk

自由变量：即xk无约束，令xk=x’k－x”kOR135非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2

≤2004X1+5X2+x4=2003X1+10X2

≤3003X1+10X2+x5=300

X1≥0X2≥0Xj≥0j=1,2,…,5OR136非标准型转化举例之二minZ=x1+2x2-3x3maxZ’=x’1－2x2+3(x’3－x”3)

x1+x2+x3

≤9－x’1+x2+x’3－x”3+x4=9-x1-2x2+x3≥2x’1－2x2+x’3－x”3-x5=23x1+x2-3x3=5－

3x’1+x2－3(x’3－

x”3

)=5x1≤0x2≥0x3无约束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

OR1372.1.4基可行解基的概念：如前所述LP标准型和式：maxZ=∑cjxj

∑aijxj=bi

xj

≥0

j=1,2,…,n

矩阵式：maxZ=CXAX=bX≥0

约束方程的系数矩阵A的秩为m，且m<n。设A=B+N，B是A中m

m阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。nj=1nj=1OR138基解的概念不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解。OR139基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!OR140例题6基可行解说明

maxZ=70X1+120X2P1P2P3P4P5

9X1+4X2+X3=360 94100

4X1+5X2+x4=200A=45010

3X1+10X2+x5=300310001

Xj≥0j=1,2,…,5这里m=3,n=5。Cmn=10OR141例题6基可行解说明基（p3,p4,p5）

，令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=－250,x5=－600.非可行解基（p2,p3,p4

），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解（P21图）OR142例题7可行基、基可行解

与最优解Maxz=2x1+x2-x3s.t:x1+x2+2x3≤6

x1+4x2-x3≤4x1，x2，x3≥0化为标准形Maxz=2x1+x2-x3s.t:x1+x2+2x3+x4=6

x1+4x2-x3+x5=4x1，x2，x3，x4，x5≥0OR143例题7可行基、基可行解

与最优解系数矩阵为：

OR144例题7可行基、基可行解

与最优解接上：

OR145例题7可行基、基可行解

与最优解接上：

共10个基OR146例题7可行基、基可行解

与最优解即同理对应同时为基本可行解，对应

同时为基本可行解，对应

OR147例题7可行基、基可行解

与最优解同理依次求解既得所有,其中B5

、B6、

B9

、B10

对应的基础解为基本可行解，最优解为B2对应的基础解，为：

OR1482.2单纯形法2.2.1初始基可行解的确定从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,……Pm)。进行等价变换－－约束方程两端分别左乘B－1得

X1++a’1m+1xm+1+…+a’1nxn=b’1

x2++a’2m+1xm+1+…+a’2nxn=b’2……………..

xm+a’mm+1xm+1+…+a’mnxn=b’m令非基变量为0，得基可行解X(0)=(b1’，b2’，……bm，0，……0）Tz0=∑cibi’OR1492.2单纯形法2.2.2最优性检验：LP经过若干步迭代，成为如下形式：X1++a’1m+1xm+1+…+a’1nxn=b’1

x1=b’1-∑

a’1jxj

x2++a’2m+1xm+1+…+a’2nxn=b’2x2=b’2-∑a’2jxj……………..……………..

xm+a’mm+1xm+1+…+a’mnxn=b’mxm=b’m-∑a’mjxjOR150单纯形法一般性表示：xi=b’i-∑a’ijxji=1,2,…m将xi代入目标函数得：Z=∑

cjxj=∑

cixi+∑

cjxj

=∑ci（b’i-∑a’ijxj

）+∑

cjxj

=∑cibi’+∑(cj-∑

cia’ij)xj

令：σj=cj-∑

cia’ij

z0=∑cibi’则Z=z0+∑σjxj

σj判别准则：

σj≤0

时,达到最优解OR151单纯形法2.2.2基变换若存在σj≥0，则取max{σj

}=σK

，相应之非基变量XK若取非零，将使Z增加,故令XK

进基。令XK≠0，其余非基变量保持为零。XK

原是非基变量，取零值，若XK

≠0将迫使某个原基变量为零，当XK取值超过任意b’i/a’ik

时,将破坏非负性条件,于是令θ=min{b’i/a’ik

a’ik>0}=b’L/a’Lk

。

这时原基变量XL=0，由基变量变成非基变量，a’Lk处在变量转换的交叉点上，称之为枢轴元素σj≥0OR152单纯形法解题举例单纯形表的格式：

CjC1C2…Cn

θiCBXBbx1

x2….xn

C1C2

…Cmx1x2…xmb1b2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θm

σjσ1σ2…σnOR153

Cj70120000CBXBbX1X2X3X4X5θj

000X3X4X5360200300

94100

45010310001904030σj0

70120000

00120X3X4X224050

307.8010-0.4

2.5001-0.50.31000.130.7620100σj3600

34000-12070120X3X1X2842024

001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2OR154单纯型法的基本思路OR155例二、试列出下面线性规划问题的初始单纯型表OR156关于检验数的数学解释设B是初始可行基，则目标函数可写为两部分(1)约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数把XB代入目标函数，整理得到(3)式第j个非基变量的机会成本如(4)式若有cj

zj>0,则未达到最优OR157标准型的单纯型算法找初试基础可行基对于(max,)，松弛变量对应的列构成一个单位阵若有bi<0，则单位阵也不能构成一个可行基检验当前基础可行解是否为最优解所有检验数cj

zj0，则为最优解，否则确定改善方向从(cj

zj)>0中找最大者，选中者称为入变量，xj*

第j*列称为主列确定入变量的最大值和出变量最小比例原则OR158标准型的单纯型算法确定入变量的最大值和出变量设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行迭代过程主行

i*行与主列

j*相交的元素ai*j*称为主元，迭代以主元为中心进行迭代的实质是线性变换，即要将主元

ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行OR159标准型的单纯型算法迭代过程(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素

aij(包括bi)四角算法公式：OR160标准型的单纯型算法5、迭代过程(4)变换CB，XB(5)计算目标函数、机会成本zj

和检验数

cj

zj

6、返回步骤2OR161例二、单纯型表的迭代过程OR162单纯型表中元素的几点说明任何时候，基变量对应的列都构成一个单位矩阵当前表中的b列表示当前基变量的解值，通过变换B

1b得到(资源已变成产品)当前非基变量对应的向量可通过变换B

1AN

得到，表示第j个变量对第i行对应的基变量的消耗率非基变量的机会成本由给出注意基变量所对应的行OR163单纯型法举例之三：OR164单纯型表如下：CBXBbˊ21-35000

X1X2X3X4X5X6X7

0X56124-11000X61223-110100X74101[1]001-z021-350000X51022501010X681[3]-2001-15X441011001-z-20-31-8000-50X514/34/3019/301-2/35/31X28/31/31-2/3001/3-1/35X441011001-z-68/3-10/30-22/300-1/3-14/3OR165用单纯型法求解线性规划问题例一：

Maxz=3x1+2x2Maxz=3x1+2x2

OR166CBXBbˊ3200

X1X2X3X40X33[2]-3101.50X45-1101--Z=032003X11.51-3/21/200X46.50-1/21/21z=4.5013/2-3/20OR167∵a21ˊ与a22ˊ都小于0，

∴原问题没有最优解OR168用单纯型法求解线性规划问题例二：OR169CBXBbˊ1-21000

X1X2X3X4X5X6

0X412111100120X56[2]1-101030X69-130001-z=01-210000X4901/2[3/2]1-1/2061X1311/2-1/201/20-0X61207/2-1/201/21-z=30-5/23/20-1/201X3601/312/3-1/301X1612/301/31/300X615011/301/31/31z=120-30-100OR170X5为非基变量，其检验数为0，

∴可能存在无穷多最优解

做进一步迭代，令X5为进基,得另一最优解为：解得无穷多最优解在端点为的线段上，最优解为：OR1712.3单纯形法的进一步讨论一般线性规划问题的处理对于一般线性规划标准形式问题：考虑一般问题：bi≥0，i=1,…,mMaxz=c1x1+c2x2+…+cn

xn

s.t.a11x1+a12x2+…+a1n

xn

=b1a21x1+a22x2+…+a2n

xn

=b2…………am1x1+am2x2+…+amn

xn

=bmx1，x2，…，xn≥0

主要是讨论初始基本可行解不明显时，常用的方法。OR172引入人工变量xn+i

≥0i=1,…,m;得到，s.t.a11x1+a12x2+…+a1n

xn+xn+1=b1

a21x1+a22x2+…+a2n

xn

+xn+2=b2…………

am1x1+am2x2+…+amn

xn

+xn+m

=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0

显然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解，对应的基是单位矩阵。OR173大M法：引入人工变量xn+i

≥0i=1,…,m;充分大正数M。得到，

Maxz=c1x1+c2x2+…+cn

xn

-Mxn+1-…-Mxn+m

s.t.a11x1+a12x2+…+a1n

xn+xn+1=b1

a21x1+a22x2+…+a2n

xn

+xn+2=b2…………

am1x1+am2x2+…+amn

xn

+xn+m

=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0显然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解，对应的基是单位矩阵。结论：若得到的最优解满足

xn+i=0

i=1,…,m则是原问题的最优解；否则，原问题无可行解。OR174两阶段法：引入人工变量xn+i

≥0，i=1,…,m；构造，

Maxz=-xn+1-xn+2-…-xn+m

s.t.a11x1+a12x2+…+a1n

xn+xn+1=b1

a21x1+a22x2+…+a2n

xn

+xn+2=b2…………

am1x1+am2x2+…+amn

xn

+xn+m

=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0第一阶段求解上述问题：显然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解，对应的基是单位矩阵。结论：若得到的最优解满足

xn+i=0

i=1,…,m则是原问题的基本可行解；否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。OR175例：（LP）Maxz=5x1+2x2+3x3-x4

s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0大M法问题（LP-M）

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0OR176OR177得到最优解：(25/3，10/3，0，11)T

最优目标值：112/3OR178两阶段法：第一阶段问题（LP-1）

Maxz=-x5-x6

s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0OR179第一阶段（LP-1）

OR180得到原问题的基本可行解：(0，15/7，25/7，52/7)TOR181第二阶段把基本可行解填入表中

OR182得到原问题的最优解：(25/3，10/3，0，11)T最优目标值：112/3OR183例2：（一）大M法的求解过程

OR184划为标准型及加入人工变量后OR185OR186答：最优解为x1=2,x2=2,x3=0。OR187（二）二阶段法的求解过程第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解若第一阶段结束时，人工变量仍在基变量中，则原问题无解OR188用二阶段法求解例2的第一阶段OR189用二阶段法求解例2的第二阶段OR190LP应用举例之一例1合理下料问题料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。OR191方案如下：方案

12345678

料型

2.9米120101002.1米002211301.5米 31203104

合计7.47.37.27.16.66.56.36.0

残料 00.10.20.30.80.91.11.4OR192应用举例之二

例2混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。OR193应用举例之三例3滚动投资问题兹有100万元闲钱，投资方向有四：

第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项目，使第五年末资本总额为最大？OR194应用举例之四例4动态生产计划问题工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求OR195第三章对偶问题与灵敏度分析要求：了解LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析

OR1963.1对偶问题3.1.1对偶问题的提出回顾例题1：现在计划不生产A、B两产品，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料9434510360200300单位利润

70

120OR197对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：

9y1+4y2+3y3≥704y1+5y2+10y3

≥120

目标：ω=360y1+200y2+300y3

出租收入越多越好？至少不低于某数OR198原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3

≥70

4X1+5X2

≤2004y1+5y2+10y3

≥1203X1+10X2

≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0OR1993.1.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0OR1100比较两形式知：OR1101对偶规则原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反OR1102标准型的对偶变换目标OR1103非标准型的对偶变换OR1104对偶规则.原问题对偶问题目标函数max

min目标函数约束条件

≤

≥

=≥变量≤无约束

≥变量符号≤

无约束≥

≤

约束条件=OR1105对偶变换的规则OR1106约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的OR1107对偶规则简捷记法原问题标准则对偶问题标准原问题不标准则对偶问题不标准例题2maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3

≤32x1+x2-4x3+x4+3x5

≥7y1+3y3≤2x1+2x3-x4≤

4-4y1+2y2

≤-6-x1+3x2-x4+x5=-2y1-y2-y3

≥

0x1，x2，x3

≥0;3y1+y3=1x4≤

0;x5无限制y1

≥0y2≤0y3

无约束

OR1108写出下列问题的对偶规划例1:OR1109例2：OR1110例3：OR1111答案:OR1112例4：OR1113变形为：OR1114对偶规划为：OR1115

3.2

线性规划的对偶定理1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值

为了便于讨论，下面不妨总是假设OR1116

弱对偶定理推论max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况OR11172最优解判别定理定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0b

CX,Y0b=CX0

Yb

。证毕。3主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。

OR1118

主对偶定理的证明

证：现证明定理的后一句话。

设X0为原问题的最优解，它所对应的基矩阵是B，X0=B

1b，则其检验数满足

C

CBB

1A0

令Y0=

CBB

1，则有Y0AC。

显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，

w(Y0)=Y0b=CBB

1b

而原问题最优解的目标函数值为

z(X0)=CX0=CBB

1b故由最优解判别定理可知Y0为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格OR11194互补松弛定理定理设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0+

V0X0=0证：由定理所设，可知有

AX0+U0=bX0,U00(1)Y0A

V0

=CY0,V00(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得

Y0U0+V0X0=Y0b

CX0若Y0U0+V0X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。OR11205原问题检验数与对偶问题的解在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量

(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量

(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。OR11213.3线性规划问题的进一步研究1.对偶单纯形法对偶单纯形法在什么情况下使用：

应用前提：

有一个基，其对应的基本解满足①单纯形表的检验数行全部非正（对偶可

行）；②变量取值可有负数（非可行解）。**注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。OR1122对偶单纯形法求解线性规划问题过程：

1、建立初始对偶单纯形表，对应一个基本解，所有检验数均非正，转2；2、若b’≥0，则得到最优解，停止；否则，若有bk

<0则选k行的基变量为出基变量，转3；3、若所有akj’≥0(j=1,2,…,n)，则原问题无可行解，停止；否则，若有akj’

<0则选

=min{j’/akj’

┃

akj’

<0}=r’/akr’那么r为进基变量，转4；4、以akr’为主元，作四角运算。OR1123例：求解线性规划问题：

Minf=2x1+3x2+4x3

S.t.

x1+2x2+x3≥32x1-x2+x3≥4

x1,x2,x3≥0

标准化：

MaxZ=-2x1-3x2-4x3

S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0OR1124表格对偶单纯形法

OR1125用对偶单纯形法求解下列问题

例1：

Min

OR1126

变形得：

MaxOR1127CB

xBb′-5-2-400

X1x2x3x4x50x4-4-3-1-2100x5-10-6[-3]-501-5-2-4000x4-2/3[-1]0-1/31-1/3-2x210/3215/30-1/3-10-2/30-2/3-5x12/3101/3-11/3-2x220112-100-1/3-1-1/3OR1128所以，最优值为，即。最优解为