《运筹学教程胡云权第五版运筹学线性规划3excel线性规划及应用课件幻灯片》由会员分享，可在线阅读，更多相关《运筹学教程胡云权第五版运筹学线性规划3excel线性规划及应用课件幻灯片（58页珍藏版）》请在金锄头文库上搜索。
1、,第一章 线性规划,主要内容,线性规划问题及其数学模型 线性规划解的概念、图解法 单纯形法原理及步骤 Excel求解和线性规划应用,线性规划数学模型标准型矩阵式：,可行解：满足约束条件(1.2)和非负条件(1.3)的解称为可行解。 可行域：可行解的集合。 最优解：满足条件(1.1)的可行解。,(1.1),(1.2),(1.3),线性规划标准型解的概念,基矩阵（基）：设A是 阶系数矩阵( )，秩A=m，则A中一定存在m个线性无关的列向量，称由m个线性无关的列向量构成的可逆矩阵 为问题L的一个基，L最多有 个基。系数矩阵A中的m阶可逆子阵，记为B。其余为非基矩阵，记为N。 基向量：基矩阵B中的列，
2、其余为非基向量。 基变量：与基矩阵B中列向量所对应的变量为基变量，记为 ，其余变量为非基变量，记为 。,线性规划标准型解的概念,线性规划标准型解的概念,基解：当A中的基B取定后，不妨设B表示A中的前m列，则可 记 ，相应地 , 约束条件AX=b可表示为 ，即 ，当取 时，则 为线性规划问题LP的基解。P20 基解的非零分量个数 m，当m时，则此基解是退化解，这种现象不多。 一个基解是由一个基来决定的，并未要求非负，因此未必可行。 基可行解：若B对应的基解中满足 ，则称该解为基本可 行解，称B为可行基。,线性规划问题的可行域为凸集（定理1）； 凸集的每个顶点对应一个基可行解（定理2），基可行解的
3、个数是有限的，当然凸集的顶点个数也是有限的； 若线性规划有最优解，必在可行域某顶点上达到，（定理3）亦即在有限个基可行解中间存在最优解。,基本定理,，,由于基可行解数目有限（ ），因此，经过有限次迭代即可找到最优解。 前提：线性规划为标准型。,单纯形法基本步骤,求初始基可行解 确定换入变量的最优性条件 确定换出变量的可行性条件 运用初等行变换求出新的基 可行解,例2 用单纯形法求解线性规划问题,单纯形法求解,解：（1）转化为标准型, ,主元素,线性规划最优解的几种情况,定理4：（无界解）若对某可行基B，若存 在 ，则该线性规划问题无有限最 优解（或称无最优解、无界解）。 证明： 设此时对应的目
4、标函数值为Z0，基可行解为 , 则有 即二者乘积所得列向量的每个元素 小于 等于0，,构造新的解 ,其分量为：,验证它满足等式约束：,又因为： 所以：,再验证它满足非负约束 由于 所以对于任意的 ， 都是可行解。 把 带入目标函数中得：,由于 大于0，故 ， 即该问题得目标函数无界。,教材P35,单纯形法小结,作 业,使用EXCEL求解线性规划,一个简单的例子,某工厂计划生产两种产品，利润分别为2和3，已知生产单位产品所需的设备台时和A、B两种原材料的消耗，如表,目标是不超过资源限制的情况下，确定两产品产量，得到最大利润。,建立数学公式（步骤一）,在工作表的顶部输入数据 确定每个决策变量所对应
5、的单元格位置 选择单元格输入公式，找到目标函数的值 确定约束单元格输入公式，计算每个约束条件左边的值 确定约束单元格输入公式，计算每个约束条件右边的值,可采用 复制粘贴 或 直接输入 的方式导入数据。,在工作表的顶部输入数据 确定每个决策变量所对应的单元格位置 选择单元格输入公式，找到目标函数的值 选择一个单元格输入公式，计算每个约束条件左边的值 选择一个单元格输入公式，计算每个约束条件右边的值,图中，规定B12、C12为可变单元格,可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数,建立数学公式（步骤二）,在工作表的顶部输入数据 确定每个决策变量所对应的单元格位置 选择单元格输入公
6、式，找到目标函数的值 确定约束单元格输入公式，计算每个约束条件左边的值 确定约束单元格输入公式，计算每个约束条件右边的值,在目标单元格中，需要填入计算目标函数值的公式。,建立数学公式（步骤三）,在工作表的顶部输入数据 确定每个决策变量所对应的单元格位置 选择单元格输入公式，找到目标函数的值 确定约束单元格输入公式，计算每个约束条件左边的值 确定约束单元格输入公式，计算每个约束条件右边的值,在约束单元格中，需要填入计算约束函数值的公式。,建立数学公式（步骤四）,在工作表的顶部输入数据 确定每个决策变量所对应的单元格位置 选择单元格输入公式，找到目标函数的值 确定约束单元格输入公式，计算每个约束条
7、件左边的值 确定约束单元格输入公式，计算每个约束条件右边的值,建立数学公式（步骤五）,调用 “规划求解” 模块,选择工具下拉菜单 选择规划求解选项（事先需用Office安装盘安装规划求解的功能）,填写目标单元格和可变单元格,出现规划求解参数对话框 在目标单元格中输入B14 在等于选择最大 在可变单元格中输入B12:C12 选择添加,在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。,添加约束,在添加约束对话框中，在单元格引用位置中输入B17，选择=，在约束值中输入D17。选择添加 第三个条件添加完毕后，选择确定 当规划求解参数对话框重新出现时，选择选
8、项,“选项”设置,当选项对话框出现时，选择假设非负。选择确定,用Excel求解,出现规划求解参数对话框，选择求解。,保存求解结果,当求解结果对话框出现时，选择保存规划求解结果。选择确定。,线性规划应用,线性规划可以应用在管理、经济、金融、战争、通讯、工程设计等各个领域。很多决策问题可以抽象为线性规划模型。线性规划方法的应用为社会带来了无法估量的巨大效益。 材料利用、混合配料、产品计划、 连续投资、人员安排 ,30,1、材料利用问题,现要做100 套钢架,每套用长为2.9m , 2.1m 和1.5m的元钢各一根制成。已知原料长7.4米，问应如何下料，使用的原材料最省？,1、材料利用问题,2、生产
9、存储问题,电扇厂每月最多可生产3000台电扇，每台成本100元。如果当月销售不了，那么每台每月要支付10元的存储费。设4、5、6月的销售量预计为1000台、2500台和4000台。已知4月初没留有存货，也不要求6月底留下存货。问如何安排4、5、6月的生产计划，可使得总的生产、存储费最低？,【解】设4、5、6月份分别生产x1、x2、x3台,2、生产存储问题,某昼夜服务的公交线路每天各时间区段内所需四级和乘务人员数如下表所示。问该公交线路至少配备多少名司机和乘务人员？,3、人员分配问题,【解】设xi (i=1，2，6)名司机和乘务员第i班次开始上班，则,3、人员分配问题,设有A1，A2，A3三个产
10、地，生产某种物质，其产量分别为7，5，7，B1，B2，B3，B4四个销地，需要该物资，销量分别为2，3，4，6，又已知各产销地之间的运价如下表，确定总运费最少的调运方案。,单位运价表,4、运输问题,A1,A2,A3,B1,B2,B3,B4,销地,产地,运输问题示意图,4、运输问题,5、动态投资问题（1）,5、动态投资问题（1）,5、动态投资问题（2）,某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%； 项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元； 项
11、目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元； 项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元； 如何确定这些项目每年投资额，使得第五年年末本利金额最大？,【解】 设 xij ( i = 1 - 5，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24,5、动态投资问题（2）,目标函数： Max z = 1.1x51+
12、1.25x42+ 1.4x33 + 1.55x24,第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投资故第二年年初的资金为 1.1x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初的资金为 1.1x21+1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12； 第四年：年初的资金为 1.1x31+1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22； 第五年：年初的资金为 1.1x41+1.25x32，于是 x51 = 1.1x41+ 1
13、.25x32； B、C、D的投资限制： xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,5、动态投资问题（2）,6、混合配料问题,6、混合配料问题,45,6、混合配料问题,46,
14、7、种植计划问题,【解】设种植大豆、玉米、小麦分别为x1、x2、x3亩，饲养奶牛x4头、鸡x5只，春夏季和秋冬季外出帮工分别x6、 x7为工时。,Max Z =50 x1 +80x2+40x3+400x4+10x5 +0.5x6+0.4 x7 x1 + x2 + x3+ 1.5x4 40 (土地约束) 400x4+3x5 2500 (资金约束) 20 x1 +35x2+10x3+50x4 +0.3x5 +x6 =4000 (春夏劳力) 50 x1 +75x2+40x3+100x4+0.6x5 +x7 =3500 (秋冬劳力) x4 8 (牛舍约束) x5 300 (鸡舍约束) x1,x2,x3
15、,x4,x5,x6 ，x7 0,7、种植计划问题,8、购销仓储问题,8、购销仓储问题,【解】设冬季购进冬、春、夏、秋季售出的木材数量分别为x11、 x12、 x13 、x14万立米, 春季购进春、夏、秋季售出的木材数量分别为 x22、 x23 、x24万立米, 夏季购进夏、秋季售出的木材数量分别为 x33 、x34万立米, 秋季购进秋季售出的木材数量为x44万立米。,Max Z= (321-310)x11 + (333-310-17)x12 + (352-310-27)x13 + (344-310-37)x14 + (333-325)x22 + (352-325-17)x23 + (344-325-27)x24 + (353-348)x33 + (344-348-17)x34 + (344-340)x44,50,x12 + x13 + x14 20 (冬季存贮约束) x13 + x14 + x23 + x24 20 (春季存贮约束) x14 + x24 + x34 20 (夏季存贮约束) x1110 (冬季销售约束
