运筹学课件-第一章线性规划及单纯形法.ppt

第一章 线性规划及单纯形法 1．线性规划介绍 2．线性规划数学模型 3．线性规划标准形式 4．线性规划的图解法 5．线性规划基本概念 6．单纯形法 7．应用举例 1．线性规划介绍 历史悠久 理论成熟 应用广泛 线性规划 运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大 从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等。 研究对象 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省 2．线性规划数学模型 用数学语言描述 线性规划模型特点 决策变量：向量(x1… xn)T 决策人要考虑和控制的因素。非负 约束条件：线性等式或不等式 目标函数：Z=?(x1 … xn) 线性式，求Z极大或极小 关于线性的界定 隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值 应 用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用) 线性规划的适用情况 3．线性规划标准形式 线性规划标准型的几种表示法 练 习 作业 4．线性规划的图解法 总 结 练 习 5．线性规划基本概念 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) ，有 LP问题解的性质 若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。 6．单纯形法 6.1、单纯形法迭代原理 6.2、单纯形法计算步骤 6.3、人工变量法 6.4、两阶段法 6.5、计算中的几个问题 6.6、单纯形法小结 6．1单纯形法迭代原理 一、确定初始基可行解 二、从一个基可行解转换为相邻基可行解 三、最优性检验和解的判别 一、确定初始基可行解 线性规划问题的标准型 总存在一个单位矩阵（P1,P2,…,Pm)。 当约束条件为?时，加上松驰变量的系数矩阵即为单位矩阵。当约束条件为?或＝时，可以构造人工基，人为产生一个单位矩阵。 基向量、基变量、非基向量、非基变量 可得初始基可行解: X=(x1,…,xm,xm+1,…xn)T=(b1,…,bm,0,…,0)T 二、基可行解的转换 两个基可行解相邻指的是它们之间变换且仅变换一个基变量。 设X(0)=(x10,x20,…xm0,0,…0)T，有 三、最优性检验和解的判别 6.2、单纯形法计算步骤 单纯形表 特点： （直观.便于理解计算关系.功能与增广矩阵相似） 单纯形表： 例题5 解： 1、先将上述问题化成标准形式有 3、列新单纯形表： 练习题 作