数学建模基础知识 线性规划单纯形方法

MaxS=CXs.t.AX=bX0基，基解，基可行解，可行基。⊙线性规划问题的可行域D是凸集。⊙顶点与基可行解相对应⊙线性规划问题的最优解，必定在D的顶点上达到。⊙目标函数在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）。第三节线性规划-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。第三节线性规划-单纯形方法单纯形方法基本思路：1.从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。2.如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进3.继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。初始解。一、消去法例1-18：一个企业需要同一两种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型maxS=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0解：引进松弛变量x3,x4,x5>=0数学模型标准形式：maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,

x3,x4,x5≥0约束条件的增广矩阵为：121008（Ab)=40010160400112显然r(A)=r(Ab)=3<5,该问题有无穷多组解。令A=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5)

A=（P1，P2，P3，P4，P5）

=12

100

40

010

04

001

X=（x1,x2,

x3,x4,x5)T

B=(P3，P4，P5）=100010001x3,x4,x5是基变量，x1,x2,是非基变量。

用非基变量表示的方程：x3=8-x1-2x2x4=16-4x1(I)x5=12-4x2S=0+2x1+3x2

令非基变量（x1,

x2）T=（0，0）T

得基础可行解：x(1)=(0,0,8,16,12)TS1=0经济含义：不生产产品甲乙，利润为零。二、已知初始可行基求最优解线性规划标准型的矩阵形式(3)：MAX

S=CX(1-17)

s.t.

AX=b(1-18)X>=0(1-19)

a11a12….a1nb1A=a21a22….a2nb

=

b2…………am1am2….amnbnc1x10c2x20Ct=X=0=……………..cnxn0并且r(A)=m<n.1.最优解判别定理：不妨假设A=（B,N）（B为一个基）相应地有XT=(XB,XN)

C=(CB,CN)由（1-17）（1-18）Z=

(CB,CN)(XB,XN)T=CBXB+CNXNAX=（B,N）(XB,XN)T=B

XB+N

XN=b因为B为一个基,|B|≠0有XB=B-1b-B-1NXNZ=CBXB+CNXN=

CBB-1b+(CN-

CBB-1N)XN令非基变量XN=0则X

=(XB,XN)T=（B-1b,0）T为基础解，其目标函数值为S=

CBB-1b只要XB=B-1b>=0,X=（B-1b,0)T>=0X为基础可行解,B就是可行基。另外，若满足CN-

CBB-1N≤0或CBB-1N-CN

≥0则对任意的x>=0有S=CX≤CBB-1b即对应可行基B的可行解x为最优解。定理（最优解判别准则）对于可行基B,若C-CBB-1A≤0则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。σ=C-CBB-1A为检验数。基变量的检验数：CB-CBB-1B

=0C-CBB-1A=（0，CN-CBB-1N）换入基变量中，得到基可行解定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况）证明：某个非基变量为最优解。故线性规划问题有无穷多最优解。为一基可行解，有一个变量Xm+k对应因为可行解。定理：若存在检验数大于零，但所对应的换入变量Xm+k的系数向量Pm+k≤0,则原问题无最优解。（无界解的情况）证明：构造一个新的解，分量为定理：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。定理：若某一个非基变量的检验数大于0，其系数列向量Pm+k≤0,则原问题无最优解。（无界解的情况）线性规划为求最大化的标准型：线性规划为求最小化的标准型时，相应的结果？单纯形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N注意：A=（B，N）检验数σ=C-CBB-1A=（0，CN-CBB-1N）非基变量检验数σ=CN-CBB-1N时,达到最优。单纯形表格：

单纯形解题步骤：（已知初始可行基）求最大化时一、作对应B的单纯形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N单纯形解题步骤：二、判别若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk≤0,则原问题无最优解，终止。若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。三、换基迭代确定换入变量Xk，其中max(σj>0)=σk,xk为换入变量j=1,2,…,m确定换出基变量Xr,根据最小比值原则min(bi/aik,aik

>0,1≤i≤m)=bl/blkalk为主元素,Xl为换出基变量。对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。例1-19求线性规划问题：

maxS=2x1+3x2s.t.x1+2x2<=84x1<=164x2<=12x1,x2>=0解：对目标函数标准化maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,

x3,x4,x5>=0

12100A=4001004001（x1x2x3x4x5）=（NB）解：

100B=010=Ib=(8,16,12)T001x3

x4,x5为基变量，CB=（0，0,0）x1,x2为非基变量。有B-1=I,B-1b=b,B-1A=A,单纯性表如下：初始单纯性表TAB(1)为：x2换入,x5换出；得TAB(2)为：x1换入,x3换出；得TAB(3)为：x5换入,x4换出；得TAB(4)为：此时所有的检验数小于等于零，此时的基础可行解X=（4，2，0，0,4）T就是最优解，对应的目标函数值：S=14就是最优值，对应的B4就是最优基。

求最大化LP问题单纯形表解题步骤：一.LP问题化成标准型,列初始单纯形表二.判别1.若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。2.若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk≤0,则原问题无最优解，终止。3.若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。三.换基迭代1.确定换入变量Xk，其中max(σj>0)=σk,xk为换入变量j=1,2,…,m2.确定换出基变量Xr,根据最小比值原则min(bi/aik,aik>0,1≤i≤m)=bl/blkalk为主元素,Xl为换出基变量。对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。定理（求最小化的最优解判别准则）（1）若σ=C-CBB-1A≥0，则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。（2）若检验数全大于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况）（3）若存在检验数小于零，但所对应的换入变量Xm+k的系数向量Pm+k≤0,则原问题无最优解。（无界解的情况）确定换入变量时，找小于0中的最小者。M法

当原问题求最大化时，假定人工变量在目标函数中的系数为（-M）（M为任意大正数），目标函数求最大化，必须把人工变量从基变量换出，否则，不可能实现最大化。

当原问题求最小化时，假定人工变量在目标函数中的系数为M（M为任意大正数），目标函数求最小化，必须把人工变量从基变量换出，否则，不可能实现最小化。例8线性规划问题

-3 1 100MMcj→cj→-3 1 100MM

线性规划问题达到最优,最优解及最优值为:

二.两阶段法

当用计算机求解含人工变量的线性规划问题时，只能用很大的数代替M，否则，会造成计算机的错误。而两阶段法避免了这一错误。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，构造目标函数为人工变量的和，约束是原问题的约束。

用单纯形法求解上述模型，若目标函数值为0，说明原问题有基可行解，进行第二阶段计算，否则，原问题无可行解。第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始表。例9线性规划问题

解：加入人工变量，给出第一阶段的线性规划模型:人工变量已经换出，则ω=0，得到基可行解，将第一阶段的人工变量取消，填入原问题的目标函数的系数，进行第二阶段运算。

cj→

0 0 00011人工变量已经换出，则ω=0，得到基可行解，将第一阶段的人工变量取消，即上表中划去人工变量所在列，填入原问题的目标函数的系数，进行第二阶段运算。

cj→ -3 1 100最优解为：x1,=4,x2,=1,x3=9,最优值z=-2.

应用举例例1配料问题某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价见下表。该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg)A原材料C不少于50﹪，原材料P不超过25﹪50B原材料C不少于25﹪，原材料P不超过50﹪35D不限25原材料名称每天最多供应量（kg)单价（元/kg)CPH10010060652535解：设xij为产品A、B、D中含C、P、H的公斤数。列表如下：原材料

产品

CPHAx11x12x13Bx21x22x23Dx31x32x33解：数学模型为：产品名称规格要求单价（元/kg)A原材料C不少于50﹪，原材料P不超过25﹪50B原材料C不少于25﹪，原材料P不超过50﹪35D不限25原材料产品CPHAx11x12x13Bx21x22x23Dx31x32x33例2连续投资问题某部门有100万元，在今后五年内考虑给下列项目进行投资项目A:从第一年到第四年每年年初需要投资，并于次年末回收本利104％；项目B:从第三年初投资，到第五年末回收本利105％；但规定最大投资额不超过40万元；项目C:从第二年初投资，到第五年末回收本利108％；但规定最大投资额不超过30万元；项目D:五年内每年可购买国债，于当年末归还，并加息3％；问该部门如何确定每年的投资计划，使五年末拥有的本金最大？解：设xiA,xiB,xiC,xiD,分别表示第i年年初给项目A、B、C、D的投资额。列表如下：

年份项目

12345

ABCD

x1Ax2Ax3Ax4A

x3B

x2Cx1Dx2Dx3Dx4Dx5D数学模型为：人力资源分配的问题

解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：MinZ=x1+x2+x3+x4+x5+x6

s.t.x1+x6

≥60

x1+x2

≥70

x2+x3

≥60

x3+x4

≥50

x4+x5

≥20

x5+x6

≥30

x1,x2,x3,x4,x5,x6

≥0

班次：1，2，3，4，5，6

x6+x1,x1+x2,x2+x3,x3+x4,x4+x5,x5+x6例求线性