生产运筹学线性规划及单纯形法 二

运筹学

OperationsResearch

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

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

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

60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。§1线性规划问题及其数学模型e.g.1资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？

表1产品资源 甲乙库存量A 1 3 60 B 1 1 40 单件利润15 25

某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第一章线性规划及单纯形法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

决策变量§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

试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第一章线性规划及单纯形法

表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§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n个子系统处理。1、决策变量xj≥0

2、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第一章线性规划及单纯形法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）为已知常数线性规划问题的一般形式：§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、所有决策变量均非负。第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。因为求minz等价于求max(-z)，令z’=-z，即化为：

2、约束条件为不等式，xn+1≥0松弛变量如何处理？§1线性性规划问题题及其数学学模型３、右端项bi<0时，，只需将等等式两端同同乘（-1）则右端项必必大于零4、决策变变量无非负负约束设xj没有非负约约束，若xj≤0，可令令xj=-xj’，则xj’≥0；又若xj为自由变量，，即xj可为任意实数数，可令xj=xj’-xj’’，且xj’,xj’’≥0第一章线线性规划划及单纯形法法e.g.3试将LP问题minz=-x1+2x2-3x3s.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-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0§1线性规规划问题及其其数学模型LP的几种表表示形式：§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*。§2线线性性规划划问题题的图图解法法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函函数变变形：：x2=-3/5x1+z/25x2x1最优解：x1=30x2=10最优值：zmax=700B点是使使z达到到最大的的唯一可可行点第一章线线性规规划及单单纯形法法LP问题题图解法法的基本本步骤：1、在平面上上建立直直角坐标标系；2、图示约束束条件，，确定可可行域和和顶点坐坐标；3、图示目标标函数（（等值线线）和移移动方向向；4、寻找最优优解。§2线线性规划划问题的的图解法法maxz=3x1+5.7x2s.t.x1+1.9x2≥3.8x1-1.9x2≤3.8x1+1.9x2≤11.4x1-1.9x2≥-3.8x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2））D0=3x1+5.7x2maxZminZ（3.8,4））34.2=3x1+5.7x2可行域x1-1.9x2=-3.8(0,2)(3.8,0)绿色线段段上的所所有点都是最优优解,即即有无穷穷多最优优解。Zman=34.2第一章线线性规规划及单单纯形法法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥0OA(１,0)x1x2Note:可行域为为无界区区域，目标函数数值可无无限增大，即即解无界界。称为无最最优解。可行域为为无界区区域一定定无最优优解吗？？§2线线性规划划问题的的图解法法由以上两两例分析析可得如如下重要要结论：：1、LP问题从解解的角度度可分为为：⑴有可行解解⑵无可行解解有唯一最最优解b.有有无穷穷多最优优解C.无无最优优解2、LP问题若有有最优解解，必在在可行域域的某个个顶点上上取到；若有有两个顶顶点上同同时取到到，则这这两点的的连线上上任一点都是最最优解。§2线性规规划问题的图图解法图解法优点：：直观、易掌握握。有助于了了解解的结构构。图解法缺点：：只能解决低维维问题，对高高维无能为力力。§3线性规规划问题解的的基本性质讨论如如下LP问题：：其中系数矩矩阵决策向向量假设A的秩为为m,且只讨讨论m<n的情形。什么意意思？？为什么么？第一章章线线性性规划划及单单纯形形法定义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)§3线线性性规划划问题题解的的基本本性质质A=(B,N)xB=(x1,…,xm)T,xN=(xm+1,…,xn)T则,代入约约束方方程（2）），得得自由变变量（独立立变量量）令称（4）为相相应于于基B的基本本解第一章章线线性性规划划及单单纯形形法是可行行解吗吗？maxz’’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0令x1=x2=x4=0如果果B-1b≥0，，则则称（（4）为为相相应应于于基基B的基基可可行行解，，此此时时的的基基B称为为可可行行基基。。§3线线性性规规划划问问题题解解的的基基本本性性质质基本本解解唯唯一一吗吗？？最最多多有有多多少少？？Rn非可行解基可行解可基解行解称它它是是非非退退化化的的解解；；反反之之，，如如果果有有一一个个基基变变量量也也取取零值值，，则则称称它它是是退退化化的的解解。。一一个个LP问问题题，，如如果果它它的的所有基基可行行解都都是非非退化化的就就称该该是非非退化化的，，否则就称称它是是退化化的。。定义4

在LP问题的一个基可行解中，如果它的所有的基变量都取正值，则第一章章线线性性规划划及单单纯形形法LP问题解解的基基本性性质定理1设x是LP问题的可行解(1)若x=0，则它一定是基可行解；(2)若x≠0，则x是基可行解的充要条件是它的非零分量所对应的列向量线性无关。Ax=0定理2

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

如果一个LP问题有最优解，则必存在一个基可行解是它的最优解。定理2、、定理理3称称为LP问题的的基本本定理理定理2证证明明向前定理3证证明明LP问题是是一个个组合合优化化问题题§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使得第一章线线性性规划及单单纯形法假定有δi≠0，取作其中由（6）式式知，必有有即又因为由（（5）式知知故有，，即也是LP的的两个可行行解。§3线性性规划问题题解的基本本性质再由的的取法知知，在式(7)的的诸式式中，至少有一个个等于零，，于是所作作的可行解解中中，它的非零分量的的个数至少少比x的减少1，，如果这些些非零分量量所对应的列向量线线性无关，，则为为基可行行解，定理理成立。否则，可以以从出出发，重重复上述步步骤，再构构造一个新的可可行解，，使它它的非零分分量的个数数继续减少。这样经经过有限次次重复之后后，必可找找到一个可可行解使它的非零零分量对应应的列向量量线性无关关，故可行行解必为基可行行解。证毕毕。返回e§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)为最优解。。返回第一章线线性性规划及单单纯形法LP问题解的几几何意义定义5设集合是n维欧氏空间中的一个点集，如果及实数则称S是一个凸集集。几何意义：：如果集合合中任意两两点连线上上的一切点点都在该集合中，，则称该集集合为凸集集。Note:空集和单点点集也是凸凸集。§3线性性规划问题题解的基本本性质定义6设则则称为点的的一个凸凸组合。定义7设凸集两点表示为则称x为S的一个极点（或顶点）。定理4LP问题的可行解集第一章线线性性规划及单单纯形法定理5设设D为LP问题的可行行解集，，，则x是D的极点的充充分必要条条件是x为LP问题的基可可行解。prove推论1如果LP

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

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

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

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

问题的最优解.（此时，该该LP问题有无穷穷多最优解解）§3线性性规划问题题解的基本本性质Note:1、如何判断LP问题有最优解解；2、计算复杂性问问题。

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

如果计算一个基可行解只需要1秒，那么计算所有的基可行解需要：1364.7101.510360024365´»´´´（年）§4单纯形形法的基本原原理单纯形法（SimplexMethod）是1947年年由G.B.Dantzig提出，是解LP问题最有效的的算法之一，，且已成为整数数规划和非线线性规划某些些算法的基础础。基本思路：基于LP问题的标准形形式，先设法法找到一个基基可行解，判断它它是否是最优优解，如果是是则停止计算算；否则，则转换到到相邻的目标标函数值不减减的一个基可可行解.（两个基可行行解相邻是指指它们之间仅仅有一个基变变量不相同）。第一章线线性规划划及单纯形法法单纯形法引例例首先，化原问问题为标准形式式：x3,x4是基变量.基变量用非基基变量表示：：x3=60-x1-3x2x4=40-x1-x2代入目标函数数：z=15x1+25x2令非基变量x1=x2=0z=0基可行解x(0)=(0,0,60,40)T是最优解吗？？maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60x1+x2+x4=40x1，x2,x3,x4≥0§4单纯形形法的基本原原理z=15x1+25x2x3=60-x1-3x2x4=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/3x1-25/3x3令非基变量x1=x3=0z=500基可行解x(1)=(0,20,0,20)T大于零！第一章线线性规划划及单纯形法法因为x1的系数大，所所以x1换入基变量。。所以x4换出。基变量用非基基变量表示：：代入目标函数数：z=700––5x3–10x4令非基变量x3=x4=0z=700基可行解x(2)=(30,10,0,0)T因为非基变量量的系数都小小于零，所以x(2)=(30,10,0,0)T是最优解zmax=700§4单纯形形法的基本原原理目标函数用非非基变量表示示时，非基变变量的系数称为检验数(40,0)(0,0)(0,20)ABC(30,10)OL1L2Z=250x2x1x(0)=(0,0,60,40)Tz=0x(1)=(0,20,0,20)Tz=500x(2)=(30,10,0,0)Tz=700第一一章章线线性性规规划划及及单单纯纯形形法法单纯纯形形法法的的基基本本原原理理称(1a)(2a)(3a)为LP问题题对对应应于于基B的典典则则形形式式（（典典式式））.Ax=b基变变量量用用非非基基变变量量表表示示：：代入入目目标标函函数数：：§4单单纯纯形形法法的的基基本本原原理理如果记则典式(1a)(2a)(3a)可可写成成第一章线线性规规划及单单纯形法法定理7在在LP问题的典式(1b)～(3b)中，如果有则对应于于基B的基可行行解是

LP问题的最优解，记为相应的目目标函数数最优值值z*=z(0)此时，基基B称为最优基基§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)出发，一一定能找找到一个个新的基基可行解解>第一章线线性规规划及单单纯形法法定理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问题解无无界（无无最优解解）。§5单单纯形法法的计算算步骤单纯形表表

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+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)第一章线线性规规划及单单纯形法法如何得到到单纯形形表？

cAb检验数0B-1b-cBB-1b

-z0IB-1NB-1b0σN检验数BNcBcNIB-1N0cN-cBB-1N§5单单纯形法法的计算算步骤e.g.4列出如下下LP问题的初始单单纯形表表。maxz=4x1+3x2+2x3+5x4s.t.x1+3x2+x3+2x4=54x1+2x2+3x3+7x4=17x1，x2，x3，x4≥0不妨已已知x3、x4为可行行基变变量

ccBxB25x3x4检验数4325x1

x2

x3

x4131242374325b51701-70126-3105-2-117101140-12x(0)=(0,0,1,2)Tz0=12第一章线线性性规划及单单纯形法单纯形法求求解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），则此问问题解无界界，停止计计算。否则则转入下一一步;§5单纯纯形法的计计算步骤Step4根据,确定定xk为换入基变量，又又根据最小小比值法则则计算:确定xr为换出基变变量。转入入下一步;Step5以为为主元元进行换换基变换换，用初初等行变变换将xk所对应的的列向量量变换成成单位列列向量，，即同时将检检验数行行中的第第k个元素也也变换为零零，得到到新的单单纯形表表。返回Step2。第一章线线性规规划及单单纯形法法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60x1+x2++x4=40x1，x2，x3，x4≥000

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§5单单纯形法法的计算算步骤思考：在单纯形法中中根据确定xk为进基变量，，是否在这次次变换中，使使目标函数值提高高最大？如果不是，应应选择哪个变变量进基，保保证这次变换使得目目标函数值提提高最大？目标函数值能能提高多少？？§6单纯形形法的进一步步讨论一、初始可行行基的求法maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……………….(2c)am1x1+am2x2+…+amnxn=bmxj≥0（j=1,2,…,n）(3c)a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2……………am1x1+am2x2+…+amnxn+xn+m=bmxj≥0（j=1,2,…,n,n+1,…,n+m）人工变量1、试算法人造基本解：x0=(0,0,…,0,b1,…,bm)T2、人工变量法§6单纯形形法的进一步步讨论(1)大M法惩罚法maxw=c1x1+c2x2+…+cnxn–M(xn+1+…+xn+m)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmxj≥0（j=1,2,…,n,n+1,…,n+m）M是一个个充分分大的的正数数结论：：设为上述述问题题的最最优解解则为原问问题的的最优优解，，这时时的目目标函函数值值为最最优值值；则原问问题无无可行行解。。不全为零，第一章章线线性性规划划及单单纯形形法e.g.5用大M法求解解maxz=3x1-x2–x3s.t.x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0maxz=3x1-x2–x3+0x4+0x5-Mx6-Mx7s.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-M200-0.2M>0?由于于人人工工变变量量x6=x7=0,所以以,得原原问问题题的的最最优优解解x*=(4,1,9,0,0)T目标标函函数数最最优优值值zmax=2Note:在计计算算过过程程中中,某某个个人人工工变变量量一一旦旦变变为为非非基基变变量量,则则该该列列可可被被删删去去§6单单纯纯形形法法的的进进一一步步讨讨论论(2)两两阶阶段段法法第一一阶阶段段：maxz=c1x1+c2x2+…+cnxn(1c)s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………………….(2c)am1x1+am2x2+…+amnxn=bmxj≥0（j=1,2,…,n）(3c)maxw=––xn+1–xn+2–…–xn+m(1d)s.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………(2d)am1x1+am2x2+…+amnxn+xn+m=bmxj≥0（j=1,2,…,n,n+1,…,n+m）(3d)判断断原原LP问题题（1c））~（（3c））是否否存存在在可可行行解解，，如如果果存存在在就就找找出出一一个初初始始基基可可行行解解；；解之之可可得得：：（a）如果果wmax<0,则原原问问题题无无可可行行解解，，停停止止计计算算；；（b）如果果wmax=0,且人人工工变变量量都都不不是是基基变变量量，，则则转转入入第二二阶阶段段；；第一一章章线线性性规规划划及及单单纯纯形形法法（c）如果果wmax=0,但仍仍有有取取零零的的人人工工变变量量为为基基变变量量；；x1x2…xnxn+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交换即可。第二阶段：从第一阶段所所求得的初始始可行基出发发，求解原问问题§6单纯形形法的进一步步讨论二、关于退化化和循环1955年Beale给出如下例子子：最优解：第一章线线性规划划及单纯形法法Bland法则：（对极大值问问题而言）则选择xk作为进基变量量。选择进基变量：选取σj

>0（1≤j≤n）中下标最小的检验数σk所对应的非基变量xk作为进基变量，即如果(2)选择出基变量：当按θ规则计算此值时，如果存在n个，同时达到最小值，就选其中下标最小的那个基变量作为出基变量。即如果则选择xl作为出基变量。§7线性规规划应用举例例e.g.6生产计划问题题某工厂明年根根据合同，每每个季度末向向销售公司提提供产品，有关信息息如表，若当当季生产的产产品过多，季季末有积余，，则一个个季度度每积积压一一吨产产品需需支付付存贮贮费0.2万元元.现现该该厂考虑明明年的的最佳佳生产产方案案，使使该厂厂在完完成合合同的的情况况下，，全年的生生产费费用最最低.试建建立线线性规规划模模型.季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810第一章章线线性性规划划及单单纯形形法解：方法一一设工厂第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≤ajj=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)minz=15.6x1+14.4x2+15.5x3+14.8x4-26s.t.x1+x2≥40,x1+x2+x3≥70x1+x2+x3+x4=80,20≤x1≤30,0≤x2≤40,0≤x3≤20,0≤x4≤10.§7线线性规划划应用举举例季度

j生产能力（aj）生产成本（dj）需求量（bj）13015．02024014．02032015．33041014．810方法二设第i季度生产产而用于于第j季度末交交货的产产品数量为为xij吨.需求约束束：x11=20x12+x22=20x13+x23+x33=30