运筹学知识点总结

x3 x4 x5 z x3 x4 x2 z x1 x4 x2 1 5 0 2 [1] 5 0 0 1 0 0

2 2 [4] 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 -2 1 -5 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 -5/4 -1/2 -1/2 1/4 -1/4 -1/2 2 1/4 8 20 12 -15 2 14 3 -19 2 4 3 最优解X*=（2，3，0，4，0）T，z*=-2×2-5×3=-19。 5、如何确定初始可行基或如何求初始基本可行解？（两阶段方

法）

例 求下列LP问题的最优解

min z?3x1?x2?x3? x1?2x2?x3?11???4x1?x2?2x3?3 ???2x1 ?x3?1?x,x,x?0?123用两阶段法来求解

它的第一阶段是先解辅助问题：

5

min g?x6?x7? x1?2x2?x3?x4 ?11???4x1?x2?2x3 ?x5?x6 ?3 ?

??2x1 ?x3 ?x7?1?x,,x?0?17 g x4 x6 x7 g x4 x6 x7 g x4 x6 x3 g x4 x2 x3 x1 0 1 -4 -2 -6 1 -4 -2 0 3 0 -2 0 3 0 -2 x2 0 -2 1 0 1 -2 1 0 1 -2 [1] 0 0 0 1 0 x3 0 1 2 1 3 1 2 [1] 0 0 0 1 0 0 0 1 x4 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 x5 0 0 -1 0 -1 0 -1 0 -1 0 -1 0 0 -2 -1 0 x6 -1 0 1 0 0 0 1 0 0 0 1 0 -1 2 1 0 x7 -1 0 0 1 0 0 0 1 -3 -1 -2 1 -1 -5 -2 1 RHS 0 11 3 1 4 11 3 1 1 10 1 1 0 12 1 1 第二阶段:

6

x1 -3 3 0 -2 -1 3 0 -2 x2 1 0 1 0 0 0 1 0 x3 1 0 0 1 0 0 0 1 x4 0 1 0 0 0 1 0 0 x5 0 -2 -1 0 1 -2 -1 0 RHS 0 12 1 1 -2 12 1 1 z x4 x2 x3 z x4 x2 x3 原问题无界。

6、如何写出原问题的对偶问题？如果已知原问题的最优解，如

何求解对偶问题的最优解？ min s.t.

cTxaiTx?biaiTx?bixj?0xj??0i?1,j?1,,p,m,n,qi?p?1,j?q?1,maxbTws.t.wi??0wi?0ATjw?cjATjw?cj例 写出下面线性规划问题的对偶问题

minz?2x1?3x2?5x3?x4? x1?x2?3x3? x4?5??2x1 ?2x3?4x4?4?? x2? x3? x4?6?x, x,?12x3?0,x4??07

解：原问题的对偶问题为：

maxy?5w1?4w2?6w3?2?w1?2w2?w ?w3?31????3w1?2w2?w3??5

?w?4w?w?1123?

??w1,w2?0,w3??07、对偶单纯形方法适合解决什么样的问题？如何求解？ 例：

min z?15x1?24x2?5x3? 6x2?x3?x4 ?2? ?5x1?2x2?x3 ?x5?1 ?x,x,x,x,x?0?12345对偶单纯形法的基本法则

法则1 最优性判定法则（检验数全部小于等于零时最优） 法则2换出变量确定法则（谁最负谁出基） 法则3换入变量确定法则（最小比值原则） 法则4 换基迭代运算法则

z x4 x5 z x2 x1 -15 0 -5 -15 0 x2 -24 [-6] -2 0 1 x3 -5 -1 -1 -1 1/6 x4 0 1 0 -4 -1/6 x5 0 0 1 0 0 RHS 0 -2 -1 8 1/3 8