第4章线性规划初步

发布 2019-07-07 11:21:00 阅读 9476

在日常生活中我们经常会遇到这样的问题:如何合理安排有限的人力、物力、财力等资源,使得这些资源的效能能够充分地发挥,以获取最佳的经济效益。线性规划就是辅助人们寻求解决这些问题的一种数学方法。

在本章的学习中,我们将把一些简单的实际问题归结为线性规划的问题,通过学习解决这些问题的思想和方法,对线性规划的建立、应用和求解有个初步的认识。

本章学习目标。

学完本章内容,你将能够。

了解建立实际问题的数学模型的方法。

会用**法解二元线性规划问题。

会用**法解线性规划问题。

学会用计算机软件excel解线性规划问题。

本章目录。§7.1线性规划问题的概念。

7.2二元线性规划问题的**法。

7.3用**法解线性规划问题。

7.4用计算机软件excel解线性规划问题。

7.1线性规划问题的概念。

**.某建筑公司建造居民小区,若建一幢普通的住宅楼需投入资金300万元,并占地200m2,可获利润100万元;若建一栋别墅需投入资金400万元,并占地100m2,可获利润200万元,该公司现有资金9000万元,拍得土地5000m2,问应作怎样的投资组合,才能获利最多?

这是一个获取最大利润的问题,正是线性规划问题所要解决的。

例1某点心店要做甲、乙两种馒头,甲种馒头的主要原料是每3份面粉加2份玉米粉,乙种馒头的主要原料是每4份面粉加1份玉米粉。这个店每天可买进面粉50公斤和玉米粉20公斤,又做1公斤甲种馒头的利润是5元,做1公斤乙种馒头的利润是4元,那么这个点心店每天做甲、乙两种馒头各多少公斤,才能获利最大?

解现将上述有关数据列为下表:

图7-1设甲、乙两种馒头计划产量分别为x,y公斤,利润为z元。

生产这两种馒头所用面粉总量为0.6x+0.8y(公斤),现共有50公斤面粉,因此,应有。

0.6x+0.8y≤50

即3x+4y≤250

类似地,得。

0.4x+0.2y≤20

即2x+y≤100

由于产品的数量不能为负数,应有。

x≥0,y≥0

总利润为。z=5x+4y

综合起来,可以把这个问题的数学形式表达为:

其中,记号“max”表示函数的最大值。

在上述式子中,我们称x,y为决策变量,式(7.1)为目标函数,式(7.2)~(7.5)统称为约束条件。根据问题的不同,目标函数可最大化或最小化。

在约束条件下求目标函数的最大值和最小值问题称为线性规划问题。

线性规划问题主要研究两类问题:

1. 如何合理利用有限的资源,使其产生最大的效益。

2. 如何制定最佳方案,以尽可能少的资源完成所要做的事情。

这就是最优化的问题。

例2某运输公司有8辆载重6吨的a型卡车,4辆载重10吨的b型卡车,并有9名驾驶员。在建造某段高速公路中,公司承包了每天至少运输沥青180吨的任务.已知每辆卡车每天往返次数为a型4次,b型6次,派出每辆卡车每天的成本为a型120元,b型200元.每天应派出a型和b型车各多少辆,能使公司总成本最低?

解:这个问题的目标是要求最小的运输费用。

设公司每天应派出型卡车辆,型卡车辆,由条件知:

即有线性规划问题:

min.记号“min”表示函数的最小值。

从上面的例子中我们看到,为了解决实际问题,往往要将这些问题抽象为数学形式,称其为数学模型。线性规划问题就常对物资调运、产品安排和下料等问题建立数学模型后用数学的方法加以解决。

问题解决将例1中的“派出每辆卡车每天的成本为a型120元,b型200元”改为“派出每辆卡车每天可得利润为a型120元,b型200元”,求“每天应派出a型、b型车各多少辆,能使公司利润最大”,你应该怎样解答?

思考交流。是不是所有求最值的问题都是线性规划问题?

练习。1.某厂计划生产甲、乙两种产品,其主要原材料有钢材3000kg,铜材2000kg,每件产品耗材定额(kg)及所获利润(元)如下表,问如何安排生产能使该厂所获利润最大?

图7-22.某饲养场要同时用a、b两种饲料喂养动物,要求每头动物每天至少应摄取700克蛋白质、30克矿物质和0.1克维生素。两种饲料的每公斤中所含三种成份的数量(克)及每公斤的单价(元)如下表,现要买两种饲料各多少公斤,才能既满足动物生长的需要,又使费用最省?

图7-3习题。

1.家具厂生产桌子和椅子,桌子售价50元一个,椅子30元一个。生产一个桌子需要木工4小时,油漆工2小时,生产一个椅子需要木工3小时,油漆工1小时。该厂每月可用木工工时120小时油漆工,工时50小时。

根据以上条件构建使销售收入最大的线性规划模型。

2.某汽车公司有两家装配厂,生产甲、乙两种不同型号的汽车,若a厂每小时可完成1辆甲型车和2辆乙型车;b厂每小时可完成3辆甲型车和1辆乙型车。今欲制造40辆甲型车和20辆乙型车,问这两家工厂各工作几小时,才能使所费的总工作时数最少?

3.饮料馆配制两种奶茶,甲种奶茶每杯含奶粉9克、咖啡4克、糖3克,乙种奶茶每杯含奶粉4克、咖啡5克、糖10克.已知每天原料的使用限额为奶粉3600克、咖啡2000克、糖3000克.如果甲种奶茶每杯能获利0.7元,乙种奶茶每杯能获利1.2元,每天在原料的使用限额内奶茶能全部售出,每天应配制两种奶茶各多少杯能获利最大?

第6章非线性规划

前面几章,我们论述了线性规划及其扩展问题,这些问题的约束条件和目标函数都是关于决策变量的一次函数。虽然大量的实际问题可以简化为线性规划及其扩展问题来求解,但是还有相当多的问题很难用线性函数加以描述。如果目标函数或约束条件中包含有非线性函数,就称这样的规划问题为非线性规划问题。由于人们对实际问题解的精...

MATLAB线性规划作业

一 某厂生产甲 乙两种产品,这两种产品一季度 的需要量如表1.1所示。表 1.1根据财务部门对产品的生产费用和库存费用的估算,如表1.2所示。为了简化计算,假设上年年底和三月底产品无库存,同时估计生产费用每月要增长10 产品加工由。一 二车间来完成,每个产品加工时间如表1.3所示。表 1.2表1.3...

数学建模 线性规划

这家公司希望广告费用不超过800 千元 还要求 1 至少要有两百万妇女收看广告 2 电视广告费用不超过500 千元 3 电视广告白天至少播出3次,最佳时间至少播出2次 4 通过广播 杂志做的广告要重复5到10次。5.2解 设电视 白天,最佳时间 无线电广播 杂志,的广告播出分别为 x x x alt...