运筹学 --线性规划（02）

《运筹学 --线性规划（02）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、MaxS=CXs.t.AX=bX0基，基解，基可行解，可行基。⊙线性规划问题的可行域D是凸集。⊙顶点与基可行解相对应⊙线性规划问题的最优解，必定在D的顶点上达到。⊙目标函数在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）。第三节线性规划-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解

2、（另一个顶点），以改进初始解。线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。第三节线性规划-单纯形方法单纯形方法基本思路：1.从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。2.如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进3

3、.继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。初始解。一、消去法例1-18：一个企业需要同一两种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型maxS=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0解：引进松弛变量x3,x4,x5>=0数学模型标准形式：maxS=2x1+3x2s.t.x1+2x2

4、+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥0约束条件的增广矩阵为：121008（Ab)=40010160400112显然r(A)=r(Ab)=3<5,该问题有无穷多组解。令A=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5)A=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5)TB=(P3，P4，P5）=100010001x3,x4,x5是基变量，x1,x2,是非基变量。用非基变量表示

5、的方程：x3=8-x1-2x2x4=16-4x1(I)x5=12-4x2S=0+2x1+3x2称(I)为消去系统，令非基变量（x1,x2）T=（0，0）T得基础可行解：x(1)=(0,0,8,16,12)TS1=0经济含义：不生产产品甲乙，利润为零。分析：S=0+2x1+3x2（分别增加单位产品甲、乙，目标函数分别增加2、3，即利润分别增加2百元、3百元。）增加单位产品对目标函数的贡献，这就是检验数的概念。增加单位产品乙（x2）比甲对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变

6、量x5换成非基变量，称x5为换出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）增加单位产品甲（x2）比乙对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变量x5换成非基变量，称x5为换出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）事实上，当x1=0，有x3=8-2x2≥0x4=16≥0（Ⅱ）x5=12-4x2≥0min(8/2,12/4)=3,当x2=0时，x5=0。x5换出基变量。确定了换入变量x2，换出变量x5以后，得到

7、新的消去系统：x3+2x2=8-x1（1）x3=2-x1+（1/2）x5x4=16-4x1（2）(Ⅲ)即：x4=16-4x14x2=12-x5（3）x2=3-（1/4）x5其中（1）—1/2（3）S=9＋2x1-（3/4）x5令新的非基变量（x1，x5）=（0，0）T得到新的基础可行解：x(2)=(0,3,2,16,0)TS2=9经济含义：生产乙产品3个，获得利润9百元。这个方案比前方案好，但是否是最优？这个方案比前方案好，但是否是最优？分析：S=9＋2x1-（3/4）x5非基变量x1系数仍为正数，确定x1为换入变量。

8、在保证正消去系统的情况下，确定x3为换出变量。得到新的消去系统：这个方案比前方案，但是否是最优？分析：S=-180-x2+（3/2）x4非基变量x2系数仍为负数，确定x2为换入变量。在保证常数项非负的情况下，x1换入，x5=0。有x3=2-x1≥0x4=16-4x1≥0(Ⅵ)x2=3≥0min{2,4,-}=2确定x3为换出变量。