数据、模型与决策MBA课程-Ch1线性规划课件_第1页
数据、模型与决策MBA课程-Ch1线性规划课件_第2页
数据、模型与决策MBA课程-Ch1线性规划课件_第3页
数据、模型与决策MBA课程-Ch1线性规划课件_第4页
数据、模型与决策MBA课程-Ch1线性规划课件_第5页
已阅读5页,还剩59页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

运筹学OperationsResearchChapter1线性规划LinearProgramming1.1LP的数学模型

MathematicalModelofLP1.2图解法

GraphicalMethod1.3标准型

StandardformofLP1.4基本概念

BasicConcepts1.5单纯形法

SimplexMethod运筹学Chapter1线性规划1.1LP的数学模型1.1数学模型

MathematicalModel1.1数学模型03一月20231.1线性规划的数学模型MathematicalModelofLP线性规划(LinearProgramming,缩写为LP)通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。28十二月20221.1线性规划的数学模型Math03一月2023【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定,每件产品甲需要消耗材料A2公斤,消耗材料B1公斤,每件产品乙需要消耗材料A1公斤,消耗材料B1.5公斤。已知在计划期内可供材料分别为40、30公斤;每生产一件甲、乙两产品,企业可获得利润分别为40、30元,如表1-1所示。假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大。1.1线性规划的数学模型MathematicalModelofLP1.1.1应用模型举例28十二月2022【例1-1】生产计划问题。某企业在计划03一月2023【解】设x1、x2分别为甲、乙产品的产量,数学模型为:1.1线性规划的数学模型MathematicalModelofLP

产品

资源

乙现有资源材料C2140材料D11.530利润(元/件)300400表1-128十二月2022【解】设x1、x2分别为甲、乙产品的产03一月2023线性规划的数学模型由决策变量

Decisionvariables

目标函数Objectivefunction及约束条件Constraints构成。称为三个要素。其特征是:1.解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;2.解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型?1.1线性规划的数学模型MathematicalModelofLP28十二月2022线性规划的数学模型由决策变量Deci03一月2023【例1-2】某商场决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,商场每天需要的营业员如表1-2所示。表1-2营业员需要量统计表商场人力资源部应如何安排每天的上班人数,使商场总的营业员最少。星期需要人数星期需要人数一300五480二300六600三350日550四4001.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-2】某商场决定:营业员每周连续03一月2023【解】设xj(j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为1.1线性规划的数学模型MathematicalModelofLP星期需要人数星期需要人数一300五480二300六600三350日550四40028十二月2022【解】设xj(j=1,2,…,7)为03一月20231X10C1404>=3001042X267C2301>=30013X3146C3350>=35004X4170C4400>=40005X597C5480>=48006X6120C6600>=60007X717C7550>=5500最优解:Z=617(人)1.1线性规划的数学模型MathematicalModelofLP28十二月20221X10C1404>=3001042X03一月2023【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根,这些轴的规格分别是1.5,1,0.7(m),这些轴需要用同一种圆钢来做,圆钢长度为4m。现在要制造1000辆汽车,最少要用多少圆钢来生产这些轴?【解】这是一个条材下料问题,设切口宽度为零。设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式1.5y1+y2+0.7y3≤4表示,求这个不等式关于y1,y2,y3的非负整数解。象这样的非负整数解共有10组,也就是有10种下料方式,如表1-3所示。表1-3下料方案

方案规格12345678910需求量y1(根)

22111000001000y210210432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.51.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-3】合理用料问题。某汽车需要用03一月2023设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:求下料方案时应注意,余料不能超过最短毛坯的长度;最好将毛坯长度按降的次序排列,即先切割长度最长的毛坯,再切割次长的,最后切割最短的,不能遗漏了方案。如果方案较多,用计算机编程排方案,去掉余料较长的方案,进行初选。1.1线性规划的数学模型MathematicalModelofLP

方案规格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.528十二月2022设xj(j=1,2…,10)为第j种下03一月20231X15002X203X304X405X506X662.57X708X809X925010X100Z=812.51.1线性规划的数学模型MathematicalModelofLP28十二月20221X15002X203X304X40503一月2023【例1-4】配料问题。某钢铁公司生产一种合金,要求的成分规格是:锡不少于28%,锌不多于15%,铅恰好10%,镍要界于35%~55%之间,不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼,每种矿物的成分含量和价格如表1-4所示。矿石杂质在治炼过程中废弃,现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中,合金含量没有发生变化。表1-4矿石的金属含量

合金矿石锡%锌%铅%镍%杂质费用(元/t)1251010253034024000303026030155206018042020040202305851517551901.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-4】配料问题。某钢铁公司生产一03一月2023解:设xj(j=1,2,…,5)是第j种矿石数量,得到下列线性规划模型注意,矿石在实际冶炼时金属含量会发生变化,建模时应将这种变化考虑进去,有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题,在许多行业生产中都能遇到。1.1线性规划的数学模型MathematicalModelofLP矿石锡%锌%铅%镍%杂质费用(元/t)12510102530340240003030260301552060180420200402023058515175519028十二月2022解:设xj(j=1,2,…,5)是第03一月20231X102X20.33333X304X40.58335X50.6667最优解:Z=347.51.1线性规划的数学模型MathematicalModelofLP28十二月20221X102X20.33333X304X03一月20231.1线性规划的数学模型MathematicalModelofLP【例1-5】投资问题。某投资公司拟将5000万元的资金用于国债、地方国债及基金三种类型证券投资,每类各有两种。每种证券的评级、到期年限及每年税后收益率见表1-5所示。表1-5证券投资方案序号证券类型评级到期年限每年税后收益率(%)1国债1183.22国债21103.83地方债券1244.34地方债券2364.75基金1434.26基金2544.6

决策者希望:国债投资额不少于1000万,平均到期年限不超过5年,平均评级不超过2。问每种证券各投资多少使总收益最大。28十二月20221.1线性规划的数学模型Math03一月20231.1线性规划的数学模型MathematicalModelofLP解设xj(j=1,2,…,6)为第j种证券的投资额,目标函数是税后总收益为资金约束:国债投资额约束:平均评级约束:平均到期年限约束:28十二月20221.1线性规划的数学模型Math03一月2023整理后得到线性规划模型1.1线性规划的数学模型MathematicalModelofLP28十二月2022整理后得到线性规划模型1.1线性规划03一月2023【例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线性规划的数学模型MathematicalModelofLP28十二月2022【例1-6】均衡配套生产问题。某产品由03一月2023目标函数线性化。产品的产量y等价于整理得到线性规划模型约束线性化。将绝对值约束写成两个不等式1.1线性规划的数学模型MathematicalModelofLP28十二月2022目标函数线性化。产品的产量y等价于整理03一月20231.1.2线性规划的一般模型一般地,假设线性规划数学模型中,有m个约束,有n个决策变量xj,j=1,2…,n,目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示,aij称为工艺系数。约束条件右端的常数用bi表示,bi称为资源限量。则线性规划数学模型的一般表达式可写成为了书写方便,上式也可写成:1.1线性规划的数学模型MathematicalModelofLP28十二月20221.1.2线性规划的一般模型为了书写03一月2023在实际中一般xj≥0,但有时xj≤0或xj无符号限制。1.1线性规划的数学模型MathematicalModelofLP28十二月2022在实际中一般xj≥0,但有时xj≤0或03一月20231.什么是线性规划,掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。1.1线性规划的数学模型MathematicalModelofLP28十二月20221.什么是线性规划,掌握线性规划在管理1.2图解法

GraphicalMethod1.2图解法03一月2023图解法的步骤:1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域,其交集就是可行解集合,或称为可行域;2.绘制目标函数图形。先过原点作一条矢量指向点(c1,c2),矢量的方向就是目标函数增加的方向,称为梯度方向,再作一条与矢量垂直的直线,这条直线就是目标函数图形;3.求最优解。依据目标函数求最大或最小移动目标函数直线,直线与可行域相交的点对应的坐标就是最优解。一般地,将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动1.2图解法TheGraphicalMethod28十二月2022图解法的步骤:1.求可行解集合。分别求03一月2023x1x2O1020304010203040(300,400)(15,10)最优解X=(15,10)最优值Z=8500例1-71.2图解法TheGraphicalMethod28十二月2022x1x2O1020304010203003一月2023246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例1-8(1,2)1.2图解法TheGraphicalMethod28十二月2022246x1x2246最优解X=(3,103一月2023246x1x2246X(2)=(3,1)X(1)=(1,3)(5,5)minZ=5x1+5x2例1-9有无穷多个最优解即具有多重解,通解为0≤α≤1

当α=0.5时X=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2图解法TheGraphicalMethod28十二月2022246x1x2246X(2)=(3,103一月2023246x1x2246(1,2)无界解(无最优解)maxZ=x1+2x2例1-101.2图解法TheGraphicalMethod28十二月2022246x1x2246(1,2)无界解(03一月2023x1x2O10203040102030405050无可行解即无最优解maxZ=10x1+4x2例1-111.2图解法TheGraphicalMethod28十二月2022x1x2O1020304010203003一月2023由以上例题可知,线性规划的解有4种形式:1.有唯一最优解(例1-7例1-8)2.有多重解(例1-9)3.有无界解(例1-10)4.无可行解(例1-11)1、2情形为有最优解3、4情形为无最优解1.2图解法TheGraphicalMethod28十二月2022由以上例题可知,线性规划的解有4种形式03一月20231.通过图解法了解线性规划有几种解的形式2.作图的关键有三点

(1)可行解区域要画正确

(2)目标函数增加的方向不能画错

(3)目标函数的直线怎样平行移动1.2图解法TheGraphicalMethod28十二月20221.通过图解法了解线性规划有几种解的形运筹学OperationsResearchChapter1线性规划LinearProgramming1.1LP的数学模型

MathematicalModelofLP1.2图解法

GraphicalMethod1.3标准型

StandardformofLP1.4基本概念

BasicConcepts1.5单纯形法

SimplexMethod运筹学Chapter1线性规划1.1LP的数学模型1.1数学模型

MathematicalModel1.1数学模型03一月20231.1线性规划的数学模型MathematicalModelofLP线性规划(LinearProgramming,缩写为LP)通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。28十二月20221.1线性规划的数学模型Math03一月2023【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定,每件产品甲需要消耗材料A2公斤,消耗材料B1公斤,每件产品乙需要消耗材料A1公斤,消耗材料B1.5公斤。已知在计划期内可供材料分别为40、30公斤;每生产一件甲、乙两产品,企业可获得利润分别为40、30元,如表1-1所示。假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大。1.1线性规划的数学模型MathematicalModelofLP1.1.1应用模型举例28十二月2022【例1-1】生产计划问题。某企业在计划03一月2023【解】设x1、x2分别为甲、乙产品的产量,数学模型为:1.1线性规划的数学模型MathematicalModelofLP

产品

资源

乙现有资源材料C2140材料D11.530利润(元/件)300400表1-128十二月2022【解】设x1、x2分别为甲、乙产品的产03一月2023线性规划的数学模型由决策变量

Decisionvariables

目标函数Objectivefunction及约束条件Constraints构成。称为三个要素。其特征是:1.解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;2.解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型?1.1线性规划的数学模型MathematicalModelofLP28十二月2022线性规划的数学模型由决策变量Deci03一月2023【例1-2】某商场决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,商场每天需要的营业员如表1-2所示。表1-2营业员需要量统计表商场人力资源部应如何安排每天的上班人数,使商场总的营业员最少。星期需要人数星期需要人数一300五480二300六600三350日550四4001.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-2】某商场决定:营业员每周连续03一月2023【解】设xj(j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为1.1线性规划的数学模型MathematicalModelofLP星期需要人数星期需要人数一300五480二300六600三350日550四40028十二月2022【解】设xj(j=1,2,…,7)为03一月20231X10C1404>=3001042X267C2301>=30013X3146C3350>=35004X4170C4400>=40005X597C5480>=48006X6120C6600>=60007X717C7550>=5500最优解:Z=617(人)1.1线性规划的数学模型MathematicalModelofLP28十二月20221X10C1404>=3001042X03一月2023【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根,这些轴的规格分别是1.5,1,0.7(m),这些轴需要用同一种圆钢来做,圆钢长度为4m。现在要制造1000辆汽车,最少要用多少圆钢来生产这些轴?【解】这是一个条材下料问题,设切口宽度为零。设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式1.5y1+y2+0.7y3≤4表示,求这个不等式关于y1,y2,y3的非负整数解。象这样的非负整数解共有10组,也就是有10种下料方式,如表1-3所示。表1-3下料方案

方案规格12345678910需求量y1(根)

22111000001000y210210432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.51.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-3】合理用料问题。某汽车需要用03一月2023设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:求下料方案时应注意,余料不能超过最短毛坯的长度;最好将毛坯长度按降的次序排列,即先切割长度最长的毛坯,再切割次长的,最后切割最短的,不能遗漏了方案。如果方案较多,用计算机编程排方案,去掉余料较长的方案,进行初选。1.1线性规划的数学模型MathematicalModelofLP

方案规格12345678910需求量y1(根)22111000001000y210210432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.528十二月2022设xj(j=1,2…,10)为第j种下03一月20231X15002X203X304X405X506X662.57X708X809X925010X100Z=812.51.1线性规划的数学模型MathematicalModelofLP28十二月20221X15002X203X304X40503一月2023【例1-4】配料问题。某钢铁公司生产一种合金,要求的成分规格是:锡不少于28%,锌不多于15%,铅恰好10%,镍要界于35%~55%之间,不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼,每种矿物的成分含量和价格如表1-4所示。矿石杂质在治炼过程中废弃,现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中,合金含量没有发生变化。表1-4矿石的金属含量

合金矿石锡%锌%铅%镍%杂质费用(元/t)1251010253034024000303026030155206018042020040202305851517551901.1线性规划的数学模型MathematicalModelofLP28十二月2022【例1-4】配料问题。某钢铁公司生产一03一月2023解:设xj(j=1,2,…,5)是第j种矿石数量,得到下列线性规划模型注意,矿石在实际冶炼时金属含量会发生变化,建模时应将这种变化考虑进去,有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题,在许多行业生产中都能遇到。1.1线性规划的数学模型MathematicalModelofLP矿石锡%锌%铅%镍%杂质费用(元/t)12510102530340240003030260301552060180420200402023058515175519028十二月2022解:设xj(j=1,2,…,5)是第03一月20231X102X20.33333X304X40.58335X50.6667最优解:Z=347.51.1线性规划的数学模型MathematicalModelofLP28十二月20221X102X20.33333X304X03一月20231.1线性规划的数学模型MathematicalModelofLP【例1-5】投资问题。某投资公司拟将5000万元的资金用于国债、地方国债及基金三种类型证券投资,每类各有两种。每种证券的评级、到期年限及每年税后收益率见表1-5所示。表1-5证券投资方案序号证券类型评级到期年限每年税后收益率(%)1国债1183.22国债21103.83地方债券1244.34地方债券2364.75基金1434.26基金2544.6

决策者希望:国债投资额不少于1000万,平均到期年限不超过5年,平均评级不超过2。问每种证券各投资多少使总收益最大。28十二月20221.1线性规划的数学模型Math03一月20231.1线性规划的数学模型MathematicalModelofLP解设xj(j=1,2,…,6)为第j种证券的投资额,目标函数是税后总收益为资金约束:国债投资额约束:平均评级约束:平均到期年限约束:28十二月20221.1线性规划的数学模型Math03一月2023整理后得到线性规划模型1.1线性规划的数学模型MathematicalModelofLP28十二月2022整理后得到线性规划模型1.1线性规划03一月2023【例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线性规划的数学模型MathematicalModelofLP28十二月2022【例1-6】均衡配套生产问题。某产品由03一月2023目标函数线性化。产品的产量y等价于整理得到线性规划模型约束线性化。将绝对值约束写成两个不等式1.1线性规划的数学模型MathematicalModelofLP28十二月2022目标函数线性化。产品的产量y等价于整理03一月20231.1.2线性规划的一般模型一般地,假设线性规划数学模型中,有m个约束,有n个决策变量xj,j=1,2…,n,目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示,aij称为工艺系数。约束条件右端的常数用bi表示,bi称为资源限量。则线性规划数学模型的一般表达式可写成为了书写方便,上式也可写成:1.1线性规划的数学模型MathematicalModelofLP28十二月20221.1.2线性规划的一般模型为了书写03一月2023在实际中一般xj≥0,但有时xj≤0或xj无符号限制。1.1线性规划的数学模型MathematicalModelofLP28十二月2022在实际中一般xj≥0,但有时xj≤0或03一月20231.什么是线性规划,掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。1.1线性规划的数学模型MathematicalModelofLP28十二月20221.什么是线性规划,掌握线性规划在管理1.2图解法

Graph

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论