运筹学 - 图文

运筹学第2章 单纯形法 2.1 单纯形法的基本思想

该方法简捷、规范，是举世公认的解决LP问，题行之有效单纯形法（Simplex Method）是美国著名运筹学家丹捷格（Dantzig）1947年首先提出的通用方法。

? 单纯形法不仅是解决LP问题的最基本的算法之一，而且成为解决整数规划和非线

性规划某些算法的基础。

2、单纯形法的3种形式—— 方程组形式（代数形式）、表格形式、矩阵形式

3、单纯形法的基本思路——基于LP问题的标准形，先设法找到某个基本可行解（称为初始基本可行解）；

开始实施从这个基本可行解向另一个基本可行解的转换，要求这种转换不仅容易实现，而且能改善（至少保持）目标函数值；

继续寻找更优的基本可行解，进一步改进目标函数值。当某一个基本可行解不能再改善时，该解就是最优解。（或者是出现无可行解、无最优解、无穷多最优解的情况） 2.1.1 方程组形式的单纯形法

例1 一个企业需要同一种原材料生产甲、乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，获得的利润也不相同（如下表）。请问，该企业应如何安排生产计划，才能使获得的利润达到最大？ 甲 乙 可利用的资源总量 原材料（吨） 2 3 100 加工时间（小时） 4 2 120 单位利润（百元） 6 4 解：该问题的LP模型为：

将该问题的LP模型化为标准形

max z ? 6x1?4x2?2x1?3x2?100?s.t. ?4x1?2x2?120?x,x?0?12

12

123

124

1234

函数约束的增广矩阵为：

很显然 R（A） = R（A，b）= 2 < 5，即该方程组有无穷多组解。 系数矩阵为： 1234

决策变量向量为： T

1234

?10?选取 B ? ? ? 3 ? 4 ? ? ? ? 为基，则 x , x 为基变量，x , 为非基变量

?01?341x2??

令非基变量 x 1 ? x 2 ? 0 ，则可以得到一基本 可行解为： X ? 0 , 0 , 100 , 120 T 下面的计算都是以它为初始点逐次实施转

0

换，故将其称为初始基本可行解。此时，Z=0，其经济含义为：该企业没 有安排甲、乙两种产品的生产，当然也就没有利润可言。

1234条典

? 初始基本可行解所对应的可行基是一个m阶的单位阵； ? 目标函数表达式中所有的基变量的系数全部为0。

? 这是单纯形法所必需的！！！ ? 分析目标函数表达式

1234

? 非基变量的系数都是正数，若将它们转换为基变量，目标函数值则就会可能增加。 ? 经济含义：每分别多生产一个单位产品甲、乙，目标函数值分别增加6、4，即利润

分别增加600元、 400元。

? 增加的单位产品对目标函数的贡献值，这就是检验数的概念。

? 只要目标函数表达式中还存在正检验数，就需要把它所对应的非基变量变为基变

量！

单纯形法一次只能把一个非基变量变为基变量

max z ? 6x?4x?100?2x?3x?x ?s.t. ?4x?2x ?x?120?x,x,x,x?0??2310100??A,b????4201120????????2310?A???4201????????X??x,x,x,x???max z ?6x?4x?0x?0xmax z ?6x?4x?0x?0x? 选择先将哪个非基变量变为基变量？

? 增加单位产品甲比增加单位产品乙对目标函数值的贡献大。（检验数大）

? 一般选择正系数最大所对应的那个非基变量作为换入变量，将它换入到基变量中 去，与此同时还要确定基变量中有一个要换出来变为非基变量！

? 增加单位产品甲比乙对目标函数的贡献值大（600>400），故先把非 基变量 x 1 变成基变量，称为让 x 1 进基，同时称 x 1为进基变量。

最大检验数规则

若记检验数为 ? ? 1 , 2 , ? , n ，其中包括 j j基变量的检验数（它们全部为0），最大检验数规 则的数学表达式为：

jjk

对于本例，则有 1故选择让 进基。

1? 当确定一个非基变量进基后，相应的就要从基变量中换出某一个基变量，使 其变为非基变量，称为让该变量离基，同时称其为离基变量。如何选择离基变量呢?

仍为非基变量即 2

31

41

?100120?120x1?min ?,?30?? 244??当且仅当 x 1 ? 30 时，原基变量中才有一个变量等于0，即 ，故

4选择 x 4 离基。因此可以确定：

?100120?120 x1?min ?,?30?? 4?4?2这样既确定了离基变量，同时又保证另外的基变量 x ? 0 ，也即保证了下面

3转换得到的解仍然是一个基本可行解。 记得：满足条典！！！

? 为了求得以 x x 3 为基变量的一个新的基本可行解，又为使其满足条典，以便检1,验它是否最优，必须对方程组进行一番初等变换，其主要目的是让进基变量 x 1的系数列向量变为单位向量。

? 在这里，我们把上式中的最小比值120/4的分母4称为主元。主元所在方程为主方

程。

??max ???0 ? ???xmax ?6,4??6????x2x?0?x?100?2x?0??x?120?4x?0x?0换基运算：

得到：

1? 2x2?x3?x4?40??2?1?x?1x ?x4?3012?24?z?6x1?4x211?? ?6?30?x2?x4??4x224??3 ?180?x2?x42令新的非基变量 x ? x ? 0 ,得到新的基本可行解: X1??30,0,40,0?T Z?18024? 经济含义——只安排生产甲产品30个单位，此时可获得利润180百元。 ? 这个方案比前方案优，但是否已经是最优？ ? 分析： 3

z?180?x2?2x4? 非基变量 x 2 的系数仍为正数，由最大检验数规则，则确定 x 2 为进基变量。再按最

小比值规则，确定 x 3 为离基变量。 ? 主方程中所含的基变量就是离基变量。

11? x?x?x4?20 23??24 ?13?x ?x?x4?2013?48?

24

344

34

最小比值规则

? 当确定进基变量后，以进基变量的系数列向量中的正数为分母，以相应的方程右端

常数为分子求最小比值，所得到的最小比值的分母就是主元。主元所在的方程中的基变量就是离基变量。即：

?bi?bl min ?ik?0??

?aik?alk

? 令新的非基变量 x 4 ? 0,得到新的基本可行解: X??20,20,0,0?T Z?200x 3 ?2

? 经济含义——分别生产甲、乙产品20个，此时可获得利润200百元。

3z?180?x?x211?3??180??20?x?x??x24?2?15?200?x?x24?? 分析

z?200?15x3?x424? 目标函数中的非基变量的系数无正数，即所有检验数小于或等于0

T 是最优解 ? 则有—— *

* 是最优值 2.1.2 单纯形法的几何意义

? 性质：LP问题的一个基本可行解与可行域的一个极点互相对应。 ? X ? 0 , 0 , , 120 T 对应O（0，0）点 1000

? X ? 30 , 0 , 40 , 0 T 对应C（30，0）点

1

? X ? 20 , 20 , 0 T 对应B（20，20）点 ,02例2 用单纯形法的方程组形式求解下列LP问题

max z?3x1?5x2

?8? x1

? 2x2 ?12?s.t. ?

?3x1?4x2 ?36

??x1,x2?0

将其化为标准形得： max z?3x1?5x2?0x3?0x4?0x5

?x3 ?8? x1

? 2x2 ?x4 ?12? s.t. ? ?x5?36 ?3x1?4x2 ?x1,x2,x3,x4,x5?0? ?101008???

A,b??0201012?

?3400136? ??

则该函数约束等式方程组有无穷多组解。

0 ? 为基矩阵 ? 取 ? 1 0

??B??010?

?001?? ??? 基变量为：

345

? 非基变量为： x1,x2? 令非基变量： x1?x2?0? 容易得到初始基本可行解为： X?0,0,8,12,36T z?0z?200?X??20,20,0,0????????R?A??R?A,b??3?5x,x,x0??0

2为进基变量

?0?x3?8

? ?x4?12?2x2?0 ?x?36?4x?02?5

?1236?12?x2?min?,??

?24?2

2是主元，其所在方程为主方程，且 x x44 为离基变量。? 此时基变量为： x3,x2,x5

? 非基变量为：

14 TX?0,6,8,0,12 z1?30? 得到另一基本可行解为： 1迭代结果

z?3x1?5x2 ? x1 ?x3 ?812?x4 ??3x?5?11?2 x ?x ?6?24

2?5 ?30?3x?x413x1 ?2x4?x5?12??2

1

??4???0,?5??1?0 2T**此时得到的基本可行解也就是最优解。即： 几何意义

2.2 单纯形法的计算过程2.2.1 单纯形表

? 方程组形式的单纯形法求解LP问题使用起来很不方便，为便于单纯形法的计算、

判断和检验，人们设计了若干种形式不同的迭代表格，但其基本思想都是一致的。下面的一种表格就是为了用更简洁、紧凑的方式描述方程组形式单纯形法的计算步骤，兼有增广矩阵的简明性和便于检验的优点而专门设计的，使用较为广泛，一般称为单纯形表。

cjcm?1cnc1?cm?初始单纯形表的一般形式

?i?????????

xm?1xnCBXBbx1?xm?

c1x1b11?0a1,m?1?a1n?1

c2x2b20?0a2,m?1a2n?2

????????

am,m?1cmxmbm0amn?m1??

?3,5??5????max?x,x??X??4,6,4,0,0? z?42检验行0?0cm?1??ciai,m?1?cn??ciaini?1i?1mm? ? ? ? ? ? CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的； b列中填入初始约束方程组右端的常数；

XB列中填入基变量，这里是x1，x2,…，xm； cj行中填入所有变量的价值系数c1,c2,…,cn；

θi列的数字在确定进基变量后，按θ规则计算后填入； 最后一行称为检验数行，对应所有变量xj的检验数是:

m

jiijjBj

i?1

2.2.2 单纯形法的计算步骤：1）把LP问题化为标准形式；

（2）在系数矩阵中找出或构造出一个m阶单位矩阵作为初始可行基，建立初始单纯形表； （3）计算各非基变量 的检验数，检查检验数，若所有检验数

j m则表示已得到最优解，可停止 计算。否则转入下一步。 (4) 在所有 j ? 0 中，只要有一个 ? r ? 0 所对应 jj?的系数列向量 ? r ? 0 ， i?1即一切 a ir ? 0 ?i ? 1 , 2 , ? ? ，则该LP问题无 ,m界解（即无最优解），停止计算。

jB否则，转入下一步。 (5) 根据最大检验数规则

jjk

c??ca?c?C?(j?1,2,?,n)??0,j?m?1,m?2,?n??c??ciaij ?c?C?jmax ???0 ? ???

确定 为进基变量，

k再按最小比值规则

il

ik

iklk

确定主元，同时也确定了主元所在行的基变量为离基变量。（6）以主元为轴心对当前表格进行换基运算，得到一个新的单纯形表，再返回第3步，继续进行迭代。 2.2.3 单纯形法计算之例 maxz?2x1?3x2?0x3?0x4?0x5

x1?2x2?x3?8

4x1??x4?16 4x2?x5?12

xj?0j?1,2,?,5

目标函数中各变量的价值系数

x?b?b??min??aa?0???a??

m

计算非基变量的检验数 jjiiji?1

jBj

? 各非基变量的检验数为

?1? ???1?c1?CB?1?2??0,0,0??4??2

?0? ?? ?2???

?2?c2?CB?2?3??0,0,0??0??3 ?4???

继续迭代得下表，可以看到所有检验数都已为非正，这表示目标函数值已不可能再增大，于是得到最优解。 cj→ 2 3 0 0 0

θ

CB XB b x1 x2 x3 X4 x5

2 x1 4 1 0 0 1/4 0

0 x5 4 0 0 -2 1/2 1

3 1 1/2 -1/8 0 x2 2 0 0 0 -3/2 -1/8 0

该LP问题的最优解为：

TX*?4,2,0,0,4

最优值为： *z?2*4?3*2?14

12单纯形法求解下列LP问题： 12

??c??ca ?c?C??? max z ?3x?2x??2x? x?2?s.t. ? x1?3x2?3?x,x?0?12用单纯形法求解下列LP问题： max z ?6x1?3x2?3x3

?3x1? x2? x3?60 ?2x?2x?4x?20?123 s.t. ? ?3x1? 3x2?3x3?60 ??x1,x2,x3?0

? 2.3 人工变量法：应用单纯形法求解LP问题时，首先将其化为标准形，

然后设法找出或构造出一单位阵作为初始可行基。当约束条件都是“≤”时，加入的松弛变量就可以做为初始可行基，这样我们就可以马上进入单纯形表的运算步骤。然而并非所有问题标准化之后我们都很容易得到一个明显的初始可行基，比如当约束条件有“≥”或“＝”型时，所加入的剩余变量就不能作为初始可行基中的基变量。为了满足单纯形法的条典要求，这时就需要我们去构造新的初始可行基。通常采用的是构造人造基的方法，即人工构造单位矩阵。这种方法称为人工变量法，所加入的变量对应称为人工变量。 人工变量法常用方法

max z ?2x1?x2?3x3? 大M法、两阶段法

设法找出或构造出下列LP问题的初始可行基

??x1?4x2?x3?5

? s.t. ?2x1?3x2?6 max z ?5x1?3x2?2x3?4x4?x,x,x?0?123

?5x1? x2? x3?8x4?10

?

s.t. ?2x1?4x2?3x3?2x4?10

?x,x,x,x?0 ?1234

min ?2x1?3x2?x3

x1?4x2?2x3?8?

? s.t. ?3x1?2x2 ?6 ?x,x,x?0?123

? 2.3.1 大M法：这种方法是在原LP问题的目标函数中添上全部 的人工变量，并令其系数为 ，而M是一个充 分大的正数，这样就将原问题转化为求解新构造 出的辅助问题：

max z ?c1x1?c2x2???cnxn ?Mxn?1?xn?2???xn?m

x n ? 2 , ?? 其中：x n ? 1 , , x n ? m 为人工变量。

大M法在求解LP问题时一般遇到的几种情况 ? 若用单纯形表求得新构造出的辅助问题有最优解，且最优解的基变量中不含有添入

的人工变量，则辅助问题的最优解去掉人工变量分量就构成了原LP问题的最优解；否则原LP问题无可行解。

???? 若辅助问题迭代最终结果为无最优解，如果此时对应的最终单纯形表基变量中无人

工变量，则原LP问题也为无最优解；否则为无可行解。

例：用大M法求解下列LP问题 123

123

123 123解：按大M法引入人工变量，构造新的辅助问题如下： max z ?3x1?x2?2x3?Mx4?Mx5

?6?3x1?2x2?3x3?x4

? s.t. ? x1?2x2? x3 ?x5?4 ?x,x,x,x,x?0?12345

此时可以看到迭代最终表中所有非基变量的检验数全为非正数，则辅助问题存在最优解为： T**

因为此时基变量中不含有人工变量，去掉人工变量，取辅助问题最优解的前3个分量，则

T得到原LP问题的最优解为：

X*?3,0,1 z*?7

练习：试用大M法求解下列线性规划问题 min ? ??3x1?x2?x3

? x1?2x2? x3?11

??4x? x?2x?3

?123 s.t. ? x3?1 ??2x1? ?x1,x2,x3?0? 解：先将原LP问题加入松弛变量x4，剩余变量x5化为标准形 ，然后加入人工变量x6,x7，得到辅助问题如下：

min z ??3x1?x2?x3?Mx6?Mx7

?11? x1?2x2? x3?x4

??4x? x?2x ?x5?x6 ?3?123s.t. ? x3 ?x7?1??2x1? ?x1,x2,x3,x4,x5,x6,x7?0?

因本例的目标函数是要求min，所以用所有非基变量的检验数≥0来判别目标函数是否实现了最小化，相应的应该是所有负检验数采用最小检验数规则选择进基变量，离基变量选择

max z ?3x?x?2x?3x?2x?3x?6?s.t. ? x?2x? x?4?x,x,x?0?X??3,0,1,0,0? z?7??

一、产大于销销地产地A1A2A3销量B153618B153618B291212B291212B327816B327816B40004产量1518174650?虚设一个销地50-46销地产地A1A2A3销量产量1518175050 ?初始基可行解产地销地5366121812162B191128140417B22157018B30B4产量15A1A2A3销量初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140 ?最优性检验产地销地553661218012-22-2162112814-6B19117204B22150317B30618B4产量15ui036A1A2A3销量vj非基变量x32的检验数?32= -2，即让非基变量x32进基。 ?闭回路法调整产地销地536B191B22B3015001164B4产量151817A1A2A3销量+6-1278-122 +x32 12418–x32 进基–最小调整量为12，x31 离基 ?最优性检验?基变量的检验数?ij= cij–ui–vj=0，且令u1 =0，计算位势量ui和vj产地销地5B1953186018021B22137281212-416B3015020142B46产量1518ui036A1A2A3销量vj3174-6所有非基变量xij的检验数?ij= cij–ui–vj≥0，即得最优解。 ?非最优方案的调整?所有偶点的值都加上调整量；所有奇点的值都减去调整量。产地销地53B19161861218122B22B30157001164B4产量151817A1A2A3销量120812 4基可行解：x13=15,x21=18,x22=0,x32=12,x33=1,x34=4，Z=116?最优性检验?基变量的检验数?ij= cij–ui–vj=0，且令u1 =0，计算位势量ui和vj产地销地5B1953186018021B22137281212-416B3015020142B46产量1518ui036A1A2A3销量vj3174-6所有非基变量xij的检验数?ij= cij–ui–vj≥0，即得最优解。 二、产小于销销地产地A1A2销量B1438B21410B3235产量1012222323-22?虚设一个产地销地产地A1A2A3销量B14308B214010B32305产量101212323 ?最优性检验产地A1A2A3销量vj销地437018210115200202B1110435B220B3产量1012101-2ui–检验数?ij≥0，得最优解:x12=10, x13=0, x21=7, x23=5, x31=1，Z=46–由于非基变量x33 的检验数?33=0，为多最优解。让x33进基,x31离基,得另一最优解:x12=10, x13=0, x21=8, x23=4, x33=1?初始基可行解产地A1销地4B11B22B3产量10A234103012A3销量07100518105初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=46 分析

利润=收入-成本，收入最大，成本最小，则利润最大。

收入：

? 每天供水总量是一常数，水价也是常数，则每天总收入也是常数。 ? 每天供水总量若能全部售出，每天总收入则能达到最大。 ? 丁区最高需求不限，每天总供水量能全售出。

? 每天总收入是常数，与水量分配无关，可以不与考虑。

? 成本：

? 各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。 ? 各区引水费不同，如果总的引水费达到最小，总成本则最低。 ? 如何分配水量，既满足最低需求，又使总的引水费最低？

? 最大需求量：

? 供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需

求量160-110+10=60。

? 四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于

销的不平衡问题。

? 产小于销的运输问题化为平衡问题，虚设水库D，供水量50。

? 各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单

位引水费（运费）为M。

? 各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故

单位引水费（运费）为0 。

三、生产调度问题

这里所说的生产调度问题是指对某产品在一一个总的计划周期内的某项既定总生产指标 （如总产量），应怎样分解到各个生产周期，才能既保证在总计划期内完成该项总生产指 标，又能使总生产费用最少。 下面举例说明如何把这类问题转化成运输 问题进行求解。

[例]拖拉机生产调度问题 前进拖拉机厂与农机供销站签订了一项生产100台某种小型拖拉机的合同。按合同规定，该厂要在今后4个月的每月内各交付一定台数的拖拉机。为此，该厂生产计划科根据本厂实际情况列出了一个生产调度数据表。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总数，但生产出来的拖拉机若当月不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用100元，问该厂应如何拟订最经济的生产进度？

?

月份合同规定交付台数/台生产能力/台单台成本/元1234合计15253525100303545201305000520051005300

本文来源：https://www.bwwdw.com/article/3gk6.html