运筹学绪论、第一章 2

运筹学基础及应用(O.R.)(美OperationsResearch)(英OperationalResearch)苗文静华北科技学院wenjingmiao@163.com1课程简介运筹学类似于数学建模。现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理中出现的一些带有普遍性的运筹问题加以提炼，构建数学模型并进行求解。随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用，如资源分配、厂址定位、库存、人员配置等各个方面。2运筹学本身也在不断发展，现在已经包括多个分支。如：数学规划（包含线性规划、非线性规划、整数规划、目标规划等）、图论、决策分析、排队论、存贮论、对策论等。通过学习该课程，应了解运筹学对优化决策问题进行定量研究的特点，理解线性规划、运输问题、整数规划、目标规划、动态规划、网络计划等的基本优化原理，掌握其中常用的模型和算法。先修课程主要为线性代数，为了深入学习这门课程，最好作必要的复习或学习。3胡运权主编.《运筹学教程》.清华大学出版社。运筹学编写组.《运筹学》.清华大学出版社。参考书目4要求考勤：旷课按考勤次数从平时成绩中逐级扣分；有事请请假.课堂：认真听讲，做好笔记.成绩：平时30%（包括考勤和平时作业）+期末考试70%.5运筹学软件LindoLingoExcel规划求解Matlab6绪论内容提要一、运筹学简介二、运筹学发展简史三、主要研究内容四、运筹学的工作步骤五、运筹学的性质与特点六、如何学好运筹学7运筹学简介运筹学的称谓

美国：OperationsResearch英国：OperationalResearch缩写：OR日本译作“运用学”，香港、台湾译为“作业研究”，我国学者从古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，充分体现了这门学科运心筹谋、策略取胜的精髓。译作“运筹学”。北美：ManagementScience管理科学8《大英百科全书》释义：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具。《中国大百科》释义：运筹学用数学方法研究国民经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。运筹学简介9运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，来解决实际中提出的专门问题，并为决策者选择最优策略提供定量依据。运筹学是一门交叉学科；运筹的目标是最优策略。运筹学简介101.运筹学问题和朴素的运筹学思想，可以追溯到古代.如：围魏救赵；田忌赛马；丁渭主持皇宫的修复等.2.运筹学诞生的三个来源：军事、管理和经济。孙武：运筹为计，知人善用，应敌为变；运筹学发展简史运筹学发展简史11运筹学的产生在阶级社会中，科学技术的发展往往受到战争的极大推动，许多新科学、新技术首先是由军事斗争的需要而产生和发展起来的.运筹学也不例外，它的产生背景为第二次世界大战.121938年7月，波德塞(Bawdsey)雷达站的负责人罗伊(A．P．Rowe)提出立即进行整个防空作战系统运行的研究，用“operationalresearch”一词作为这方面研究的描述，这就是O.R.（运筹学)这个名词的起源。

13●1940年9月，英国成立了由物理学家P.M.S.布莱克特领导的第一个运筹学小组。成员有：三名生物学家、两名数学物理学家、一名天文学家、一名军官、一名测量员、一名普通物理学家和两名数学家。由于人员组成多专业性，所以有人称这个小组为“布莱克特马戏团”。●1942年，美国和加拿大都相继建立了运筹学小组。这些运筹学小组在确定护航舰队的规模、开展反潜艇战的侦察、组织有效的对敌轰炸等方面作了大量研究，为运筹学有关分支的建立作出了贡献。改进威耳孙云室方法及在核物理和宇宙线领域的发现，获得1948年诺贝尔物理学奖14

1947年丹齐克(G.B.Danzig)在研究美国空军资源的优化配置时提出了线性规划及其通用解法——单纯形法;1948年美国麻省理工学院把运筹学作为一门课程介绍；50年代初用电子计算机求解线性规划获得成功;1951年莫尔斯(P.M.Morse)和金博尔(G.E.KimbaU)合著的“运筹学方法”一书正式出版。1．从1945年到50年代初，被称为创建时期。特点：从事研究的人数不多，范围较小，人员从军事转为民用。所有这些，标志运筹学这门学科的基本形成。运筹学的发展阶段1550年代末，美国大约有半数的大公司在自己的经营管理中应用运筹学，如用于制订生产计划、物资储备、资源分配、设备更新等方面酌决策。有更多刊物、学会出现。1957年在英国牛律大学召开了第一次国际运筹学会议。1959年成立国际运筹学联合会。2．50年代初到50年代末，被认为是其成长时期。特点：电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，得以用来解决实际管理系统中的优化问题．促进了运筹学的推广应用。运筹学发展简史163．自60年代以来，是其迅速发展和开始普及的时期。第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统，如城市交通、环境污染、国民经济计划等。特点：运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中。运筹学发展简史17成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势运筹学发展简史18我国于上世纪50年代开始研究运筹学。50年代中期由钱学森、许国志等教授由西方引入；投入产出表、质量管理的研究和应用开展较早；1970年后，华罗庚教授在全国范围内推广统筹法和优选法，一大批数学家开始研究运筹学；中国运筹学会于1980年成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。某些分支的研究达到当时国际水平。运筹学发展简史19主要内容线性规划、对偶理论、运输问题整数规划、目标规划、动态规划

图论与网络分析决策分析库存伦对策论20运筹学解决问题的方法步骤提出并形成问题

建立模型分析并求解模型检验并评价模型

应用或实施模型的解21引入数学方法解决实际问题

--定性与定量方法结合系统与整体性

--从全局考察问题应用性

--源于实践、为了实践、服务于实践交叉学科

--涉及经济、管理、数学、工程和系统等多学科开放性

--不断产生新的问题和学科分支多分支

--问题的复杂和多样性运筹学的性质与特点22如何学习运筹学课程

学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。

自学时要掌握三个重要环节：

1.认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。

2.要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。3.要学会做学习小结。23LinearProgramming（LP）

线性规划问题及其数学模型

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用第一章线性规划及单纯形法24

线性规划问题及其数学模型第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用25一、问题的提出

为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例1、有一正方形铁皮，应如何裁剪能使容积最大？xa无约束的极值问题26例2、如何安排生产才能使利润最大？资料如图

设备产品ABCD利润（元）

Ⅰ21402

Ⅱ22043有效台时1281612目标max

x1≥0,x2≥0s.t.2x1+2x2≤12

带约束的极值问题x1x2z=2x1+3x2

约束条件x1+2x2≤84x1≤164x2≤12subjectto函数数学模型27例3、合理配料问题数学模型x1x2

x3

x4

x5

x6z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用这六种营养物各多少克，才能既获得每日最少所需又使花费最省？28二、数学模型组成要素：

决策变量

约束条件

目标函数线性规划：连续的（数值取实数）关于变量的线性等式或不等式关于变量的线性函数（一次方）问题中有未知的变量，需要我们去求解，此外有目标函数及约束条件，一般有非负条件存在，由此组成规划问题的数学模型。29线性规划数学模型的一般形式s.t.s.t.30向量形式s.t.s.t.31向量形式矩阵形式s.t.s.t.32线性规划问题的数学模型s.t.s.t.s.t.s.t.33三、线性规划问题的标准形式s.t.s.t.s.t.s.t.34标准形式的主要特征s.t.③决策变量xj取值非负④约束条件右端常数项bi为非负值①目标函数为求极大值（也可用求极小值）②所有约束条件都是等式（非负条件除外）

√35非标准形式化为标准形式的方法⑴目标函数的转换⑵约束方程的转换：由不等式转换为等式⑶变量的变换称为松弛变量称为剩余变量x1+x24x1+x2－

x3=4⑷约束条件右端常数项的变换：bi﹤0x1+x23x1+x2+x3=336例1、将下列线性规划问题化为标准形式+0x5+0x4maxz

=－2x1

+

x2

－3x3

maxz

=－2x1

+

(x2－

x2)

+3x3

+0x4+0x53x1

－2(x2－

x2)－

x3

=－4－3x1

+2(x2－

x2)+

x3

=4解：设min

x1≥0,x2取值无约束,x3≤0s.t.x1+2x2+4x3≤6z=2x1

－x2

+3x3

3x1

－2x2+x3=－4

2x1

－

x2－3x3≥

5

x1,x2,x2,x3,x4,x5≥0

x1+2x2+4x3+x4

=6s.t.

2x1

－

x2－

3x3－

x5

=5引入变量令x1

+

2(x2－

x2)－4x3

+

x4=6第二个约束方程两边乘(－1),从而得到标准形式2x1

－

(x2－

x2)＋3x3

－

x5

=5－3x1

+2x2－2x2+

x3

=4

x1,x2,x2,x3,x4,x5≥0s.t.x1

+2x2－2x2－4x3

+

x4=62x1

－

x2＋

x2＋3x3

－

x5

=5maxz

=－2x1

+

x2－

x2+3x3

+0x4+0x537例2、将下列线性规划问题化为标准形式x1

＋2(x2－

x2)＋

x3

＋

x4

=5x1,x2,x2,x3,x4,

x5,

x6

≥0x1

＋

(x2－

x2)＋

x3

＋

x6

=2maxz=x1

+2(x2－

x2)

+3x3

+0x4+0x5+

0x6解：max

x1≥0,x2取值无约束,x3≤0s.t.x1+2x2－

x3≤5z=x1+2x2

－3x3

2x1+

3x2－

x3≥6

－x1

－

x2+

x3≥

－2引入变量令第三个约束方程两边乘(－1),从而得到标准形式2x1

＋3(x2－

x2)＋

x3

－

x5

=6s.t.x1

＋2x2－2x2＋

x3

＋

x4

=5x1,x2,x2,x3,x4,x5,x6≥0x1

＋

x2－

x2＋

x3

＋

x6

=2maxz=x1

+2x2－2x2+3x3

+0x4+0x5+

0x62x1

＋3x2－3x2＋

x3

－

x5

=638练习：将下列线性规划问题化为标准形式min

x1,x2≥0,x3取值无约束s.t.x1

－

x2+x3≤10z=－2x1+3x2

－

x3

3x1+

2x2－

x3≥8x1

－3x2+

x3=－1－x1

＋3x2

－

x3＋

x3

=1maxz

=2x1

－3x2+

x3－

x3

+0x4+0x53x1

＋2x2

－

x3＋

x3

－

x5

=8

x1,x2,x3,x3,x4,x5≥0s.t.x1

－

x2

＋

x3－

x3

＋

x4

=10解：设引入变量令第三个约束方程两边乘(－1),从而得到标准形式39

线性规划问题的求解方法第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题及其数学模型

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用40一、预备知识：解的概念

可行解：满足约束条件的解

最优解：使目标函数达到极值的可行解

可行域：所有可行解构成的集合s.t.41一、预备知识：凸集与顶点x1x2x2x1x1x2x1x2x1x2x1x2凸集：集合C中任意两点连线上的所有点还在C内

任给x1,x2C,x=x1+(1－)x2

C(0<<1)顶点：凸集C中不在任意两不同点连线上的点对x,任给x1,x2C,不存在x=x1+(1－)x2(0<<1)凸集非凸集42二、图解法步骤：将约束条件在图上表示建立直角坐标系确立满足约束条件的解的范围(可行域)绘制出目标函数的图形在可行域中确定最优解定义：用图示的方法求解线性规划问题的最优解优点：直观性强，计算方便缺点：只适用于问题中是两(三)个变量的情况43123456781234562x1+2x2=12x1+2x2=84x1=164x2=12唯一最优解此时z=14。(4,2)示例1：s.t.①②③④0x2

x1z=0x1=4,x2=2,

44123456781234563x1+2x2=12x1+2x2=6x2=2无穷多最优解示例2：0x2

x1s.t.①②③45x1－x2=－1x1+2x2=2无界解(无最优解)示例3：s.t.①②x1x2

0思考：若目标函数改为minz=x1+x2呢？若改为minz=x1+

2x2呢？46无可行解示例4：s.t.①②x1+x2=1x1x2

02x1+3x2=6472x2=12练习：s.t.x1=83x1+4x2

=36(4,6)x1812x243690唯一最优解此时z=42。x1=4,x2=6,

48（4）无可行解：无可行域，模型约束条件矛盾图解法的几点启示线性规划问题解的情况有：（1）唯一最优解：只有一点为最优解点（2）无穷多最优解：有许多点为最优解点（3）无界解：最优解取值无界，无最优解LP问题的可行域若存在则一定是凸集(有限个顶点)LP问题若有最优解，则定能在可行域某顶点达到LP问题的解题思路：顶点→相邻顶点→……49三、单纯形法（SimplexMethod）美国数学家丹齐格(G.B.Dantzig)1947年创建简捷、规范，是举世公认的解决线性规划问题行之有效的方法。

理论根据：基本思想：在凸集的有限个顶点上搜索最优解该搜索策略可极大地减少访问顶点的数量。

由可行域的一个顶点出发，沿着凸集边缘逐个计算与判定所遇到的顶点，直至找到最优解所对应的顶点为止。

线性规划问题的可行域是n维向量空间中的多面凸集，其最优值如果存在则必在该凸集的某顶点处达到。50s.t.(一)基解与基可行解系数矩阵A是m×n矩阵（设m<n），其秩R(A)=m。线性规划问题的基：矩阵A中的m×m阶满秩子矩阵B。(|B|≠0)基解：令非基变量为零，对m个基变量求解后合并所得的解。最多个基向量：B中的m个列向量Pr。基变量：与基向量对应的m个变量xr。剩下n-m个非基变量。51(一)基解与基可行解基解：令非基变量为零，对m个基变量求解后合并所得的解。设

，

令非基变量基变量为，|B|≠0基变量的唯一解基解最多个52(一)基解与基可行解基解：令非基变量为零，对m个基变量求解后合并所得的解。基可行解：满足变量非负约束条件xj≥0的基解。可行基：对应于基可行解的基。基可行解可行解非可行解基解53基基解是否基可行解目标函数值例题：列出全部基、基解、基可行解和指出最优解s.t.s.t.标准化系数矩阵:54例题：用图解法求最优解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

x1基解对应于各直线交点基可行解是可行域的顶点55(二)单纯形法的基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。定理3：若线性规划问题有最优解，则一定存在一个基可行解是最优解。定理2：线性规划问题的基可行解对应其可行域的顶点。理论根据：

线性规划问题的可行域是n维向量空间中的多面凸集，其最优值如果存在则必在该凸集的某顶点处达到。在有限个基可行解中搜索最优解（迭代）56(三)单纯形法的求解思路确定一个初始基可行解是否最优改进为新的基可行解最优解是否循环结束化标准形571、确定初始基可行解s.t.s.t.标准化约束方程组的系数矩阵：基变量值：初始基可行解：58记2、最优性检验s.t.初始基可行解：任一可行解：由约束方程组得代入目标函数可得：则有：检验数基变量的59其中2、最优性检验当前基可行解是最优解若所有，则对任意可行解X，都有线性规划问题存在无界解（无最优解）若存在某个，且所有令只需保证由所有显然此时因找可行解X，使z无限大。60线性规划问题无可行解2、最优性检验当前基可行解是最优解：所有线性规划问题有唯一最优解′线性规划问题有无穷多最优解′′线性规划问题存在无界解（无最优解）若存在某个，且所有存在和当前基可行解非最优解，但LP问题有最优解其中所有；

或

有非基变量,且613、寻找改进的基可行解相邻的基可行解：若两个基可行解之间仅变换一个基变量。将一个基变量变成非基变量（换出），一个非基变量变成基变量（换入），进而找出一个目标函数值更大的“相邻”基可行解。入基变量的确定由和越大，值上升的可能性越大因此，一般取对应的变量作为换入基的变量。623、寻找改进的基可行解出基变量的确定令换入变量为得到基可行解，需保证且至少一个为0（换出）则只需取其余非基变量，存在此时换出。确定为换出变量，由称为主元素。可行解：证明是基可行解？§3-1引理633、寻找改进的基可行解约束方程组的系数矩阵：初始基

，

变量换入,换出，新可行解对应向量：是线性无关的，故是基可行解。s.t.64单纯形法的求解思路确定一个初始基可行解是否最优改进为新的基可行解最优解是否循环结束化标准形？65步骤简单总结经过何种运算可转到第③步，实现循环迭代？①将线性规划问题化成标准形式;②找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解;③计算各非基变量xj的检验数j，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{j|j＞0}=k原则，确定xk为入基变量，再按=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量，得到改进的基可行解。66将其化为单位矩阵，则LP问题形式为s.t.4、迭代运算初始基

，

变量换入,换出，新可行基：s.t.674、迭代运算①主元素所在行：②其余行：684、迭代运算新检验数

s.t.整理后可得

69①将线性规划问题化成标准形式;②找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解;③计算各非基变量xj的检验数j，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{j|j＞0}=k原则，确定xk为入基变量，再按=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量；⑥以alk为主元素进行迭代，利用初等行变换将xk所在列化为单位向量，即alk化为1，其它元素化为0，得到改进的可行基，转入第③步。计算步骤总结70(四)单纯形表格法——单纯形表s.t.7172……73max

x1,x2≥0s.t.

2x1+2x2≤12z=2x1+3x2

4x1

≤

165x2≤15例题：用单纯形法求解线性规划问题+0x4+0x3maxz=2x1

+3x2s.t.引入变量得到标准形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥074+0x4+0x3maxz=2x1

+3x2s.t.引入变量得到标准形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥07576此时所有检验数得到最优解最优值为77①将线性规划问题化成标准形式;②找出或构造一个单位矩阵作初始可行基，确定初始基可行解，建立初始单纯形表;③检验各非基变量xj的检验数j，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{j|j＞0}=k原则，确定xk为入基变量，再按=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量；⑥用xk替换基变量中的xl，利用初等行变换将xk所在列化为单位向量，得到新的单纯形表，转入第③步。单纯形法计算步骤78练习：求解线性规划问题：79标准化系数矩阵(五)单纯形法的进一步讨论

用单纯形法解题时，需要有个单位矩阵作为初始可行基当约束条件都是“≤”时，加入松弛变量就形成了初始基

但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵s.t.－2x1＋

x2－x3

－

x5

=1解：引入变量从而得到标准形式s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9maxz=－3x1

+

0x2

+

x3+0x4+0x5约束方程组的系数矩阵：80maxz=－3x1

+

0x2

+

x3+0x4+0x5(五)单纯形法的进一步讨论采用添加人工变量的方法因是在等式中人为加进的，为保证约束条件的意义，最优解中人工变量只能等于0

在等式约束中加入若干人工变量，人为构造一个单位矩阵

人工变量的添加不能影响最优解的取值：－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9约束方程组的系数矩阵：两种处理方法

大M法两阶段法＋

x6

=1

＋

x7

=9=4,x6,x7≥0如何处理？811、大M法maxz=－3x1

+

0x2

+

x3+0x4+0x5－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0－Mx6－Mx7为保证最优解中人工变量取值为0，可令目标函数中人工变量的系数为足够大的一个负值，用“－M”代表。由于系数是一个足够大的负值，因此，只要人工变量的取值不为零，目标函数就不可能实现最大化。

计算时，把M看做一个代数符号直接参加单纯形法求解。若最终单纯形表中，人工变量仍是基变量且值不为零，则说明该问题求不到最优解，即无可行解。82－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+

0x2

+

x3+0x4+0x5－Mx6－Mx783使人工变量尽快出基8485此时所有检验数得到最优解最优值为86－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+0x2

+

x3+0x4+0x5用大M法处理人工变量，用手工计算不会出现任何问题。

但用计算机求解时，由于在程序中只能用很大的数代替M，有可能受计算机的误差影响，导致结果发生错误，使大M法失效。2、两阶段法

第一阶段：构造判断是否存在可行解的模型

构造仅含人工变量(系数为1)且要求极小化的目标函数用单纯形法求解，若minw=0，说明人工变量为0，问题存在基可行解，进入第二个阶段；若minw≠0，说明最优解中人工变量非零，无可行解，停止。minw=x6+

x787minw=x6+

x72、两阶段法－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0882、两阶段法

第二阶段：从上阶段的最终单纯形表出发，去掉人工变量，引入原来的目标函数，继续迭代，找出问题的最终解maxz=－3x1

+

0x2

+

x3+0x4+0x589人工变量法总结约束方程组

在等式约束中加人工变量，人为构造单位矩阵作初始可行基目标函数

为保证原约束条件的意义，最优解中人工变量只能是0大M法

令目标函数中人工变量的系数为足够大的一个负值“－M”两阶段法1、构造仅含人工变量且求极小化的目标函数，单纯形法求解；2、去掉上阶段最终单纯形表中的人工变量，引入原目标函数，继续迭代，找出问题的最终解。若最终单纯形表中，人工变量仍是基变量且值不为零，则说明该问题求不到最优解，即无可行解。903、由单纯形表判别解的类别无可行解唯一最优解所有无穷多最优解无界解（无最优解）最终单纯形表的基变量中仍有非零人工变量存在某个，且所对应的系数最优解某非基变量至少一个且91≤0≥0保证当前的基可行解是最优解至少有一个等于0，如至少有一个大于0，如

＞0存在，保证当xp入基时有xl出基说明能得到另一个最优基可行解两个基可行解连线上的所有点都是最优解92无穷多最优解示例1：s.t.标准化s.t.9394此时所有检验数得到最优解最优值为95此时所有检验数得另一最优解最优值为96无界解(无最优解)示例2：s.t.标准化s.t.且所对应系数取值无限制160x2

x14x1=1697无可行解示例3：s.t.标准化s.t.98此时所有检验数但人工变量仍留在基变量中且不为零，问题无可行解。99补充说明单纯形法在计算中可能出现以下两种情况：同时出现多个相同的最大j值同时出现多个相同的最小θ值理论上可能出现死循环，但实际很罕见，一般不需特殊处理，任选其中一个对应的变量入基或出基即可。若遇到极端情况，可利用勃兰特(bland)规则：当存在多个j>0时，选取下标值最小的变量入基；当出现多个相同最小θ时，选取下标值最小的变量出基。100

线性规划模型的应用第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题及其数学模型

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法101线性规划问题的建模

建模是运筹学方法的核心和精髓，建立一个正确的数学模型，是问题解决的关键，答案利用线性规划程序可很快获得。正确的建模要求建模者：理解生产和管理问题的本质，明确目标和错综复杂的约束条件，通过调查和统计资料获取原始可靠的数据。建模过程的规律：①通过对实际问题的分析、理解，明确那些是决策变量，目标要求是什么，有哪些资源限制条件；②把变量、常数、约束条件、目标要求的相互关系联系起来列出相应的方程式；③注意变量、系数、常数的计量单位要统一。102线性规划问题的应用

问题需满足的条件

①目标函数能用数值指标来反映，且为线性函数；

②存在多种方案及有关数据；

③要达到的目标是在一定约束条件下实现的，这些条件可用线性等式或不等式描述。相关问题生产计划问题（合理利用资源，使利润最高或完成计划）合理配料问题（保证饮食、药品等效果前提下使成本最低）投资方案选择问题（固定资金投入时使效益最高）人员分派问题（多项任务分配，使人数最少或效率最大）合理下料问题（在给定材料中截取零件，使用料最省）运输问题＊（多个产销地及运价限制，安排方案使运费最低）……103生产计划问题：如何安排生产使利润最大？资料如图

设备产品ABCD利润（元）

Ⅰ21402

Ⅱ22043有效台时1281612max

x1,x2≥0s.t.2x1+2x2≤12z=2x1+3x2

x1+2x2≤84x1≤164x2≤12设xj表示第j种产品在计划期内的产量104合理配料问题：资料如图

设xj表示第j种营养物所需克数z=4x1+3x2+6x3+5x4+2.7x5+2.2x