1、第第1章章 线性规划线性规划线性规划模型及单纯形法线性规划模型及单纯形法 （2学时）学时）单纯形法续（单纯形法续（2学时）学时）对偶理论对偶理论 （2学时）学时）灵敏度分析及整数规划（灵敏度分析及整数规划（2学时）学时）单纯形法举例（单纯形法举例（1.4.3)人工变量法（人工变量法（1.4.4)重重 点：单纯形法，人工变量法点：单纯形法，人工变量法难难 点：人工变量法点：人工变量法基本要求：掌握单纯形法步骤及人工变量法基本要求：掌握单纯形法步骤及人工变量法 显然，显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解对应的基是单位矩阵。以下是初始单纯形表：以下是初始单纯形表：m其
2、中：其中：j=cj-cn+i aij 为检验数为检验数 cn+i=0 i=1,m i=1 an+i,i=1 ,an+i,j=0(ji)i,j=1,m1 确定初始基可行解：确定初始基可行解：令xj=0 j=1,n;则xn+i=bi i=1,m 是基本可行解。2 解的最优性检验：解的最优性检验：计算非基变量检验数计算非基变量检验数 m j=cj-cn+i aij，j=1,n i=1基变量检验数为基变量检验数为0，即即n+i=0 i=1,m若若 ，则该基可行解为最优解，否则转下面，则该基可行解为最优解，否则转下面若若 ，则该问题为无界解（无最优解）。否则转第，则该问题为无界解（无最优解）。否则转第3
3、步。步。3 解的改进：解的改进：确定换入变量确定换入变量 为换入变量为换入变量 确定换出变量确定换出变量 为换出变量为换出变量 换基迭代换基迭代 以以 为主元，为主元，将将 化为单位向量，主元为化为单位向量，主元为1，得到新的基，得到新的基可行解。转第可行解。转第2步。步。njj,.,1,00,0jjpkjnjkx,0max1lnikikimilxaab0min1lkakpChapter 14Chapter 15Chapter 16Chapter 17练习练习 用单纯形法求解用单纯形法求解 Max z=50 x1+100 x2 s.t.x1+x2+x3 =300 2 x1+x2+x4 =400
4、 x2+x5 =250 x1,x2,x3,x4,x5 0Chapter 18作业：习题作业：习题1 2，4，5，6，Chapter 110Chapter 111Chapter 112Chapter 113解：先标准化，再对第2，3个约束条件引入人工变量x6,x7，Chapter 114该问题的最优解X=（4，1，9）T,最优值w=-2Chapter 115（1-45）（1-46）Chapter 116Chapter 117Chapter 118例例1-16 用两阶段单纯形法求解例1-14 约束条件同例1-14Chapter 119Chapter 120该问题的最优解X=（4，1，9）T,最优值w=-2Chapter 121
