运筹学基础-线性规划(4).ppt.ppt

思考题: 思考题: maxZ =3x 1 - x 2 -2 x 3 3x 1 + 2 x 2 -3 x 3 =6 x 1 - 2 x 2 + x 3 =4 x 1 , x 2 , x 3 ≥0 -2-13 41-21 6-323问题是:无标准的初始可行解问题是:无标准的初始可行解 x 1x 2 x 3b 已经是标准型,不需再划为标准型另例: 另例: ????????????0, 12 23 16 42 34 21 21 21 21xx xx xx xxZ Min??????????????? 12 23 16 42 0034 max 421 321 4321xxx xxx xxxxZ000 -3 -4 12 -1 023 16 0 -1 42x 1x 2 x 3 x 4 b 问题:无标准的初始可行基,如何利用单纯形法求解问题:无标准的初始可行基,如何利用单纯形法求解化为标准形不是标准的初始可行基不是标准的初始可行基三、人工变量问题三、人工变量问题?用单纯形法解题时,需要有一个单位矩阵作为初始基初始基。?当约束条件都是“≤”时,加入松弛变量就形成了初始基松弛变量就形成了初始基。?但如果存在“≥”或“=”型的约束, 就没有现成的单位矩阵就没有现成的单位矩阵。采用人造基的办法: 人为构造单位矩阵人为构造单位矩阵处理方法有两种: ––大大 M M 法法––两阶段法两阶段法(一)大(一)大 M M法法 maxZ =3x 1 - x 2 -2 x 3 3x 1 + 2 x 2 -3 x 3 =6 x 1 - 2 x 2 + x 3 =4 x 1 , x 2 , x 3 ≥0 . ?没有单位矩阵,不符合构造初始基的条件, 需加入人工变量需加入人工变量。 maxZ =3x 1 - x 2 -2 x 3 -M x 4 -M x 5 3x 1 + 2 x 2 -3 x 3 + x 4 =6 x 1 - 2 x 2 + x 3 + x 5 =4 x 1 , x 2 , x 3 , x 4 , x 5 ≥0 ?人工变量最终必须等于 0才能保持原问题性质不变。?为保证人工变量为 0,在目标函数中令其系数为目标函数中令其系数为-M -M 。?M为无限大的正数,这是一个惩罚项,倘若人工变量不为零, 则目标函数就永远达不到最优,所以必须将人工变量将人工变量逐步从基变量中替换出去替换出去。?如若到最终表中人工变量仍没有置换出去最终表中人工变量仍没有置换出去,那么这个问题就没有可行解,当然亦无最优解无最优解。大大M M法求解法求解按大 M法构造人造基,引入人工变量 x 4 , x 5 的辅助问题如下: ?例如 maxZ =3x 1 - x 2 -2 x 3 3x 1 + 2 x 2 -3 x 3 =6 x 1 - 2 x 2 + x 3 =4 x 1 , x 2 , x 3 ≥0 . maxZ =3x 1 - x 2 -2 x 3 -M x 4 -M x 5 3x 1 + 2 x 2 -3 x 3 + x 4 =6 x 1 - 2 x 2 + x 3 + x 5 =4 x 1 , x 2 , x 3 , x 4 , x 5 ≥0 初始单纯形表为: 初始单纯形表为: 0 -M -2 -1 3 41 1 -2 1 60 -3 23 -M 0 1~ 10M 0 -2-2M -1 3+4M 41 1 -2 1 60 -3 230 0 1