《Chapter 1 1.1.3 线性规划的图解法》由会员分享，可在线阅读，更多相关《Chapter 1 1.1.3 线性规划的图解法（46页珍藏版）》请在金锄头文库上搜索。
1、1 1 Chapter 1 1.1.3 线性规划的图解法线性规划的图解法线性规划的图解法线性规划的图解法 1 1 8 7 6 5 4 3 2 2x1876543 O 10 9 x2 A B C E D F G H 1 2 3 f(x)=12 f(x)=24 f(x)=36 .36)(max , 6, 2: 0, 7 8 102 . . 46)(max 21 21 2 21 21 21 = = + + += xf xx xx x xx xx ts xxxf 最优解 2 线性规划问题的几个特点线性规划问题的几个特点线性规划问题的几个特点线性规划问题的几个特点： 线性规划问题的可性解的集合是凸集线性
2、规划问题的可性解的集合是凸集线性规划问题的可性解的集合是凸集线性规划问题的可性解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点线性规划问题的基础可行解一般都对应于凸集的极点线性规划问题的基础可行解一般都对应于凸集的极点线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的凸集的极点的个数是有限的凸集的极点的个数是有限的凸集的极点的个数是有限的 最优解只可能在凸集的极点上最优解只可能在凸集的极点上最优解只可能在凸集的极点上最优解只可能在凸集的极点上，而不可能发生在凸集而不可能发生在凸集而不可能发生在凸集而不可能发生在凸集 的内部的内部的内部的内部 3 1.2 线性
3、规划问题的单纯型解法线性规划问题的单纯型解法线性规划问题的单纯型解法线性规划问题的单纯型解法 1.2.1 线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式 为了使线性规划问题的解法标准为了使线性规划问题的解法标准为了使线性规划问题的解法标准为了使线性规划问题的解法标准，就要把一般形式化为标准形就要把一般形式化为标准形就要把一般形式化为标准形就要把一般形式化为标准形 式式式式 = = = = = = + = + = = = njmixb mibxa ts xcxf njx mibxa ts xcxf ji i mn j jij mn j jj j i n
4、j jij n j jj ,2 , 1 , 2 , 1 , 0, , 2 , 1 , . )(max ,2 , 1 ,0 , 2 , 1 ,),( . )(max(min) 1 1 1 1 LL L L L 4 变换的方法变换的方法变换的方法变换的方法： 目标函数为min型，价值系数一律反号。令 f(x) = -f(x) = -CX, 有 min f(x) = - max - f(x) = - max f (x) 第i 个约束的bi为负值，则该行左右两端系数同时反 号，同时不等号也要反向 第i 个约束为 型，在不等式左边增加一个非负的变量 xn+i，称为松弛变量；同时令 cn+i= 0 第i
5、个约束为 型，在不等式左边减去一个非负的变量 xn+i，称为剩余变量；同时令 cn+i= 0 若xj0，令 xj= -xj，代入非标准型，则有xj 0 若xj不限，令 xj= xj- xj， xj 0，xj 0，代入非标 准型 5 变换举例变换举例变换举例变换举例： =+ + =+ + = + + += + + + += 0, 200 400665 3004432 . . 0004423)(max: 0, , 200 40065 300432 . . 423)(min: 6543321 63321 53321 43321 6543321 213 321 321 321 321 xxxxxxx
6、xxxxx xxxxx xxxxx ts xxxxxxxxf xxx xxx xxx xxx ts xxxxf 标准型 不限 原非标准型 6 关于标准型解的若干基本概念关于标准型解的若干基本概念关于标准型解的若干基本概念关于标准型解的若干基本概念： 标准型有标准型有标准型有标准型有 n+m 个变量个变量个变量个变量， m 个约束行个约束行个约束行个约束行 “基基基基”的概念 在标准型中，技术系数矩阵有 n+m 列，即 A = ( P1, P2 , , Pn+m) A中线性独立的 m 列，构成该标准型的一个基基基基，即 B = ( P1, P2 , , Pm )， | B | 0 P1 , P2
7、 , , Pm 称为基向量基向量基向量基向量 与基向量基向量基向量基向量对应的变量称为基变量基变量基变量基变量，记为 XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量非基变量非基变量非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T，有 X= XB + XN 最多有个基 m nm C + 2 7 关于标准型解的若干基本概念关于标准型解的若干基本概念关于标准型解的若干基本概念关于标准型解的若干基本概念： 可行解可行解可行解可行解与非可行解非可行解非可行解非可行解 满足约束条件和非负条件的解 X 称为可行解可行解可行解可行解，满足约束条件 但不满
8、足非负条件的解 X 称为非可行解非可行解非可行解非可行解 基础解基础解基础解基础解 令非基变量非基变量非基变量非基变量 XN = 0，求得基变量基变量基变量基变量 XB的值称为基础解基础解基础解基础解 即XB = B-1b XB是基础解基础解基础解基础解的必要条件为XB 的非零分量个数 m 基础可行解基础可行解基础可行解基础可行解 基础解基础解基础解基础解 XB 的非零分量都 0 时，称为基础可行解基础可行解基础可行解基础可行解，否则为基基基基 础非可行解础非可行解础非可行解础非可行解 基础可行解基础可行解基础可行解基础可行解的非零分量个数 0, 则未达到最优 (5) (4) ) 3( )(
9、)()( (2) )( (1) )( 1 jj m iijij zc acz xf xf = += += = = =+ += = 检验数 机会成本 NN 1 BN 1 B NN 1 BNN NN 1 B NNB BNN BBNN XABCCbBC XAbBCXC XAbBX XAbBX bBXXA XCXC 3 13 1.2.4 标准型的单纯型算法标准型的单纯型算法标准型的单纯型算法标准型的单纯型算法 1 找初始基础可行基找初始基础可行基找初始基础可行基找初始基础可行基 对于(max,)，松弛变量对应的列构成一个单位阵 2 检验当前基础可行解是否为最优解检验当前基础可行解是否为最优解检验当前基
10、础可行解是否为最优解检验当前基础可行解是否为最优解 所有检验数cjzj0，则为最优解，否则 3 确定改善方向确定改善方向确定改善方向确定改善方向 从(cjzj) 0 中找最大者，选中者称为入变量入变量入变量入变量，xj* 第j*列称为主列主列主列主列 4 确定入变量的最大值和出变量确定入变量的最大值和出变量确定入变量的最大值和出变量确定入变量的最大值和出变量 最小比例原则 (1.2.4) 0min * * = ij ij i i a a b 14 1.2.4 标准型的单纯型算法标准型的单纯型算法标准型的单纯型算法标准型的单纯型算法 4 确定入变量的最大值和出变量确定入变量的最大值和出变量确定入
11、变量的最大值和出变量确定入变量的最大值和出变量 设第i* 行使最小，则第i* 行对应的基变量称为出变量出变量出变量出变量，第 i* 行称为主行主行主行主行 5 迭代过程迭代过程迭代过程迭代过程 主行主行主行主行i* 行与主列主列主列主列j* 相交的元素ai*j* 称为主元主元主元主元，迭代以主元主元主元主元为 中心进行 迭代的实质是线性变换，即要将主元主元主元主元ai*j*变为1，主列主列主列主列上其它 元素变为0，变换步骤如下： (1)变换主行变换主行变换主行变换主行 nmjaaa jijiji +=, 2 , 1 * L 15 1.3 人工变量的引入及其解法人工变量的引入及其解法人工变量的
12、引入及其解法人工变量的引入及其解法 1.3.1 当约束条件为当约束条件为当约束条件为当约束条件为“ ”型型型型，引入剩余变量和人工变量引入剩余变量和人工变量引入剩余变量和人工变量引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为1，不能构成初 始基变量，为此引入一个人为的变量（注意，此时约 束条件已为“=”型），以便取得初始基变量，故称为人 工变量 由于人工变量在原问题的解中是不能存在的，应尽快 被迭代出去，因此人工变量在目标函数中对应的价值 系数应具有惩罚性，称为罚系数。罚系数的取值视解 法而定 两种方法 大M法 二阶段法 16 1.3.2 大大大大M法的求解过程法的求解过程法的求解过
13、程法的求解过程 例例例例1.3.1 =+ =+ = + + += 0, 4 6 2 . . )7810max()(max 0, 4 6 2 . . 7810)(min 654321 5321 6421 6321 321 321 21 321 xxxxxx xxxx xxxx ts Mxxxxxf xxx xxx xx ts xxxxf 17 表表表表1.3.1 例例例例1.3.1的单纯型表迭代过程的单纯型表迭代过程的单纯型表迭代过程的单纯型表迭代过程 x1x2x3x4x5x6序 号CBXB b 108700Mbi/aij* M x6 6(2)10 1 01(3) 7 x3 41110 1 04
14、 6M28-2M7 M77M7M I 初 始 解 cj z j 2M3M10 M7 0 10 x1 311/201/201/26 7 x3 10(1/2)11/211/2(2) 371017/2 7 3/27 3/2 II cj z j 01/203/2 7M+3/2 10 x1 210 11 11 8 x2 20121 21 3610 8 6 26 2 III 最 优 解 cj z j 00 1 2 6 M+2 答：最优解为x1=2, x2=2, x3=0, OBJ=36 18 大大大大M法的一些说明法的一些说明法的一些说明法的一些说明 大M法实质上与原单纯型法一样，M可看成一个很大的常数
15、人工变量被迭代出去后就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明 原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易 4 19 1.3.3 二阶段法的求解过程二阶段法的求解过程二阶段法的求解过程二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而找 到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采 用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问 题无（可行）解 为了简化计算，在第一阶段重新定义价值系数如下： = = = = 不是人工变量时当 为人工变量时当 时目标函数为 不是人工变量时当 为人工变量时当 时目标函数为 jj jj jj jj xc xc xc xc 0 1 max 0 1 min 20 表表表表1.3.2 用二阶段法求解例用二阶段法求解例用二阶段法求解例用二阶段法求解例1.3.1的第一阶段的第一阶段的第一阶段的第一阶段 x1x2x3x4x5x6序 号CB XBb00000 1 bi/aij* 1 x6 6(2)10101(3) 0 x3 41110 1 04 6 2 1 010 1 I cjzj210100 0 x1 311/201/2
