运筹学第一章线性规划.ppt

绪 论 运筹学释义与发展简史 operational research, operations research, 简写O.R. 运筹学研究的基本特征 系统的整体性，多学科的综合性，模型方法的应用性 运筹学在工商管理中的应用 运筹学的主要分支 目录 O.R.在工商管理中的应用 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。 库存管理：多种物资库存量的管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。 例1.1：（计划安排问题） 例1.2 (成本问题) 线性规划模型特点: 决策变量：向量(x1… xn)T , xi非负 约束条件：线性等式或不等式 目标函数：Z=?(x1 … xn) 线性式， 求Z极大或极小 （资源利用问题） （货物调度问题） 二、线性规划问题的标准型 3 -1-M 1-M -1 0 0 0 1 表3 1 0 0 0 1 0 -2 1 x3 -2 1 -1 0 0 1 0 1 x2 -5 2 -2 1 0 0 [3] 12 x4 x7 x6 x5 x4 x3 x2 x1 b* XB -M -M 0 0 -1 -1 cj 2/3-M 1/3-M -1/3 -1/3 0 0 0 表4 -7/3 4/3 -4/3 2/3 1 0 0 9 x3 -2 1 -1 0 0 1 0 1 x2 -5/3 2/3 -2/3 1/3 0 0 1 4 x1 所有 ?j ? 0，X* = ( 4, 1, 9, 0, 0, 0, 0 )T S’ = 2 S= -2 判定无解条件： 当进行到最优表时，仍有人工变量在基中，且≠0，则说明原问题无可行解。 用两阶段法求解L.P的最优解: 解:加入松弛变量、剩余变量、 人工变量： x6 , x7 ?第一阶段的问题 min W= x6 +x7 = max W’= - x6 - x7 x1 -2x2 + x3 ? 11 -4x1 + x2 + 2x3 ? 3 -2x1 +x3=1 x1 , x2 , x3 ?0 maxS= 3x1 -x2 -x3 x1 -2x2 + x3 +x4 =11 -4x1 + x2 + 2x3 -x5 =3 -2x1 +x3 =1 x1 , x2 ,… ,x5 , ?0 +x6 +x7 ,x6 ,x7 (二)、两阶段法--例 s.t. s.t. 1. 凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点?X1+(1-?)X2，( 0 ? ? ? 1)都在集合K中，即：?X1+(1-?)X2 ?K ( 0 ? ? ? 1) 则称K为凸集。 从直观上讲，凸集无凹入部分，其内部没有洞。 如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。 2. 凸组合：设X1，X2，···，Xk是n维欧氏空间En中的k个点，若存在?1，?2，···，?k，且0 ? ?i ? 1，i = 1,2, ···, k，? ?i = 1，使X = ?1X1 + ?2X2 + ··· + ?kXk，则称X为由X1，X2，···，Xk所构成的凸组合。 按照定义，凡是由x，y的凸组合表示的点都在x，y的连线上，而且反之亦然。 3. 顶点： 假设K是凸集，X ?K；X若不能用不同的两个点X1、X2 ?K的线性组合表示为： X = ?X1+(1-?)X2 ， ( 0 ? 1) 则称X为凸集K的一个顶点（或称为极点）。 顶点不位于凸集K中的任意不同两点的连线内。 三、基本定理 定理1.1 若线性规划问题存在可行域，则其可行域： D = { X | AX = b , X ? 0 } ，是凸集。 引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。 定理1.2 线性规划问题的基本可行解对应于可行域的顶点。 定理1.3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达