教案标准型及解的几何意义资料.ppt

* (p1,p2, …,pn) ΣPjxj=b a11 a12 … a1n  a21 a22 … a2n  … … … am1 am2 … amn  x1x2 ? xn = xj≥0 (j=1,…,n) x1x2 ? xn Max z= x1x2 ? xn (c1 , c2, …,cn ) =Σcjxj =CX = Σaijxj =bi (i=1,…,m) AX = b X ≥0 b b1 b2 … bm * 如例1，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 x1 x2 O 4 Q2(4,2) Q1 Q3 Q4 3 A * 选基变量 基 基解 是否为基可行解 z值 （x1,x2,x4) 2 0 0 1 0 4 0 （2,3,0,8,0）T 是 13 （x1,x2,x3) 2 1 0 0 0 4 0 （4,3,-2,0,0）T 否 —— （x1,x3,x5) 2 0 0 0 0 4 1 （4,2,0,0,4）T 是 14 （x1,x3,x4) 1 0 0 1 0 0 0 |B|=0 无基和基解 —— （x1,x4,x5) 0 0 1 0 0 0 1 （8,0,0,-16,12）T 否 —— * 选基变量 基 基解 是否为基可行解 z值 （x2,x3,x4) 2 1 0 0 0 1 4 0 0 （0,3,2,16,0）T 是 9 （x1,x3,x5) 1 0 0 0 0 0 1 （4,0,4,0,12）T 是 8 （x2,x4,x5) 2 0 0 0 1 0 4 0 1 （0,4,0,16,-4）T 否 —— （x2,x3,x5) 2 1 0 0 0 0 4 0 1 |B|=0 无基和基解 —— （x3,x4,x5) 0 0 0 1 0 0 0 1 （4,3,-2,0,0）T 是 0 page() * * 第一章 线性规划 1.1线性规划问题模型及数学模型 1.1.1 问题的提出--引例 例1-1 某家具厂生产桌子和椅子两种家具，有关资料如表1-1所示。 产 品 工 时 单位售价 木 工 油漆工 桌子 4h/月 2h/个 50元/个 椅子 3h/月 1h/个 30元/个 供应量 120h/月 50h/月 问：企业应如何安排生产计划，使每月的销售收入最大？ * * * （1-3） （1-1） （1-2） 1.2线性规划问题的基本理论1.1.2 线性规划问题的几何意义 本节重点： 凸组合的概念 凸集的概念 线性规划基本定理 * * 1. 基本概念 ? 凸组合 设 ，若存在 （0 ? ? 1 ，且 ），使 则称X 为 的凸组合。 X1 X2 X 2 1 二维空间 两点连线上的任何一点都是这两点的凸组合 * (a) (b) (c) (d) (e) 凸集 * (a) (b) (c) (d) (e) 图中红粗线和红点是顶点。 * 2.线性规划问题的解的概念 (1-4) (1-5) (1-6) * 还可以广泛的矩阵形式来表示，如式（1-7） （1-7） C称为价值系数向量或目标函数系数向量，A称为技术系数矩阵或约束系数矩阵，b称为资源常数向量或右端常数向量。 * ? 基 A中的m × m 阶非奇异矩阵B ； （意味着A的秩为