水资源系统分析-第2章线性规划与单纯形法.pptxVIP

第二章 线性规划;1 一般数学模型;例2 某灌区在年初估算可供水量为360万m3,计划灌溉小麦、玉米两种.总面积1000hm2,两种作物的毛灌溉定额及灌溉净效益如表，问该年两种作物的种植计划如何安排可使灌溉总净效益最大？ ;模型;;;;Obj. minf(x)=c1ax1a+c1bx1b+…+c2cx2c;规划模型的要素 决策变量：规划的措施、方案，是需要 确定的未知变量。 目标函数：规划的目的和用要求 约束条件：决策变量的取值范围 线性目标和约束组成线性规划模型;产生和发展 19世纪，法国科学家Fourier提出线性规划。 1939年苏联数学家康托维奇：机器负荷分配、原材料的合理利用等生产组织问题。 二战期间开始应用于军事规划 　(英、美)。1947年， Dantzig 　 美国空军----斯坦福大学教授， 　提出了单纯形法求解线性规划问题。 “线性规划之父”。;Dantzig 「配餐问题」;线性规划一般形式: ob. Max(min) Z=c1x1+c2x2+…cnxn (1.1) s.t. a11x1+a12x2+…+a1nxn≤(≥,=)b1 a21x1+a22x2+…+a2nxn ≤(≥,=)b2 ..... am1x1+am2x2+…+amnxn ≤(≥,=)bm x1,x2,….xn≥0;简写形式;向量形式;矩阵形式: ob. Max(min) Z=c1x1+c2x2+…cnxn (1.1) s.t. a11x1+a12x2+…+a1nxn≤(≥,=)b1 a21x1+a22x2+…+a2nxn ≤(≥,=)b2 ..... am1x1+am2x2+…+amnxn ≤(≥,=)bm x1,x2,….xn≥0;1.3 线性规划的标准型;目标函数为求极小值 变量X小于等于0 X=0 X’=-X=0 c. 变量X无约束 X=X`-X``; X`,X``=0; ;d. 约束条件为不等式 ;将下面的模型化为标准型;;将下列LP问题化为标准型 Ob. Min Z=2x1+3x2 s.t. ;Max z’=-2x1-3x2+0x4-0x5+0x6+0x7 ;1.4 线性规划问题的解;基 B为A的一个m阶的满秩矩阵，则为一个基。 Pj，基向量；xj，基变量，其他非基变量。;;基可行解 满足非负约束的基解。 可行基 对应基可行解的基。 满意解 可行不最优的解。;例5 ;系数矩阵;;; 找出下面模型的一个基，求基解，判断是 否可行基。 Max z=x1-2x2+3x4-3x5+0x6+0x7 ;;2 图解法;求解的直观原理;ob: max z=2 x1+3 x2 s.t x1+2 x2 ≤8 4x1≤16 , 4x2≤12 2x1+2x2 ≤12 x1≥0, x2≥0 ;O;O;无界解;无解:无可行域;图解法练习 ;;3 单纯形法原理;顶点：C中点X，若不在C中任何其他两点的连线上，则为顶点。;扩展到n维;3.2 几个基本定理;证明：;引理 可行解X=（x1,…,xn）为基本可行解的充要条件是X的正分量对应的系数列向量是线性独立的。 证明：（1）必要性 基本可行解 X的正分量对应的系数列向量是线性独立的。 （2）充分性 X的正分量对应的系数列向量是线性独立的 基本可行解 ;基可行解 满足非负约束的的基解。 由于非基变量为0，所以基可行解（x1…xm）中正分量集合不超过m，其对应系数列向量也不超出（p1…pm） （p1…pm）线性独立，其子集必然线性独立。 ; P1,P2,…,Pk线性独立，若P的秩为m，k=m，恰构成一个基，X为基可行解。;基本可行解