运筹学2.线性与单纯形方法

1第2章2.32.42.62产品产品12原材料40原材料0423解：设I、II两种产品的产量分别为x1x2。建立该问题的MaxZ=x1+2x2≤ ≤ 4x2≤x1,x2≥3生产一件产品II可获利100元，问工厂应如何安排生产才产品12原料40原料0423-产品I产品II12原料40原料0423-解：设I、II两种产品的产量分别为x1x2学模型为

MaxZ=2x1+设备x1+2x2

原料原料

4x2x1,x2≥例2 热量蛋白质钙价格(元12542-6热量蛋白质钙价格(元1283542-解：设xj为第j种食物每

MinZ= x3+170x4≥蛋白质203x1133x274x3+15x4

钙60x+56x+130x+ ≥ x1,x2,x3,x4≥7 热量蛋白质钙价格(元1633428例热量蛋白质钙价格(元1263342解：设xj为第j种食品每

MinZ=1000x1+800x2+900x3+200x4≥50x1+60x2+20x3+10x4≥400x1+200x2+300x3+500x4≥x1,x2,x3,x4≥9MaxZ

x1+2x2≤ ≤

4x2≤x1x1,x2≥MinZ=1000x1+800x2+900x3+200x4≥50x1+60x2+20x3+10x4≥400x1+200x2+300x3+500x4≥x1,x2,x3,x4≥每一个问题变量都用一组决策变量（x1,x2,…,xn）a11x1+a12x2+…+a1nxn≤(=,≥)a21x1+a22x2+…+a2nxn≤(=,≥)s.t. am1x1+am2x2+…+amnxn≤(=,≥)xj≥0,j=1,2,bi－右端项；aij－技术系数线性不等式的几何意义—半平面例x12x2

3 3

Q(4,2，表明最优生产计划为：0

987654321FEAB3987654321FEAB3C21O1234D 7H82x s.t.

x1x2 x2 x1,x2最优解x1x2Z0

凸集：设K为 一点集，任取两点X（1）X（2）若X（1）（1）X（2）K，[0，1]，则K为一凸集。2SX（0）S，若不存在两点X（1）X（2）SmaxmaxZc1x1c2x2cnxns.t.aa11x1a12x2a1nxna 22 xxn2 m xmnxnmxj0,j1,2,nbi0,i1,2,mn:变量个数 m:约束行数cj:价值系数 bi:右端项;aij:技术系 矩阵式:Maxs.t.

其中：Cc1c2b=(b1,b2,...,X=(x1,x2,...,nMaxZ

n

s.t.∑

xj≥0,j=1,2,...

=(P1 P2,...,Pn令ZZ，MinZCXMaxZ将不等式约束条件化为等式约束条aijxjbiaijxaijxjbiaijx

xn1bixn10为松弛变量xn2bixn20为剩余变量若xj0，令xjxj若xj ，令xjxjxj;(xj0,xj0)若axjb令xjxja,xjba,xjxn3ba.(xj0)若bi0aijxjbi0,则aijxjbiMaxZ2x13x12x24 s.t.

4x2MaxZ2x13x20x30x40

x12x24x4x 2 4x2

例5例5例6x1x2x3 x MaxZ’=x1+2x’2+3x4- 3x

3x

x1-x’2+x4- =

x+x’+x- -x=x0x0x

-3x1-x’2+3x4- =x’2≥0,xj≥0,令x3x4x5其中x40,x5令x2x2，x2在第一个约束不等式号的左端加入松弛变量x6在第二个约束不等式号的左端减去剩余变量x7在第三个约束条件号两端同乘以1,以满足非负约束条件；令ZZ，把求MinZ改为求MaxZ;即可得到该问题的MaxZx12x24x1x23x3s.t.3x1x24x3 x, 0,2 x3x32则有0x34x40满足x3MaxZx12x24x38;即MaxZx12x24

x42x1x23 143 4 17s.t.

x

0,j1,2,4;x3 MaxZCTX(1)s.t.AXb(2 X0(3)c1

x1

a11 a12

a1nCc2Xx2Aa21

a22

a2n,(mn,r(A)m)

cn xn am1am2amn可行解（2）（3）最优解满足）的可行解，为LP问题的最优解；设Amn为LP问题的系数矩阵，rA)mBmm为A的非奇异矩阵（B0）B为LP问题的一个基。MaxZx1xx 2x2x s.t.3x 5x 10 x 0,j1,2,3x 12A1210, 12,12

11 ,

3010

21

20, 10B33

,

, 5 01 B1B6LP

a12a1m令B=

=(P1,P2,…,Pm 且|B|0，则称Pjj=1,2,…,m为基向量。与基向量Pj对应的变量xj称为基变量，记为XBx1x2xm)T，其余的变量称为非基变量，记为XNxm+1xm+2xm+n)T。21如在上例中，B4 50则对应的x2、x3为一组基变量，x1、x4为非基变量。令非基变量XN 2x1,x2

G FC

x4,x4,x3=-x3,x3,x2,x2,x4=-x1,x1,x5=-x1,例例 MaxZx12x2x+2x12≤4x2≤ 14x50 Z=2x x1, x2,987654321FEABC32K1OD H 解HGK凸集：设S为 一点集,X(1)、X(2)对于[0，1],有XX(1(1X(2S则称SS为一凸集X（0）S若不存在X(1)X(2)S,对于(0，1使X（0）X(1(1X(2)成立则称X(0)为S的一顶点 中的k个点k若存在,,,,使得X （1）X（2）X（k）,(0 1, k X

i则称X为X（1）X（2）,X(k)的一个凸组合。定理定理1LP问题的可行域为一凸集证明：记SX|AXb，X任取X（1）X（2）S则AX（1）b，X（1）0；AX（2）b，X（2）对于[0，1],作XX(1)(1X(2)则AXA[X(1)(1X(2b(1)b显然X0,则XS则S为一凸集。(凸集的交集一定是凸集，而凸集的并集不一定是凸集线性规划问题的可行解线性规划问题的可行解X=(x1x2xn)T是基可行解先证充分性：不妨设Xx1x2,xk,0,,0),其中xi0(i1,2,kx1x2xk所对应的系数列向量为P1P2Pk由于向量P1P2Pk线性独立，必有kkm时，它们恰为一个基，Xx1x2,xk,0,,0)为相应基可行解km时，一定可以从其余列向量中取出(mk)个与P1P2,构成极大无关组，对应解恰为X所以由定义X为基可行解。再证必要性：由基可行解的定义可知定理2定理2证明：第I步先证“若X是基可行解,则X是LP问题的可行域顶点”。逆反命题为“若X不是可行域顶点则X不是基可行解设X不是顶点，X（x1x2,xk则存在不同的两个点、X（2）为LP问题的可行解使XX（1）（1）X（2）(0,1)成立。 , aixi所对应的系数列向量(i12k) （1a

（1a

（1a

(1)

(2) (1)(2),得:a(x（1）x（2）) (x（1）x（2）)0;又X（1） 所以a1,a2,,ak线性相关，则X不是基可行解 第II步：用反证法证X是可行域顶点，则X是基可行解设Xx1x2,xk,0,,0)是可行解但不是基可行解。其中xi0i1,2,k.则xi所对应的系数列向量ai线性相关。即存在一组不全为零的数i使1a12a2(30)1a12a2kak由于x是LP问题的可行解，则AX1 1 x2

(3)即（a1a2akak1an）xkbx1a10 0

x2a2xkak

(5) (x1(x1令X(1)（x,x,, X(2)（x,x,, 1X2

1X(2)2另外，当充分小时，可保证xii0(i1,2,,m即、X（2）是可行解。这证明X不是可行域的顶点。引理引理若S是有界凸集，则任何一点X∈S可表示为S的顶点的证明：设X(1X(2X(k)为LP问题可行域的顶点若X(0)也是可行解，且目标函数在X(0)处达到最优Z*因X(0)不是顶点，所以它可以表示成：

aX(i其中a0a因此

ai

i i kik在所有的顶点中必能找到某一个顶点（m，使之为所有的CX(i)中最大者。

(i

ai

(m

m)。所以CX

i i又CX(0)为最优值，所以只能CX(0)CX(m)，即目标函数在顶点X(m)达到最大值

1947年，G.B. 化LP问题为 例 x2+ 3x1+ x3= 1 1

x1+1/2x2+x3= 以x2

+

-

=-

(1)’-(2)’/3,(2)’

x1+0x2+5/3x3= x2-4/3x3=- Maxs.t.令A=(B,NX=XB,CT=(CT,C

X X N由

Z=CTX=(CT,C

TX+CTX=CT(B-1b-B-1NX)+C B XNB=Z0+∑(cj-CTB-B若cj-CBTB-1Pj=σj≤0,则Z≤Z0Z0即为最优解基变量的检验数必为

Step1.化LP问题 Step2.若所有检验数≤0否则,计算σk=max{σj|σj 0},选取σk所对应的j量xk为换入变量Step3.计算θ=min{ | >0}

,选取θ 的变量xl为换出变量Step4.以alk为主元素进行旋转运算,转StepMaxZ2x1x12x2 16 4x

23000b23000b 081210 04001 0000 023000初始基可行解：x1=0x2=0,x3=8x4=16,x5σk=max{σj|σj>0所对应的变量xkj23000b081210004001000001023000 检验数j的计算方法：σjcj-CBB 选取θ=min{ >0} 所对应的变量x为换出变量 23000b 081210 04001 0000 023000最小比值2300023000b 081210 04001 0000 02300023000b02010040010330100MaxZ2x13x2x12x214 1 4x2

x12x2

23000b 081210 04001 0000 023000

2300023000 b 20102 400104 30100-20002300023000b221010-08001433010000023000b2410000400132010000X*=(4,2)TMaxZ=14X1=(0,0)T,

4

X2=(0,3)T,X3=(2,3)T,

QX=(4,2)T,

4QO3QO

8D.GoldfarbandJ.K.Apracticablesteepest-edgesimplexalgorithm,J.J.ForrestandD.Steepest-edgesimplexalgorithmsforlinearAX

SSs.t.X

X, 2x2x34x 2x

2x x

x4;剩余变量 人工变量x6

s.t4x1x2

x MaxZCTXMV(M为，V为人工变量 MinZCTXMVi计算(单纯形法实现了最小化。因而换入变量xk的选取标准为kMin{j|j1100MMb0111000M312010M10100011-0M00030100-M101001111010001-00M01100MMb03001241101001-11010001-00014100110100119001000此时所有检验数j0,即认为达到了最优解结果得: 第I不考虑原问题是否存在可行解，给原LP问题加第II阶段：将第一阶段得到的最终表除去人工变量，将x12x2x34xx2x x

x6

2x2

x3

变量

4x

x

2x

x 0000011b011100013120101101000116-0100030100-1101001101010001-00010303001240101001-01010000-0000011由于人工变量x6x7=0,所以(011121100b030014110100-110100-0001410011010019001000, 1例：MaxZ31

20

1

6313

8 9x x12x x3xs.t

x,x,x, MaxZ3x20 1 6 0x50x601

8

1

9

s.t

x112x2

x33 x6xx 7 xj0;j000b0091000030100100100010000000b01400000401001001000100400 kmin{j|j0},则选取k所对应的变量为进基变量）当按规则计算存在两个和两个以上的最小比值时，选取下标最小的基变量为换出变量。而σk对应列向量Pk’≤0,则此LP问题有 2300b2300b060113410100 x2 2

x0;j 说明：ZZ0

CTB1a) 若存在kCkCB ak NX

bB

B1bB1NXN令Xk0其余Xj0Xj为非基变量 B1bB1a ZZ0k例：MaxZ3x14

2x23x4x X*=λX(1)*+(1-λ)X(2)*;

0340034000b04001460100341000000060014301038101000000例1某工厂要用三种原材料D、P、H混合调配出三种不同规格A原材料D不少于原材料P不超过B原材料D不少于C应量(元DPHB中D、P、H的含量为x21、x22、x23MaxZ50(x11x12x13)35(x21x22x2325(x31x32x33)65(x11x21x3125(x12x22x32)35(x13x23x3315x1125x1215x1330x2110x22040x310x32

x11x21x31

xx11x12x

x

x

x

x11x12

xij0;i,j例2设：i表示工厂的第i类设备(i1,2,,m)j表示工厂生产的第j种产品(j1,2