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

课程基本介绍

夫运筹帷幄之中，决胜千里之外。——《史记·高祖本纪》

由来：西汉初年，天下已定，汉高祖刘邦在洛阳南宫举行盛大的宴会，喝了几轮酒后，他向群臣提出一个问题：“我为什么会取得胜利？项羽为什么会失败？”高起、王陵认为高祖派有才能的人攻占城池与战略要地，给立大功的人加官奉爵，所以能成大事业。而项羽恰恰相反，有人不用，立功不授奖，贤人遭疑惑，所以他才失败。汉高祖刘邦听了，认为他们说的有道理，但是最重要的取胜原因是能用人。他称赞张良说：“夫运筹帷幄之中，决胜千里之外，吾不如子房（古人有名，有字，子房为张良的字）。”意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜利。这说明张良心计多，善用脑，善用兵。后来人们就用“运筹帷幄”表示善于策划用兵，指挥战争。课程基本介绍夫运筹帷幄之中，决胜千里之外。无论哪种案例，这里都有筹划，以策略取胜的意思课程基本介绍——起源与发展我国古代运筹学应用例子：田忌赛马丁渭修皇宫运筹学美：OperationsResearch英：OperationalResearch运作研究/作业研究无论哪种案例，这里都有筹划，以策略取胜的意思课程基本介绍——学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的研究问题：随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站和整个防空作战系统的协调配合问题1938年7月，波得塞雷达站的负责人罗伊（A.P.Rowe）用OperationalResearch命名防空作战系统运行的研究，这是运筹学OperationalResearch（O.R.）的由来1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组。l942年美国和加拿大也都相继成立运筹学小组据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。课程基本介绍——起源与发展学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的课程基本介绍——起源与发展

二次世界大战后，从事这些活动的许多专家转到了民用部门，使运筹学很快推广到了工业企业和政府工作的各个方面，从而促进了运筹学有关理论和方法的研究和实践，使得运筹学迅速发展并逐步成熟起来。运筹学发展到现在，但其内容已相当丰富，所涉及领域也十分广泛。现在这门新兴学科的应用已深入到国民经济的各个领域，成为促进国民经济多快好省，健康协调发展的有效方法。这门课的目的就是要系统地了解运筹学的基本概念、基本原理、研究方法及其应用，掌握运筹学整体优化的思想和定量分析的优化技术，并能正确应用各类模型分析和解决实际问题。课程基本介绍——起源与发展二次世界大战后，从课程基本介绍——定义“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。——《大英百科全书》运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”——《中国大百科全书》课程基本介绍——定义“运筹学是一门应用于管理有组织系统的科学课程基本介绍——定义运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”——《辞海》运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。——《中国企业管理百科全书》课程基本介绍——定义运筹学“主要研究经济活动与军事活动中能用课程基本介绍——定义运筹学所研究的，就是在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。中国学者根据“运筹于帷幄之中，决胜于千里之外”意译为“运筹学”，其意为运算筹划，出谋献策，以最佳策略取胜。这实际上极为恰当地概括了这门学科的精髓。课程基本介绍——定义运筹学所研究的，就是在经营管理活动中如何运筹学具有如下的性质特点运筹学是一门应用科学，应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”，这也是运筹学的目地定量化分析：通过数学方法的应用来对问题建立模型，并对模型的分析与求解最优化思想多学科的交叉与结合，如交通工程、物流工程、经济学、物理、化学等方法课程基本介绍——性质系统的整体思想运筹学具有如下的性质特点运筹学是一门应用科学，应用现有的科学课程基本介绍——分支规划理论线性规划非线性规划运输问题

整数规划动态规划目标规划图论与网络理论排队论存储论决策论对策论课程基本介绍——分支规划理论本课程具体内容与性质运筹学教学大纲运筹学进度安排本课程具体内容与性质运筹学教学大纲运筹学进度安排课程特点与相关要求课程特点与线性代数联系紧密，做好相关数学知识的复习课程要求认真听讲。有问题及时反映按时完成作业。每周第一次课之前交。要求独立、准时完成答疑时间每周二下午2:30-3:30，其它时间课程特点与相关要求课程特点与线性代数联系紧密，课程要求认真听课程考试方式与成绩构成考试方式闭卷考试成绩构成平时成绩占50%，期末考试占50%平时成绩由考勤和平时表现、平时作业、测验和实验等环节共同构成。课程考试方式与成绩构成考试方式闭卷考试成绩构成平时成绩占50

第一章线性规划和单纯形法本章主要内容：线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子第一章线性规划和单纯形法本章主要内容：线性规划问

第一节线性规划问题及数学模型1.线性规划（Linearprogramming）问题的提出

生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）第一节线性规划问题及数学模型1.线性规划（

第一节线性规划问题及数学模型

例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。问题的提出第一节线性规划问题及数学模型例1美佳公

第一节线性规划问题及数学模型例2

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2第一节线性规划问题及数学模型例2捷运公司在下一年度课程基本介绍——解决问题步骤

(1)提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；

(2)建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；

(3)求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；

(4)解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；

(5)解的控制。通过控制解的变化过程决定对解是否要作一定的改变；

(6)解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。课程基本介绍——解决问题步骤 (1)提出和形成问题。即要

第一节线性规划问题及数学模型2.线性规划问题模型的建立对例1试着建模：

例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。第一节线性规划问题及数学模型2.线性规划问

第一节线性规划问题及数学模型解：用变量x1和x2分别表示美佳公司制造家电Ⅰ和Ⅱ的数量。这时该公司可获取的利润为(2x1+x2)元，问题中要求获取的利润为最大，即max(2x1+x2)，称为目标函数，它是变量x1，x2的线性表达式函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”s.t.

subjectto的缩写，“受限制于……”第一节线性规划问题及数学模型解：用变量x1和

第一节线性规划问题及数学模型例2

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2第一节线性规划问题及数学模型例2捷运公司在下一年度

第一节线性规划问题及数学模型例2中：若用变量xij表示捷运公司在第i(i=1,…,4)个月初签订的租借期为j(j=1,…,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件s.t.第一节线性规划问题及数学模型例2中：若用变量xij表

第一节线性规划问题及数学模型

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

（2）确定目标函数，即要用来实现的目标，一般用决策变量的线性函数来表示，通常要求实现该函数的最大或最小。第一节线性规划问题及数学模型分析以上的

第一节线性规划问题及数学模型

如何辨别一个模型是线性规划问题？

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

4.线性规划数学模型的形式称为价值系数或目标函数系数

称为资源常数或约束右端常数称为技术系数或约束系数

称为决策变量

第一节线性规划问题及数学模型max（或min）

第一节线性规划问题及数学模型线性规划问题的数学模型简写形式如下：max（或min）

Mathematicalmodel第一节线性规划问题及数学模型线性规划问题的数学模型简矩阵形式：max（或min）

称为决策变量向量称为价值系数向量或目标函数系数向量称为资源常数向量或约束右端常数向量称为技术系数或约束系数矩阵

第一节线性规划问题及数学模型矩阵形式：max（或min） 称为决策变量向量称为价值向量形式：其中：

第一节线性规划问题及数学模型注意：向量形式时，每一个列向量Pj都是对应变量的系数，如P1对应的是x1的系数向量形式：其中：第一节线性规划问题及数学模型注意：向第一节线性规划问题及数学模型5.线性规划问题的标准形式特点：(1)目标函数统一变成求最大值（有些书规定求最小值）(2)约束条件统一变为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。即：第一节线性规划问题及数学模型5.线性规划问题的标准如何化标准形式？第一节线性规划问题及数学模型设目标函数为

minf=c1x1

+c2x2

+…+cnxn

则可以令z

＝-f

，该极小化问题与下面的极大化问题有相同的最优解，即

maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

minf

＝-maxz（1）极小化目标函数的问题：如何化标准形式？第一节线性规划问题及数学模型设（2）约束条件不是等式的问题：第一节线性规划问题及数学模型

若约束条件为ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差，即s=bi–(ai1x1

+ai2x2

+…+ainxn

)

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi化标准型时为了使约束由小于等于不等式成为等式而引进的变量s称为“松弛变量”。

松弛变量在目标函数中的价值系数是多少呢？价值系数应为0（2）约束条件不是等式的问题：第一节线性规划问题及数（2）约束条件不是等式的问题：第一节线性规划问题及数学模型当约束条件为ai1x1+ai2x2+…+ainxn

≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi

化标准型时为了使约束由大于等于不等式成为等式而引进的变量s称为“剩余变量”。

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

minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

第一节线性规划问题及数学模型解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3

例1：将以下线性规划问题转化为标准形式

第一节线性规第一节线性规划问题及数学模型其次考虑约束，有2个不等式约束，引进松弛变量x4和剩余变量x5，我们可以得到以下标准形式的线性规划问题：maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥0第一节线性规划问题及数学模型其次考虑约束，有2个不等第一节线性规划问题及数学模型（3）右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。

当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：

-ai1x1-ai2x2-…-ainxn

=-bi第一节线性规划问题及数学模型（3）右端项有负值的问题（4）

变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj’-xj”(xj’≥0，xj”≥0)

或xj=-xj’(xj’≥0)第一节线性规划问题及数学模型（4）变量无符号限制的问题：第一节线性规划问题及数第一节线性规划问题及数学模型例2：将以下线性规划问题转化为标准形式minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0第一节线性规划问题及数学模型例2：将以下线性规划问题第一节线性规划问题及数学模型解：首先，将目标函数转换成极大化令z=-f=3x1–5x2–8x3+7x4

；其次考虑约束，有3个不等式约束，引进松弛变量x5,x7和剩余变量x6；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：第一节线性规划问题及数学模型解：首先，将目标函数转换第一节线性规划问题及数学模型

maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

第一节线性规划问题及数学模型maxz=3x第一节线性规划问题及数学模型总结：把一般的LP化成标准型的过程：1目标标准化

minZ

等价于max(-Z)maxZ’=-∑cjxj2化约束为等式加松弛变量、减剩余变量3右端非负4变量非负化做变换或第一节线性规划问题及数学模型总结：把一般的LP化成标

1、P43：1.2（1）；P45：1.13；选作1.15、1.17；2、复习线性代数相关知识本次作业

第一节线性规划问题及数学模型1、P43：1.2（1）；P45：1.13；选作1课程基本介绍

夫运筹帷幄之中，决胜千里之外。——《史记·高祖本纪》

由来：西汉初年，天下已定，汉高祖刘邦在洛阳南宫举行盛大的宴会，喝了几轮酒后，他向群臣提出一个问题：“我为什么会取得胜利？项羽为什么会失败？”高起、王陵认为高祖派有才能的人攻占城池与战略要地，给立大功的人加官奉爵，所以能成大事业。而项羽恰恰相反，有人不用，立功不授奖，贤人遭疑惑，所以他才失败。汉高祖刘邦听了，认为他们说的有道理，但是最重要的取胜原因是能用人。他称赞张良说：“夫运筹帷幄之中，决胜千里之外，吾不如子房（古人有名，有字，子房为张良的字）。”意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜利。这说明张良心计多，善用脑，善用兵。后来人们就用“运筹帷幄”表示善于策划用兵，指挥战争。课程基本介绍夫运筹帷幄之中，决胜千里之外。无论哪种案例，这里都有筹划，以策略取胜的意思课程基本介绍——起源与发展我国古代运筹学应用例子：田忌赛马丁渭修皇宫运筹学美：OperationsResearch英：OperationalResearch运作研究/作业研究无论哪种案例，这里都有筹划，以策略取胜的意思课程基本介绍——学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的研究问题：随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站和整个防空作战系统的协调配合问题1938年7月，波得塞雷达站的负责人罗伊（A.P.Rowe）用OperationalResearch命名防空作战系统运行的研究，这是运筹学OperationalResearch（O.R.）的由来1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组。l942年美国和加拿大也都相继成立运筹学小组据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。课程基本介绍——起源与发展学科产生：第二次世界大战英国波得塞（Bawdsey）雷达站的课程基本介绍——起源与发展

二次世界大战后，从事这些活动的许多专家转到了民用部门，使运筹学很快推广到了工业企业和政府工作的各个方面，从而促进了运筹学有关理论和方法的研究和实践，使得运筹学迅速发展并逐步成熟起来。运筹学发展到现在，但其内容已相当丰富，所涉及领域也十分广泛。现在这门新兴学科的应用已深入到国民经济的各个领域，成为促进国民经济多快好省，健康协调发展的有效方法。这门课的目的就是要系统地了解运筹学的基本概念、基本原理、研究方法及其应用，掌握运筹学整体优化的思想和定量分析的优化技术，并能正确应用各类模型分析和解决实际问题。课程基本介绍——起源与发展二次世界大战后，从课程基本介绍——定义“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。——《大英百科全书》运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”——《中国大百科全书》课程基本介绍——定义“运筹学是一门应用于管理有组织系统的科学课程基本介绍——定义运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”——《辞海》运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。——《中国企业管理百科全书》课程基本介绍——定义运筹学“主要研究经济活动与军事活动中能用课程基本介绍——定义运筹学所研究的，就是在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。中国学者根据“运筹于帷幄之中，决胜于千里之外”意译为“运筹学”，其意为运算筹划，出谋献策，以最佳策略取胜。这实际上极为恰当地概括了这门学科的精髓。课程基本介绍——定义运筹学所研究的，就是在经营管理活动中如何运筹学具有如下的性质特点运筹学是一门应用科学，应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”，这也是运筹学的目地定量化分析：通过数学方法的应用来对问题建立模型，并对模型的分析与求解最优化思想多学科的交叉与结合，如交通工程、物流工程、经济学、物理、化学等方法课程基本介绍——性质系统的整体思想运筹学具有如下的性质特点运筹学是一门应用科学，应用现有的科学课程基本介绍——分支规划理论线性规划非线性规划运输问题

整数规划动态规划目标规划图论与网络理论排队论存储论决策论对策论课程基本介绍——分支规划理论本课程具体内容与性质运筹学教学大纲运筹学进度安排本课程具体内容与性质运筹学教学大纲运筹学进度安排课程特点与相关要求课程特点与线性代数联系紧密，做好相关数学知识的复习课程要求认真听讲。有问题及时反映按时完成作业。每周第一次课之前交。要求独立、准时完成答疑时间每周二下午2:30-3:30，其它时间课程特点与相关要求课程特点与线性代数联系紧密，课程要求认真听课程考试方式与成绩构成考试方式闭卷考试成绩构成平时成绩占50%，期末考试占50%平时成绩由考勤和平时表现、平时作业、测验和实验等环节共同构成。课程考试方式与成绩构成考试方式闭卷考试成绩构成平时成绩占50

第一章线性规划和单纯形法本章主要内容：线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子第一章线性规划和单纯形法本章主要内容：线性规划问

第一节线性规划问题及数学模型1.线性规划（Linearprogramming）问题的提出

生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）第一节线性规划问题及数学模型1.线性规划（

第一节线性规划问题及数学模型

例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。问题的提出第一节线性规划问题及数学模型例1美佳公

第一节线性规划问题及数学模型例2

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2第一节线性规划问题及数学模型例2捷运公司在下一年度课程基本介绍——解决问题步骤

(1)提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；

(2)建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；

(3)求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；

(4)解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；

(5)解的控制。通过控制解的变化过程决定对解是否要作一定的改变；

(6)解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。课程基本介绍——解决问题步骤 (1)提出和形成问题。即要

第一节线性规划问题及数学模型2.线性规划问题模型的建立对例1试着建模：

例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。第一节线性规划问题及数学模型2.线性规划问

第一节线性规划问题及数学模型解：用变量x1和x2分别表示美佳公司制造家电Ⅰ和Ⅱ的数量。这时该公司可获取的利润为(2x1+x2)元，问题中要求获取的利润为最大，即max(2x1+x2)，称为目标函数，它是变量x1，x2的线性表达式函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”s.t.

subjectto的缩写，“受限制于……”第一节线性规划问题及数学模型解：用变量x1和

第一节线性规划问题及数学模型例2

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2第一节线性规划问题及数学模型例2捷运公司在下一年度

第一节线性规划问题及数学模型例2中：若用变量xij表示捷运公司在第i(i=1,…,4)个月初签订的租借期为j(j=1,…,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件s.t.第一节线性规划问题及数学模型例2中：若用变量xij表

第一节线性规划问题及数学模型

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

（2）确定目标函数，即要用来实现的目标，一般用决策变量的线性函数来表示，通常要求实现该函数的最大或最小。第一节线性规划问题及数学模型分析以上的

第一节线性规划问题及数学模型

如何辨别一个模型是线性规划问题？

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

4.线性规划数学模型的形式称为价值系数或目标函数系数

称为资源常数或约束右端常数称为技术系数或约束系数

称为决策变量

第一节线性规划问题及数学模型max（或min）

第一节线性规划问题及数学模型线性规划问题的数学模型简写形式如下：max（或min）

Mathematicalmodel第一节线性规划问题及数学模型线性规划问题的数学模型简矩阵形式：max（或min）

称为决策变量向量称为价值系数向量或目标函数系数向量称为资源常数向量或约束右端常数向量称为技术系数或约束系数矩阵

第一节线性规划问题及数学模型矩阵形式：max（或min） 称为决策变量向量称为价值向量形式：其中：

第一节线性规划问题及数学模型注意：向量形式时，每一个列向量Pj都是对应变量的系数，如P1对应的是x1的系数向量形式：其中：第一节线性规划问题及数学模型注意：向第一节线性规划问题及数学模型5.线性规划问题的标准形式特点：(1)目标函数统一变成求最大值（有些书规定求最小值）(2)约束条件统一变为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。即：第一节线性规划问题及数学模型5.线性规划问题的标准如何化标准形式？第一节线性规划问题及数学模型设目标函数为

minf=c1x1

+c2x2

+…+cnxn

则可以令z

＝-f

，该极小化问题与下面的极大化问题有相同的最优解，即

maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

minf

＝-maxz（1）极小化目标函数的问题：如何化标准形式？第一节线性规划问题及数学模型设（2）约束条件不是等式的问题：第一节线性规划问题及数学模型

若约束条件为ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差，即s=bi–(ai1x1

+ai2x2

+…+ainxn

)

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi化标准型时为了使约束由小于等于不等式成为等式而引进的变量s称为“松弛变量”。

松弛变量在目标函数中的价值系数是多少呢？价值系数应为0（2）约束条件不是等式的问题：第一节线性规划问题及数（2）约束条件不是等式的问题：第一节线性规划问题及数学模型当约束条件为ai1x1+ai2x2+…+ainxn

≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi

化标准型时为了使约束由大于等于不等式成为等式而引进的变量s称为“剩余变量”。

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

minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

第一节线性规划问题及数学模型解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8