xB x1 x2 x3 b 4 1 9 -2 x1 1 0 0 0 x2 0 1 0 0 x3 0 0 1 0 x4 1 3x5 ?2 30 2 31? 3-1 ?4 31? 3*****故最优解：x1?4,x2?1,x3?9,x4?x5?0. z*?2。
§1.6 单纯形法的评述
1． 非退化的情况
单纯形法
换入变量：当检验数有两个以上为正时，就取其中最大者，由此确定换入变量；若同时有多个最大的检验数，则取其中最小的下标为主元的列。
换出变量：当按最小比值确定主元的行号时，若同时有多个等值的最小比，则选取其中最小的下标为主元的行号，由此确定换出的变量。
定理1.在非退化的情况下，应用单纯形法经过有限次迭代，必可得到最优解或断定原问题无解。 2． 退化的情况
单纯形计算中用?规则确定换出变量时，有时存在两个以上相同的最小值，这样在下一次迭代中就有一个或几个基变量等于0，这就出现退化解。这时换出变量xl?0，迭代后目标函数不变，这时不同基表示为同一个顶点。 例1.
31x1?150x2?x3?6x44501?1x?60x?x3?9x4?x5?012?425??1x?90x?1x?3x?x6?0234?2150?x3?x7?0??x?0,j?1,...,7?jmaxz?
通过6次迭代还原（1955，Beale）。
3． 避免循环 Bland规则
（I）由min{j|?j?0}?k，确定xk为换出变量；
19
（II）按?规则（同单纯形法一致）。
定理2.按Bland规则迭代一定可以避免循环。 4． 单纯形法是非多项式算法
设输入数据的规模是l（通常与变量及约束数有关），设在最坏情况下运算次数是f(l)，这样的f(l)称为算法的计算复杂性。
多项式算法：f(l)是l的一个多项式或以多项式为上界； 指数算法：f(l)是l的一个指数式或以指数式为上界。 例如：l=60，f(l)?l3，100万次/秒的一台计算机需0.2秒； 但f(l)?3l，100万次/秒的10亿台计算机需100万年。 例：1972，Klee and Minty
nmaxZ??10(n?j)xjj?1?xj?2?10(j?i)xi?102j?2,j?1,...,n
?1?i?j???xj?0,j?1,...,n可行域有2n个顶点，迭代2n?1次，指数算法。 特别的，n=3
maxz?100x1?10x2?x3?1?x1?20x?x2?100?1 ??200x1?20x2?x3?10000?xj?0,j?1,2,3?1982年，Borgward及1983年Smale证明单纯形法的平均运算次数是多项式； 1979年，前苏联哈奇扬提出第一个多项式算法——椭球法；
1984年，美国Karmarkar给出Karmarkar算法——实用的多项式算法。
§1.7 单纯形法的矩阵描述
1． 标准形
maxz?cxAx?b x?0 20
?x?设A?(B,N)（B是可行基），x??B?，这里xB是基变量，xN是非基变量。
?xN?则Ax?b?xB?B?1b?B?1NxN，目标函数
z?CBxB?CNxN?CB(B?1b?B?1NxN)?CNxN ?CBB?1b?(CN?CBB?1N)xN这里C?(CB,CN)。 此时单纯形表为 xB 基 变 量 或 b xB I 0 xN B?1N B?1b -CBB?1b CN?CBB?1N xB 基 变 量 这里
b xB I xN B?1N B?1b -CBB?1b C?CBB?1A C?CBB?1A?(CB,CN)?CBB?1(B,N) ?(0,CN?CBB?1N)2． 非标准形
maxz?cxAx?b x?0化为标准形
maxz?cxAx?xS?b x?0，xs?0这里xS?(xn?1,...,xn?m)T。设B是一个可行基，且(A,I)?(B,N)，则
21
?x?z?(c,0)?? ?xS??CBB?1b?(CN?CBB?1N)xN对应于xN的检验数是：CN?CBB?1N???1C?CBA ?B?1对应于xB的检验数是：CB?CBBB??对应于xS的检验数是：0?CBB?1I??CBB?1 此时单纯形表 xB 基 变 量 或者
b x B?1A xS B?1 B?1b -CBB?1b C?CBB?1A ?CBB?1 xB 基 变 量
b x B?1A xS B?1 B?1b -CBB?1b 1 （C，0）-CBB?（A，I）第二章 线性规划的对偶理论
§2.1 问题
第一章考虑的例子
产品 设备 原料A 原料B 利润
22
Ⅰ 1 4 0 2元/件 Ⅱ 2 0 4 3元/件 8台时 16kg 12kg 问如何决策利润最大？
设x1,x2分别是生产Ⅰ，Ⅱ的件数，则有
maxz?2x1?3x2?x1?2x2?8?4x?16 ?1?4x2?12???x1,x2?0如果决策者不生产Ⅰ和Ⅱ两种产品，而是将设备、资源出租或外售，问决策者如何给每种资源定价？
设y1,y2,y3分别表示出租单位设备台时的租金和转让单位原材料A，B的附加额。
因为1个设备台时+4kg原料A=1个Ⅰ产品，可获利2元，则出租、转让的利润应不低于生产，故有
y1?4y2?2
同理
2y1?4y3?3
把所有设备和资源都出租和转让，其收入为
w?8y1?16y2?12y3
从工厂的决策者来看，当然w愈大愈好，但从接受着来看他的支付愈少愈好，所以工厂的决策者只能在w满足?所有产品的利润条件下，使其总收入尽可能的小，他才能实现其愿望，为此需解线性规划：
minw?8y1?16y2?12y3y1?4y22y1?2?4y3?3
yi?0,i?1,2,3称该线性规划为前面线性规划的对偶规划。
下面从另一角度来讨论，对线性规划（?）
maxz?cxAx?bx?0(?)
将其化为标准形
maxz?cxAx?xs?b x,xs?0 23