线性规划与单纯形法幻灯片.ppt

《线性规划与单纯形法幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形法幻灯片.ppt（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划与单纯形法第1页，共120页，编辑于2022年，星期一第二章 线性规划与单纯形法n2.1线性规划问题与数学模型n2.2图解法n2.3线性规划的应用n2.4单纯形法基本原理及计算步骤n2.5单纯形法的进一步讨论n2.6线性规划的对偶问题第2页，共120页，编辑于2022年，星期一2.1 线形规划线形规划(Linear Programming)问题及其数问题及其数学模型学模型【引例引例】某工厂在计划期内要安排甲乙两种产品的生产，某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及已知生产单位产品所需的设备台时及A A、B B两种原材料的两种原材料的消耗，以及资源的限制

2、如下表所示：消耗，以及资源的限制如下表所示：甲甲乙乙资源限制资源限制设备设备1 11 1300300台时台时原料原料A A2 21 1400400千克千克原料原料B B0 01 1250250千克千克单件利润单件利润5050（元（元/件）件）100100（元（元/件）件）问问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？工厂应分别生产多少个产品甲、乙才能使工厂获利最多？第3页，共120页，编辑于2022年，星期一设生产甲产品x1个，生产乙产品x2个目标函数目标函数 max Z=50 x1+100 x2 约束条件x1+x2 300 2x1+x2 400 x2 250 x10,x2 0第4页

3、，共120页，编辑于2022年，星期一 线性规划模型线性规划模型n1.适用条件：适用条件：n（1）优化条件）优化条件:问题目标最大化、最小化的要求；问题目标最大化、最小化的要求；n（2）约束条件）约束条件:问题目标受一系列条件的限制；问题目标受一系列条件的限制；n（3）选择条件）选择条件:实现目标存在多种备选方案；实现目标存在多种备选方案；n（4）非负条件的选择）非负条件的选择:根据问题的实际意义决定是否非负。根据问题的实际意义决定是否非负。n2.构建线性规划模型的步骤构建线性规划模型的步骤n（1）科学选择决策变量）科学选择决策变量n（2）明确目标要求）明确目标要求n（3）根据实际问题的背景材

4、料，找出所有的约束条件）根据实际问题的背景材料，找出所有的约束条件n（4）确定是否增加决策变量的非负条件）确定是否增加决策变量的非负条件 第5页，共120页，编辑于2022年，星期一线性规划模型表示形式线性规划模型表示形式决策决策变变量；量；目目标标函数系数、价函数系数、价值值系数或系数或费费用系数；用系数；右端右端项项或或资资源常数；源常数；称称为约为约束系数或技束系数或技术术系数。系数。（1）一般形式：）一般形式：第6页，共120页，编辑于2022年，星期一（2）集合形式：）集合形式：（3）向量形式：）向量形式：（4）矩阵形式：）矩阵形式：第7页，共120页，编辑于2022年，星期一【例例

5、】将将线性性规划模型一般表达式化划模型一般表达式化为矩矩阵阵形式。形式。解解:设设:第8页，共120页，编辑于2022年，星期一例例1.目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 (A)2 x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1=50，x2 =250 最优目标值 z =275002图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第9页，共120页，编辑于2022年，星期一步骤：(1)分别取决策变量X1,

6、X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0第10页，共120页，编辑于2022年，星期一（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400第11页，共120页，编辑于2022年，星期一（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250

7、 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1第12页，共120页，编辑于2022年，星期一（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+1

8、00 x2CBADE第13页，共120页，编辑于2022年，星期一解的几种可能结果解的几种可能结果唯一最优解解唯一最优解解无穷多个最优解无穷多个最优解无界解无界解(可行域无界，常为模型遗漏了某些必可行域无界，常为模型遗漏了某些必要的约束条件要的约束条件)无可行解（可行域为空集，约束条件自相矛无可行解（可行域为空集，约束条件自相矛盾盾,资源满足不了人们的需求）资源满足不了人们的需求）可行解：满足可行解：满足LP问题所有约束条件的解问题所有约束条件的解最优解：满足目标要求的可行解最优解：满足目标要求的可行解第14页，共120页，编辑于2022年，星期一四种四种结结局局:x1x2唯一最优解x2x1无

9、穷多最优解x1x2无界解x2x1无可行解第15页，共120页，编辑于2022年，星期一无界解第16页，共120页，编辑于2022年，星期一 无可行解：可行域为空集增加的约束条件第17页，共120页，编辑于2022年，星期一线性规划标准形式线性规划标准形式线线性性规规划划标标准模型的一般表达式准模型的一般表达式：非非标标准形式准形式标标准化方法准化方法：1.目目标标函数函数 2.约约束条件束条件为为不等式不等式:引引进进松松驰变驰变量量xs:引引进进剩余剩余变变量量xs:4.决策决策变变量量为为自由自由变变量量:5.约约束右端束右端项为负项为负:两端乘两端乘-1:03.约约束条件束条件为为不等式

10、不等式:第18页，共120页，编辑于2022年，星期一n引入松驰变量（含义是资源的剩余量）【引例】中引入 s1，s2，s3 模型化为 目标函数：Max z=50 x1+100 x2+0 s1 +0 s2 +0 s3 约束条件：s.t.x1+x2 +s1 =300 2 x1+x2+s2 =400 x2 +s3 =250 x1 ,x2 ,s1,s2 ,s3 0 对于最优解 x1 =50 x2 =250，s1=0 s2 =50 s3=0 说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。第19页，共120页，编辑于2022年，星期一 【例例】将将

11、线线性性规规划模型划模型转转化化为标为标准式准式解解:无无约约束束(4)在第一、第三在第一、第三约约束左端加上松弛束左端加上松弛变变量量x4,x60，在第二约束左端减去剩余变量，在第二约束左端减去剩余变量x50 第20页，共120页，编辑于2022年，星期一习题习题n1.用图解法求解下列LP问题（1）minZ=6x1+4x2 (2)maxZ=3x1-2x2 2x1+x2 1 x1+x2 1 3x1+4x2 3 2x1+2x2 4 x1，x2 0 x1，x2 0第21页，共120页，编辑于2022年，星期一2、对下面LP问题(1)用图解法求解(2)写出此问题的标准形式(3)求剩余变量的值 min

12、Z=11x1+8x2 s.t.10 x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x2 0第22页，共120页，编辑于2022年，星期一图解法的灵敏度分析图解法的灵敏度分析n1、目标函数中的系数Ci的灵敏度分析分析Ci在什么范围内变化，原最优解不变原最优解不变 C1=50 C2=100第23页，共120页，编辑于2022年，星期一EADCBF第24页，共120页，编辑于2022年，星期一 直线BC 的斜截式为：x x2 2=-x=-x1 1+300+300 斜率为-1 直线BF 的斜截式为：x2=0 x1+250 斜率为0 目标函数Z=c1x1+c2x2的斜截式为：x=

13、-c1/c2x1+z/c2 斜率为-c1/c2 所以,当-1-c/c0时，顶点B仍然是最优解 假设c2 不变,则有-1-c1/100 0，解之得0 c1100，第25页，共120页，编辑于2022年，星期一练习：计算计算C 在什么范围内变化时顶在什么范围内变化时顶 点点B 仍然是最优解仍然是最优解第26页，共120页，编辑于2022年，星期一2、约束条件右边约束条件右边b系数的灵敏度分析系数的灵敏度分析 b b变化时通常引起可行域的变化从而引起最优解的变化。变化时通常引起可行域的变化从而引起最优解的变化。设例设例1 1中的设备台时增加了中的设备台时增加了1010个台时数个台时数,则约束变为：则

14、约束变为：x x1 1+x+x2 2310 310 代入求得新的最优解为代入求得新的最优解为x x1 1=60,x=60,x2 2=250 =250 Z=5060+100250=28000 Z=5060+100250=28000比原来最大的利润比原来最大的利润2750027500增加了增加了500500元元,可知每增加一个台时的设可知每增加一个台时的设备可多获利润备可多获利润500/10=50500/10=50元元 在约束条件右边常量每增加一个单位而使最在约束条件右边常量每增加一个单位而使最优目标函数得到改进的量称为这个约束条件的优目标函数得到改进的量称为这个约束条件的对偶价格对偶价格第27页

15、，共120页，编辑于2022年，星期一 练习：练习：将原料将原料A A增加增加1010千克计算最优解和最优值千克计算最优解和最优值某一约束条件的对偶价格仅仅在某一某一约束条件的对偶价格仅仅在某一范围内有效范围内有效总结当约束条件右边常数增加一个单位时：当约束条件右边常数增加一个单位时：(1)(1)如果对偶价格大于零如果对偶价格大于零,则最优目标函数值得到改进则最优目标函数值得到改进,即即求最大值时变得更大求最大值时变得更大;求最小值时变得更小求最小值时变得更小(2)(2)如果对偶价格小于零如果对偶价格小于零,则最优目标函数值变坏则最优目标函数值变坏,即求最即求最大值时变得小了大值时变得小了;求

16、最小值时变得大了求最小值时变得大了(3)(3)如果对偶价格等于零如果对偶价格等于零,则最优目标函数值不变则最优目标函数值不变第28页，共120页，编辑于2022年，星期一练习练习:某公司目前正生产甲乙两种产品公司目前正生产甲乙两种产品,产量分别为产量分别为 30个和个和120个个,公司经理希望了解是否通过改变公司经理希望了解是否通过改变 这两种产品的数量而提高公司的利润这两种产品的数量而提高公司的利润.公司制造公司制造 每个产品所需的加工工时和各个车间的加工能每个产品所需的加工工时和各个车间的加工能 力如下表力如下表:车间车间产品甲产品甲产品乙产品乙车间能力车间能力(每天加工工时数每天加工工时

17、数)12030020354032244041.21.5300利润利润/每个产品每个产品(元元)500400第29页，共120页，编辑于2022年，星期一(1)假设生产的全部产品都能销售出去假设生产的全部产品都能销售出去,用图解法确定用图解法确定 最优产品组合最优产品组合(2)在上面求得的最优产品组合中在上面求得的最优产品组合中,那些车间的能力还那些车间的能力还 有剩余有剩余,剩余多少剩余多少?是剩余变量还是松弛变量是剩余变量还是松弛变量?(3)各车间的能力分别增加一个加工工时数给公司带各车间的能力分别增加一个加工工时数给公司带 来多少额外的利润来多少额外的利润.(4)当产品甲的利润不变时当产品

18、甲的利润不变时,产品乙的利润在什么范围产品乙的利润在什么范围 内变化时此最优解不变内变化时此最优解不变?当产品乙的利润不变时当产品乙的利润不变时,产品甲的利润在什么范围内变化时最优解不变产品甲的利润在什么范围内变化时最优解不变.(5)当产品甲的利润从当产品甲的利润从500降为降为450元元,而产品乙的利润而产品乙的利润 从从400元增加为元增加为430元时元时,原来产品组合是否依然是原来产品组合是否依然是 最优产品组合最优产品组合.第30页，共120页，编辑于2022年，星期一第31页，共120页，编辑于2022年，星期一第32页，共120页，编辑于2022年，星期一第33页，共120页，编辑

19、于2022年，星期一第34页，共120页，编辑于2022年，星期一2.3 LP的应用的应用n一.人力资源分配问题人力资源分配问题n例例1.某昼夜服务的公交线路每天各时间段所需司某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下：机和乘务人员数如下：班次 时间 所需人数 1 6：00-10：0060 2 10：00-14：0070 3 14：00-18：0060 4 18：00-22：0050 5 22：00-2：0020 6 2：00-6：0030第35页，共120页，编辑于2022年，星期一设司机和乘务人员分别在各时段一开始时上班设司机和乘务人员分别在各时段一开始时上班,并连续工作并连

20、续工作8小时小时,问该公交线路怎样安排人员问该公交线路怎样安排人员,既能满足工作需要又配备最少司机和乘务人员。既能满足工作需要又配备最少司机和乘务人员。第36页，共120页，编辑于2022年，星期一设xi表示第i班次开始上班的人员s.t.minZ=X1+X2+X3+X4+X5+X6 X1+X6 60 X1+X2 70 X2+X3 60 X3+X4 50 X4+X5 20 X5+X630 X1,X2,X3,X4,X5,X6 0第37页，共120页，编辑于2022年，星期一最优解最优解 ：x=50 x=20 x=50 x=0 x=20 x=10 最优目标函数值最优目标函数值 Z=150第38页，共

21、120页，编辑于2022年，星期一【练习练习】某中型百货商场对售货人员的需求统计如下表某中型百货商场对售货人员的需求统计如下表,并规并规定售货员每周工作定售货员每周工作5天且连续休息天且连续休息2天，问如何安排天，问如何安排 人员的作人员的作息既满足工作需要又使配备人员最少？息既满足工作需要又使配备人员最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28第39页，共120页，编辑于2022年，星期一解：设解：设x x1 1为星期一开始休息的人数为星期一开始休息的人数,x x2 2为星期二开始休息为星期二开始休息的人数的人数,x x7 7为星期日开始休息

22、的人数为星期日开始休息的人数目标函数目标函数:minZ=x1+x2+x3+x4+x5+x6+x7x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x428 xi 0 第40页，共120页，编辑于2022年，星期一最优解最优解：x1=12 x2=0 x3=11 x4=5 x5=0 x6=8 x7=0 目标函数最小值为目标函数最小值为：36第41页，共120页，编辑于2022年，星期一二二 生产计划问题生产计划问题例例2、某公司生

23、产甲，乙，丙三种产品，这三种某公司生产甲，乙，丙三种产品，这三种产品都要经过铸造，机加工和装配三个车间。甲产品都要经过铸造，机加工和装配三个车间。甲乙两种产品的铸件可以外包协作也可自行生产，乙两种产品的铸件可以外包协作也可自行生产，但丙产品必须本厂铸造才能保证质量。有关情况但丙产品必须本厂铸造才能保证质量。有关情况见下表；公司中可利用的总工时为铸造见下表；公司中可利用的总工时为铸造8000小时小时机加工机加工12000小时和装配小时和装配10000小时。公司为了小时。公司为了获得最大利润，甲，乙，丙三种产品各生产多少获得最大利润，甲，乙，丙三种产品各生产多少件，甲乙两种产品的铸造应多少由本公司

24、完成？件，甲乙两种产品的铸造应多少由本公司完成？多少由外包协作？多少由外包协作？第42页，共120页，编辑于2022年，星期一工时与成本工时与成本甲甲乙乙丙丙每件铸造工时每件铸造工时510 7每件机加工工时每件机加工工时648每件装配工时每件装配工时322自产铸件每件成本自产铸件每件成本354外协铸件每件成本外协铸件每件成本56机加工每件成本机加工每件成本213装配每件成本装配每件成本322每件产品售价每件产品售价231816第43页，共120页，编辑于2022年，星期一解：解：设设x1，x2，x3分别为三道工序都由本公司加工的分别为三道工序都由本公司加工的 甲，乙，丙三种产品的件数，设甲，乙

25、，丙三种产品的件数，设x4，x5分别为由外分别为由外 协铸造再由本公司机加工和装配的甲乙两种产品的协铸造再由本公司机加工和装配的甲乙两种产品的 件数。件数。计算每件产品的利润分别如下：计算每件产品的利润分别如下：产品甲全部自制的利润产品甲全部自制的利润 =23-（3+2+3）=15产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润=23-（5+2+3）=13产品乙全部自制的利润产品乙全部自制的利润 =18-（5+1+2）=10产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润=18-（6+1+2）=9产品丙的利润产品丙的利润 =16-（4+3+2）=7第44页，共120页，

26、编辑于2022年，星期一目标函数目标函数：max Z=15X1+10X2+7X3+13 X4+9X5 5X1+10X2+7X3 80006 X1+4X2+8X3+6 X4+4X5 12000 3X1+2X2+2 X3+3X4+2X5 10000X1,X2,X3,X4,X5 0第45页，共120页，编辑于2022年，星期一三三 套裁下料问题n例例3、某工厂要做、某工厂要做100套钢架，每套用套钢架，每套用29m、21m和和15m的原钢各一根。已知原料每根长的原钢各一根。已知原料每根长74m，问应如何下料，可使所用原料最省。，问应如何下料，可使所用原料最省。第46页，共120页，编辑于2022年，

27、星期一 下料 方案长度291201021002211531203合计7473727166余料001020308第47页，共120页，编辑于2022年，星期一设按各方案下料的原材料根数分别为设按各方案下料的原材料根数分别为X1，X2，X3，X4，X5。目标函数：目标函数：min Z=X1+X2+X3+X4+X5 约束条件：约束条件：X1+2X2 +X4100 2 X3+2X4+X5 100 3X1+X2+2X3+3X5 100 X1，X2，X3，X4，X5 0最优解X1=30 X2=10 X3=0 X4=50 X5=0 Z=90第48页，共120页，编辑于2022年，星期一四四、投资问题、投资问

28、题例例4、某部门现有资金、某部门现有资金200万元，今后五年内考虑以下的万元，今后五年内考虑以下的项目投资，已知项目项目投资，已知项目A：第一年到第五年年初都可投资，：第一年到第五年年初都可投资，当年末能收回本利当年末能收回本利110%。已知项目。已知项目B：第一年到第四：第一年到第四年年初都可投资，次年末能收回本利年年初都可投资，次年末能收回本利125%，但规定每，但规定每年最大投资额不能超过年最大投资额不能超过30万元。项目万元。项目C：第三年初需要：第三年初需要投资，到第五年末能回收本利投资，到第五年末能回收本利140%，但规定最大投资，但规定最大投资额不超过额不超过80万元。项目万元。

29、项目D：第二年初需要投资，到第五：第二年初需要投资，到第五年末能回收本利年末能回收本利155%，但规定最大投资额不超过，但规定最大投资额不超过100万万元。元。问：应如何确定这些项目的每年投资，使得第五年：应如何确定这些项目的每年投资，使得第五年末拥有资金的本利和金额最大？末拥有资金的本利和金额最大？第49页，共120页，编辑于2022年，星期一这是一个连续投资的问题，设：这是一个连续投资的问题，设：X i j=第第i年初投资年初投资j项项目的金额，见表：目的金额，见表：年份年份项目项目12345AX 1AX 2AX 3AX 4AX 5ABX 1BX 2BX 3BX 4BCX 3CDX 2D第

30、50页，共120页，编辑于2022年，星期一目标函数：目标函数：maxz=11X 5A125 X 4B 140X 3C155 X 2D X 1A X 1B=200，X 2A X 2B X 2D=11X 1A，X 3A X 3B X 3C=11 X 2A 125X 1B，X 4A X 4B=11 X 3A 125 X 2B，X 5A=11X 4A 125 X 3B，X i B 30 （i=1，2，3，4），X 3C 80，X 2D 100，X i j0，第51页，共120页，编辑于2022年，星期一五、配料问题 例例5 5：某工厂要用三种原料1、2、3混合调配出三种 不同规格的产品甲、乙、丙，数

31、据如右表。问：该厂应如何安排生产，使利润收入为最大？第52页，共120页，编辑于2022年，星期一解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出 约束条件：规格要求 4 个；供应量限制 3 个第53页，共120页，编辑于2022年，星期一n利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙

32、丙使用的原料单价*原料数量，故有目标函数目标函数Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 约束条件：约束条件：从第1个表中有：x110.5(x11+x12+x13)x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23)第54页，共120页，编辑于2022年，星期一 从第2个表中，生产

33、甲乙丙的原材料不能超过原材料的供应限额，故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60 第55页，共120页，编辑于2022年，星期一习题习题1、某锅炉制造厂要制造一种新锅炉锅炉制造厂要制造一种新锅炉10台，每台锅炉台，每台锅炉需要不同长度的锅炉钢管数量如下：需要不同长度的锅炉钢管数量如下：规格（mm）2640165117701440需要数量（根）835421库存的原材料的长度只有库存的原材料的长度只有5500mm一种规格，问一种规格，问如何下料才能使总的用料根数最少？如何下料才能使总的用料根数最少？第56页，共120页，编辑于2022

34、年，星期一2.、前进电器厂生产前进电器厂生产A，B，C三种产品有关资料如下表三种产品有关资料如下表：产品产品材料消耗材料消耗（千克（千克/件）件）台时消耗台时消耗（台时（台时/件）件）产品利润产品利润（元（元/件）件）市场容量市场容量（件）（件）A1.0210200B1.51.212250C4.0114100资源资源限制限制2000千克千克1000台时台时问问:在资源及市场允许的条件下如何安排生产获利最大在资源及市场允许的条件下如何安排生产获利最大第57页，共120页，编辑于2022年，星期一3.某公司在今后四个月内需租用仓库堆放物资某公司在今后四个月内需租用仓库堆放物资已知各个月所需的仓库面

35、积数字如下表已知各个月所需的仓库面积数字如下表：月份月份1234所需仓库面积所需仓库面积(百平方米百平方米)15102012合同租借期限合同租借期限1个月个月 2个月个月 3个月个月 4个月个月合同期内每百平方米合同期内每百平方米仓库面积的租借费用仓库面积的租借费用2800450060007300表表2表表1第58页，共120页，编辑于2022年，星期一仓库的租借费用仓库的租借费用,当租借合同期限越长时当租借合同期限越长时,享受的折享受的折扣优惠也越大扣优惠也越大,具体数字如表具体数字如表2,租借仓库的合同每租借仓库的合同每月初都可办理月初都可办理,每份合同具体规定租用面积数和每份合同具体规定

36、租用面积数和期限期限.因此该厂可根据需要在任何一个月初办理租因此该厂可根据需要在任何一个月初办理租借合同借合同,且每次办理可签一份也可同时签若干份租用且每次办理可签一份也可同时签若干份租用面积和租借期限不同的合同面积和租借期限不同的合同.求一个所付的租借费为求一个所付的租借费为最小的租借方案最小的租借方案.第59页，共120页，编辑于2022年，星期一设xij(i=1,2,3,4)(j=1,4-i+1)为第i个月初签定的租借期为j个月的合同的租界面积minZ=2800 x11+4500 x12+6000 x13+7300 x14+2800 x21+4500 x22+6000 x23+2800

37、x31+4500 x32+2800 x41 x11+x12+x13+x1415s.t x12+x13+x14+x21+x22+x2310 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x4115 xij 0第60页，共120页，编辑于2022年，星期一4、某公司从两个产地某公司从两个产地A1,A2将货物运往三个销地将货物运往三个销地B1,B2B3,各产地的产量及各销地的销量和各产地运往各销各产地的产量及各销地的销量和各产地运往各销地的每件物品的运费如下表地的每件物品的运费如下表,问如何调运使得总运输问如何调运使得总运输费用最小费用最小?运费运费 销地销地 单价单

38、价产地产地B1B2B3产量产量(件件)A1646200A2655300销量销量150150200第61页，共120页，编辑于2022年，星期一设设xij表示从产地表示从产地Ai调运到调运到Bj的运输量的运输量(i=1,2;j=1,2,3)min f=6x11+4x12+6x13+6x21+5x22+5x23 x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0s.t.第62页，共120页，编辑于2022年，星期一 班次 时间 所需人数 1 6：00-10：0015 2 10：00-14：0025 3 1

39、4：00-18：0020 4 18：00-22：0018 5 22：00-2：0012 6 2：00-6：00105、某医院昼夜24h各时段内需要的护士数量如下：若医院可聘用合同工护士，上班时间同正式护士。护士于每班开始上班，并连续工作8小时，若正式工护士报酬为10元/h,合同工为15元/h,问医院是否应聘用合同工护士及聘用多少名？第63页，共120页，编辑于2022年，星期一6、红英公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额的贷款：2003年100万元、2004年150万元、2005年120万元、2006年110万元。为了充分发挥这笔资金的作用，在满足每年贷款额的情况

40、下，可将多余资金分别用于下列投资项目：（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元。（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，但限购90万元。（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元。（4）于年初将任意数额的资金存放于银行，年息4%，于年底取出。问：该公司应如何运用好这笔筹集到的资金，问：该公司应如何运用好这笔筹集到的资金，使使20022002年底需筹集到的资金数额为最少？年底需筹集到的资金数额为最少？第64页，共120页，编辑于2022年，星期一7、某厂生产

41、甲乙丙丁四种产品，产品甲需经过、某厂生产甲乙丙丁四种产品，产品甲需经过A A、B B两两种机器加工，产品乙需经过种机器加工，产品乙需经过A A、C C两种机器加工，产品两种机器加工，产品丙需经过丙需经过B B、C C两种机器加工，产品丁需经过两种机器加工，产品丁需经过A A、B B两种两种机器加工。有关数据如下，试为该厂制定一个最优的生机器加工。有关数据如下，试为该厂制定一个最优的生产计划。产计划。产 品机器生产率（件/小时）原料成本（元）产品价格（元）ABC甲10201665乙20102580丙10151250丁20101870机器成本 元/小时200150225每周可用小时数1501207

42、0第65页，共120页，编辑于2022年，星期一8 8、某某快快餐餐店店坐坐落落于于一一个个旅旅游游景景点点，平平时时游游客客不不多多，而而在在每每周周六六游游客客猛猛增增。该该快快餐餐店店雇雇佣佣了了两两名名正正式式员员工工，正正式式员员工工每每天天工工作作8 8小小时时，其其余余工工作作由由临临时时工工来来担担任任，临临时时工工每每班班工工作作4 4小小时时。根根据据游游客客就就餐餐情情况况，在在星星期期六六每每个个营营业业小小时时所所需需职职工工数数（包包括括正正式式工工和和临临时时工工）如如下下表表。已已知知一一名名正正式式工工1 11 1点点开开始始上上班班，工工作作 4 4小小时时

43、后后休休息息1 1小小 时时而而后后再再工工作作4 4小小时时；另另一一名名正正式式工工1 13 3点点开开始始上上班班，工工作作 4 4小小时时后后休休息息1 1小小时时，而而后后再再工工作作4 4小小时时。又又知知临临时时工工每每小小时时的的工工资资为为4 4元元。在在满满足足对对职职工工需需求求的的条条件件下下，如如何何安安排排 临临 时时 工工 的的 班班 次次，使使 得得 使使 用用 临临 时时 工工 的的 成成 本本 最最 小小？第66页，共120页，编辑于2022年，星期一时间时间所需职工数所需职工数时间时间所需职工数所需职工数11:00-12:00917:00-18:00612

44、:00-13:00918:00-19:001213:00-14:00919:00-20:001214:00-15:00320:00-21:00715:00-16:00321:00-22:00716:00-17:003第67页，共120页，编辑于2022年，星期一x2x3x4x51 3 x3x4x5x62 3 x4x5x6x71 6 x5x6x7x82 12 x6x7x8x92 12 x7x8x9x101 7 x8x9x10 x111 7 min f=16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11）st x11 9 x1 x21 9 x1 x2x32 9 x1x2x3

45、x42 3 第68页，共120页，编辑于2022年，星期一9、某厂按合同规定于当年每个季度末分别提供、某厂按合同规定于当年每个季度末分别提供10、15、25、20台台同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的成本如下表所示，又如果生产出来的柴油机当季不交货，每台每成本如下表所示，又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用积压一个季度需储存、维护等费用0.15元。要求在完成合同的情况元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。下，做出使该厂全年生产费用最小的决策。季度季度1 12

46、23 34 4生生产产能力能力2525353530301010单单位成本（万元）位成本（万元）10.810.811.111.111.011.011.311.3第69页，共120页，编辑于2022年，星期一2.4 2.4 单纯形法基本原理及计算步骤单纯形法基本原理及计算步骤一、单纯形法的基本思路一、单纯形法的基本思路 从可行域中某一个顶点开始从可行域中某一个顶点开始 判断此顶点是否判断此顶点是否是最优解，如不是则再找另一个使得目标函是最优解，如不是则再找另一个使得目标函数值更优的顶点，称之为迭代。再判断此点数值更优的顶点，称之为迭代。再判断此点是否是最优解。直到找到一个顶点为最优解，是否是最优解

47、。直到找到一个顶点为最优解，就是使得其目标函数值最优的解，或者能判就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解断出线性规划问题无最优解第70页，共120页，编辑于2022年，星期一n最优解一定在可行域的顶点上最优解一定在可行域的顶点上,将顶将顶点坐标代入目标函数有点坐标代入目标函数有:n(0,0):z=30+20=0n(5,0):z=35+20=15n(0,8):z=30+28=16n(2,6):z=32+26=18n单纯形法的基本思路就是基本可单纯形法的基本思路就是基本可行解的转移，先找到一个初始基行解的转移，先找到一个初始基本可行解，如果不是最优解，设本可行解，如果不是最

48、优解，设法转移到另一个基本可行解，并法转移到另一个基本可行解，并使目标函数值不断增加，直到找使目标函数值不断增加，直到找到最优解到最优解。(5,0)(2,6)108302 5 8x2(0,8)x1第71页，共120页，编辑于2022年，星期一 二、单纯形法计算步骤：二、单纯形法计算步骤：1、找出一个初始基本可行解、找出一个初始基本可行解 单纯形法中可行域的顶点叫做基本可行解，找到的第一个基本可行解叫做初始基本可行解第72页，共120页，编辑于2022年，星期一目标函数目标函数 max Z=50 x1+100 x2 x1+x2+s1 =300 2x1+x2 +s2 =400 x2 +s3=250

49、 x1,x2,s1,s2,s3,0系数矩阵系数矩阵A=1 1 1 0 0 2 1 0 1 0 0 1 0 0 1由于由于A中存在一个不为零的三阶子式，可知中存在一个不为零的三阶子式，可知A的秩为的秩为3因为因为A的秩的秩m小于此方程组的变量的个数小于此方程组的变量的个数 n，可知其有，可知其有无穷多组解无穷多组解第73页，共120页，编辑于2022年，星期一基本概念基本概念 基基：已知A是约束条件的mn系数矩阵，其秩 为m，若B是A中mm阶可逆矩阵，则称B 是线形规划问题中的一个基。B是由A中m个线形无关的系数列向量组成的。本例中 1 1 1 与 1 0 0 2 1 0 0 1 0 0 1 0

50、 0 0 1 都是该线性规划的一个基。它们都是由3个线性 无关的系数列向量组成。第74页，共120页，编辑于2022年，星期一基向量基向量:基基B中的一列称为一个基向量。基中的一列称为一个基向量。基B中共有中共有m 个基向量个基向量非基向量非基向量:在在A中除了基中除了基B之外的一切列称为基之外的一切列称为基B的的非基非基 向量向量基变量基变量:与基向量与基向量pi对应的变量对应的变量xi叫做基变量叫做基变量,基变量有基变量有m个个非基变量非基变量:与非基向量与非基向量pj对应的变量对应的变量xj叫做非基变量叫做非基变量,基基 变量有变量有n-m个个.例中对基基B1=1 1 1 来说来说 1