1、第第 1 1 页页运筹学第 1 页2023-8-32023-8-3上海财经大学第一章 线性规划线性规划主要内容w线性规划问题及其数学模型线性规划问题及其数学模型w线性规划解的概念、图解法线性规划解的概念、图解法 w单纯形法原理及步骤单纯形法原理及步骤wExcel求解和线性规划应用线性规划数学模型标准型矩阵式：CXZmax0XbAX可行解：满足约束条件(1.2)和非负条件(1.3)的解称为可行解。可行域：可行解的集合。最优解：满足条件(1.1)的可行解。(1.1)(1.2)(1.3)线性规划标准型解的概念线性规划标准型解的概念基矩阵（基）：设A是 阶系数矩阵()，秩A=m，则A中一定存在m个线性
2、无关的列向量，称由m个线性无关的列向量构成的可逆矩阵 为问题L的一个基，L最多有 个基。系数矩阵A中的m阶可逆子阵，记为B。其余为非基矩阵，记为N。基向量：基矩阵B中的列，其余为非基向量。基变量：与基矩阵B中列向量所对应的变量为基变量，记为 ，其余变量为非基变量，记为 。nm nm),(jmj2j1PPPBmnCTjmjjxxx),(21BXNX线性规划标准型解线性规划标准型解的概念的概念线性规划标准型解线性规划标准型解的概念的概念基解：当A中的基B取定后，不妨设B表示A中的前m列，则可 记 ，相应地 ,约束条件AX=b可表示为 ，即 ，当取 时，则 为线性规划问题LP的基解。P20 基解的非
3、零分量个数 m，当m时，则此基解是退化解，这种现象不多。一个基解是由一个基来决定的，并未要求非负，因此未必可行。基可行解：若B对应的基解中满足 ，则称该解为基本可 行解，称B为可行基。()A BN()TBNXXX()BNXAXBNbX11BNXB b B NX0NX 1BXB b10B bX10B b|线性规划问题的可行域为凸集（定理1）；|凸集的每个顶点对应一个基可行解（定理2），基可行解的个数是有限的，当然凸集的顶点个数也是有限的；|若线性规划有最优解，必在可行域某顶点上达到，（定理3）亦即在有限个基可行解中间存在最优解。基本定理基本定理，初始基可行解是否是最优解结束找一个较好 基可行解N
4、Y由于基可行解数目有限（），因此，经过有限次迭代即可找到最优解。前提：线性规划为标准型。mnC单纯形法基本步骤单纯形法基本步骤I.求初始基可行解II.确定换入变量的最优性条件III.确定换出变量的可行性条件IV.运用初等行变换求出新的基 可行解712000XBCBB-1bx1x2x3x4x5x303609410090 x402004501040 x5030031000130712000例2 用单纯形法求解线性规划问题单纯形法求解单纯形法求解12121212943604+5200s.t.310300,0 xxxxxxxx12m ax712zxx解：（1）转化为标准型123124125123459
5、43604+5200s.t.310300,0 xxxxxxxxxxxxxx12345m ax712000zxxxxx1111970,0,0437BcCBP 主元素主元素0ika1360490iikba线性规划最优解的几种情况线性规划最优解的几种情况定理4：（无界解）若对某可行基B，若存在 ，则该线性规划问题无有限最优解（或称无最优解、无界解）。证明：设此时对应的目标函数值为Z0，基可行解为 ,则有即二者乘积所得列向量的每个元素 小于等于0，0,0kkPB1TmbbbX)0,0,()0,(),(21)0(bB0X1BbBXB0kPB1kia,mi,2,1构造新的解 ,其分量为：)1(Xkjnmj
6、xxmiabxjkkiii,1,0,2,1,)1()1(,)1(验证它满足等式约束：又因为：所以：bBXBbAX)1(BkBkk1Bk1BBXPPBBBXPPBXBPBXNBAXk1)1()(0000),(j=k0000)1(k1BPBXX 再验证它满足非负约束 由于 所以对于任意的 ，都是可行解。把 带入目标函数中得：,0,kia0)1(X)1(Xk0)()(0000),(ZCcCcCCcCCCZBkBkBBkBNBk1Bk1Bk1Bk1BPBXPBXPBXPBX由于 大于0，故 ，即该问题得目标函数无界。kZ时，教材P35单纯形法小结单纯形法小结作作 业业使用使用EXCEL求解线性规划求解
7、线性规划第第 1616 页页运筹学第 16 页2023-8-32023-8-3上海财经大学一个简单的例子一个简单的例子某工厂计划生产两种产品，利润分别为某工厂计划生产两种产品，利润分别为2和和3，已知生产单位，已知生产单位产品所需的设备台时和产品所需的设备台时和A、B两种原材料的消耗，如表两种原材料的消耗，如表产品1产品2设备128台时原材料A4016KG原材料B0412KGn目标是不超过资源限制的情况下，确定两产品产量，得到最大利润。第第 1717 页页运筹学第 17 页2023-8-32023-8-3上海财经大学建立数学公式（步骤一）建立数学公式（步骤一）在工作表的顶部输入数据在工作表的顶
8、部输入数据确定每个决策变量所对应的确定每个决策变量所对应的单元格位置单元格位置选择单元格输入公式，找到选择单元格输入公式，找到目标函数的值目标函数的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件左边的值计算每个约束条件左边的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件右边的值计算每个约束条件右边的值可采用 复制粘贴 或 直接输入 的方式导入数据。第第 1818 页页运筹学第 18 页2023-8-32023-8-3上海财经大学在工作表的顶部输入数据在工作表的顶部输入数据确定每个决策变量所对应的确定每个决策变量所对应的单元格位置单元格位置选择单元格输入公
9、式，找到选择单元格输入公式，找到目标函数的值目标函数的值选择一个单元格输入公式，选择一个单元格输入公式，计算每个约束条件左边的值计算每个约束条件左边的值选择一个单元格输入公式，选择一个单元格输入公式，计算每个约束条件右边的值计算每个约束条件右边的值图中，规定B12、C12为可变单元格可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数建立数学公式（步骤二）建立数学公式（步骤二）第第 1919 页页运筹学第 19 页2023-8-32023-8-3上海财经大学在工作表的顶部输入数据在工作表的顶部输入数据确定每个决策变量所对应的确定每个决策变量所对应的单元格位置单元格位置选择单元格输入公式
10、，找到选择单元格输入公式，找到目标函数的值目标函数的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件左边的值计算每个约束条件左边的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件右边的值计算每个约束条件右边的值在目标单元格中，需要填入计算目标函数值的公式。建立数学公式（步骤三）建立数学公式（步骤三）第第 2020 页页运筹学第 20 页2023-8-32023-8-3上海财经大学在工作表的顶部输入数据在工作表的顶部输入数据确定每个决策变量所对应的确定每个决策变量所对应的单元格位置单元格位置选择单元格输入公式，找到选择单元格输入公式，找到目标函数的值目标函数的
11、值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件左边的值计算每个约束条件左边的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件右边的值计算每个约束条件右边的值在约束单元格中，需要填入计算约束函数值的公式。建立数学公式（步骤四）建立数学公式（步骤四）第第 2121 页页运筹学第 21 页2023-8-32023-8-3上海财经大学在工作表的顶部输入数据在工作表的顶部输入数据确定每个决策变量所对应的确定每个决策变量所对应的单元格位置单元格位置选择单元格输入公式，找到选择单元格输入公式，找到目标函数的值目标函数的值确定约束单元格输入公式，确定约束单元格输入公式，计
12、算每个约束条件左边的值计算每个约束条件左边的值确定约束单元格输入公式，确定约束单元格输入公式，计算每个约束条件右边的值计算每个约束条件右边的值建立数学公式（步骤五）建立数学公式（步骤五）第第 2222 页页运筹学第 22 页2023-8-32023-8-3上海财经大学调用调用“规划求解规划求解”模块模块选择选择工具工具下拉菜单下拉菜单选择选择规划求解规划求解选项（事先选项（事先需用需用Office安装盘安装规划安装盘安装规划求解的功能）求解的功能）第第 2323 页页运筹学第 23 页2023-8-32023-8-3上海财经大学填写目标单元格和可变单元格填写目标单元格和可变单元格出现出现规划求
13、解参数规划求解参数对话框对话框在在目标单元格目标单元格中输入中输入B14B14在在等于等于选择最大选择最大在在可变单元格可变单元格中输入中输入B12:C12B12:C12选择选择添加添加在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。第第 2424 页页运筹学第 24 页2023-8-32023-8-3上海财经大学添加约束添加约束在在添加约束添加约束对话框中，在对话框中，在单元格引用位置单元格引用位置中输入中输入B17，选择选择=，在约束值中输入，在约束值中输入D17。选择。选择添加添加第三个条件添加完毕后，第三个条件添加完毕后，选择选择确定确定当
14、当规划求解参数规划求解参数对话框重对话框重新出现时，选择新出现时，选择选项选项第第 2525 页页运筹学第 25 页2023-8-32023-8-3上海财经大学“选项选项”设置设置当选项对话框出现时，选当选项对话框出现时，选择择假设非负假设非负。选择。选择确定确定第第 2626 页页运筹学第 26 页2023-8-32023-8-3上海财经大学用用Excel求解求解出现出现规划求解参数规划求解参数对话框，对话框，选择选择求解求解。第第 2727 页页运筹学第 27 页2023-8-32023-8-3上海财经大学保存求解结果保存求解结果当当求解结果求解结果对话框出现时，选择对话框出现时，选择保存
15、规划求解结果保存规划求解结果。选择。选择确定确定。线性规划应用线性规划应用第第 2929 页页运筹学第 29 页2023-8-32023-8-3上海财经大学 线性规划可以应用在线性规划可以应用在管理、经济、金融、战争、管理、经济、金融、战争、通讯、工程设计通讯、工程设计等各个领域。很多决策问题可以抽象等各个领域。很多决策问题可以抽象为线性规划模型。线性规划方法的应用为社会带来了为线性规划模型。线性规划方法的应用为社会带来了无法估量的巨大效益。无法估量的巨大效益。材料利用、材料利用、混合配料、产品计划、混合配料、产品计划、连续投资、人员安排连续投资、人员安排 第第 3030 页页运筹学第 30
16、页2023-8-32023-8-3上海财经大学301 1、材料利用问题、材料利用问题 现要做现要做100 套钢架套钢架,每套用长为每套用长为2.9m,2.1m 和和1.5m的元钢各一根制成。已知原料长的元钢各一根制成。已知原料长7.4米，问应如何下料，米，问应如何下料，使用的原材料最省？使用的原材料最省？第第 3131 页页运筹学第 31 页2023-8-32023-8-3上海财经大学1 1、材料利用问题、材料利用问题第第 3232 页页运筹学第 32 页2023-8-32023-8-3上海财经大学2 2、生产存储问题、生产存储问题 电扇厂每月最多可生产电扇厂每月最多可生产3000台电扇，每台
17、成本台电扇，每台成本100元。如果当月销售不了，那么每台每月要支付元。如果当月销售不了，那么每台每月要支付10元的存储费。设元的存储费。设4、5、6月的销售量预计为月的销售量预计为1000台、台、2500台和台和4000台。已知台。已知4月初没留有存货，也不要求月初没留有存货，也不要求6月底留下存货。问如何安排月底留下存货。问如何安排4、5、6月的生产计划，月的生产计划，可使得总的生产、存储费最低？可使得总的生产、存储费最低？第第 3333 页页运筹学第 33 页2023-8-32023-8-3上海财经大学【解解】设设4、5、6月份分别生产月份分别生产x1、x2、x3台台2 2、生产存储问题、
18、生产存储问题123112112123123min100()10(1000)10(2500)1000100025001000250040003000300030000,1,2,3iZxxxxxxxxxxxxxxxxi第第 3434 页页运筹学第 34 页2023-8-32023-8-3上海财经大学 某昼夜服务的公交线路每天各时间区段内所需四某昼夜服务的公交线路每天各时间区段内所需四级和乘务人员数如下表所示。问该公交线路至少配备级和乘务人员数如下表所示。问该公交线路至少配备多少名司机和乘务人员？多少名司机和乘务人员？班次班次时间时间所需人数所需人数16：00 10：0060210：00 14：00
19、70314：00 18：0060418：00 22：0050522：00 2：002062：00 6：00303 3、人员分配问题、人员分配问题第第 3535 页页运筹学第 35 页2023-8-32023-8-3上海财经大学【解解】设设x xi i (i i=1=1，2 2，6)6)名司机和乘务员第名司机和乘务员第i i班次班次开始上班，则开始上班，则123456161223344556min6070605020300,1,2,6iZxxxxxxxxxxxxxxxxxxxi3 3、人员分配问题、人员分配问题第第 3636 页页运筹学第 36 页2023-8-32023-8-3上海财经大学产地
20、 销地 B1 B2 B3 B4A1A2A3 2 11 3 4 10 3 5 9 7 8 1 2 设有A1，A2，A3三个产地，生产某种物质，其产量分别为7，5，7，B1，B2，B3，B4四个销地，需要该物资，销量分别为2，3，4，6，又已知各产销地之间的运价如下表，确定总运费最少的调运方案。单位运价表4 4、运输问题、运输问题第第 3737 页页运筹学第 37 页2023-8-32023-8-3上海财经大学A1A2A3B1B2B3B4销地产地运输问题示意图4 4、运输问题、运输问题第第 3838 页页运筹学第 38 页2023-8-32023-8-3上海财经大学5 5、动态、动态投资投资问题（
21、问题（1 1）第第 3939 页页运筹学第 39 页2023-8-32023-8-3上海财经大学5 5、动态、动态投资投资问题（问题（1 1）第第 4040 页页运筹学第 40 页2023-8-32023-8-3上海财经大学5 5、动态、动态投资投资问题（问题（2 2）某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项
22、目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；如何确定这些项目每年投资额，使得第五年年末本利金额最大？第第 4141 页页运筹学第 41 页2023-8-32023-8-3上海财经大学【解解】设 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 x245 5、动态、动态投资投资问题（问题（2 2）目标函数：目标函数：Max z=1.1x51+1.25x
23、42+1.4x33+1.55x24 第第 4242 页页运筹学第 42 页2023-8-32023-8-3上海财经大学第一年：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
24、.1x41+1.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 5、动态、动态投资投资问题（问题（2 2）第第 4343 页页运筹学第 43 页2023-8-32023-8-3上海财经大学6 6、混合、混合配料问题配料问
25、题第第 4444 页页运筹学第 44 页2023-8-32023-8-3上海财经大学6 6、混合、混合配料问题配料问题第第 4545 页页运筹学第 45 页2023-8-32023-8-3上海财经大学456 6、混合、混合配料问题配料问题第第 4646 页页运筹学第 46 页2023-8-32023-8-3上海财经大学467 7、种植计划、种植计划问题问题第第 4747 页页运筹学第 47 页2023-8-32023-8-3上海财经大学【解】设种植大豆、玉米、小麦分别为x1、x2、x3亩，饲养奶牛x4头、鸡x5只，春夏季和秋冬季外出帮工分别x6、x7为工时。Max Z=50 x1+80 x2+
26、40 x3+400 x4+10 x5+0.5x6+0.4 x7 x1+x2+x3+1.5x4 40 (土地约束)400 x4+3x5 2500 (资金约束)20 x1+35x2+10 x3+50 x4+0.3x5+x6=4000(春夏劳力)50 x1+75x2+40 x3+100 x4+0.6x5+x7=3500(秋冬劳力)x4 8 (牛舍约束)x5 300 (鸡舍约束)x1,x2,x3,x4,x5,x6，x7 07 7、种植计划、种植计划问题问题第第 4848 页页运筹学第 48 页2023-8-32023-8-3上海财经大学8 8、购销仓储问题、购销仓储问题第第 4949 页页运筹学第 4
27、9 页2023-8-32023-8-3上海财经大学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
28、+(344-348-17)x34 +(344-340)x44 第第 5050 页页运筹学第 50 页2023-8-32023-8-3上海财经大学50 x12+x13+x14 20 (冬季存贮约束)x13+x14+x23+x24 20 (春季存贮约束)x14+x24+x34 20 (夏季存贮约束)x1110 (冬季销售约束)x12+x22 14 (春季销售约束)x13+x23+x33 20 (夏季销售约束)x14+x24+x34+x44 16 (秋季销售约束)xij 0 ,i=1,2,3,4,j=1,2,3,48 8、购销仓储问题、购销仓储问题第第 5151 页页运筹学第 51 页2023-8-
29、32023-8-3上海财经大学9 9、年度、年度生产计划问题生产计划问题某公司生产某种产品，他们每年要对下一年的市场需求做出预测，并据此做出明年每个月的生产和存贮计划。根据调查，明年的市场需求如下表：该公司认为市场需求必须满足。在安排生产时，公司可采取以下措施正常生产和加班生产：正常生产和加班生产：每个工人每月的正常产量为20件；每个工人每月的加班产量不超过6件，每加班生产一件要增加费用20美元。月份 需求量（件）月份 需求量（件）月份 需求量（件）153005410097300251006480010780034400760001176004280087100126400第第 5252 页页
30、运筹学第 52 页2023-8-32023-8-3上海财经大学增加和减少工人：增加和减少工人：通过增加或减少工人调节产量，相邻两月工人增加或减少不能超过40人；每次增加一个工人要支付300美元费用；每次减少一个工人要支付420美元费用。存贮：存贮：仓储产品和当月生产的产品可供市场，剩余产品可存贮在仓库里；每月每件产品的存贮费用为8美元，以月底的存贮量结算存贮费用。现预计今年年底的工人数为290人，仓库存贮量为0件，并要求明年年底仓库存贮量也为0件。公司希望以总费用最低为目标，作一个明年的生产和存贮计划。9 9、年度、年度生产计划问题生产计划问题第第 5353 页页运筹学第 53 页2023-8
31、-32023-8-3上海财经大学记明年j月份的需求量为d j件。设明年j月份的正常产量为xj件，加班产量为yj件，仓库存贮量为zj，工人数为sj人，增加或减少工人的费用为tj美元。总费用：Cost=j=1,2,12(20yj+8zj+tj)正常产量：xj=20sj(j=1,2,12)加班产量：yj 6sj(j=1,2,12)工人数增减：sj sj-1 40(j=1,2,12)sj-1 sj 40(j=1,2,12)工人数增减费用：tj 300(sj sj-1)(j=1,2,12)tj 420(sj-1 sj)(j=1,2,12)仓库存贮量：zj-1+xj+yj=dj+zj(j=1,2,12)今
32、年底情况：s0=290 z0=0 明年底情况：z12=0为了减少变量，用sj=0.05xj取代所有sj。9 9、年度、年度生产计划问题生产计划问题第第 5454 页页运筹学第 54 页2023-8-32023-8-3上海财经大学9 9、年度、年度生产计划问题生产计划问题第第 5555 页页运筹学第 55 页2023-8-32023-8-3上海财经大学知识、经验知识、经验创造力创造力描述问题描述问题如何描述问题并抽象为模型如何描述问题并抽象为模型？抽象为模型抽象为模型 经济管理领域大量的决策问题的描述和建模，富有经济管理领域大量的决策问题的描述和建模，富有难度和挑战性难度和挑战性第第 5656
33、页页运筹学第 56 页2023-8-32023-8-3上海财经大学建立数学模型的困难建立数学模型的困难第第 5757 页页运筹学第 57 页2023-8-32023-8-3上海财经大学某公司有三项工作需要分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领导三个力工来完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务，该公司需要每周总有效工作小时数为：第一项工作
34、10000小时，第二项工作20000小时，第三项工作30000小时。又能招收到的工人数为技工不超过400人，力工不超过800人。试着建立数学模型，确定招收技工和力工人数，使得总的工资支出为最少。（建立数学模型，不求解）作业作业提问与解答环节Questions And Answers谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal
