第一章线性规划及单纯形法第讲

第一章线性规划及单纯形法第讲第1页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法

线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。

1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。

60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。第2页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型e.g.1

资源的合理利用问题问：如何安排生产计划，使工厂获总利润最大？

表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润

15 25

某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第3页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

设x1，x2为下一个生产周期产品甲和乙的产量；

约束条件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目标函数：z=15x1+25x2表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润15 25

决策变量第4页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型e.g.2

营养问题

假定在市场上可买到B1,B2,…Bnn

种食品，第

i

种食品的单价是ci,另外有m

种营养A1,A2,…Am。设Bj内含有Ai

种营养数量为aij

(i=1~m,j=1~n)，又知人们每天对Ai

营养的最少需要量为bi。见表2：

表2

食品最少营养 B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amnbm

单价

c1c2…cn

试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第5页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法

表2

食品最少营养 B1B2…Bn需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amnbm

单价

c1c2…cn

解：

设xj

为购买食品Bj

的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）0≤xj≤lj第6页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n

个子系统处理。1、决策变量xj≥0

2、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第7页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法

max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn≤（或=，≥）bm

xj≥0（j=1,2,…,n）

其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数线性规划问题的一般形式：第8页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型线性规划问题的标准形式：

max

z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn

=

b2

……am1x1+am2x2+…+amnxn=

bm

xj≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m）

特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。第9页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。

因为求minz等价于求max(-z)，令z’=-z，即化为：

2、约束条件为不等式，xn+1≥0松弛变量如何处理？第10页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型

３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零

4、决策变量无非负约束

设xj

没有非负约束，若xj≤0，可令xj=-xj’

，则xj’≥0；

又若xj

为自由变量，即xj

可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0第11页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法e.g.3试将LP

问题minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化为标准形式。解：令x3=x4-x5

其中x4、x5

≥0；对第一个约束条件加上松弛变量x6

；对第二个约束条件减去松弛变量x7

；对第三个约束条件两边乘以“-1”；令z’=-z

把求minz

改为求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

第12页，共64页，2023年，2月20日，星期一§1线性规划问题及其数学模型LP的几种表示形式：第13页，共64页，2023年，2月20日，星期一§2线性规划问题的图解法定义1在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T

称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2

设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D

都有cx*≥cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值，记作z*=cx*。第14页，共64页，2023年，2月20日，星期一§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形：x2=-3/5

x1+z/25x2x1最优解：

x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点第15页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。第16页，共64页，2023年，2月20日，星期一§2线性规划问题的图解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2第17页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？第18页，共64页，2023年，2月20日，星期一§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴

有可行解⑵

无可行解a.有唯一最优解b.有无穷多最优解c.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。第19页，共64页，2023年，2月20日，星期一§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。第20页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质讨论如下

LP

问题：其中系数矩阵决策向量

假设

A的秩为

m,且只讨论

m<n的情形。什么意思？为什么？第21页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法定义3在上述

LP问题中，约束方程组（2）的系数矩阵A的任意一个m×m阶的非奇异的子方阵B（即|B|≠0），称为LP问题的一个基阵或基。

称

pi(i=1,2,…,m)为基向量;xi(i=1,2,…,m)为基变量；

xj(j=m+1,…,n)为非基变量pj(j=m+1,…,n)为非基向量;记：则A=(B,N)第22页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质

A=(B,N)xB=(x1,…,xm)T,xN=(xm+1,…,xn)T则,代入约束方程（2），得自由变量（独立变量）令称（4）为相应于基

B的基本解第23页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法是可行解吗？maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

令x1=x2=x3=0

如果

B-1b

≥0，则称（4）为相应于基

B的基可行解，此时的基

B

称为可行基。第24页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质基本解唯一吗？最多有多少？Rn非可行解基可行解可基解行解称它是非退化的解；反之，如果有一个基变量也取零值，则称它是退化的解。一个LP问题，如果它的所有基可行解都是非退化的就称该是非退化的，否则就称它是退化的。定义4

在LP问题的一个基可行解中，如果它的所有的基变量都取正值，则第25页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法LP

问题解的基本性质定理1设x是LP问题的可行解(1)若x=0，则它一定是基可行解；(2)若x≠0，则x是基可行解的充要条件是它的非零分量所对应的列向量线性无关。Ax=0定理

2

如果一个LP问题有可行解，则它必有基可行解。定理

3

如果一个LP问题有最优解，则必存在一个基可行解是它的最优解。

定理2、定理3称为LP问题的基本定理

定理2证明向前定理3证明LP问题是一个组合优化问题第26页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质定理2证明设x=(x1,x2,…,xn)T

是LP问题的一个可行解，如果x=0，则由定理1知，它是LP问题的一个基可行解，定理成立。如果x≠0，不妨设

x的前k个分量为非零分量。则有

x1p1+x2p2+…+xkpk=b，及x1>0,x2>0,…,xk>0，分两种情况讨论：如果p1,p2,…,pk线性无关，即x的非零分量对应的列向量线性无关，则由定理1知，它是LP的一个基本可行解，定理成立。(2)如果p1,p2,…,pk线性相关，则必存在一组不全为零的数

δ1,δ2,…,δk使得第27页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法假定有δi≠0，取作其中由（6）式知，必有即又因为由（5）式知故有，，即也是LP的两个可行解。第28页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质

再由的取法知，在式(7)的诸式中，至少有一个等于零，于是所作的可行解中，它的非零分量的个数至少比x的减少1，如果这些非零分量所对应的列向量线性无关，则为基可行解，定理成立。否则，可以从出发，重复上述步骤，再构造一个新的可行解，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。返回e第29页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质定理3证明设是LP

的一个最优解。如果

x*是基本解，则定理成立；如果

x*不是基本解，则由定理2的证明过程可构造两个可行解它的非零分量的个数比x*

的减少，且有

，

又因为x*

是最优解，故有由式（8）和（9）知，必有即x(1),x(2)

仍为最优解。如果x(1)或x(2)

是基可行解，则定理成立。否则，按定理2证明过程，可得基可行解x(s)或x(s+1),使得即得基可行解x(s)或x(s+1)为最优解。返回第30页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法LP

问题解的几何意义定义5设集合是n维欧氏空间中的一个点集，如果及实数

则称

S是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在该集合中，则称该集合为凸集。

Note:空集和单点集也是凸集。第31页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质定义6

设则称为点的一个凸组合。定义7设凸集两点表示为则称x为S

的一个极点（或顶点）。定理4LP问题的可行解集第32页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法定理5设D为

LP问题的可行解集，，则x是

D的极点的充分必要条件是

x为

LP问题的基可行解。prove推论1如果LP

问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的。推论2如果LP

问题有最优解，则一定可在可行解集

D的极点上达到。定理6设LP

问题在多个极点x(1),x(2),…x(k)处取到最优解，则它们的凸组合，即也是LP

问题的最优解.（此时，该LP

问题有无穷多最优解）第33页，共64页，2023年，2月20日，星期一§3线性规划问题解的基本性质Note:1、如何判断

LP

问题有最优解；2、计算复杂性问题。

设有一个50个变量、20个约束等式的LP问题，则最多可能有个基。即约150万年

如果计算一个基可行解只需要1秒，那么计算所有的基可行解需要：1364.7101.510360024365´»´´´（年）第34页，共64页，2023年，2月20日，星期一§4单纯形法的基本原理

单纯形法（SimplexMethod）是1947年由

G.B.Dantzig提出，是解

LP问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。基本思路：基于LP问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不相同）。第35页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法单纯形法引例

首先，化原问题为标准形式：x3,x4

是基变量.基变量用非基变量表示：x3=60-x1-3x2

x4=40-x1

-x2代入目标函数：z=15x1+25x2令非基变量x1=x2=0z=0

基可行解

x(0)=(0,0,60,40)T是最优解吗？maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2+x4=40x1，x2,x3,

x4≥0

第36页，共64页，2023年，2月20日，星期一§4单纯形法的基本原理z=15x1+25x2x3=60-x1-3x2

x4=40-x1

-x2因为x2的系数大，所以x2换入基变量。x3=60-3x2≥0x4=40-x2≥

0谁换出？如果x4换出，则x2=

40，x3=-60，不可行。如果是“+”会怎样？如果x3换出，则x2=

20，x4=

20。最小比值法则所以x3

换出。基变量用非基变量表示：代入目标函数：z=500+20/3

x1-25/3

x3令非基变量x1=x3=0

z=500

基可行解

x(1)=(0,20,0,20)T大于零！第37页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法因为x1的系数大，所以x1换入基变量。所以x4换出。基变量用非基变量表示：代入目标函数：z=700–5x3–10

x4令非基变量x3=x4=0

z=700

基可行解

x(2)=(30,10,0,0)T因为非基变量的系数都小于零，所以x(2)=(30,10,0,0)T是最优解zmax=700

第38页，共64页，2023年，2月20日，星期一§4单纯形法的基本原理

目标函数用非基变量表示时，非基变量的系数称为检验数(40,0)(0,0)(0,20)ABC(30,10)OL1L2Z=250x2x1x(0)=(0,0,60,40)Tz=0

x(1)=(0,20,0,20)Tz=500

x(2)=(30,10,0,0)Tz=700

第39页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法单纯形法的基本原理称(1a)(2a)(3a)为LP问题对应于基B

的典则形式（典式）.Ax=b基变量用非基变量表示：代入目标函数：第40页，共64页，2023年，2月20日，星期一§4单纯形法的基本原理如果记则典式(1a)(2a)(3a)可写成第41页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法定理7在LP问题

的典式(1b)

～(3b)中，如果有则对应于基B

的基可行解是

LP问题的最优解，记为相应的目标函数最优值z*=z(0)此时，基B称为最优基第42页，共64页，2023年，2月20日，星期一§4单纯形法的基本原理定理8在LP问题

的典式(1b)

～(3b)中，是对应于基B

的一个基可行解，如果满足下列条件：(1)有某个非基变量

xk的检验数

σk>0(m+1≤k≤n);(2)aik(i=1,2,…,m)不全小于或等于零，即至少有一个

aik>0(i=1,2,…,m);(3)>0(i=1,2,…,m),即x(0)为非退化的基可行解。则从

x(0)出发，一定能找到一个新的基可行解>第43页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法定理9在LP问题的典式(1b)

～(3b)中，如果检验数满足最优准则σj≤0(j=m+1,…,n)，且其中有一个σk=0(m+1≤k≤n)，则该

LP问题有无穷多个最优解。这在应用中很有价值定理10在LP问题的典式(1b)

～(3b)中，如果有某个非基变量的检验数σk>0(m+1≤k≤n)，且有则该

LP问题解无界（无最优解）。第44页，共64页，2023年，2月20日，星期一§5单纯形法的计算步骤单纯形表

c

c1c2cmcm+1cm+2cncBxB

x1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m检验数

0

00

-z(0)第45页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法如何得到单纯形表？

cAb检验数0B-1b-

cBB-1b

-z0

IB-1NB-1b

0σN检验数

BNcBcN

IB-1N

0cN-cBB-1N第46页，共64页，2023年，2月20日，星期一§5单纯形法的计算步骤e.g.4

列出如下

LP

问题的初始单纯形表。maxz=4x1+3x2+2x3+5x4s.t.x1+3x2+x3+2x4=54x1+2x2+3x3+7x4=

17

x1，x2

，x3，x4≥0不妨已知x3、x4

为可行基变量

ccBxB25x3x4检验数4325x1

x2

x3

x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2)Tz0=12第47页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法单纯形法求解LP

问题的计算步骤：Step1

找出初始可行基，列初始单纯形表,确定初始基可行解；

Step2

检验各非基变量xj的检验数σj,如果所有

的

σj

≤0（j=1,2,…,n），则已求得最优解，停止计算。否则转入下一步；

Step3

在所有的σj

>0中，如果有某个σk>0，所对应的xk的系数列向量p’k≤0（即a’ik≤0，i=1,2,…,m），则此问题解无界，停止计算。否则转入下一步;第48页，共64页，2023年，2月20日，星期一§5单纯形法的计算步骤Step4根据,确定xk为换入基变量，又根据最小比值法则计算:确定xr为换出基变量。转入下一步;

Step5以为主元进行换基变换，用初等行变换将

xk所对应的列向量变换成单位列向量，即同时将检验数行中的第k个元素也变换为零，得到新的单纯形表。返回Step2。第49页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40x1，x2

，x3

，x4≥0

00

ccBxB00x3x4检验数152500x1

x2

x3

x413101101152500b6040001θx(0)=(0,0,60,40)Tz0=0x21/3-500x(1)=(0,20,0,20)Tz1=500x10-700x(2)=(30,10,0,0)Tz2=7001/2检验数都小于等于零x(2)为最优解

zmax=70060/340/12531/312000-1/312020/3-25/3020/1/320/2/3152/32/310-1/23/2300-1/2100-5-10第50页，共64页，2023年，2月20日，星期一§5单纯形法的计算步骤思考：在单纯形法中根据确定xk为进基变量，是否在这次变换中，使目标函数值提高最大？

如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？目标函数值能提高多少？第51页，共64页，2023年，2月20日，星期一§6单纯形法的进一步讨论一、初始可行基的求法

maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

………….

(2c)

am1x1+am2x2+…+amnxn=bm

xj≥0（j=1,2,…,n）

(3c)

a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）人工变量1、试算法人造基本解：x0=(0,0,…,0,b1,…,bm)T2、人工变量法第52页，共64页，2023年，2月20日，星期一§6单纯形法的进一步讨论(1)大M法惩罚法

maxw=c1x1+c2x2+…+cnxn–M(xn+1+…+xn+m)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）M是一个充分大的正数结论：设为上述问题的最优解则为原问题的最优解，这时的目标函数值为最优值；则原问题无可行解。不全为零，第53页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法e.g.5用大M

法求解maxz=3x1-x2–

x3s.t.x1-2x2+x3≤11-4x1

+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0

maxz=3x1-x2–

x3+0

x4+0

x5-M

x6-M

x7s.t.x1-2x2+x3+x4=11-4x1

+x2+2x3-x5+x6=3-2x1+x3+

x7=1xj≥0(j=1,2,…,7)解：引入松弛变量

x4，

x5

和人工变量

x6，

x7得

ccBxB-M0x4x6检验数

3-1-100-M-Mx1

x2

x3

x4x5

x6

x7131011012-100b110001θ-2-4-20011x7-M3-1-100-M-M3-4MM-12M-10-M0-M3M3-6MM-13M-10-M004M11/13/21/1x3-113-201100-1100100-11-211M-100-M1-3MM+11/11x2-13001-22-5121000-1-1-M2112/3x13001/3-2/32/3-5/340012/3-4/34/3-7/39000-1/3-1/32/3-M-23101-M1/3-M

200-0.2M>0?

由于人工变量

x6=x7=0,

所以,得原问题的最优解x*=(4,1,9,0,0)T

目标函数最优值

zmax=2

Note:在计算过程中,某个人工变量一旦变为非基变量,则该列可被删去

第54页，共64页，2023年，2月20日，星期一§6单纯形法的进一步讨论(2)两阶段法第一阶段：

maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

………….

(2c)

am1x1+am2x2+…+amnxn=bm

xj≥0（j=1,2,…,n）

(3c)

maxw=–xn+1–xn+2–…–xn+m(1d)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2………… (2d)

am1x1+am2x2+…+amnxn+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）(3d)

判断原LP

问题（1c）~（3c）是否存在可行解，如果存在就找出一个初始基可行解；解之可得：（a）如果

wmax<0,

则原问题无可行解，停止计算；（b）如果

wmax=0,且人工变量都不是基变量，则转入第二阶段；第55页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法（c）如果

wmax=0,但仍有取零的人工变量为基变量；x1

x2

…

xn

xn+1

…xn+k

…

xn+mba’l1a’l2…

a’lna’ln+1…

1

…

a’n+m0如xn+k=0

是基变量，在最终单纯形表中：

a’l1a’l2…

a’ln

不可能全为零，必有某个a’lj≠0，这时xj不是基变量，与xn+k交换即可。第二阶段：从第一阶段所求得的初始可行基出发，求解原问题第56页，共64页，2023年，2月20日，星期一§6单纯形法的进一步讨论二、关于退化和循环1955

年

Beale

给出如下例子：最优解：B0=(P1,P2,P3)作为初始可行基，经6次迭代又得B0第57页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法Bland

法则：（对极大值问题而言）则选择xk作为进基变量。选择进基变量：选取σj

>0（1≤j≤n）中下标最小的检验数σk所对应的非基变量xk作为进基变量，即如果(2)选择出基变量：当按θ规则计算此值时，如果存在n个，同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果则选择xl作为出基变量。第58页，共64页，2023年，2月20日，星期一§7线性规划应用举例e.g.6

生产计划问题

某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元.现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型.季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810第59页，共64页，2023年，2月20日，星期一第一章线性规划及单纯形法解：方法一设工厂第j季度生产产品xj

吨需求约束：第一季度末需交货20吨，x1≥20第二季度末需交货20吨，x1-20+x2≥20这是上季末交货后积余第三季度末需交货30吨，x1+x2-40+x3≥30第四季度末需交货10吨，x1+x2+x3-70

+x4=10生产能力约束：0≤xj≤aj

j=1,2,3,4季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810生产、存储费用：第一季度：15x1第二季度:14x2+0.2(x1-20)第三季度:15.3x3+0.2(x1+x2-40)第四季度:14.8x4+0.2(x1+x2+x3-70

)min

z

=15.6x1

+14.4x2+15.5x3+

14.8x4-26s.t.x1+x2≥40,x1+x2+x3≥70

x1+x2+x3+

x4=80,20≤x1≤30,0

≤x2≤40,0

≤x3≤20