线性规划模型

1第1节线性规划问题与模型

一、线性规划模型

从招聘总经理谈起

2泰山工厂生产状况泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600产品A产品B资源限量设备劳动力原材料9434510360200300利润元/kg701203招聘总经理！约翰：我应聘！

在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=276<3604*20+5*24=2003*20+10*24=3004怎么达到的？约翰使用了运筹学中的线性规划模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2≤360

人力约束4X1+5X2

≤200

原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥05线性规划图解法由数学知识可知：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

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

x29x1+4x2

≤3604x1+5x2

≤2003x1+10x2

≤300ABCDEFGHIZ=70x1+120x27最优解：X1=20

,

x2=24对应的生产方案：生产A产品20

生产B产品24获利：70*20+120*24=42808约翰就任泰山工厂总经理！9二、线性规划图解法例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2

约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥010例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

最优目标值z=27500图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：11线性规划图解法（续）(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=012线性规划图解法（续）（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040013线性规划图解法（续）（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-114线性规划图解法（续）（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE15线性规划图解法（续）重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。16线性规划图解法（续）

例2

某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？17线性规划图解法（续）解：目标函数：Minf=2x1+3x2

约束条件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q18三、线性规划一般形式企业管理的重点内容之一就是在各种生产因素和产品的调配问题上。一方面，在一固定阶段，企业管理者所能“投入”的生产因素：原料、人力、设备时间是由一定限量的。在一固定期间，任何一工厂的厂房、工场、机器、一切固定资本是不会变动的，再雄厚的资本，也还是有它的限度。再从流动资本来看，原料的来源和存量，各种技工的人数和时间，在一相当的短期中也是有一定的限度。19线性规划一般形式另一方面，企业管理者“投入”生产因素时，一定有一完整的目标。在商言商，企业管理者的目标当然是求最高的利润和最低的成本。如何将受时间、空间、数量限制的“投入”生产因素调配“得当”，达到最佳的境界而获得最佳的“产出”量，因而获得最大的收益。以上就是企业管理者须面对的一个问题的两个方面。企业管理者不仅要知道如何调配手头上有限的生产因素，同时要从不同的调配中，找出最佳的调配，来达到他的企业经营目标——最低成本、最高利润。20线性规划一般形式事实上，用最低的代价去追求最高的收获，原是一种理性的要求，因此在任何理性活动中，都有一求“最佳”问题的存在。21例题3——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求7003020022例题3建模设抓取饲料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≥023例题4：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

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

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

≥0,j=1,2,…625归纳：线性规划的一般模式目标函数：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≥0

26四、线性规划的标准型一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥027线性规划的标准型

可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:28线性规划的标准型1.极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即

Minf

＝-Maxz29线性规划的标准型2、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi30线性规划的标准型

当约束条件为

ai1x1+ai2x2+

…

+ainxn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi31线性规划的标准型

为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

3.右端项有负值的问题：

在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。32线性规划的标准型例：将以下线性规划问题转化为标准形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3

其次考虑约束，有2个不等式约束，引进松弛变量x4，x5

≥0。第三个约束条件的右端值为负，在等式两边同时乘-1。33线性规划的标准型通过以上变换，可以得到以下标准形式的线性规划问题：

Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***变量无符号限制的问题***：

在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。34五、计算机求解算法单纯形算法基本思想：从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。35求解线型规划的算法

单纯形算法且听下回分解3637第三章运筹学优化模型大连海事大学刘巍38第2节线性规划求解

单纯性算法

求解线性规划的最常用算法！

39单纯形算法

基本思想：从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。40

单纯形法

引例maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X5041解：(1)、确定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=

X2=0X(1)=(0,0,30,60,24)TZ(1)=042(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解43(3)、由一个基可行解→另一个基可行解。∵50>40选X2从0↗，X1=0X3=30-2X20X230/2

X4=60-2X20X260/2

X5=24-2X20X224/2

X2=min(30/2,60/2,24/2)=12X2进基变量，

X5出基变量。44B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1

②2X2=24-X5③45③×1/2

，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=

36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=60046(2)'

判断∵40>0∴X(2)不是。(3)'

选X1从0↗，X5=0X3=6-X10

X4=

36-3X10

X2=120

X1=min(6/1,36/3,1)=6X1进基，

X3出基。47B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=

18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=84048(2)"∵15>0∴X(3)不是(3)"

选X5从0↗，X3=0X1=6+X50

X4=

18-2X50

X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5进基，

X4出基。49B4=(P1P5P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=

9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975500(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)51maxZ=CX当LP的数学模型为矩阵型AX=b时，

X0两个重要公式：XB=B-1b-B-1NXNZ=CBB-1b+(CN-CBB-1N)XN当XN=0时，B-1b0X=Z=CBB-1b52当LP的数学模型为一般型时两个重要公式形如：5310…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amn设A=B=(P1P2…Pm)=I54当Xj=0(j=m+1,…,n)时,551.5.2

单纯形法原理56此时，B=(P1P2…Pm)对应的基本可行解为(1)(1)57定理1：对解X(1)

，若检验数j(j=m+1,…,n)全部

0，则X(1)为最优解。定理2：对X(1)，若有某个非基变量Xm+k→m+k>0且相应的Pm+k=(a1m+k,…,amm+k)T

0，则原问题无有限最优解。58定理2证明Xi=bi-aijxjJ=m+1n令非基变量Xm+k=(﹥0)X(2)

=(b1-a1m+k,…,bm-amm+k,0,…,,…,0)TAX(2)

=bX(2)0Z=Z0+m+k

当时

Z59例：Z=30X1+20X2-X1+3X2+X3=10-3X1+2X2+X4=15初始基B1=(P3P4)X(1)=(0,0,10,15)TZ(1)=0Z=0＋30X1+20X2X3=10-(-X1+3X2)X4=15-(-3X1+2X2)60选中X1从0↗，X2=0X3=10-(-X1)0

X4=15-(-3X1)0

求X1，X1→+,Z→+61换基迭代公式：(1)、决定换入变量：maxj=m+k，则Xm+k为换入变量j>0(2)、决定换出变量：bi-aim+kXm+k0

(i=1,2,…,m)Xm+kbiaim+k(aim+k>0)62θ=minaim+k>0=biaim+kbrarm+k则Xr为换出变量。63定理3：经单纯形法得到的X(2)

=(b1-a1m+k,…,bm-

amm+k,0,…,,…,0)T是基本可行解，且Z(2)﹥

Z(1)

64证明：设Xr=Xm,

Xm=0,Xm+k==bmAmm+k(﹥0)X(1)中P1,…

Pm线性无关，下证P1,…

Pm-1,Pm+k线性无关。若否，因为P1,…

Pm线性无关则Pm+k=a1m+kP1+…+amm+kPm①而Pm+k=l1P1+…+lm-1Pm-1②65

①-②(a1m+k-

l1)P1+…+(am-1m+k-

lm-1)Pm-1+amm+kPm=0P1,…,Pm线性相关，矛盾。X(2)是基本解，且是可行解

66单纯形法基本步骤(1)、定初始基，初始基本可行解(3)、若有k>0，Pk全

0，停，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全

0。

若是，停，得到最优解；若否，转(3)。67θ=minaim+k>0=biaim+kbrarm+k定Xr为换出变量，arm+k为主元。由最小θ比值法求：maxj=m+k→Xm+k换入变量j>0(4)、68转(2)m+k0

…………a1m+k0arm+k1amm+k0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代69证明可用归纳法（略）X(1)X(2)X(3)X’XX在边界上X在内部X＝X’

+(1-)X(2)

(0

1)X’＝X(1)

+(1-)X(3)

X(1)(1-)X(2)(1-)X(3)X=++(0

1)70证明：设X(1),…,X(k)

为可行域顶点，若X*不是顶点，但

maxZ=CX*

X*=定理2：可行域有界，最优值必可在顶点得到µ

iX(i)ki=1µ

i=1ki=10µi1CX*=µ

iC

X(i)ki=1µ

iCX(m)ki=1=CX(m)[设CX(m)＝Max(C

X(i))]1ik71Z(1)

=Cibii=1mZ(2)

=Ci(bi-aim+k)+Cm+ki=1m

=Cibi-+Cm+ki=1mCiaim+ki=1m

=Cibi+[Cm+k-Ciaim+k]i=1m

i=1mZ(2)-

Z(1)=(Cm+k-Zm+k)=

m+k﹥0

721.5.3

单纯形表

C1C2…

CmCm+1…

Cm+k…CnX1X2…XmXm+1…

Xm+k…XnCBXBZ000

…0m+1…m+k…

nC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………734050000X1X2X3X4X5CBXB04050000θ0X33012100150X460

3

2010300X5240(2)00112XB60040000-250X36(1)010-160X4363001-11250X21201001/284000-4001540X161010-10X41800-31250X21201001/274XB97500-35/2-15/2040X11510-1/21/200X5900-3/21/2150X215/2013/4-1/40本问题的最优解X=(15,15/2,0,0,9)T

Z=97575几点说明：(1)、例maxZ=X1+2X2X1

4X2

3X1+2X2

8

X1,X20

X1+X3=

4X2+X4=

3X1+2X2+X5=

8

X1…X507612000X1X2X3X4X5CBXB0120000X34101000X430(1)0100X5812001CBXB6100-200X34101002X23010100X52

(1)00-21(接下表)7712000X1X2X3X4X5

CBXB80000-10X32001(2)-12X23010101X12100-21CBXB80000-10X41001/21-1/22X2201-1/201/21X14

1010078X(1)=(2,3)Z(1)=8X(2)=(4,2)Z(2)=8无穷多解全部解：X=α+(1-α)

(0α1)243279(2)、例：求minZ=X1-X2+X3-3X5X2+X3-X4+2X5=6X1+2X2-2X4=52X2+X4+3X5+X6=8X1…X60801-110-30X1X2X3X4X5X6CBXB110-403-501X36011-1201X15120-2000X68020131CBXB-7/30-2/3014/305/31X32/30-1/31-5/30-2/31X15120-200-3X58/3

02/301/311/3CBXB-41/300405/31X33/21/601-20-2/3-1X25/21/210-100-1X51-2/300111/381判定定理1：基本可行解X，当全部j0时，X为最优解。判定定理2：对可行基B，当某k<0，且Pk=(a1k…amk)T

0，则原问题无有限最优解。

换入变量：maxj=j

=m+k→Xm+kj<082(3)、maxZ=10X1+

12X23X1+4X264X1+X223X1+2X23X1,X20831012000X1X2X3X4X5

XB01012000θi

X363(4)1003/2

X42410102/1

X53320013/2

XB1810-300θi

X23/23/411/4002

X41/213/40-1/4102/13

X50

(3/2)0-1/2010

XB1800-8/30-2/3

X23/2011/20-1/2

X41/2005/61-13/6

X1010-1/302/384退化解X*=(0,3/2,0,1/2,0)TZmax=1885例：maxZ=-3/4X4+20X5-1/2X6+6X7

X1+1/4X4-8X5-X6+9X7=0X2+1/2X4-12X5-1/2X6+3X7=0

X3+X6=1X1…X70(P1P2P3)(P4P2P3)(P4P5P3)(P6P5P3)(P6P7P3)(P1P7P3)(P1P2P3)86(4)例：maxZ=4X1+X2-X1+X2

2X1-4X2

4X1-2X2

8X1,X2087

41000

X1X2X3X4X5CBXB

0410000

X32-111000

X44(1)-40100X581-200188160170-400X360-31104X141-40100X540(2)0-11500009/2-17/20

X312001-1/23/24

X112100-121

X22010-1/21/289本问题无界。X1X2OZ=0901.5.4初始基本可行解的求法(一)、大M法：判定无解条件：当进行到最优表时，仍有人工变量在基中，且≠0，则说明原问题无可行解。91例1：maxZ=6X1+4X22X1+3X2

1004X1+2X2

120X1=14X2

22X1X2

092maxZ=6X1+4X22X1+3X2+X3=1004X1+2X2+X4=120X1=14X2-X5=

22X1…X5

093maxZ=6X1+4X2-MX6-MX72X1+3X2+X3=1004X1+2X2+X4=120X1+X6=14X2-X5+X7=

22X1…X7

09464000-M-MX1X2X3X4X5X6X7CBXB-36M

M+6M+400-M000X310023100000X4120

4

201000-MX614(1)000010-MX7220100-101CBXB84-22M0M+400-M6-M00X37203100-200X4640

2010-406X1141000010-MX7220(1)00-10195CBXB172

0

0004

6-M4-M0X360010(3)-2-30X420

0

0012-4-26X11410000104X2220100-101CBXB180

00-4/300-M-10/3-M0X52001/301-2/3-10X4160

0-2/310-8/306X11410000104X224011/300-2/3-296(二)、两阶段法：原问题maxZ=Cjxjj=1nxj0j=1naijxj=bi(i=1,2,…,m)97作辅助问题minW=yii=1mXj，yi0j=1naijxj+yi

=bi(i=1,2,…,m)解题过程：第1阶段：解辅助问题当进行到最优表时，①、若W=0,则得到原问题的一个基本可行解，转入第2阶段。②、若W>0,则判定原问题无可行解。98两阶段法原理：(1)、辅助问题的基本可行解X(0)

为最优解，对应最小值=0

则X(0)

的前n个分量是原问题的基本可行解。99

设X(0)=(X1(0)…Xn(0),

y1(0)…yn(0))T

使aijxj(0)+yi(0)≡

bi(i=1,2,…,n)nj=1∵=0,∴y1(0)=…=

yn(0)=0

aijxj(0)≡

bi(i=1,…,m)∴nj=1证明：100(2)、原问题有可行解时，辅助问题最优值=0

。证明：若原问题有可行解X(0)=(X1(0),

…,Xn(0)