《教学课件PPT线性规划》由会员分享，可在线阅读，更多相关《教学课件PPT线性规划（98页珍藏版）》请在金锄头文库上搜索。
1、运筹学 Operations ResearchChapter 1 线性规划 Linear Programming1.1 LP的数学模型 Mathematical Model of LP 1.2 图解法 Graphical Method 1.3 标准型 Standard form of LP 1.4 基本概念 Basic Concepts 1.5 单纯形法 Simplex MethodDate1.1 数学模型 Mathematical Model Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 3 1.1 线性规划的数学模型
2、Mathematical Model of LP线性规划通常研究资源的最优利用、设备最佳运行等 问题。例如，当任务或目标确定后，如何统筹兼顾，合理 安排，用最少的资源 （如资金、设备、原标材料、人工、 时间等）去完成确定的任务或目标；企业在一定的资源条 件限制下，如何组织安排生产获得最好的经济效益（如产 品量最多 、利润最大）。线性规划（Linear Programming,缩写为LP）是运筹学的 重要分支之一，在实际中应用得较广泛，其方法也较成熟， 借助计算机，使得计算更方便，应用领域更广泛和深入。Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear Prog
3、rammingPage 4 【例1.1】最优生产计划问题。某企业在计划期内计划生产甲、 乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需 要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加 工及所需要的资源如表1.1所示。已知在计划期内设备的加工能 力各为200台时，可供材料分别为360、300公斤；每生产一件甲 、乙、丙三种产品，企业可获得利润分别为40、30、50元，假 定市场需求无限制。企业决策者应如何安排生产计划，使企业 在计划期内总的利润收入最大？1.1 线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例Date南京理工大学经济
4、管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 5 产产品资资源甲乙 丙现现有资资源设备设备 A 3 1 2 200 设备设备 B 2 2 4 200 材料C 4 5 1 360 材料D 2 3 5 300 利润润（元/件） 40 30 50表1.1 产品资源消耗1.1 线性规划的数学模型 Mathematical Model of LPDate南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 6 【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型 为：1.1 线性规划的数学
5、模型 Mathematical Model of LP产产品资资源甲乙 丙现现有资资 源设备设备 A 3 1 2 200 设备设备 B 2 2 4 200 材料C 4 5 1 360 材料D 2 3 5 300 利润润（元/ 件） 40 30 50最优解X=(50,30,10);Z=3400Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 7 线性规划的数学模型由决策变量 Decision variables 目标函数Objective function 及约束条件Constraints 构成。称为三个要素。n其特征是：n1解
6、决问题的目标函数是多个决策变量的线性函数，通 常是求最大值或 最小值；n2解决问题的约束条件约束条件是一组多个决策变量的线性不等 式或等式。怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型 Mathematical Model of LPDate南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 8 【例1.2】某商场决定：营业员每周连续工作5天后连续休息2天， 轮流休息。根据统计，商场每天需要的营业员如表1.2所示。表1.2 营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员 最少。 星期需要人数星期
7、需要人数 一300五480 二300六600 三350日550 四4001.1 线性规划的数学模型 Mathematical Model of LPDate南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 9 【解】 设xj(j=1，2，7)为休息2天后星期一到星期日开始上班 的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型 Mathematical Model of LP星 期需要 人数星 期需要 人数 一300五480 二300六600 三350日550 四400Date南京理工大学经济管理学院 包文彬 Chapt
8、er 1 线性规划 Linear ProgrammingPage 10 1 X10 C1404 =300104 2 X267 C2301 =3001 3 X3146 C3350 =3500 4 X4170 C4400 =4000 5 X597 C5480 =4800 6 X6120 C6600 =6000 7 X717 C7550 =5500最优解：Z617（人）Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 11 【例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格 的轴各一根，这些轴的规格分别是1.5，1，0.7（m
9、），这些轴需 要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车 ，最少要用多少圆钢来生产这些轴？ 表13 下料方案方案 规规格1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m ）00.30.5 0.1o.4 00.30.60.20.51.1 线性规划的数学模型 Mathematical Model of LPDate南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 12 解设xj(j=1,2,10)为第j种
10、下料方案所用圆钢的根数。则用料 最少数学模型为为: :1.1 线性规划的数学模型 Mathematical Model of LP方案 规规格1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）00.30.5 0.1o.4 00.30.60.20.5Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 13 1 X1500 2 X20 3 X30 4 X40 5 X50 6 X662.5 7 X70 8 X80 9 X
11、9250 10 X100 Z812.5Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 14 【例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格 是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于 35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级别 的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。矿 石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量 。假设矿石在冶炼过程中，合金含量没有发生变化。表1.4 矿石的金属含量合金 矿矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费费用（元/t ）1
12、251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型 Mathematical Model of LPDate南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 15 解: 设xj（j=1,2，5）是第j 种矿石数量1.1 线性规划的数学模型 Mathematical Model of LP矿矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费费用（元/t ） 12510102530340 240003030260 301552060180 420200
13、4020230 585151755190Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 16 Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 17 【例1.5】投资问题。某投资公司在第一年有200万元资金，每年都有如下的 投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续 投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍 金额”。投资公司决定最优的投资策略使第六年所掌握的资金最多。第五年：(x7/2+x9)=x8+2x5第一年：x1+
14、x2=200(万元)第二年：(x1/2 +x3)+x4=x2第三年(x3/2+x5)+x6=x4+2x1第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型 1.1 线性规划的数学模型 Mathematical Model of LP【解】设 x1：第一年的投资； x2：第一年的保留资金x3：第二年新的投资； x4：第二年的保留资金x5：第三年新的投资； x6：第三年的保留资金x7：第四年新的投资 x8：第四年的保留资金x9：第五年的保留资金 Date南京理工大学经济管理学院 包文彬 Chapter 1 线性规划 Linear ProgrammingPage 18 1.1 线性规划的数学模型 Mathematical Model of LP1 X155.2846 2 X2144.7155 3 X3117.0732 4 X40 5 X552.0325 6 X60 7 X7208.1301 8 X80 9 X90最优解：Z 416.26万元x1：第一年的投资； x2：第一年的保留资金x3：第二年新的投
