绪论线性规划数学模型.ppt

《绪论线性规划数学模型.ppt》由会员分享，可在线阅读，更多相关《绪论线性规划数学模型.ppt（41页珍藏版）》请在三一办公上搜索。

1、课程基本介绍,夫运筹帷幄之中，决胜千里之外。史记高祖本纪,由来：西汉初年，天下已定，汉高祖刘邦在洛阳南宫举行盛大的宴会，喝了几轮酒后，他向群臣提出一个问题：“我为什么会取得胜利？项羽为什么会失败？”高起、王陵认为高祖派有才能的人攻占城池与战略要地，给立大功的人加官奉爵，所以能成大事业。而项羽恰恰相反，有人不用，立功不授奖，贤人遭疑惑，所以他才失败。汉高祖刘邦听了，认为他们说的有道理，但是最重要的取胜原因是能用人。他称赞张良说：“夫运筹帷幄之中，决胜千里之外，吾不如子房（古人有名，有字，子房为张良的字）。”意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜利。这说明张良心计多，善用脑，善

2、用兵。后来人们就用“运筹帷幄”表示善于策划用兵，指挥战争。,无论哪种案例，这里都有筹划，以策略取胜的意思,课程基本介绍起源与发展,我国古代运筹学应用例子：田忌赛马丁渭修皇宫,运筹学,美：Operations Research,英：Operational Research,运作研究/作业研究,学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的研究问题：随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站和整个防空作战系统的协调配合问题1938年7月，波得塞雷达站的负责人罗伊（A.P.Rowe）用Operational Research命名防空作战系统运行的研究，这是

3、运筹学Operational Research（O.R.）的由来1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组。l 942年美国和加拿大也都相继成立运筹学小组据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。,课程基本介绍起源与发展,课程基本介绍起源与发展,二次世界大战后，从事这些活动的许多专家转到了民用部门，使运筹学很快推广到了工业企业和政府工作的各个方面，从而促进了运筹学有关理论和方法的研究和实践，使得运筹学迅速发展并逐步成熟起来。,运筹学发展到现在，但其内容已相当丰富，所涉及领域也十分广泛。现在这门新兴学科的应用已深入到

4、国民经济的各个领域，成为促进国民经济多快好省，健康协调发展的有效方法。这门课的目的就是要系统地了解运筹学的基本概念、基本原理、研究方法及其应用，掌握运筹学整体优化的思想和定量分析的优化技术，并能正确应用各类模型分析和解决实际问题。,课程基本介绍定义,“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。大英百科全书运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”中国大百科全书,课程基本介绍定义,运筹学“主要研究经济活

5、动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”辞海运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。中国企业管理百科全书,课程基本介绍定义,运筹学所研究的，就是在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。中国学者根据“运筹于帷幄之中，决胜于千里之外”意译为“运筹学”，其意为运算筹划，出谋献策，以最佳策略取胜。这实际上极为恰当地概括了这门学科的精髓。,运筹

6、学具有如下的性质特点,运筹学是一门应用科学，应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”，这也是运筹学的目地,定量化分析：通过数学方法的应用来对问题建立模型，并对模型的分析与求解,最优化思想,多学科的交叉与结合，如交通工程、物流工程、经济学、物理、化学等方法,课程基本介绍性质,系统的整体思想,课程基本介绍分支,规划理论 线性规划 非线性规划 运输问题 整数规划 动态规划 目标规划图论与网络理论排队论存储论决策论对策论,本课程具体内容与性质,运筹学教学大纲,运筹学进度安排,课程特点与相关要求,课程特点,与线性代数联系紧密，做好相关数学知识的复习,

7、课程要求,认真听讲。有问题及时反映按时完成作业。每周第一次课之前交。要求独立、准时完成,答疑时间,每周二下午2:30-3:30，其它时间,课程考试方式与成绩构成,考试方式,闭卷考试,成绩构成,平时成绩占50%，期末考试占 50%平时成绩由考勤和平时表现、平时作业、测验和实验等环节共同构成。,第一章 线性规划和单纯形法,本章主要内容：,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,第一节 线性规划问题及数学模型,1.线性规划（Linear programming）问题的提出,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分

8、利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）,第一节 线性规划问题及数学模型,例1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,问题的提出,第一节 线性规划问题及数学模型,例2 捷运公司

9、在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,课程基本介绍解决问题步骤,(1)提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；(2)建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；(3)求解。用各种

10、手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；(4)解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；(5)解的控制。通过控制解的变化过程决定对解是否要作一定的改变；(6)解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。,第一节 线性规划问题及数学模型,2.线性规划问题模型的建立,对例1试着建模：,例1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件

11、时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,第一节 线性规划问题及数学模型,解：用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，问题中要求获取的利润为最大，即max(2x1+x2)，称为目标函数，它是变量x1，x2的线性表达式函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。,max:maximize的缩写，“最大化”s.t.subject to的缩写，“受限制于”,第一节 线性规划问题及数学模型,例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。

12、已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,第一节 线性规划问题及数学模型,例2中：若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最

13、小，故有如下数学模型：,第一节 线性规划问题及数学模型,分析以上的建模过程，我们可以看出要对规划问题建模，基本遵循以下三个步骤：,决策变量、目标函数和约束条件通常称为规划问题的三要素。,（3）确定约束条件。决策变量的取值受到各种资源的限制，这些限制通常用包含决策变量的等式或不等式表示，这就是约束条件的表示。,（1）确定变量，即问题中的未知量。它是由决策者决定的影响决策目标的未知量，未知量的取值代表一种方案，故我们把这些变量称之为决策变量。,（2）确定目标函数，即要用来实现的目标，一般用决策变量的线性函数来表示，通常要求实现该函数的最大或最小。,第一节 线性规划问题及数学模型,如何辨别一个模型是

14、线性规划问题？,当一个规划问题的模型具备上述特点时我们称之为线性规划,其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,将以上问题推广,可得线性规划含义：,对于求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,第一节 线性规划问题及数学模型,max（或min）,4.线性规划数学模型的形式,称为价值系数或目标函数系数,称为资源常数或约束右端常数,称为技术系数或约束系数,称为决策变量,第一节 线性规划问题及数学模型,线性规划问题的

15、数学模型简写形式如下：,max（或min）,Mathematical model,矩阵形式：,max（或min）,称为决策变量向量,称为价值系数向量或目标函数系数向量,称为资源常数向量或约束右端常数向量,称为技术系数或约束系数矩阵,第一节 线性规划问题及数学模型,向量形式：,其中：,第一节 线性规划问题及数学模型,注意：向量形式时，每一个列向量Pj都是对应变量的系数，如P1对应的是x1的系数,第一节 线性规划问题及数学模型,5.线性规划问题的标准形式,特点：(1)目标函数统一变成求最大值（有些书规定求最小值）(2)约束条件统一变为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负

16、。,即：,如何化标准形式？,第一节 线性规划问题及数学模型,设目标函数为 min f=c1x1+c2x2+cnxn 则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即 max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 min f-max z,（1）极小化目标函数的问题：,（2）约束条件不是等式的问题：,第一节 线性规划问题及数学模型,若约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差，即 s=bi(ai1 x1+ai2 x2+ain xn)

17、显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi,化标准型时为了使约束由小于等于不等式成为等式而引进的变量 s 称为“松弛变量”。,松弛变量在目标函数中的价值系数是多少呢？,价值系数应为0,（2）约束条件不是等式的问题：,第一节 线性规划问题及数学模型,当约束条件为 ai1 x1+ai2 x2+ain xn bi时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi,化标准型时为了使约束由大于等于不等式成为等式而引进

18、的变量 s 称为“剩余变量”。,剩余变量在目标函数中的价值系数也是零,第一节 线性规划问题及数学模型,剩余量：线性规划中，一个大于等于约束条件中超过资源或能力最底限的部分称之为剩余量。2 xl+x2400，假如最优解为（150,110）那么剩余量就为10。,两个概念,松弛量：线性规划中，小于等于约束条件中未被使用的资源或能力的值成为松弛量。xl+x2300，假如最优解为（150,140）那么本约束的松弛量就为10。,例1：将以下线性规划问题转化为标准形式minf=3.6 x1-5.2 x2+1.8 x3 s.t.2.3 x1+5.2 x2-6.1 x3 15.7 4.1 x1+3.3 x3 8

19、.9 x1+x2+x3=38 x1,x2,x3 0,第一节 线性规划问题及数学模型,解：首先,将目标函数转换成极大化：令 z=-f=-3.6x1+5.2x2-1.8x3,第一节 线性规划问题及数学模型,其次考虑约束，有2个不等式约束，引进松弛变量x4和剩余变量x5，我们可以得到以下标准形式的线性规划问题：max z=-3.6 x1+5.2 x2-1.8 x3s.t.2.3x1+5.2x2-6.1x3+x4=15.7 4.1x1+3.3x3-x5=8.9 x1+x2+x3=38 x1,x2,x3,x4,x5 0,第一节 线性规划问题及数学模型,（3）右端项有负值的问题：,在标准形式中，要求右端项

20、必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi,（4）变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”(xj0，xj”0)或 xj=-xj(xj0),第一节 线性规划问题及数学模型,第一节 线性规划问题及数学模型,例2：将以下线性规划问题转化为标准形式 minf=-3 x1+5 x2+8 x3-7 x4s.t.2 x1-3 x2+5 x3+6 x4 28 4 x1+2 x2+3 x3-9 x4 39 6 x2+2 x3+3

21、 x4-58 x1,x3,x4 0,第一节 线性规划问题及数学模型,解：首先，将目标函数转换成极大化 令 z=-f=3x15x28x3+7x4；其次考虑约束，有3个不等式约束，引进松弛变量x5,x7和剩余变量x6；由于x2无非负限制，可令x2=x2-x2”,其中x20，x2”0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：,第一节 线性规划问题及数学模型,max z=3x15x2+5x2”8x3+7x4 s.t.2x13x2+3x2”+5x3+6x4+x5=28 4x1+2x2-2x2”+3x3-9x4-x6=39-6x2+6x2”-2x3-3x4-x7=58 x1,x2,x2”,x3,x4,x5,x6,x7 0,第一节 线性规划问题及数学模型,总结：把一般的LP化成标准型的过程：,1 目标标准化 min Z 等价于 max(-Z)max Z=-cjxj 2 化约束为等式 加松弛变量、减剩余变量 3 右端非负 4 变量非负化 做变换 或,1、P43：1.2（1）；P45：1.13；选作1.15、1.17；2、复习线性代数相关知识,本次作业,第一节 线性规划问题及数学模型,