线性规划问题总结

如何建立线性规划的数学模型；

线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？

如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？ 如何用单纯形方法求解线性规划问题？

如何确定初始可行基或如何求初始基本可行解？（两阶段方法） 如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件） 对偶单纯形方法适合解决什么样的问题？如何求解？

对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？

1、建立线性规划的数学模型：

特点：

（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；

（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；

（3）有一个需要优化的目标，它也是变量的线性函数。 2、线性规划的标准形有哪些限制？如何把一般的线性规划化为

标准形式？

目标求极小；约束为等式；变量为非负。

min zCXAXb X0T

例：把下列线性规划化为标准形式：

max z2x13x2x12x28x1 x2 1 x1 2x0,x012

解：令x1x3,x2x4x5,标准型为：

min z{2x33(x4x5)}x32(x4x5)x68x3 (x4x5) x71 x3 +x82x0,i3,4,5,6,7,8i,

3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？

（唯一最优解、无穷多最优解、无界解、无解）

线性规划解的性质：（基、基本解、基本可行解、凸集、顶点） 定理1 线性规划的可行域是凸集。

定理2 X是线性规划基本可行解的充分必要条件是X是可行域的顶点。

定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。

4、如何用单纯形方法求解线性规划问题？（单纯形表） 单纯形法的基本法则

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

min z2x15x2 x12x2x3 85x12x2 x4 20  4x2 x512x,x,x,x,x012345 x1 x2 x3 x4 x5 RHS z x3 x4 x5 z x3 x4 x2 z x1 x4 x2 2 1 5 0 2 [1] 5 0 0 1 0 0

5 2 2 [4] 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 -2 1 -5 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 -5/4 -1/2 -1/2 1/4 -1/4 -1/2 2 1/4 0 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用两阶段法来求解

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

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 第二阶段:

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.

cxaixbiaixbixj0xj0TTTmaxi1,,pip1,,mj1,,qjq1,,ns.t.bwwi0wi0AjwcjAjwcjTTT例写出下面线性规划问题的对偶问题

minz2x13x25x3x4 x1x23x3 x452x1 2x34x44 x2 x3 x46x, x,x0,x02341

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

maxy5w14w26w3w12w22w1w333w12w2w35w14w2w31w1,w20,w307、对偶单纯形方法适合解决什么样的问题？如何求解？

例：

min z15x124x25x3 6x2x3x4 2 5x12x2x3 x51 x1,x2,x3,x4,x50对偶单纯形法的基本法则

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

z x4 x5 z x1 -15 0 -5 -15 x2 -24 [-6] -2 0 x3 -5 -1 -1 -1 x4 0 1 0 -4 x5 0 0 1 0 RHS 0 -2 -1 8 x2 x5 z x2 x3 0 -5 -15/2 -5/4 15/2 1 0 0 1 0 1/6 [-2/3] 0 0 1 -1/6 -1/3 -7/2 -1/4 1/2 0 1 -3/2 1/4 -3/2 1/3 -1/3 17/2 1/4 1/2 写出对偶问题并求解？（利用互补松紧条件）

8、对于已经求解的一个线性规划问题如果改变价值向量和右端

向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？

例：线性规划

max z5x14x2x13x2902x1x280 x1 x245x,x012

已知最优表：

z x3 x1 x2 x1 0 0 1 0 x2 0 0 0 1 x3 0 1 0 0 x4 -1 2 1 -1 x5 -3 -5 -1 2 RHS -215 25 35 10 （1）确定x2的系数c2的变化范围，使原最优解保持最优；

（2）若c2=6，求新的最优计划。

解 （1）将上表中的第0行重新计算检验数，得到：

z x3 x1 x2 z x3 x1 x2 x1 5 0 1 0 0 0 1 0 x2 c2 x3 0 1 0 0 0 1 0 0 x4 0 2 1 -1 c2－5 x5 0 -5 -1 2 RHS 0 25 35 10 0 0 1 0 0 0 1 5－2c2 -175-10c2 2 1 -1 -5 -1 2 25 35 10 令c2－5≤0，5－2c2≤0，解得5/2≤c2≤5，即当c2在区间[5/2，5]中变化时，最优解X*=（35，10，25，0，0）T保持不变。

（2）当c2=6时，c2－5=1>0，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：

z x3 x1 x2 z x4 x1 0 0 1 0 0 0 x2 0 0 0 1 0 0 x3 0 1 0 0 -1/2 1/2 x4 1 [2] 1 -1 0 1 x5 -7 -5 -1 2 -9/2 -5/2 RHS -235 25 35 10 -495/2 25/2 x1 x2 1 0 0 1 -1/2 1/2 0 0 3/2 -1/2 45/2 45/2 故新的最优解为x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，最优值z*=495/2，

例 对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。

解原最优基为B=（P3，P1，P2），由表2-6可得：

1 2 -50 1 1B－1=0 -1 290B－180b3

250-5b3=80b3802b3（1）由

1 2 -50 1 1=0 -1 29080b3≥0

解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变，最优解为：

*x3250-5b3*x1=80b3*802b3x2，x4*=x5*=0，z*=5×（80－b3）+4×（－80+2b3）

=80+3b3

（2）当b3=55时，

250-5b380b3802b32525=30，以它代替表的b列，用对偶单纯形法继续求

解。

z x1 0 x2 0 x3 0 x4 -1 x5 -3 RHS -245 x3 x1 x2 z x5 x1 x2 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 -3/5 -1/5 -1/5 2/5 2 1 -1 -11/5 -2/5 3/5 -1/5 [-5] -1 2 0 1 0 0 -25 25 30 -230 5 30 20 故新的最优解为x1*=30，x2*=20，x5*=5，x3*= x4*=0，最优值z*=230。

整数线性规划0-1规划

如何建立整数线性规划的数学模型？

如何用图解法求解两个变量的整数线性规划问题？

割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？

分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？

如何建立0-1规划问题的数学模型？

如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？

1、 如何建立整数线性规划的数学模型？

2、 如何用图解法求解两个变量的整数线性规划问题？ 3、 割平面方法的基本思想？如何用割平面方法求解整数线性

规划问题？

例考虑纯整数规划问题

maxzx1x2

2x1x264x15x220

x10,x20且为整数解先不考虑整数条件，求得其松弛问题的最优单纯形表为： x1 z x1 x2 0 1 0 x2 0 0 1 13x3 -1/6 5/6 -2/3 x3+x4>=

33x4 -1/6 -1/6 1/3 RHS -13/3 5/3 8/3 由第二行可以生成割平面：

112引入松弛变量s1后得：－x3－x4+s1＝－

31233将此约束条件加到表中继续求解如下：

x1 z x1 x2 0 1 0 x2 0 0 1 x3 -1/6 5/6 -2/3 x4 -1/6 -1/6 1/3 s1 0 0 0 RHS -13/3 5/3 8/3 s1 z x1 x2 x3 0 0 1 0 0 0 0 0 1 0 [-1/3] 0 0 0 1 -1/3 0 -1 1 1 1 -1/2 5/2 -2 -3 -2/3 -4 0 4 2 所以原问题的最优解为：x1*=0，x2*=4，最优值z*=4。

4、 分支定界方法的基本思想？如何用分支定界方法求解整数

线性规划问题？

例 求解下面整数规划

maxz3x12x2

2x1x292x13x214且为整数值x10,x20(P0)

x1=3.25 x2=2.5 z(0)=14.755 X2<=2 (P1)

X2>=3

(P2)

x1=3.5 x2=2 z(1)=14.5 X1<=3 X1>=4 (P3)

x1=2.5

x2=3 z(2)=13.5 (P4)

x1=4 x2=1 z(4)=14 * x1=3 x2=2 z(3)=13 ×

5、如何建立0-1规划问题的数学模型？

6、如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？

例maxz5x14x23x3

x3x2x51232x17x23x352x2x325x3x22x371x0或1j=1,2,3j

（x1，x2，x3） （0，0，0） （0，0，1） （0，1，0） （0，1，1） （1，0，0） （1，0，1） （1，1，0） （1，1，1）

◎ × × √ √ √ √ √ 满 足 条 件 ？ ① √ √ √ √ × ② √ × √ √ ③ × √ √ ④ √ √ 满足所有条件？ × × √ × √ √ × z值 4 8 9 ①②③④5x14x23x34 ◎