运筹学第一章详解.ppt

OR1 operations research 1 第一章 线性规划与单纯形法 重点与难点： 1、线性规划的概念和模型，线性规划问题的标准型，线性规划问题的标准化； 2、线性规划问题解的概念，图解法(解的几何表示)，基本可行解的几何意义，线性规划求解思路(单纯形法思想)； 3、单纯形法的一般描述，表格单纯形法，一般线性规划问题的处理，单纯形迭代过程中的注意事项； 4、线性规划建模，决策变量，约束不等式、等式，目标函数，变量的非负限制。 第一章 线性规划与单纯形法 1.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。 LP有一组有待决策的变量，（决策变量） 一个线性的目标函数， 一组线性的约束条件。 1.1.1 LP的数学模型  例题1：生产计划问题 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？ 例题1建模 步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0 综上所述，该问题的数学模型表示为： 例题2：人员安排问题 医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 例题2建模 目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6 例题3：运输问题 三个加工棉花的加工厂，并且有三个仓库供应棉花，各供应点到各工厂的单位运费以及各点的供应量与需求量分别如下表所示：问如何运输才能使总的运费最小？ 例题3建模 设Xij为第i个仓库运到底j座工厂的运输量。 目标函数：总运费最省：minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33 约束条件： 供给要求：x11+x12+x13 ＝50需求要求：x11+x21+x31=40 x21+x22+x23 ＝30 x12+x22+x32=15 x31+x32+x33 ＝10 x13+x23+x33=35 非负要求： Xij ≥0 例题4：连续投资问题（书P42页） 某投资者有资金10万元，考虑在今后5年内给下列4个项目进行投资，已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115％。 项目B：第三年初需投资，到第五年末能回收本利125％。但规定投资额不超过4万元。 项目C：第二年初需要投资，到第五年末能回收本利140％，但规定最大投资额不超过3万元。 项目D：5年内每年初可购买公债，于当年末归还，并加利息6％。 问该投资者应如何安排他的资金，确定给这些项目每年的投资额，使到第五年末能拥有的资金本利总额为最大？ 建模 解：记xiA,xiB,xiC,xiD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额，它们都是决策变量，为了便于书写数学模型，我们列表如下： 例题5：合理下料问题 将长8m的圆钢，截取成长2.5m的毛坯100根、长1.3m的毛坯200根，问应该怎样选择下料方式，才能既满足需要，又使总的用料最少? 各种搭配方案如下： 例题5建模 设Xj表示采用第j种方案下料的根数。 目标函数：minZ=x1+x2+x3+x4 约束条件：3x1+2x2+x3 ≥ 100 2x2+4x3+6x4 ≥ 200 xj ≥0且为整数