《运筹学》课件 第1、2章 线形规划、单纯形法

第一章线性规划第1章内容提要1.1线性规划问题及其数学模型1.2图解法1.3线形规划的标准形式1.4线形规划解的概念1.5线形规划的基本理论线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian(哈奇扬

)提出“椭球法”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar(卡马卡)提出“投影梯度法”

线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的哈奇扬提出“椭球法”1984年印度的卡马卡提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。1.1线性规划问题及其数学模型LP:LinearProgramming1.1.1问题的提出1.1.2线性规划问题的标准型1.1.3线性规划问题解的概念1.1.1问题的提出生产经营中经常提出的一个问题是：如何合理地利用人、财、物，以降低成本，获取效益提问

建模

求解

检验

控制

实施运筹学的工作步骤生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1-1线性规划基本概念

一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。

——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。

另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。线性规划研究的主要问题例1:某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：III合计设备128台时原材料A4016千克原材料B0412千克该工厂每生产一件I

可获得2元，每生产一件产品II可获得3元。问应如何安排计划使该工厂获得最多？例1解这是一个求极大值问题，可用数学模型来描述。设计划期内产品的产量为：I

x1IIx2则得到利润z为:z=2x1+3x2约束条件台时约束：x1+2x2

8原材料约束4x1

164x2

12问题为求x1、

x2的值，使得利润z

最大例1数学模型归结为：目标函数Max

z=2x1+3x2约束条件x1+2x2

84x1

16s.t.4x2

12x1,x2

0s.t.Subjectto受…约束例2某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。

8221丁7141丙6102乙5321甲单位成本（元／吨）CBA药物原料解：1.决策变量：设四种原料的使用量分别为：x1、x2、x3

、x42.目标函数：设总成本为z，则有：

minz=5x1+6x2+7x3+8x43.约束条件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0例题3：人员安排问题(自己动手做一做)医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

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

x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30X6+X1≥60非负性约束：xj≥0,j=1,2,…6船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？课堂练习：某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：解：设：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400xj≥0j=1,2,3,4其他典型问题：合理下料问题其他典型问题：合理下料问题运输问题其他典型问题：合理下料问题运输问题生产的组织与计划问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题线性规划模型特点决策变量：向量(x1…

xn)T决策人要考虑和控制的因素非负目标函数：有一个目标函数可以表示为这组变量的线形函数约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…

xn)线性式，求Z极大或极小线形规划的一般数学模型1.决策变量：X=(x1,x2,…..,xn)T2.目标函数：max(minz)=c1

x1+c2

x2+…….+cnxn3.约束条件：

a11x1+a12

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0模型特点1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；———

满足以上三个条件的数学模型称为线性规划2都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。其它形式其中：①求和形式②矩阵形式决策变量常数项系数矩阵价值系数其中：线性规划图解法一、解题步骤4将最优解代入目标函数，求出最优值。1在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2标出目标函数值增加的方向。3若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。图解法最简单、直观的方法但只适用有两个决策变量的情况非负约束Thenon-negativityconstraintsx2x1可行域

满足线性规划模型所有约束条件的所有点（可行解）的集合——可行域

可行域的性质：(1)、可行域为凸多边形。(2)、若有最优解，定可在可行域的极点得到。X(1)X(2)凸多边形凹多边形X(1)X(2)012345678可行域x2非可行域x1+2x2£84x2£

1243214x1£16x1用图解法解例1最优解点x1=4，x2

=2例1数学模型归结为：目标函数Max

z=2x1+3x2约束条件x1+2x2

84x1

16s.t.4x2

12x1,x2

0z=2x1+3x2即x2=-2x1/3+z/3z取不同值时是一束斜率为-2/3平行线，z最大值出现在最高的一条线上。某玩具公司生产S和Z两种塑料玩具其所用特殊塑料每周可用量为1000磅每周生产时间是40小时市场需求是总产量不能超过700件，其中S产量不能超过Z产量350件生产每件S产品需2磅塑料和3分钟时间生产每件Z产品需1磅塑料和4分钟时间生产计划要求尽可能地生产利润更高的S产品（每件利润8元，而Z每件利润5元）问如何安排两种产品的生产，使获利最大？例2玩具公司生产计划

Maxz=8x1+5x2

subjectto 2x1+1x2≤1000(1)塑料约束

3x1+4x2≤2400(2)生产时间约束（分钟）

x1+x2≤700(3)总产量约束

x1-x2≤350(4)产量差约束

xj>=0,j=1,2(5)例2的线性规划模型为1000500可行域x2非可行域生产时间约束(3)3x1+4x2£

2400总产量约束(2)x1+x2£

700(多余的)500700塑料约束(1)2x1+x2£1000x1700图解法1000500可行域x2非可行域生产时间约束(3)

3x1+4x2£2400总产量约束(2)

x1+x2£700(多余的)500700产量差约束(4)

x1-x2£

350塑料约束(1)2x1+x2£1000x1700图解法三种可能的点域内点边界点顶点用图解法求最优解寻求最优解从任意一个z值开始，如

z=2000如可能，增加z值直到不能再增加最大利润Z*=43605007001000500x2x1Maxz=8x1+5x2即x2=-8x1/5+z/5斜率-8/5的直线例2结果总结

x1

=320

x2=360

z*=4360约束(1)、(2)全部取等号

2x1+x2≤1000(1)3x1+4x2≤2400(2)x1+x2

只有680(而不是700)。x2-x1

只有

40。012345678910可行域x2非可行域直线5x1+10x2=50直线x1+x2=

154321直线x2=

4x1例3最优解点x1=2,x2

=4目标函数Max

z=

x1+3x2约束条件5x1+10x2

50

x1

+x2

1

x2

4x1,x2

0z=

x1+3x2即x2=-x1/3+z/3z取不同值时是一束斜率为-1/3平行线，z最大值出现在最高的一条线上。如果线性规划问题有最优解，可行域的一个顶点肯定是最优解顶点和最优解如果存在多个最优解，目标函数必须与某一个约束条件平行。多个最优解在此线段上的任一点均为最优解。无界解和无可行解若可行域无界，目标函数值可以增大到无穷大，则为无界解。若可行域为空集，即无可行解，也不存在最优解。无界解

可行域Thefeasibleregion

Maximize目标函数值最大化

112323无可行解没有点能同时处在直线1上方和直线2、3的下方。总结

唯一解无穷多解无有限最优解无可行解有解无解可行域为封闭的有界区域：唯一、多个最优解可行域为非封闭的无界区域：唯一、多个最优解对于目标函数无界：无最优解可行域为空集：没有可行解，更无最优解线性规划的可行域及最优解的可能结果(a)可行域封闭，唯一最优解(b)可行域封闭，多个最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界(f)可行域为空集(c)可行域开放，唯一最优解线性规划的可行域及最优解的可能结果图示:线性规划问题的标准型Max

z=

c1x1+c2x2+…+cnxna11x1+a12x2+…+

a1nxn=b1a21x1+a22x2+…+

a2nxn=b2

……am1x1+am2x2+…+

amnxn=bm

x1,x2…

,xn

0

并规定,右端项

bi

0s.t.和式标准型的矩阵表示Max

z=CXAX=bX

0C价值向量b资源向量X决策变量向量A约束条件的m

n阶系数矩阵,一般m<n标准型的特征目标函数极大化约束条件为等式决策变量非负化标准型若目标函数为最小化,即Min

z=CX,可令,z‘=-z得到Max

z‘=-CX,就成目标函数最大化了。若约束方程为不等式:

在不等式号左端加非负松驰变量在不等式号左端减非负剩余变量若存在取值无约束的变量xk，可令xk=

x’k-

x”k

，其中x’k,

x”k

0

。(1)、约束条件

X1+2X2+X3=303X1+2X2+X4=602X2+

+X5=24

X1,

…,X50

松弛变量

例1maxZ=40X1+50X2+0·X3+0·X4+0·X54X1+6X2+X3+2X4-X5=12X1+X2+7X3+5X4-X6=142X2+X3+3X4-X7=8

X1,

…,X70

剩余变量

例2

minZ=2X1+5X2+6X3+8X4(2)、变量3X1'-3X1"+2X28X1'

-X1"-4X2

14X1',X1",X201、3X1+2X28X1-4X2

14X20令X1=X1'-X1"X1'

+X211X1'

16X1',X202、X1+X25-6

X110X20-6+6X1+6

10+6

令X1'

=X1+6

0

X1'

16例：将minZ=-X1+2X2-3X3X1+X2+X37X1-X2+X32X1，X20，X3无限制化为标准型解：①令X3=X4-

X5②加松弛变量X6③加剩余变量X7

④令Z'=-ZmaxZ'=X1-2X2+3X4-3X5X1+X2+X4-X5+X6=7X1-X2+X4-X5-X7=2X1,

X2,

X4,…,X70例：将以下线性规划问题转化为标准形式

Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0解：首先，将目标函数转换成极大化：令

z=-f=3x1–5x2–8x3+7x4

；其次考虑约束，有3个不等式约束，引进松弛变量x5,剩余变量x6,x7

≥0；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

非标准型转化举例之一maxZ=70X1+120X29X1+4X2≤3604X1+5X2≤2003X1+10X2≤300X1≥0X2≥0

maxZ=70X1+120X29X1+4X2+X3=3604X1+5X2+X4=2003X1+10X2+X5=300Xj≥0j=1,2,…,5非标准型转化举例之二minZ=x1+2x2-3x3

x1+x2+x3≤9-x1-2x2+x3≥23x1+x2-3x3=5x1≤0x2≥0x3无约束

maxZ’=x’1－2x2+3(x’3－x”3)－x’1+x2+x’3－x”3+x4=9x’1－2x2+x’3

－x”3-x5=2－3x’1+x2－3(x’3

－x”3)=5x’1≥0x2≥0x’3≥0x”3≥0x4≥0x5≥0练习

minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2+x3≥-2x1≥0,x3≤0S.t.

minZ=

x1+2x2+3x3′x1+2x2+x3′≤52x1+3x2+x3′≥6

-x1-x2-x3′≥-2x1≥0,x3′≥0

标准化1解答过程标准化2minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)

+x3′≥6

-x1-(x2′-x2〃)

-x3′≥-2x1,

x2′,x2〃

,x3′≥0

标准化3minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃

)

+x3

′≤2x1,

x2′,x2〃,x3′≥0标准化4minZ=

x1+2(x2′-x2〃)

+3x3′

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4≥0标准化5minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=5

2x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4,x5≥0标准化6minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′+x6=2

x1,

x2′,x2〃,x3′,x4,x5,x6

≥0标准化7maxZ’=-x1-2(x2′-x2〃)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

线性规划解的概念可行解：满足约束条件(2)和(3)的解

X=(x1,x2,…,xn)T称为可行解最优解：使目标函数达到最大值的可行解基Basis设A是约束方程组的m

n维系数矩阵(Matrix)，其秩为mB是矩阵A中m

m

阶非奇异子矩阵则称B为线性规划问题的一个基即矩阵B由m个线性独立的列向量(vector)组成矩阵B是由m个线性独立的列向量组成。称Pj(j=1,2,…,m)是为基向量。与基向量Pj为相应的变量xj为基变量(basicvariables)，否则称为非基变量(

nonbasicvariables)。线性规划的基本概念线性规划的基矩阵、基变量、非基变量==目标函数约束条件行列式≠0基矩阵右边常数1可行解（feasiblesolution）：满足线性规划约束条件的解称为可行解。线性规划解的概念2最优解（optimalsolution）：使线性规划目标函数达到最优的可行解称为最优解。3基本解（basicsolution）：以线性规划约束等式的系数矩阵A中任意m行m列组成的m×m满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basicvariable），其余变量称为非基变量，令非基变量为零，可求得基变量的值，这样求出的解称为基本解。

4基本可行解（basicfeasiblesolution）：满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数≤基可行解(basicfeasiblesolution)：满足非负条件的基解(Basicsolution)。可行基(feasiblebasis)：对应于基可行解的基。非可行解可行解基解基可行解s.t.x1+3x2+x3£152x1+3x2-x3£18x1-x2+x3£3x1,x2,x3³0例化为标准形式stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x6³0基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x4=152x1+3x2=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2=152x1+3x2=18x1-x2+x6=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。3x2+x3+x4=153x2-x3=18-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=389例：maxz=-x1+2x2+０x3+０x4-x1+x2

+x3=2

x1+2x2+x4=6x1,x2,x3,x4

0转变为：

maxz=-x1+2x2-x1+x2

=2

x1+2x2=6x1,x2

0√√××√√

基基变量基解基可行解z值基本最优解-6／／40

√

基础解、基础可行解max z=x1+3x2 Ds.t. x1+x2+x3 =6 B -x1+2x2+x4 =8 C x1,x2,x3,x4≥0 x1=0

E x2=0Ax3=00x4=0OABCDE基变量x3

x4x1

x4x1

x2x2

x3x2

x4x1

x3非基变量x1

x2x2

x3x3

x4x1

x4x1

x3x2

x4xj<0--------x4x1基础可行解是是是是否否线性规划解的性质（几何意义）凸集概念：

设D是n维线性空间Rn的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2)

∈D，存在0<

<1使得x=

x(1)+(1-

)x(2)∈D,则称D为凸集凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。

两个基本概念：凸组合：

设x(1),x(2)…..x(k)是n维线性空间Rn中的k个点，若存在数u1,u2,….uk且0<ui<1(i=1,2,…k),

ui=1,使得x=u1x(1)+u2x(2)+…..+

uk

x(k)成立，则称x为x(1),x(2)…..x(k)的凸组合。两个基本概念：顶点：设D是凸集,若D中的点x不能成为D中任何线段上的内点，则称x为凸集D的顶点。即：若D中的任意两点x(1),x(2)

，不存在数

（0<

<1）使得

x=

x(1)+(1-

)x(2)成立，则称x为凸集D的一个顶点。线性规划解的性质定理1线性规划的可行域R是一个凸集，且有有限个顶点。定理2X是线性规划可行域R顶点的充要条件是X线性规划的基本可行解。定理3若线性规划有最优解，则必有基本最优解。定理4若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。——线性规划问题的可行域是一个凸集。——线性规划的每一个基本可行解对应凸集的每一个顶点。——若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。——若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。——最优解一定是基本可行解，但基本可行解不一定是最优解。第二章单纯形法第2章内容提要2.1单纯形法的一般原理2.2单纯形法的计算步骤2.3表格单纯形法2.4人工变量问题2.5解的讨论线性规划单纯形法

单纯形法(SimplexMethod)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法单纯形法线性规划问题的几何意义：凸集：没有凹入部分，内部没有空洞。实习圆、实心球体、实心立方体都是凸集；两个凸集的交集是凸集。若线性规划问题存在可行域，则可行域是凸集。线性规划问题的基可行解对应可行域的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。2.1纯形法的一般原理考虑线形规划问题：

maxZ＝CXAX＝bX≥0如果有可行域D＝{X∈Rn|AX=b,X≥0}非空有界，则D上的最优目标函数值Z＝CX一定可以在D的顶点达到。单纯形法的基本思路根据线性规划问题的标准型，从可行域中某个基可行解一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，问题就得到最优解。因此得到5个步骤：初始解

判优

判无界

换基

迭代确定初始的基本可行解确定初始的基本可行解＝确定初始的可行基初始的可行基确定——对应初始基本可行解确定最优解判别不妨假设

A=（B,N）（B为一个基）相应地有

Xt=(XB,XN)t

C=(CB,CN)

由式

maxZ＝CXAX＝bX≥0Z=

(CB,CN)(XB,XN)t=CBXB+

CNXNAX＝（B,N)(XB,XN)t=B

XB+N

XN=b因为B为一个基,det(B)>0有XB=B-1b-B-1NXN（2.1）Z=CBB-1b+(CN-

CBB-1N)

XN（2.2）令XN＝0，则基变量XB＝B-1bX

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

CBB-1b只要XB=B-1b>=0,Xt=（B-1b,0）>=0X为基础可行解,B就是可行基。对公式Z=CBB-1b+(CN-CBB-1N)

XN

（2.2）若满足CN-

CBB-1N<=0或CBB-1N-CN>=0

则对任意的x>=0有

Z=CX<=CBB-1b即对应可行基B的可行解x为最优解。σN＝(CN-CBB-1N)为非基变量XN的检验向量

定理（最优解判别准则）对于可行基B,若

CBB-1A-C>=0则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。

CBB-1A-C为检验数。由于基变量的检验数：CBB-1B-CB=0CBB-1A-C=（0，CBB-1N-CN）2.2单纯形法的求解步骤1、确定初始基可行解basicfeasiblesolution

先找出初始可行基，确定初始基可行解，建立初始单纯形表initialsimplextableau。若能从列向量中直接观察到存在m个线性无关的单位向量，经过重新安排次序便可得到一个可行基。对约束条件都是≤，则加入的松驰变量就构成初始基。对约束条件都是≥，且不存在单位矩阵的等式约束，就要采用人造基的方法：大M法、对偶单纯法。单纯形法的求解步骤2：判优2、检验数判别得到初始基可行解后，要检验其是否为最优解：若是，问题解决；否则继续下一步。最优性判别定理：若所有检验数都

j≤0，则找到最优解。单纯形法的求解步骤3：判无界3、判断是否无界在

j>0,j=m+1,…,n中，若有某个

k对应xk的系数列向量Pk≤0

，则此问题无界，停止计算；否则转入下一步。即在单纯形表中的某xk检验数

k>0

，而该列系数全小于0，则无界。单纯形法的求解步骤4：换基4、确定换入变量和换出变量换入变量=进基变量=EnteringVariable根据max(

j>0)=

k，确定xk为换入变量换出变量=出基变量=LeavingVariable按

规则计算，可确定xl为换出变量。单纯形法的求解步骤5：迭代

5、迭代以alk为主元素（pivotnumber）进行迭代，得到新的单纯形表。迭代又称旋转运算，或高斯消去法。单纯形法的求解步骤重复步骤2~5，直到终止。判优

换基

迭代判优

换基

迭代判优

换基

迭代判优

最优解换入变量的确定——最大增加原则假设检验向量σN＝(CN-CBB-1N)=(σm+1,σm+2,…,σn),若其中有两个以上的检验数为正，选取最大正检验数所对应的非基变量为换入变量。若：max{σj|σj>0,m+1≤j≤n}=σm+K

则选取对应的xm+k为换入变量。基本可行解的改进换出变量的确定——最小比值原则基本可行解的改进例：maxZ=5x1+2x2+3x3-x4+x5x1+2x2+2x3+x4=83x1+4x2+x3+x5=7x1,x2,x3,x4,x5≥0

其中用初等变换求改进了的基本可行解在系数矩阵A中存在一个单位矩阵B＝（p4,p5）取x4,x5为基变量，x1,x2,x3为非基变量，在这一情况下：（1）确定初始基本可行解令XN=0,XB=B-1b=b=基本可行解X=(0,0,0,8,7)T目标函数值：（2）检验X=(0,0,0,8,7)T是否最优：由最优解判别定理，非基变量检验数σ1＝3>0，σ3＝4>0,所以X=(0,0,0,8,7)T不是最优解①选取换入变量：因为max{3,4}=4,

按最大增加原则，取x3为换入变量②选取换出变量

因为：

所以取θ＝min(8/2,7/1)=4,

由最小取值原则选取x4为换出变量

（3）基本可行解X=(0,0,0,8,7)T的改进（4）求改进的基本可行解X’：再转向步骤（2）（2）检验X’=(0,0,4,0,3)T是否最优：由最优解判别定理，非基变量检验数σ1＝1>0，所以X‘=(0,0,4,0,3)T不是最优解①选取换入变量：因为σ1＝1>0,

按最大增加原则，取x1为换入变量②选取换出变量

因为：

所以取θ＝min(4/(1/2),3/(5/2))=6/5,

由最小取值原则选取x5为换出变量

（3）基本可行解X’=(0,0,4,0,3)T的改进（4）求改进的基本可行解X’’：再转向步骤（2）（2）检验X’’=(6/5,0,17/5,0,0)T是否最优：由最优解判别定理，非基变量检验数σ2,σ4,σ5

都小于0，所以X‘‘=(6/5,0,17/5,0,0)T是最优解表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。

一、单纯形法表CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n

1CB2xB2b2a21a22…a2j…a2n

2………………………CBnxBnbmam1am2…amj…amn

m检验数j-Z

1

2…

j…

n2.3表格单纯形法①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数

j=Cj-CBPj′，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个

k所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{

j｜

j＞0}=

k原则，确定xk为换入变量(进基变量)，再按

规则计算：

=min{bi′/aik′|aik′＞0}=bl′/aik′

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③步。二、单纯形法的计算步骤

例、某航空食品公司利用甲、乙、丙三种原料生产A1、A2、A3和A4四种食品，每月可供应该公司的原料及每种食品可获利情况如下表所示，试求该食品公司每月应如何安排生产计划，才能使总利润最大。

1500300025002000利润（元/吨）2000121丙3003110乙5002211甲每月原料供应量（吨）A4A3A2A1

消耗食品原料解：此问题的线性规划模型为MaxZ=2000x1+2500x2+3000x3+1500x4(1)

x1+x2+2x3+2x4

500(2)x2+x3+3x4

300(3)x1+2x2+x3

200(4)xi

0(i=1,2,3,4)(5)

x1+x2+2x3+2x4+

x5

=

500(2‘)x2+x3+3x4+

x6

=300(3’)x1+2x2+x3 +

x7

=200(4‘)xi

0(i=1,2,…,7)(5’)化为标准型：MaxZ=2000x1+2500x2+3000x3+1500x4(1)s.t.s.t.cBxBbx1x2x3x4x5x6x72000250030001500000x5x6x700050030020010111221123010001000102000250030001500000-z

3000

2503002002001初始单纯形表0-1-1-11000-3-1-2x330001100重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算

cBxBbx1x2x3x4x5x6x72000250030001500000x5x600200121230100010-1-1000-3500150000-3000-z

0

5033.3--1第2单纯形表0-1-11000-3-1-2x3300011001x415001/3-1/3-1/333.30-2/3033.3-1/3-1/3-7/3-4/30-500-2500-500-3000-650000检验数全非正,已经取得最优解,最优解为:X*=(0,0,200,33.3)TZ*=650000计算

非基变量检验数为检验数判别最终单纯形表FinalSimplextableau0

maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

三、单纯形法计算举例Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9检验数j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=42最优基

Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1x3x2x1最优基的逆

最优基和最优基的逆2.4人工变量问题用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。一、人工变量

采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有两种：大M法两阶段法大M法人工变量开始作为基变量，最后要换出来，全部成为非基变量，问题才有解。假设人工变量在目标函数中的价值系数为-M，M为很大的正数；只要基变量中还存在人工变量，目标函数就不能实现极大化。大M法：引入人工变量xn+i

≥0（i=1,…,m）及充分大正数M

。得到：Maxz=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.a11x1+a12x2+…+a1nxn

+xn+