第二章 线性规划问题及单纯形法.ppt

? + = + = n m j j j x z z 1 0 s —— Z 与当前非基变量的关系 由此可知，若存在 j s 0 (m+1 ￡ j ￡ n) ，则有 x j 0, 其他非基变量仍为零的可行解 ，其目标函数值为 这说明 当前解不是最优解。若所有 ￡ 0 (m+1 ￡ j ￡ n) ，则 z 0 为可行解所 能取得的目标函数最大值，说明当前解是最优解。故称 为检验数。将基变量的检验数0也视为其检验数，可得： , z x z z j j 0 0 + = s j s j s 注意：xj 的检验数 是当z 表示为非基变量的函数时 目标函数中xj 的系数。基变量的检验数为零。 最优性判别定理： 若基本可行解对应的检验数 ? 0 ( j=1，2，…,n) 则此解是最优解，否则不是最优解。 例10 中 z = 2x1+3x2 ， x1 ，x2为非基变量，?1=20， ?2=30，X(0)不是最优解。 3.基变换 求一个改进的、“相邻”的可行基，一个基变量 将变成非基变量（换出），一个非基变量将变成 基变 量（换入）。 (1) 换入变量的确定 一般，当 j max { j s | j s 0}= s k ，取 x k 为换入变量。 例 10 中， s 2 s 1 ，可取 x 2 为换入变量。 第k列为主元列。 第2列为主元列。 (2) 换出变量的确定 在 中，令xk0 ， 而xj =0(m+1 ? j ? n，j ? k)，要保持xi ? 0 ( i=1，2，…,m)， 即 若所有 则xk 可取无穷大，问题无最优解。 必须 Xk≤ 于是，当 为换出变量。 L行为主元行，alk为主元素 例：找出下述线性规划问题的全部基本解，指出其中的基本可行解，并确定最优解。 解:该线性规划问题的全部基本解见下表中的 ①-⑧， 打√者为基本可行解，注*者为最优解，z* ＝l9。 x1 x2 x3 x4 x5 z 是否基本可行解 ① 0 0 5 10 4 5 √ ② 0 4 5 2 0 17 √ ③ 5 0 0 5 4 10 √ ④ 0 5 5 0 ?1 20 × ⑤ 10 0 ?5 0 4 15 × ⑥ 5 2.5 0 0 1.5 17.5 √ ⑦ 5 4 0 ?3 0 22 × ⑧* 2 4 3 0 0 19 √ 六、线性规划标准型问题解的关系 约束方程的 解空间 基本解 可行解 非可行解 基本 可行解 退化解 如: max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 ?0 以(P3、P4、P5)作为基，令x1 = x2 =0，得到 X=(0，0，8，16，12)T 为一个基本可行解，对应图中O点； 2 x2 = 8 x4 =16 4 x2 +x5 =12 以(P1、P2、P5)为基，令x3 = x4 =0，可得X=(4，2，0，0，4)T是基本最优解，对应图中Q2点。 x1 x2 O 4 Q2(4,2) Q1 Q3 Q4 3 A 以(P2、P4、P5)作为基，令x1 = x3 =0，由 得X=(0，4，0，16，-4)T是个基本解，不是基本可行解，对应图中A点 某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下： 课堂作业：用图解法求解下列问题 产品名称 甲 乙 单位产品消耗原料 原料名称 可供利用的原料数量（T/日） 6 8 2 2 1 A B 产品售价 （千元/T） 3 2 根据市场调查，有如下资料： 1.乙产品的需求量至多 2 T/日; 2.乙产品的需求量比甲产品的需求量至多大 1 T/日。 求该厂产值最大的生产方案。 max Z= 3x1+2x2 x1+2x2≤6 2x1+x2≤8 x2≤2 x2 -x1≤1 x1，x2≥0 0 x1 x2 x1=10/3,x2 =4/3