第2章__线性规划.pptVIP

§2.1 线性规划的数学模型 线性规划模型特点 决策变量：向量(x1… xn)T 决策人要考虑和控制的因素非负 约束条件：线性等式或不等式 目标函数：Z=?(x1 … xn) 线性式，求Z极大或极小 隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值 应 用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用) 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件 §2.2 线性规划的标准型 §2.3 图解法 总结 §2.4 LP问题解的性质 X(1) , X(2) , … ,X(k) 是n维欧氏空间中的k个点，若有一组数 μ1 , μ2 , … , μk 满足 0 ? μi ?1 (i=1,… ,k) 凸集D, 点 X?D，若找不到两个不同的点X(1) , X(2) ?D 使得 X=? X(1) +(1- ? ) X(2) (0? 1) 则称X为 D的顶点。 证明： 设LP问题的可行解域为集合C C={ X| AX=b X ? 0 } 任取X(1) , X(2) ?C, 则 X=? X(1) +(1- ? ) X(2) ? 0 (0 ? ? ? 1) 又因为 A X(1) =b， A X(2) =b 所以 AX=A[? X(1) +(1- ? ) X(2) ] = ? b +(1- ? ) b=b 则 X?C，C为凸集 只须证明： D的k个顶点X(1) , … ,X(k) ，有 0 ? μi ?1， 使 X= μ1 X(1) + … + μk X(k) LP问题解的性质 若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。 §2.5 单纯形法 单纯形法基本步骤 Pm+k = B-1Pm+k = a1m+k amm+k … ③ 基变量XB = B-1b = b1 bm … 由② 、③，用最小? 比值法得主元arm+k ④ 主元已知，新基B确定。返回(1) (二)、改进单纯形法 对 maxZ=CX AX ? b X?0 A=(P1 P2 … Pn) (1)、已有初始可行基B，求B-1 ， XB = B-1 b (2)、计算λj = Cj -CB B-1Pj 若全部 λj ?0，则计算Z0 = CB B-1 b, 停；否则，取λm+k =maxλj ， Xm+k换入。 λj0 (3)、计算Pm+k = B-1Pm+k ，若Pm+k ?0，则无有限最优解, 停；否则 (5)、新基B。转(1)。 θ=min bi Aim+k arm+k 0 = br arm+k Xr 换出 (4)、最小θ比值法： (5)、1) 求初等变换矩阵Er (r ?换出变量在基中的位置) B=(P1 … Pr-1 Pr Pr+1 … Pm ) B=(P1 … Pr-1 Pm+k Pr+1 … Pm ) BB=(B-1P1 , … ,B-1Pr-1 , B-1Pr , B-1Pr+1 , … ,B-1Pm ) =E B-1B=(B-1P1 , … ,B-1Pr-1 , B-1Pm+k , B-1Pr+1 , … ,B-1Pm ) B-1B= 1 a1m+k 1 ar-1m+k arm+k ar+1m+k 1 amm+k 1 r ? ? … …… r Er =(B-1B)-1= a1m+k arm+k - ar-1 m+k arm+k - 1 arm+k ar+1 m+k ar