第2章 单纯形法

1、山西大学经济与管理学院山西大学经济与管理学院运筹学运筹学主讲：范建平主讲：范建平 博士博士第二章 单纯形法2.1 基本思想2022年3月7日星期一山西大学经济与管理学院 范建平22.1 基本思想2022年3月7日星期一山西大学经济与管理学院 范建平3p单纯形法（单纯形法（Simplex Method） ，1947年由美国学者年由美国学者George Dantzig首先提出。首先提出。p从内容上分从内容上分2种种n原本方法（原本方法（Primal Simplex Method）n对偶方法（对偶方法（Dual Simplex Method）p从形式上分从形式上分3种种n方程组形式（方程组形式（基本

2、思想基本思想）n表格形式（表格形式（运算步骤运算步骤）n矩阵形式矩阵形式*2.1.1 基本思路2022年3月7日星期一山西大学经济与管理学院 范建平4D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z=0等值线R2.1.1 基本思路2022年3月7日星期一山西大学经济与管理学院 范建平5p首先确定可行域首先确定可行域R内的一个极点作为内的一个极点作为始点始点，称为，称为初始基初始基本可行解；本可行解；p然后检验当前解（可行极点）是否最优，是则结束；然后检验当前解（可行极点）是否最优，是则结束；p否则，从该点出发，进化到另一极点，使目标函数值上否则，从该点出发，进化到另

3、一极点，使目标函数值上升（至少不降），又保达点可行；升（至少不降），又保达点可行；p如此不断迭代，直到目标函数值达到最大，或依法判明如此不断迭代，直到目标函数值达到最大，或依法判明无解。无解。2.1.2 唯一前提2022年3月7日星期一山西大学经济与管理学院 范建平6p【例例2-1】试用方程组形式的单纯形法，求解范例的试用方程组形式的单纯形法，求解范例的LP问题。问题。p解：范例的标准形如下：解：范例的标准形如下：12132412512345max321628. .2318,0zxxxxxxstxxxx x x x x【例2-1】2022年3月7日星期一山西大学经济与管理学院 范建平7 312

4、12124532=06282318zxxxxxxxxx（0）1,2,3,4,5jzxj 牢记变量 值须达最大，恒保其余变量均须非负，只需求解下列方程组： 345zxxx将 作为附加方程式（0）的永恒基变量，再取松弛变量 ， ， 作为约束方程式，的基变量，典式它们的列向量构成一个4阶单位阵，这说明方程组已是。如前1.2.4节所述，这是单纯形法的唯一前提。1212-3 -2=302zxzxxxLP将目标函数改写成 ，将其纳入约束方程组中，得到问题的等价问题。2.1.3 进化规程2022年3月7日星期一山西大学经济与管理学院 范建平8p1. 确定一个可行极点作为始点确定一个可行极点作为始点34500

5、3450,0,0,1,6,8 8Tx x xz 00在典式（）的约束方程组中，以=为基，得到相应的一个基本可行解是以为基变可行解的本=基量XBa a aX 325121412032=02218368zxxxxxxxxx（ ）03450,z=x x x各分量中，基变量的值，约束方程式，的右端常数；对应的目标函数值，附加方程式（0）对应的右端常数，0.恰为恰为XX 00z=很容易识别方程组的一个基本可行解，及其对应的目标函数值0.这样就能确定 这是典为始式的必然结果，（初始基）。点本可行解XX2.1.3 进化规程2022年3月7日星期一山西大学经济与管理学院 范建平9p2. 检验当前解是否最优，称

6、为最优性检验检验当前解是否最优，称为最优性检验 1,2,jjxjn将式（0）成为，其中 的系数。称为，记为可据以检这正是将式（检验方程检验0）引入方程验前解组的是否最优，数用意所在。01,2,LP0,jjjn最优性检验的准则：若一切检验数非负：，则问题的当前解最优；否则，只要存在一个负（1）（2）检验数则当前解非优。 1213241253=0062823182zxxxxxxxxx（ ）0120= 32=-对范例的当前解进行最优性检验如下：，可以判定当前解非优。XX201,z00 xx：的前两个分量意味着不生产甲、乙两种产品，利润为0；只要安排生产甲、乙两种产品就能范例的经济使利润值意义释。解增

7、大X2.1.3 进化规程2022年3月7日星期一山西大学经济与管理学院 范建平10p3. 从当前极点进化到另一极点，既使目标值上升，又保达点可行从当前极点进化到另一极点，既使目标值上升，又保达点可行 12,0z00 xx由于目前均为非基变量，如果让它们变为基变量，即让其取值从0变为正数，由是可知，就能使目标函数值 增大。121,200kxxxk 这就需要从当前的非基变量和选择一个变为基变量，即所谓选择“上进路线”。kkkxxx专业术语称为：；或者说选择一个非基变量，让选择一个进基变量进基。m：在一个线性规划中，基变量的个数恒注等于阶数意.选哪个xk作为进基变量？甲产品的单位利润为300元，乙产

8、品的单位利润为200元，所以选择生产甲产品2.1.3 进化规程2022年3月7日星期一山西大学经济与管理学院 范建平111345=33rmxxxxx范例的阶数，有 个基变量。在确定进基后，必须在原有的3个基变量， ，中选择一个变为非基变量。rrkrrxxxxx专业术语称为：选择一个；或者说选择一个基变量，让离基。即以变量替换离基1145113511340,0,6,8,18,0,0,0,0,0,0TTTTxx xxxxxx x0=上述基变量的替换意味着，要将当前的基本可行解转化为另一个=本解：或或基XXXX要保证新基本解的可行性。选哪个xr作为出基变量？ 要确保达点X1的可行性，X1的各分量除了

9、x1变为正数， x2仍为非基变量等于0，其他分量x3，x4，x5必须全都保持取值非负保持取值非负。2.1.3 进化规程2022年3月7日星期一山西大学经济与管理学院 范建平1231511416 -82-118-2618 2xxxxxxx00031452 1=66,0,0,8,6Txxx即所谓“”，从而，有式可得：0（离基），8，从而得到一个新的基本可行解，即所谓“”确定行程抵达的新极点=X134516,-=min 6,18 2 =6xxxxx不能取否则， ，全都为正数，无一离基。所以式（2 2）只能取等式，即有：1min 6,18 2 =6-x （有：2故2）345:(0)xxx从方程组中的式

10、，中，依次解出， ， ，并令其，可得 这就实现了一次基本可行解的转换，或可行基之间的变换，简称为（可行）基变换。相应的运算称为换基运算。单纯形法本质上就是一种迭代运算。 325121412032=02218368zxxxxxxxxx（ ）2.1.4 可行基变换2022年3月7日星期一山西大学经济与管理学院 范建平13p1.转换规则转换规则主元的确定主元的确定n通过进基、离基变量的更替，实现了从一个极点进化到另一个极点。通过进基、离基变量的更替，实现了从一个极点进化到另一个极点。为确保始终是在可行基或可行极点之间转换，必须遵循以下规则。为确保始终是在可行基或可行极点之间转换，必须遵循以下规则。确

11、定进基变量的规则最小检（1） 验数规则2|01,2,3jjkkkkkjxaxn min ，进按照：确定的对应的非基变量，同时，确定的系数列向量基列。为主a 12131241252=00160+ 2823183zxxxxxxxxxx（ ）进基主列2.1.4 可行基变换2022年3月7日星期一山西大学经济与管理学院 范建平14p1.转换规则转换规则主元的确定主元的确定确定离基变量和主元的规则最小（2） 比值规则1,2,20=3|0ikilikiklklkkraaimblaaaxbbamin最根据主列中中的一切正数按照式确定，以及对应的第 行（方程）为（主方程），主行中的原基变量就是离基变量，同时确

12、定主列中的主行小比值主素行元为主元。 12131241252=00160+ 28231368 18 21zxxxxxxxxxx（ ）进基主列比值主行主元离基2.1.4 可行基变换2022年3月7日星期一山西大学经济与管理学院 范建平15p2. 转换方法转换方法换基运算换基运算n换基运算即对当前方程组进行一系列换基运算即对当前方程组进行一系列初等变换初等变换，其目的是：，其目的是：将主列化成将主列化成单位向量单位向量，以符合典式。，以符合典式。n（1）将主元化为）将主元化为1。l用主元的倒数乘以主方程，得到新方程（用主元的倒数乘以主方程，得到新方程（a），称为），称为源方程。源方程。n（2）再将

13、主列中其余元素全部消去）再将主列中其余元素全部消去，都化为，都化为0.l欲消去主列中哪行非欲消去主列中哪行非0元素，就用其相反数乘以源方程（元素，就用其相反数乘以源方程（a）后，再）后，再加给该非加给该非0元素所在行。反复这样，主列化成元素所在行。反复这样，主列化成单位列向量单位列向量。 (1)由于主元为1，已经符合要求；将主方程填写入新方程组中，仍置于原行序处，作为，表上记号（如打），以备正确识别源方程、援用。2.1.4 可行基变换p范例的可行基变换范例的可行基变换 12131241252=00160+ 28231368 18 21zxxxxxxxxxx（ ）进基主列比值主元离基 100.(

14、2)再将方程组主列中其余非元素全部消去，都化为a 这样得到一个新方程组 ，如右所示。 2313242352+3=180628326zxxxxxxxxx（ ） 114150=,18,6,0,0,8,6Tz 换基运算可确保方程组 必定符合典式，得到以为基的基本可行解：其标值。比好目Ba aXaX2.1.4 可行基变换2022年3月7日星期一山西大学经济与管理学院 范建平17 23123242352=180106288 236 32zxxxxxxxxxx（ ）进基主列比值主行主元离基35133452355 32 3=22064 32 342 31 32zxxxxxxxxxx（ ） 1210=-2进行

15、最优性检验：式存在负检验数，可以判定当前解非优，仍需进行换。再对基变XX 按主元对方程组 进行一次换基运算，得到新方程组 ： *6,2,0,4,00T由于式中，所有检验数均为非负，故得到最优基本解：X*z =22 ,最优值：同图解法结果一致。2.2 基本方法2022年3月7日星期一山西大学经济与管理学院 范建平182.2.1 单纯形表上述方程组的初等变换，可以用形式更简明的增广矩阵的初等变换取代。上述方程组的初等变换，可以用形式更简明的增广矩阵的初等变换取代。1211211111,11222,12,10122-1000001001010jmmnmmnmnmnmmm mmnmnmccccccxx

16、xxxcxaabbbcxaacxaaz表一般单纯形表的基本结构比值基解检验行“”列填写基基变量；jc“ ”列填写基变量对应的价值系数；012,0,0Tmb bb“”列填写方程组的右端常数，他们就是同行基变量的，据此识别当前的基本可解行解：值X 0=(24a),1,2,(24 )jTBTjBjjzzcjnb00它们按如下公检验行对应上一节所谓检验方程。其中 为当前解对应的，目标函数值检验数。式算出：为C bC a2.2.2 单纯形法的运算步骤20LP=,1,12,2,TBTjBjjzcjn0将原问题化成标准形。在系数矩阵中找出或一个做初始基，建立典式构造满秩排列阵初始单纯形表。其检验行的数据按下

17、列公式算出：标准化建立单纯性表C bC a 单纯形法的运算步骤共有六步，其中前2步为预备步骤，后4步为迭代步骤。预备步骤仅为建立符合典式的初始单纯形表。而迭代步骤则是反复运用的主要步骤，包括：解的判断（3、4两步）和基变换（5、6两步）两部分工作，具体如下：2022年3月7日星期一山西大学经济与管理学院 范建平2.2.2 单纯形法的运算步骤21134,2,40,LP5jssjna只要检若所有检验数都非负：0，则当前解最优，停止；否则转。检验数而且它对应的系数列向量 中不含正数，即可判断最优性原问题解无验行界，检验解无界停止；否则中存在一个转判断。2.2.2 单纯形法的运算步骤|01,2,5,j

18、jkkkkkjnxxa 先按最小检验数规则确定进基变量和主列，即按确定的对应的非基变量，同确定主元时，确定的系数列向量min ，进基列。为主610.jlkca先画一个新表，调整“基”列、“ ”列，即以进基变量及其价值系数替代离基变量及其价值系数；其余基变量及其价值系数不变。然后，按主元对原表进行一次换基运算，其目的是，其中主元化为换基运，其余把主元素列化成算单位全化为向量=|0ilikiklklkrbbaalxaa再按最小比值规则确定主行和离基变量，从而确定主元，即按确min定，以及对应的第 行为，主行中的原基变量离基，同时确定主行、主列交叉处元素最小比值主行为主元。2.2.3 单纯形法的运算

19、过程 2022年3月7日星期一山西大学经济与管理学院 范建平23p【例例2-2】试用表格形式的单纯形法，再次求解范例的试用表格形式的单纯形法，再次求解范例的LP问题问题12132412512345max321628. .12318,0zxxxxxxstxxxx x x x x解：（第0次迭代）标准化满秩单位阵，符合典式，可以建立初始单纯形表。先画出表头2jc建立典式单纯形表基解2.2.3 单纯形法的运算过程 2022年3月7日星期一山西大学经济与管理学院 范建平24545132433261000802001800123000320002001100jxxcxxxxxx比值基解检建立典式单纯形验

20、表行00111222=0,0,06,8,180=0,0,0 1,0,233=0,0,0 1,0,2022,jTTBTTBjTTBzzcc 不必计算；只需计算目标值 和非基变量检计算检验行验数基变：量的检验数C bC aC a13=-3=-2最由于检验行中优性存在负检验数，,2，所以当检验前解非优。142由于负检验数,所对应的系数列向量中都含有正数，不属解无界判断故于解无界。2.2.3 单纯形法的运算过程 2511113111min -3 -2 =-53=6 186=min=121=6xxxa按最小检验数规则：，确定对应的非基变量,同时确定的系数列向量为主列。再按最小比值规则：，确定最小比值对应

21、的第1行位主行，主行中的原基变量（第1次迭。代）确定主进基离。元基为主元a12345345320000601006 1=6=08020100182300118 2=9032000jcxxxxxxxx检行比值基解验442515133200036010008020100603-201810-2300jxxcxxxxxx1比值基解检验行2.2.3 单纯形法的运算过程 2022年3月7日星期一山西大学经济与管理学院 范建平261336jcxx画一个新表，调整“基”列、“ ”列,即以进基变量及其价值系数 替代离基变量及其价值系数0；其余变量及其价值系换基运算数不变。2454531120060300080

22、2010018230010-3-2000301jcxxxxxxxx1比值基解检验行3=-2由于检验行中存在负检验数2，所以当最优前性检验:解非优。42由于负检验数所对应的系数列向量含有正数，不解无界判属于断故:解无界。2.2.3 单纯形法的运算过程 2022年3月7日星期一山西大学经济与管理学院 范建平272322252=-2=25axxx唯一负检验数对应的非基变量,同时确定 的系数列向量为主列。再按最小比值规则：对应的第3行位主行，主行中的原基变（第2次迭代）进基离基确定元。主量。为主元a513451422-5 3200036010008020108 24062-206 3=11802=-3

23、002jcxxxxxxxx表范例的迭代单纯形表主元的确定比值基解1检验行2.2.3 单纯形法的运算过程 3236jca画一个新表，调整“基”列、“ ”列,按主元对原表进行一次换换基运算基运算。134512422-6 3200036010004004 31-2 3220-2 301 322005 302 3jxxcxxxxxx表范例的最优单纯形表比值基解1检验行1*6,2,0,4-02-,2Tz在单纯性表计算过程中，除了初始单纯形表的检验行数据，须按公式（2 4）计算外，其余迭代单纯形表的检验行数据，都由由于所有检验数都非负，所以当前解最优，换基运算而得出，但公式（2 4。有：）仍有效X=(24

24、a),1,2,(24 )TBTjBjjzcjnb0C bC a2.3 其他法则2022年3月7日星期一山西大学经济与管理学院 范建平292.3.1 人工方法2022年3月7日星期一山西大学经济与管理学院 范建平30p如前所述，单纯形方法首先需要确定一个初始基本可行如前所述，单纯形方法首先需要确定一个初始基本可行解，这是通过确定解，这是通过确定典式典式自动得到的。自动得到的。n典式典式： 在约束方程组的系数矩阵中存在一个在约束方程组的系数矩阵中存在一个满秩排列阵满秩排列阵的的标准型标准型LP问题。问题。p这样就产生以下问题：这样就产生以下问题：n有些有些LP问题根本没有可行解，更无基本可行解；问

25、题根本没有可行解，更无基本可行解；n有些约束方程组线性相关，其系数矩阵为降秩矩阵；有些约束方程组线性相关，其系数矩阵为降秩矩阵；nLP问题的标准型多为非典式问题的标准型多为非典式。p本节介绍本节介绍LP问题问题典范化典范化的一般法的一般法人工方法人工方法n即即大大M法法和和两阶段法两阶段法【例2-3】试用单纯形法求解下列LP问题2022年3月7日星期一山西大学经济与管理学院 范建平311212212max232. . -23,0zxxxxstxxx x12123241234max23(0)2-=. . -2+=3,0zxxxxxstxxxx x x x所得模型并非所得模型并非典式典式解：标准化

26、模型。1212325254413max232-+=2. . -2+=3,0zxxxxxstxxxxxxxxx加非负人工变量加非负人工变量x5x4 ，x5的系数构的系数构成成满秩排列阵满秩排列阵，已成典式已成典式00,0,20,3TX x4 ，x5为基变量的初始为基变量的初始基本可行解基本可行解前前4个分量显然不是原个分量显然不是原方程的解。方程的解。 一般而言，给一个等式方程左端加上一个非负变量，多半会破坏原方程的解，除非该变量取值为0.启发：通过单纯形方法的换基运算，让人工变量全部离基，从而取值为0。关键是如何构造目标函数。1. 大M法2022年3月7日星期一山西大学经济与管理学院 范建平3

27、2p这里，这里，M0，是一个很大的正数。，是一个很大的正数。p大大M法的基本思想：法的基本思想：n在标准型在标准型LP模型（模型（1-2）的函数约束方程（）的函数约束方程（1-2b）左端，适当引入非负）左端，适当引入非负人工变量，为系数矩阵构造一个满秩排列阵，并将人工变量，为系数矩阵构造一个满秩排列阵，并将M作为人工变量在目作为人工变量在目标函数中的系数，构成人工问题。标函数中的系数，构成人工问题。n所谓所谓“适当引入适当引入”，即，即 “最少引入最少引入”，如，如【例例2-3】，只需引入一个人，只需引入一个人工变量就可构造工变量就可构造2阶（满秩）排列阵，从而构造成如下人工问题：阶（满秩）排

28、列阵，从而构造成如下人工问题：12512352412345max232-+=2. . -2+=3,0zxxMxxxxxstxxxx x x x x注意：用单纯形法求解这类人工问题，只要最终全部人工变量都能从“基”列中替换出去，则不论在第三步（最优解），还是第四步（解无界）结束，所得人工问题的结果就是原问题的结果；否则，若存在人工变量无法从“基”列中被替换出去，原问题无可行解。1. 大M法33p用大用大M法求解法求解【例例2-3】的人工问题的人工问题2345441512-7 M-3200-21-1010312010-3- -200311 2-1 201 20405 2-1 211 230-1 2

29、-3 20+3 2jxcxxxxxxxx表按大法求解【例2 3】迭代单纯形表M比值基解M检验行2M2MM检验行M1M(a)(b)32-7b=-3 22-7bLP在表的（ ）的检验行中存在一个检验数，它所对应的系数列向量中不含正数，可确定该人工问题解无界。在表的（ ）“基”列中不存在人工变量，故原问题也为无界。注意：一旦一个人工变量离基，即可删除该列。大M法不便于计算机编程；编程时往往采用两阶段法。2. 两阶段法2022年3月7日星期一山西大学经济与管理学院 范建平34p该法把问题的求解分为该法把问题的求解分为两个阶段两个阶段：n第第1阶段通过构造并求解人工问题来判断有无可行解，无则阶段通过构造

30、并求解人工问题来判断有无可行解，无则结束，有则能够获得原问题的一个初始基本可行解；结束，有则能够获得原问题的一个初始基本可行解；n然后转入第然后转入第2阶段求解原问题。阶段求解原问题。【例2-4】试用两阶段法求解例2-3中的LP问题2022年3月7日星期一山西大学经济与管理学院 范建平35p解解 第第1阶段阶段 构造并求解人工问题：构造并求解人工问题：512352412345max-2-+=2. . -2+=3,0wxxxxxstxxxx x x x x注意：目标函数是脱离原目标函数而虚拟的，必须纳入全部人工变量，并且其系数全都为-1；原变量的系数全部为0。 人工问题的目标函数值w0，当用单纯

31、形法求解这类人工问题而最终结果为：【例2-4】试用两阶段法求解例2-3中的LP问题2022年3月7日星期一山西大学经济与管理学院 范建平36p（1）若）若w*0,则意味着原问题无可行解，停止。则意味着原问题无可行解，停止。p（2）若）若w*=0,则意味着原问题有可行解，分以下情况：则意味着原问题有可行解，分以下情况：若基列中不存在人工变量，则直第2阶段接转入求解原问题。BlBllxnx若基列中存在人工变量，譬如第 行的基变量是人工变量，而且该行的前个变量(即原问题的变量)系数全都是0。这说明原问题的该约束与其他约束线性相关,是多余无用的,删除所在行和列,类似情况全都删除相应行、列。0,Bllk

32、lkkBllxnaaxx第 行的基变量是人工变量，而且该行的前个变量系数不全是0，譬如则以为主元进行一次换基运算，可以使原变量取代作基变量；类似情况全都这样处理。2. 两阶段法37p用两阶段法求解用两阶段法求解【例例2-3】的人工问题的人工问题2345454112-8 -0000-21-10103-12010-10011 2-1 201 20405 2-1 211 20000001jcxxxxxxxxx表按两阶段法求解【例2 4】迭代单纯形表1比值基解1检验行22第一阶段11检验行(a)(b)*2-800,bjw在表的（ ）的所有检验数全都非负，意味着人工问题已获最优解；最优值则意味着原问题有

33、可行解；基列中不可转存在入第人工变量，二阶段。2. 两阶段法p第第2阶段阶段 求解原问题求解原问题1123442-9 -320011 2-1 200405 2-1 2130-1 2-3 203jxxxxcxx第二阶段表按两阶段法求解【例2 4】初始单纯形表比值基解检验行132-9=-3 2LP在表的检验行中，存在一个负检验数，它所对应的系数列向量中不含正数，可确定原问题解无界。0-jjjjjccccz首先，建立原问题的初始单纯型表，这可以依据第一阶段的最终单纯型表来构建（1） 删除人工变量各列，清空“ 行”、“ 列”和检验行中一切原有数据。（2） 将原问题目标函数中的价值系数填入“ 行”、“

34、列”中。（3） 按公式（2 4）重新计算目标函数值和检验数，填入检验行中。然后，按单纯形法的迭代步骤，完成后续运算工作。 构建的初始单纯形表如下：【例2-5】试用单纯形法求解下列LP问题2022年3月7日星期一山西大学经济与管理学院 范建平391212212max2-. . -2,0zxxxxstxxx x1解：引入剩余变量x3、 x4，化为标准型。试用单纯形法求解下列LP问题再引入人工变量x5、 x6， 按两阶段法构造并求解人工问题。121221234max2-. . -2,0 xxzxxxxstxxx x x x15612251234566max-. . -2,0wx xxxxstxxxx

35、 x x x xxxx1【例2-5】试用单纯形法求解下列LP问题2022年3月7日星期一山西大学经济与管理学院 范建平40123456562-10 -0000-11-1-1010-2-110-101-300100jcxxxxxxxx表第按两阶段法求解【例2 5】初始单纯形表11比值基解一阶检验行1段112-10= -在表的检验行中，所有检验数都非负，人工问题已获最优解，其目标值30,判定原问题无可行解。课堂练习 1231323123min6818023. .232,0wyyyyystyyy yy*5 3, , 2 3202TYw其最优解和最优值为：2.3.2 相持规则2022年3月7日星期一山

36、西大学经济与管理学院 范建平42p当备择进基、离基变量相持不下时，如何选择？当备择进基、离基变量相持不下时，如何选择？1min|0.(23a)jjkkkx按最小检验数规则确定进基变量时，若有不止一个同时最进基相持的小，则相应的哪个进基呢？此即处理规则进基相持。kx尽管不同选择后续迭代繁简不一，但因目前没有简明方法据以恰当判断，因此，的处理规则是：在相持的诸变量任选一中，作为进进基相个持基变量。【例2-6】试用单纯形法求解下列LP问题2022年3月7日星期一山西大学经济与管理学院 范建平431212212max+. . 22,0zxxxxstxxx x1试用单纯形法求解下列LP问题解：引入松弛变

37、量x3、 x4，化为标准型,已经符合典式。121221234max+. . 2+2,0 xxzxxxxstxxx x x x1用单纯形法求解，在初始单纯形表就出现了x1、 x2的进基相持 。任选x1进基，又出现x3、 x4的离基相持。1234342-11 -61100011101 1=021012 2=0-1-100jcxxxxxx表【例2 】的初始单纯形表进基离基变量相持比值基解1检验行2.3.2 相持规则2022年3月7日星期一山西大学经济与管理学院 范建平44p按此规则续解按此规则续解【例例2-6】=min|0(2.23 )ilikiklkrbbabaax按最小比值规则确定离基变量时，若

38、有不止一个比值同时最小，则相应的哪个离基呢离基相持的？此即处理规则离基相持。342-11=,x x如表中：两个最小比值1对应的变量的离基相持，如何选择？这是一个重要问题，因为无论如何选择，换基运算后，必然导致一个，而这就有可能使后续的迭退代化基本可行解出现循环。rrxrx的处理规则：在相持的诸变量中,那个离基相作选下标最为离大的持基变量。【例2-6】试用单纯形法求解下列LP问题p在离基相持的在离基相持的x3、 x4中，选下标大的中，选下标大的x4离基，结果如下：离基，结果如下：23434312112-12 -61100011101 1=021012 2=0-1-10001 21-1 20=11

39、11 201 2210-1 211 2112-11110-111001000jcxxxxxxxxxx表【例2 】的迭代单纯形表突破离基相持退化比值基解1检验行0检验行0检验行(a)(b)(0) 在表（2-12a）得到以B1=a3、 a1为基的退化基本可行解及其目标值：X1=(1,0,0,0)T, z=1X1中有一个基变量x3=0,故谓之“退化”45 在表（2-12b）得到以B2=a1、 a2为基的最优基本可行解及其目标值：X*=(1,0,0,0)T, z*=1X*也是退化基本可行解2.3.2 相持规则2022年3月7日星期一山西大学经济与管理学院 范建平46p3. 多重最优解多重最优解p求解线

40、性规划有求解线性规划有4种可能的结果：种可能的结果：n唯一解；多重解；解无界；无可行解。唯一解；多重解；解无界；无可行解。p其中，、都已就单纯形法举例说明，只有多重其中，、都已就单纯形法举例说明，只有多重解未做说明。解未做说明。p单纯形法的单纯形法的3、4两步，分别给出两种停止运算的规两步，分别给出两种停止运算的规则。最优性检验步骤则。最优性检验步骤3，在迭代表格首次出现检验数全，在迭代表格首次出现检验数全部非负时（该表格称为部非负时（该表格称为最优单纯形表最优单纯形表，简称，简称最优表最优表），），算法结束。此时，算法结束。此时，如何识别多重解如何识别多重解？2.3.2 相持规则2022年3月7日星期一山西大学经济与管理学院 范建平47p【定理定理2-1】 多重最优解判别准则多重最优解判别准则=1LP0jjx非基变量的（） 在最优表中,有一个或更多个,则该问题有多重检验数最优解。2jjjxax（ ）若该的系数列向量中含有,则按单纯形法另作几次迭代，每次都选一个这样的进基，就能得到其他最优基本解或最正数优极点；*11221LP,=+01,2,1