资源描述
运筹学运筹学Operations ResearchChapter 1 线性规划线性规划Linear Programming1.1 LP的数学模型的数学模型 Mathematical Model of LP1.2 图解法图解法 Graphical Method1.3 标准型标准型 Standard form of LP1.4 基本概念基本概念 Basic Concepts1.5 单纯形法单纯形法 Simplex Method运筹学运筹学Chapter 1 线性规划线性规划1.1 LP的数学模型的数学模型 1.1 数学模型数学模型 Mathematical Model 1.1 数学模型数学模型 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 3 08 七月 20241.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP线性规划线性规划（Linear Programming,缩写为LP）通常研究资源通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源确定后，如何统筹兼顾，合理安排，用最少的资源（如资（如资金、设备、原标材料、人工、时间等）去完成确定的任务金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多产获得最好的经济效益（如产品量最多、利润最大）。、利润最大）。13 八月八月 20231.1 线性规划的数学模型线性规划的数学模型 Mathe 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 4 08 七月 2024【例例1-1】生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙两两种种产产品品。按按工工艺艺资资料料规规定定，每每件件产产品品甲甲需需要要消消耗耗材材料料A 2公公斤斤，消消耗耗材材料料B 1公公斤斤，每每件件产产品品乙乙需需要要消消耗耗材材料料A 1公公斤斤，消消耗耗材材料料B 1.5公公斤斤。已已知知在在计计划划期期内内可可供供材材料料分分别别为为40、30公公斤斤；每每生生产产一一件件甲甲、乙乙两两产产品品，企企业业可可获获得得利利润润分分别别为为40、30元元，如如表表11所所示示。假假定定市市场场需需求求无无限限制制。企企业业决决策策者者应应如如何何安安排排生生产计划，使企业在计划期内总的利润收入最大。产计划，使企业在计划期内总的利润收入最大。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例应用模型举例13 八月八月 2023【例【例1-1】生产计划问题。某企业在计划期】生产计划问题。某企业在计划期 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 5 08 七月 2024【解解】设设x1、x2分别为甲、乙产品的产量，数学模型为：分别为甲、乙产品的产量，数学模型为：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 产品产品 资源资源 甲甲 乙乙现有资现有资源源材料材料C2 21 14040材料材料D1 11.51.53030利润（元利润（元/件）件）300300400400表表1-113 八月八月 2023【解】设【解】设x1、x2分别为甲、乙产品的产量分别为甲、乙产品的产量 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 6 08 七月 2024线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函数Objective function及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的约束条件约束条件约束条件约束条件是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023线性规划的数学模型由决策变量线性规划的数学模型由决策变量 Decis 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 7 08 七月 2024【例例1-2】某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1-2所示。所示。表表1-2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023【例【例1-2】某商场决定：营业员每周连续工】某商场决定：营业员每周连续工 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 8 08 七月 2024【解解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上班天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四40013 八月八月 2023【解】【解】设设xj(j=1，2，7)为休为休 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 9 08 七月 20241 1 X1X10 0 C1C1404404=3003001041042 2 X2X26767 C2C2301301=3003001 13 3 X3X3146146 C3C3350350=3503500 04 4 X4X4170170 C4C4400400=4004000 05 5 X5X59797 C5C5480480=4804800 06 6 X6X6120120 C6C6600600=6006000 07 7 X7X71717 C7C7550550=5505500 0最优解：最优解：Z617（人）（人）1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 20231X10C1404=3001042X2 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 10 08 七月 2024【例例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长），这些轴需要用同一种圆钢来做，圆钢长度为度为4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？【解解】这是一个条材下料问题这是一个条材下料问题，设切口宽度为零。，设切口宽度为零。设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1-3所示。所示。表表1-3 下料方案下料方案 方案方案规格规格 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 LP13 八月八月 2023【例【例1-3】合理用料问题。某汽车需要用甲】合理用料问题。某汽车需要用甲 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 11 08 七月 2024设设xj(j=1,2,10)为为第第j种种下下料料方方案案所所用用圆圆钢钢的的根根数数。则则用用料料最最少少数学模型数学模型为为为为:求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案。如果方案较多，用计算。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。机编程排方案，去掉余料较长的方案，进行初选。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.513 八月八月 2023设设xj(j=1,2,10)为第为第j种下料种下料 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 12 08 七月 20241 1 X1X15005002 2 X2X20 03 3 X3X30 04 4 X4X40 05 5 X5X50 06 6 X6X662.562.57 7 X7X70 08 8 X8X80 09 9 X9X92502501010 X10X100 0Z812.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 20231X15002X203X304X405X 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 13 08 七月 2024【例例1-4】配配料料问问题题。某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他成成分分。钢钢铁铁公公司司拟拟从从五五种种不不同同级级别别的的矿矿石石中中进进行行冶冶炼炼，每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1-4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最最低低的的矿矿物物数数量量。假设矿石在冶炼过程中，合金含量没有发生变化。假设矿石在冶炼过程中，合金含量没有发生变化。表表1-4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）1251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023【例【例1-4】配料问题。某钢铁公司生产一种】配料问题。某钢铁公司生产一种 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 14 08 七月 2024解解:设设xj（j=1,2，5）是第）是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 注注意意，矿矿石石在在实实际际冶冶炼炼时时金金属属含含量量会会发发生生变变化化，建建模模时时应应将将这这种种变变化化考考虑虑进进去去，有有可可能能是是非非线线性性关关系系。配配料料问问题题也也称称配配方方问问题题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）12510102530340240003030260301552060180420200402023058515175519013 八月八月 2023解解:设设xj（j=1,2，5）是第）是第j 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 15 08 七月 20241 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最优解：最优解：Z=347.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 20231X102X20.33333X304X4 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 16 08 七月 20241.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例例1-5】投资问题。某投资公司拟将投资问题。某投资公司拟将5000万元的资金用于国万元的资金用于国债、地方国债及基金三种类型证券投资，每类各有两种。每种债、地方国债及基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后收益率见表证券的评级、到期年限及每年税后收益率见表1-5所示。所示。表表15 证券投资方案证券投资方案序序号号证券类型证券类型 评级评级 到期年限到期年限 每年税后每年税后收益率收益率(%)1国债国债1 1 83.22国债国债2 1 103.83地方债券地方债券1 2 44.34地方债券地方债券2 3 64.75基金基金1 4 34.26基金基金2 5 44.6 决策者希望：国债决策者希望：国债投资额不少于投资额不少于1000万，万，平均到期年限不超过平均到期年限不超过5年，平均评级不超年，平均评级不超过过2。问每种证券各。问每种证券各投资多少使总收益最投资多少使总收益最大。大。13 八月八月 20231.1 线性规划的数学模型线性规划的数学模型 Mathe 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 17 08 七月 20241.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP解解 设设xj(j=1,2,，6)为第为第j种证券的投资额，目标函数是税后总收种证券的投资额，目标函数是税后总收益为益为资金约束：资金约束：国债投资额约束：国债投资额约束：平均评级约束：平均评级约束：平均到期年限约束：平均到期年限约束：13 八月八月 20231.1 线性规划的数学模型线性规划的数学模型 Mathe 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 18 08 七月 2024整理后得到线性规划模型整理后得到线性规划模型1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023整理后得到线性规划模型整理后得到线性规划模型1.1 线性规划的线性规划的 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 19 08 七月 2024【例例1-6】均均衡衡配配套套生生产产问问题题。某某产产品品由由2件件甲甲、3件件乙乙零零件件组组装装而而成成。两两种种零零件件必必须须经经过过设设备备A、B上上加加工工，每每件件甲甲零零件件在在A、B上上的的加加工工时时间间分分别别为为5分分钟钟和和9分分钟钟，每每件件乙乙零零件件在在A、B上上的的加加工工时时间间分分别别为为4分分钟钟和和10分分钟钟。现现有有2台台设设备备A和和3台台设设备备B，每每天天可可供供加加工工时时间间为为8小小时时。为为了了保保持持两两种种设设备备均均衡衡负负荷荷生生产产，要要求求一一种种设设备备每每天天的的加加工工总总时时间间不不超超过过另另一一种种设设备备总总时时间间1小小时时。怎怎样样安安排排设设备备的的加加工工时时间间使使每每天天产产品品的的产量最大。产量最大。【解解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约束小时的约束为为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023【例【例1-6】均衡配套生产问题。某产品由】均衡配套生产问题。某产品由2 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 20 08 七月 2024目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于整理得等价于整理得 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 21 08 七月 20241.1.2 线性规划的一般模型线性规划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中，有有m个个约约束束，有有n个个决决策策变变量量xj,j=1,2,n，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束束条条件件右右端端的的常常数数用用bi表表示示，bi称称为为资资源源限限量量。则则线线性性规规划划数数学学模模型型的的一一般般表表达达式可写成式可写成为了书写方便，上式也可写成：为了书写方便，上式也可写成：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 20231.1.2 线性规划的一般模型为了书写方线性规划的一般模型为了书写方 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 22 08 七月 2024在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 2023在实际中一般在实际中一般xj0,但有时但有时xj0或或x 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 23 08 七月 20241.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP13 八月八月 20231.什么是线性规划，掌握线性规划在管理中什么是线性规划，掌握线性规划在管理中1.2 图解法图解法 Graphical Method1.2 图解法图解法 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 25 08 七月 2024图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非 负要求的负要求的区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动1.2 图解法图解法The Graphical Method13 八月八月 2023图解法的步骤：图解法的步骤：1.求可行解集合。分别求出求可行解集合。分别求出 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 26 08 七月 2024x1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优值最优值Z=8500例例1-71.2 图解法图解法The Graphical Method13 八月八月 2023x1x2O102030401020304 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 27 08 七月 2024246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例1-8(1,2)1.2 图解法图解法The Graphical Method13 八月八月 2023246x1x2246最优解最优解X=(3,1)制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 28 08 七月 2024246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例1-9有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2 图解法图解法The Graphical Method13 八月八月 2023246x1x2246X（2）（）（3,1）制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 29 08 七月 2024246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例1-101.2 图解法图解法The Graphical Method13 八月八月 2023246x1x2246(1,2)无界解无界解(无无 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 30 08 七月 2024x1x2O10203040102030405050无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例1-111.2 图解法图解法The Graphical Method13 八月八月 2023x1x2O102030401020304 制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 31 08 七月 2024由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1-7例例1-8)2.有多重解有多重解(例例1-9)3.有无界解有无界解(例例1-10)4.无可行解无可行解(例例1-11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法The Graphical Method13 八月八月 2023由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式：种形式：制作与教学 武汉理工大学管理学院 熊伟 Chapter 1 线性规划线性规划Linear Programming Page 32 08 七月 20241.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动1.2 图解法图解法The Graphical Method13 八月八月 20231.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式
展开阅读全文