③运筹学 第一章线性规划 、单纯形法的预备知识 1。线性规划问题的标准型 Maxz=cx aX=b st X≥0 其中,A的秩为m(m≤n),b≥0 标准型的特征:Max型、等式约束、非负约束
http://www.tju.edu.cn 第一章 线性规划 一、单纯形法的预备知识 1. 线性规划问题的标准型 ⎩ ⎨ ⎧ ≥ = = 0 .. X bAX ts Maxz CX 标准型的特征：Max型、等式约束、非负约束 其中， A ×nm 的秩为 bnmm ≥≤ 0, 。）（
③运筹学 第一章线性规划 中◆线性规划问题的一般型如何化为 标准型? (1)如果目标函数求极小,则 f(x) Mn=CX一加负号→Maxz=CX (2)如果约束条件为不等式,则弓 入松弛或剩余变量 9x+4x<360 9x+4x+x=360 3称为松弛变量。问题:它的实际意义是什么? 煤资源的“剩余
http://www.tju.edu.cn 第一章 线性规划 线性规划问题的一般型如何化为 标准型？ （ 1）如果目标函数求极小，则 （ 2）如果约束条件为不等式，则引 入松弛或剩余变量 Min z =CX Maxz = − CX 加负号 / 1 + xx 2 ≤ 36049 1 + 49 2 + xxx 3 = 360 f x)( − f x)( * x x3称为松弛变量。问题：它的实际意义是什么？ —— 煤资源的“剩余
③运筹学 第一章线性规划 (3)如果存在自由变量,则:x=x-x,x2,x≥20 (4)右端项b;<0仅需将等式或不等 式两端同乘(-1) (5)对x<0令x=-x即可
http://www.tju.edu.cn 第一章 线性规划 （3）如果存在自由变量，则： （4）右端项 仅需将等式或不等 式两端同乘（-1） （5）对 0 令 ' −=≤ xxx 即可 < 0 i b 0,, ////// = − xxxxx kkkkk ≥
③运筹学 第一章线性规划 9x1+4x2<360 位易 练习:请将例1的约束 阵见 化为标准型 4x1+5x2<200 s t 3x1+10x2<300 x1.x2≥0 松 解:增加松弛变量x,x,x,则约束化为 9x1+4x2+x 360 数 4x1+5x2+x4 200心驰变量在月标函数 s, t 3x1+10x2 +x5=300中的系数是什么?成 x1,x2x,x,,x≥0 单
http://www.tju.edu.cn 第一章 线性规划 练习：请将例 1的约束 化为标准型 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≤+ ≤+ + ≤ 0, 300103 20054 36049 .. 21 1 2 21 21 xx xx xx xx ts ,,, 543 xxx ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + =+ =++ ++ = 0,,,, 103 300 54 200 49 360 .. 543 21 5 1 2 4 21 3 21 xxxxx xx x xxx xxx ts 解：增加松弛变量 则约束化为 位阵 易见，增加的松弛变量的系数恰构成一个单 I
③运筹学 第一章线性规划 般地,记松弛变量的向量为X,则 AX+Ⅸ=b s t ∫AX≤b s t x≥0 X.X>0 AX≥b AX-X=b Lx20 s t X.X≥0
http://www.tju.edu.cn 第一章 线性规划 一般地，记松弛变量的向量为 Xs，则 ⎩ ⎨ ⎧ ≥ ≤ 0 .. X bAX ts ⎩ ⎨ ⎧ ≥ + = 0, .. s s XX bIXAX ts ⎩ ⎨ ⎧ ≥ ≥ 0 .. X bAX ts ⎩ ⎨ ⎧ ≥ − = 0, .. s s XX bIXAX ts