(完整版)Ch1线性规划_1

1、2021-11-201建建 模模 练练 习习【例【例1.2】某商场决定：营业员每周连续工作】某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。 1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp【解】【解】 设设xj(j=1，2，7)为休息为休息2天后星期一到星

2、期日开始上班天后星期一到星期日开始上班的营业员的营业员7 ,2, 1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzj1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp10112345134678924578910min22 1000 +2 432 1000 23 + 24510000,1,2,jjjzxxxxxxxxxxxxxxxxxxxxxj.,105,.,2, 1,01

3、45.08.04.07.07.035.017.04.02.03.025.055.017.04.02.03.025.01.015.005.01.015.005.02.015.01.028.008.02.04.025.0190230180260340min5432154321543215315431542154321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzj【例【例1.6】均衡配套生产问题。某产品由】均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。须经设备须经设备a、b加工，甲在加工，甲在a、b上的加工时间分别为上的加工时间分别为5和和9分

4、钟，乙在分钟，乙在a、b上的加工时间分别为上的加工时间分别为4和和10分钟。现有分钟。现有2a和和3b，每天可供加工时间，每天可供加工时间为为8小时。设备均衡负荷生产，一种设备每天的加工总时间不超过另一小时。设备均衡负荷生产，一种设备每天的加工总时间不超过另一种设备总时间种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。小时。怎样安排设备的加工时间使每天产品的产量最大。【解】【解】 设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是)31,21min(21xxy 设备设备a、b加工工时约束加工工时约束608310960824

5、52121xxxx一种设备每台每天的加工时间不超过另一种设备一种设备每台每天的加工时间不超过另一种设备1小时的约束小时的约束 60)109()452121xxxx（1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp2131,21xyxy60)109()45(60)109()45(21212121xxxxxxxx1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp121212121212m a x1213549 6 091 01 4 4 0466 0466 00zyyxyxxxxxxxxxyxx、2021-11

6、-2010产地销地 a1 10 a2 8 a3 5 b4 3 b3 8 b2 7 b1 5354231682329物资调运物资调运总运费最低总运费最低需求得到满足需求得到满足2021-11-201134333231242322211413121192428353623minxxxxxxxxxxxxz5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 4,3,2, 13,2, 1,0jixij；2021-11-2012设

7、备更新问题2008年初购新或役龄1年或2年设备，生产5年，至2012年底卖掉。求利润最大的方案役龄0 1 2 3 4 5 6 7价格年利润以旧换新费用50 42 38 30 22 10 5 515 13 12 10 7 2 -1 -1 0 8 12 20 28 40 45 452021-11-2013【例】【例】最短路径问题最短路径问题 下图表示从起点下图表示从起点a到终点到终点e之之间各点的距离。求间各点的距离。求a到到e的最短路径。的最短路径。 v2v3v4v7v5v9v6v8v1028512131071013112865885405847v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段

8、1217142019运筹学运筹学operations researchchapter 1 线性规划线性规划linear programming1.1 lp的数学模型的数学模型 mathematical model of lp1.2 图解法图解法 graphical method1.3 标准型标准型 standard form of lp1.4 基本概念基本概念 basic concepts1.5 单纯形法单纯形法 simplex method1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp 线性规划通常研究资源的最优利用、设备最佳运行等问线性规划通

9、常研究资源的最优利用、设备最佳运行等问题。题。 当任务或目标确定后，如何统筹兼顾，合理安排，用最当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源少的资源 （如资金、设备、原材料、人工、时间等）去完（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标。成确定的任务或目标。 企业在一定的资源条件限制下，如何组织安排生产获得企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产量最多最好的经济效益（如产量最多 、利润最大）。、利润最大）。【例【例1.1】最优生产计划问题。】最优生产计划问题。1.1 线性规划的数学模型线性规划的数学模型 mathematical mode

10、l of lp1.1.1 应用模型举例应用模型举例321503040maxxxxz0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解】设【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量分别为甲、乙、丙三种产品的产量1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp最优解最优解x=(50,30,10);z=3400线性规划的数学模型线性规划的数学模型决策变量决策变量 decision variables 目标函数目标函数 objective function约束条件约束条件 co

11、nstraints1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数线性函数，通常是求最大值或，通常是求最大值或 最小值；最小值；2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的的线性线性不等式或等式。不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp1.1.2 线性规划的一般模型线性规划的一般模型 一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决个决策变量策变量xj, j=1,2,

12、n，目标函数的变量系数用，目标函数的变量系数用cj表示表示, cj称为称为价值价值系数系数。约束条件的变量系数用。约束条件的变量系数用aij表示，表示，aij称为称为工艺系数工艺系数。约束。约束条件右端的常数用条件右端的常数用bi表示，表示，bi称为称为资源限量资源限量。112211112211211222221122max(min)(,)(,)(,)0,1,2,nnnnnnmmmnnmjzc xc xc xa xa xa xba xaxaxbaxaxaxbxjn 或或或1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp11max(min)(, )1

13、,2,0,1,2,njjjnijjijjzc xa xbinxjn 或在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 mathematical model of lp2021-11-2021军事可能性建建 模模 练练 习（续）习（续）某轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升（l）、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2公里，携带轻型炸弹时每升汽油可飞行3公里。又知每架飞机每次只能装载一枚炸弹，每出

14、发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4公里）外，起飞和降落每次各消耗100升。有关数据如表所示。为了使摧毁敌方军事目标的可能性最大，应如何确定飞机轰炸的方案。要求建立这个问题的线性规划模型。 要害部位离机场距离/公里摧毁可能性每枚重型弹每枚轻型弹12344504805406000.100.200.150.250.080.160.120.202021-11-2022军事可能性1311121423212224min(1 0.1)(1 0.2)(1 0.15)(1 0.25)(1 0.08)(1 0.16)(1 0.12)(1 0.2)xxxxxxxxz 111213142122232

15、4111213142122232411121311.54501.54801.55401.560022221.754501.754801.755401.756003333100()48000 xxxxxxxxxxxxxxxxxxxx42122232432 48 0ijxxxxx1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材作业：教材p36 11.1 线性规划的数学模型线性规划的数学模型 mathemat

16、ical model of lp下一节：图解法下一节：图解法图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非负要求的分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。

17、求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最求最大大值时直线沿着矢量方向移动值时直线沿着矢量方向移动 求最求最小小值时沿着矢量的值时沿着矢量的反反方向移动方向移动1.2 图解法图解法the graphical methodx1x2o1020304010203040(3,4)(15,10)最优解最优解x=(15,10)最优值最优值z=8540221xx305 . 121xx0, 0305 .

18、 1402212121xxxxxx例例1.72143maxxxz1.2 图解法图解法the graphical method246x1x2246最优解最优解x=(3,1)最优值最优值z=5(3,1)006346321212121xxxxxxxx、min z=x1+2x2例例1.8(1,2)1.2 图解法图解法the graphical method246x1x2246x（2）（3,1）x（1）（1,3）(5,5)006346321212121xxxxxxxx、min z=5x1+5x2例例1.9有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 ,)1 ()2() 1 (xxx 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 图解法图解法the graphical method246x1x2246(1,2)0