第1章 绪论线性规划数学模型

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

2、在军帐中运用计谋，就能决定千里之外战斗的胜利。这说明张良心计多，善用脑，善用兵。后来人们就用“运筹帷幄运筹帷幄”表示善于策划策划用兵，指挥战争。北京联合大学 自动化学院 耿钰无论哪种案例，这里都有筹划，以策略取胜的意思课程基本介绍起源与发展 我国古代运筹学应用例子： 田忌赛马 丁渭修皇宫运筹学运筹学美：美：Operations ResearchOperations Research英：英：Operational ResearchOperational Research运作研究运作研究 /作业研究作业研究北京联合大学 自动化学院 耿钰 学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的

3、研究问题：随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站和整个防空作战系统的协调配合问题1938年7月，波得塞雷达站的负责人罗伊（A . P .Rowe ）用Operational Research命名防空作战系统运行的研究，这是运筹学Operational Research（ O . R . ）的由来1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组。l 942年美国和加拿大也都相继成立运筹学小组据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。课程基本介绍起源与发展北京联合大学 自动化学院 耿钰课程基

4、本介绍起源与发展 二次世界大战后，从事这些活动的许多专家转到了民用部门，使运筹学很快推广到了工业企业和政府工作的各个方面，从而促进了运筹学有关理论和方法的研究和实践，使得运筹学迅速发展并逐步成熟起来。 运筹学发展到现在，但其内容已相当丰富，所涉及领域也十分广泛。 现在这门新兴学科的应用已深入到国民经济的各个领域，成为促进国民经济多快好省，健康协调发展的有效方法。 这门课的目的就是要系统地了解运筹学的基本概念、基本原理、研究方法及其应用，掌握运筹学整体优化的思想和定量分析的优化技术，并能正确应用各类模型分析和解决实际问题。北京联合大学 自动化学院 耿钰课程基本介绍定义 “运筹学是一门应用于管理有

5、组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。大英百科全书 运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”中国大百科全书北京联合大学 自动化学院 耿钰课程基本介绍定义 运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”辞海 运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排

6、，为决策者提供有依据的最优方案，以实现最有效的管理”。中国企业管理百科全书北京联合大学 自动化学院 耿钰课程基本介绍定义 运筹学所研究的，就是在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。 中国学者根据“运筹于帷幄之中，决胜于千里之外” 意译为“运筹学”，其意为运算筹划，出谋献策，以最佳策略取胜。这实际上极为恰当地概括了这门学科的精髓。北京联合大学 自动化学院 耿钰运筹学具有如下的性质特点运筹学具有如下的性质特点运筹学是一门应用科学运筹学是一门应用科学，应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”，这

7、也是运筹学的目地定量化分析：定量化分析：通过数学方法的应用来对问题建立模型，并对模型的分析与求解最优化思想最优化思想多学科的交叉与结合多学科的交叉与结合，如交通工程、物流工程、经济学、物理、化学等方法课程基本介绍性质系统的整体思想系统的整体思想北京联合大学 自动化学院 耿钰课程基本介绍分支 规划理论规划理论 线性规划线性规划 非线性规划非线性规划 运输问题运输问题 整数规划整数规划 动态规划动态规划 目标规划目标规划 图论与网络理论图论与网络理论 排队论排队论 存储论存储论 决策论决策论 对策论对策论北京联合大学 自动化学院 耿钰本课程具体内容与性质运筹学教学大纲运筹学教学大纲运筹学进度安排运

8、筹学进度安排北京联合大学 自动化学院 耿钰课程特点与相关要求课程特点课程特点与线性代数联系紧密，与线性代数联系紧密，做好相关数学知识的复习做好相关数学知识的复习课程要求课程要求认真听讲。认真听讲。有问题及时反映有问题及时反映按时完成作业。每周第一次课之按时完成作业。每周第一次课之前交。要求前交。要求独立独立、准时完成、准时完成答疑时间答疑时间每周二下午每周二下午2:30-3:30，其它时间，其它时间北京联合大学 自动化学院 耿钰课程考试方式与成绩构成考试方式考试方式闭卷考试闭卷考试成绩构成成绩构成平时成绩占平时成绩占50%，期末考试占，期末考试占 50%平时成绩由考勤和平时表现、平平时成绩由考

9、勤和平时表现、平时作业、测验和实验等环节共同时作业、测验和实验等环节共同构成。构成。 北京联合大学 自动化学院 耿钰第一章第一章 线性规划和单纯形法线性规划和单纯形法v线性规划问题及数学模型v图解法v单纯形法原理v单纯形法计算步骤v单纯形法进一步讨论v数据包络分析v其他应用例子北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型1. 1. 线性规划线性规划（Linear programming）问题的提出问题的提出 生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这物力

10、等各种资源得到充分利用，获得最大的效益，这就是规划问题。就是规划问题。（1 1）当任务或目标确定后当任务或目标确定后，如何如何统筹兼顾，合理安排，统筹兼顾，合理安排，用最用最少的资源少的资源 （如资金、设备、原标材料、人工、时间等）去完（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标成确定的任务或目标（2 2）在一定的资源条件限制下，如何在一定的资源条件限制下，如何组织安排生产组织安排生产获得获得最好最好的经济效益的经济效益（如产品量最多（如产品量最多 、利润最大、利润最大. .）北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型 例例1

11、1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。问题的提出问题的提出北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例例2 2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合

12、同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表表1-2单位：单位：100m2表表1-3单位：元单位：元/100m2北京联合大学 自动化学院 耿钰课程基本介绍解决问题步骤 (1) 提出和形成问题。提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；(2) 建立模型。建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来； (3) 求解。求解。用各种手段( 主要是数学方法，也可用其他方法 )将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精

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

14、件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型解：用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，问题中要求获取的利润为最大，即max (2x1+x2) ，称为目标函数，目标函数，它是变量x1，x2的线性表达式函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件约束条件。(1.1c)0,52426155. .2max212121221xxxxxxxt sxxz目标函数目标函数约

15、束条件约束条件(1.1a)(1.1b)(1.1d)max: maximizemax: maximize的缩的缩写，写，“最大化最大化”s.t.s.t. subject tosubject to的缩的缩写，写，“受限制受限制于于”北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例例2 2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每

16、次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表表1-2单位：单位：100m2表表1-3单位：元单位：元/100m2北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例2中：若用变量xijxij表示捷运公司在第第i i( (i i=1,4)=1,4)个月初签订的个月初签订的租借期为租借期为j(j=1,4)j(j=1,4)个月的仓库面积个月的仓库面积的合同。因5 5月份起该公月份起该公司不需要租借仓库，故司不需要租借仓库，故x24x24，x33x33，x34x34，x42x42

17、，x43x43，x44x44均为均为零零。该公司希望总的租借费用为最小租借费用为最小，故有如下数学模型：ijmin a0(i =1,.,m; j=1,.,n)112131411222321323141112131412131421222313142223313214233241z= 2 800(x +x +x +x)+4 500(x +x +x)+6 000(x +x)+7 300 xx +x +x +x15x +x +x +x +x +x10 x +x +x +x +x +x20 x +x +x +x12目标函数目标函数约束条件约束条件 s.t.s.t.北京联合大学 自动化学院 耿钰 第一节

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

19、把这些变量称之为决策变量。决策变量。 （2 2）确定）确定目标函数目标函数，即要用来实现的目标目标，一般用决策变量的线性函数来表示，通常要求实现该函数的最大或最小要求实现该函数的最大或最小。北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型 如何辨别一个模型是线性规划问题？如何辨别一个模型是线性规划问题？ 当一个规划问题的模型具备上述特点时我们称之为线性当一个规划问题的模型具备上述特点时我们称之为线性规划规划线性函数线性函数线性不等式或等式线性不等式或等式将以上问题推广将以上问题推广, ,可得可得线性规划含义线性规划含义： 对于求取一组变量对于求取一组变

20、量x xj j(j=1,2,.,n)(j=1,2,.,n)，使之既满足线性约束使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。为线性规划问题。北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型自由, 00,),(),(),(. .2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsmax（或或min） nnxcxcxcZ22114. 线性规划数学模型的形式线性规划数学模型的形式称为价值系数或目标函

21、数系数称为价值系数或目标函数系数 ), 2 , 1(njcj称为资源常数或约束右端常数称为资源常数或约束右端常数 ), 2 , 1(mibi称为技术系数或约束系数称为技术系数或约束系数 ija0(i =1,.,m; j =1,.,n)称为决策变量称为决策变量 ), 2 , 1(njxj北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型线性规划问题的线性规划问题的数学模型简写形式数学模型简写形式如下如下：max（或或min） njjjxcZ1?L?njxmibxatsjnjijij, 2 , 10),.,1(),(. .1Mathematical mode

22、l北京联合大学 自动化学院 耿钰矩阵形式矩阵形式：m a x （ 或或 m i n ） 称为决策变量向量称为决策变量向量 称为价值系数向量或目标函数系数向量称为价值系数向量或目标函数系数向量 称为资源常数向量称为资源常数向量或约束右端常数向或约束右端常数向量量 称为技术系数或约束系称为技术系数或约束系数矩阵数矩阵 CXZ0XbAXts),(. .nxxxX21),(21ncccCmnmmnnaaaaaaaaaA212222111211mbbbb21 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型北京联合大学 自动化学院 耿钰向量形式：向量形式：) (21ncccC nxxX1 mj

23、jjaaP1mbbb1 0)b,(or (min) max1XxPCXznjjj其中：其中： 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型注意：向量注意：向量形式时，每形式时，每一个列向量一个列向量Pj都是对应都是对应变量的系数，变量的系数，如如P1对应的对应的是是x1的系数的系数北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型5. 线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特点：特点：(1) 目标函数统一变成求最大值（有些书规定求最小值）目

24、标函数统一变成求最大值（有些书规定求最小值）(2) 约束条件统一变为等式方程，且右端常数项约束条件统一变为等式方程，且右端常数项bi都大于都大于或等于零或等于零(3) 决策变量决策变量xj为非负。为非负。即：即：北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型设目标函数为设目标函数为 min min f f = = c c1 1x x1 1 + + c c2 2x x2 2 + + + + c cn nx xn n 则可以令则可以令z z -f-f ，该极小化问题与下面的极大化，该极小化问题与下面的极大化问题有相同的最优解，即问题有相同的最优解，即 m

25、ax max z z = = -c-c1 1x x1 1 - c- c2 2x x2 2 - - - - c cn nx xn n 但必须注意，尽管以上两个问题的最优解相同，但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即但他们最优解的目标函数值却相差一个符号，即 min min f f - max - max z z（1 1）极小化目标函数的问题：）极小化目标函数的问题：北京联合大学 自动化学院 耿钰（2 2）约束条件不是等式的问题：约束条件不是等式的问题： 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型 若约束条件为若约束条件为 a ai1

26、i1 x x1 1+ +a ai2 i2 x x2 2+ + +a ainin x xn n b bi i 可以可以引进一个新的变量引进一个新的变量s s ，使它等于约束右边与左边之，使它等于约束右边与左边之差，即差，即 s s = =b bi i(a ai1 i1 x x1 1 + + a ai2 i2 x x2 2 + + + + a ainin x xn n ) ) 显然，显然，s s 也具有非负约束，即也具有非负约束，即s s00，这时新的约束条件成为这时新的约束条件成为 a ai1 i1 x x1 1+ +a ai2 i2 x x2 2+ + +a ainin x xn n+ +s

27、s = = b bi i化标准型时为了使约束由化标准型时为了使约束由小于等于小于等于不等式成为等式而不等式成为等式而引进的变量引进的变量 s s 称为称为“松弛变量松弛变量”。 松弛变量在目标函数中的价值系数是多少呢？松弛变量在目标函数中的价值系数是多少呢？价值系数应为价值系数应为0北京联合大学 自动化学院 耿钰（2 2）约束条件不是等式的问题：约束条件不是等式的问题： 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型当约束条件为当约束条件为 a ai1 i1 x x1 1+ +a ai2 i2 x x2 2+ + + +a ainin x xn n b bi i时时，类似地令类似地

28、令 s s =(=(a ai1 i1 x x1 1+ +a ai2 i2 x x2 2+ + +a ainin x xn n)- )- b bi i 显然，显然，s s 也具有非负约束，即也具有非负约束，即s s00，这时新的约束条，这时新的约束条件成为件成为 a ai1 i1 x x1 1+ +a ai2 i2 x x2 2+ + +a ainin x xn n- -s s = = b bi i 化标准型时为了使约束由大化标准型时为了使约束由大于等于于等于不等式成为等式而不等式成为等式而引进的变量引进的变量 s s 称为称为“剩余变量剩余变量”。 剩余变量在目标函数中的价值系数也是零剩余变量

29、在目标函数中的价值系数也是零北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型剩余量：剩余量：线性规划中，一个大于等于约束条件中超过资源或能力最底限的部分称之为剩余量。2 xl + x2400，假如最优解为（150,110）那么剩余量就为10。两个概念两个概念松弛量：松弛量：线性规划中，小于等于约束条件中未被使用的资源或能力的值成为松弛量。 xl+ x2300，假如最优解为 （150,140）那么本约束的松弛量就为10。北京联合大学 自动化学院 耿钰例例1 1：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式minfminf = 3.6

30、 = 3.6 x x1 1 - 5.2 - 5.2 x x2 2 + 1.8 + 1.8 x x3 3 s. t. 2.3 s. t. 2.3 x x1 1 + 5.2 + 5.2 x x2 2 - 6.1 - 6.1 x x3 3 15.715.7 4.1 4.1 x x1 1 + 3.3 + 3.3 x x3 3 8.98.9 x x1 1 + + x x2 2 + + x x3 3 = 38= 38 x x1 1 , , x x2 2 , , x x3 3 0 0 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型解：首先解：首先, ,将目标函数转换成极大化：将目标函数转换成极大

31、化：令令 z z= -= -f f = -3.6 = -3.6x x1 1+5.2+5.2x x2 2-1.8-1.8x x3 3 北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型其次考虑约束，有其次考虑约束，有2 2个不等式约束，引进松弛变个不等式约束，引进松弛变量量x4x4和剩余变量和剩余变量x5x5，我们可以得到以下标准形式，我们可以得到以下标准形式的线性规划问题：的线性规划问题： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.ts.t. 2.3x1+

32、5.2x2-6.1x3+x4= 15.7. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 0 x1 ,x2 ,x3 ,x4 ,x5 0北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型（3 3）右端项有负值的问题：）右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量在标准形式中，要求右端项必须每一个分量非负。非负。 当某一个右端项系数为负时，如当某一个右端项系数为负时，

33、如 b bi i00，则把，则把该等式约束两端同时乘以该等式约束两端同时乘以-1-1，得到：，得到： - -a ai1 i1 x x1 1- -a ai2 i2 x x2 2- - -a ainin x xn n = -= -b bi i北京联合大学 自动化学院 耿钰（4） 变量无符号限制的问题：变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。在标准形式中，必须每一个变量均有非负约束。当某一个变量当某一个变量x xj j没有非负约束时，可以令没有非负约束时，可以令 x xj j = = x xj j- - x xj j” (” (x xj j00，x xj j”0)”0) 或或

34、 x xj j =- =-x xj j (x(xj j0)0) 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型北京联合大学 自动化学院 耿钰 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例例2 2：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式 minfminf= -3 = -3 x x1 1 + 5 + 5 x x2 2 + 8 + 8 x x3 3 - 7 - 7 x x4 4s.t. 2 s.t. 2 x x1 1 - 3 - 3 x x2 2 + 5 + 5 x x3 3 + 6 + 6 x x4 4 28 28 4 4 x x1 1 + 2 + 2 x x2 2 + 3 + 3 x x3 3 - 9 - 9 x x4 4 39 39 6 6 x x2 2