北京交通大学 运筹学 教案标准型及解的几何意义(改).pptVIP

page() * * 1．3 线性规划问题的标准形式 ? 为了求解LP问题，必须统一其模型，本课程选用标准型式为 （1) 目标函数为求最大 对于目标函数是求最小怎么办？ min Z=1000 x1+800 x2 令：z’= -z, 则minz=maxz’ maxZ’= -1000 x1-800 x2 （2)约束条件均用线性等式方程来表示， 且右边常数项均非负。 实际情形约束条件显然不可能都是等式关系。 当表达式中含“≤”时 可在约束条件左边加上一个非负的变量——松弛变量，使原来的“≥”变为“＝”； max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 ?0 max z = 2x1 + 3x2 s.t. x1 + 2 x2 ? 8 4 x1 ? 16 4 x2 ? 12 x1，x2 ?0 当表达式中含“≥”时， 可以在约束条件左边减去一个非负变量——剩余变量， 使原来的“≥”变为“＝”。 目标：min f =1000 x1+800 x2 约束条件： x1 ≥1 0.8 x1+ x2 ≥1.6 x1 ≤2 x2 ≤1.4 x1、x2 ≥0 maxz＝–minz＝－1000 x1－800 x2＋0·x3＋0·x4＋0·x5＋0·x6 s．t． x1 －x3 ＝1 0.8 x1+ x2 －x4 ＝1.6 x1 ＋x5 ＝2 x2 ＋x6＝1.4 x1、x2、x3、x4、x5、x6≥0 （3）所有变量要求非负 现实中，有些变量可能从物理意义或经济意义上讲没有非负要求 min z =x1－x2＋4 x3 s．t． 3 x2－4 x3 ≥－9 －x1 + x2 ≥6 5 x2＋2 x3 ≤16 x1 ≤0 ，x2 ≥0， x3无符号限制 解：令x1’=－x1，x1’≥0， x3 = x3’－x3’’, x3’、x3’’ ≥0 将第一个约束条件两端乘“－1”并加入松弛变量x4， 第二个约束减剩余变量x5，第三个约束加入松弛变量x6，代入整理后得： maxz ’=x1’＋x2－4 x3’＋4 x3’’ ? s．t． －3 x2＋4 x3’－4 x3’’＋x4 ＝9 x1’ + x2 －x5 = 6 5 x2＋2 x3’－2 x3’’ +x6 = 16 x1’， x2， x3’、 x3’’，x4，x5，x6≥0 练习： min z =2x1－x2＋2x3 s．t． －x1＋x2＋x3 ＝4 －x1 + x2 －x3 ≤ 6 x1 ≤0 ，x2 ≥3， x3无符号限制 max z =2x1+x2＋3x3 ＋x4 s．t． x1+x2＋x3 ＋x4 ≤ 7 2x1-3x2＋x3 ＝-8 －x1-2x2＋2x4 ≥ 1 x1 , x3 ≥ 0, x2 ≤ 0， x4无符号限制 再思考：如果x有区间限制怎么办？ 经过上述过程，可得到线性规划问题数学模型的标准形式为： max z =c1x1 + c2x2 +···+ cnxn (1.1) s.t. a11x1 + a12x2 +···+ a1nxn = b1 a21x1 + a22x2 +···+ a2nxn = b2 ··· ··· (1.2) am1x1 + am2x2 +···+ a