2-1线性规划单纯形法`.ppt

小结：已知初始可行基求最优解 将线性规划问题化成标准形式。 例如：max S=10x1+3x2 +4 x3 -x4 + x5 s.t. 3x1+6x2+ 2x3 + x4 =19 9x1+3x2 + x3 + x5 =9 x1,x2 , x3 , x4 , x5 ≥0 用单纯形法解决线性规划问题。 X2 进基变量， X3出基变量， 主元（1） 第二行加上第一行的负1/2倍 基础可行解X(3)=(15,20,0,0)T, 也是最优解,其最优值 S = 1350 X(3)=(15,20,0,0)T 相当于Q2(15,20) X(1)=(0, 0,120,50)T 相当于O(0,0) X(1)=(0, 0,120,50)T 相当于O(0,0) X(2)=(25, 0,20,0)T 相当于Q1(25,0) X(2)=(25, 0,20,0)T 相当于Q1(25,0) X(3)=(15,20,0,0)T 相当于Q2(15,20) 课堂练习： P46 — 1.3 * * 1-5 线性规划-单纯形方法 单纯形方法基本思路： 从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。 线性规划-单纯形方法 单纯形方法基本思路： 从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。 如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。 线性规划（2）-单纯形方法 单纯形方法基本思路： 从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。 如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。 继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。 二、已知初始可行基求最优解（表格单纯形法） 例1-19 数学模型标准型: max S=10x1+3x2 +4 x3 -x4 + x5 s.t. 3x1+6x2+ 2x3 + x4 =19 9x1+3x2 + x3 + x5 =9 x1,x2 , x3 , x4 , x5 ≥0 初始可行基B1=(P4,P5)=I 基变量为x4, x5 非基变量x1,x2 , x3 初始基础可行解:X(0)=(0,0,0,19,9)T 计算检验数: 基变量检验数=0 非基变量检验数σj= Cj -CBTPj 目标函数值: S = CBT*b = 10 选择检验数最大的非基变量X2 作为进基变量,并选定该列. 利用最小比值原则: 计算各基变量的比值 利用最小比值原则: 计算各基变量的比值, 选择X5作为出基变量 进基变量X2与出基变量X5,交叉位置为主元(3). 第二行除以3 第一行加上第二行的（-6）倍 作主元运算,即用初等行变换把主元位置变成为1,该列元素变成0. 得到新的基础可行解:X(1)=(0,3,0,1,0)T S = 8 判断X(1)=(0,3,0,1,0)T S =8是否是最优解.再计算检验数. X3的检验数大于零. X3进基变量 X3的检验数大于零. X3进基变量,计算相应的比值.确定X2出基变量,主元为(1/3) 第二行乘以3 作主元运算, 得到新的基础可行解: X(2)=(0,0,9,1,0)T S=35 判断是否最优解:X(2)=(0,0,9,1,0)T S=35 计算检验数,所有检验数全小于零,达到最优解, X*=(0,0,9,1,0)T S = 35, 最优值为35. 单纯形法的几何意义： 例1．1生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大