管理运筹学课件

运筹学的产生与发展

运筹学的基本内涵

运筹学模型

运筹学的工作步骤

运筹学的基本内容第一章绪论**

运筹学的产生1.时间：第二次世界大战前后

2.地点：英国

3.主要事件

(1)1937年研究雷达运作问题

(2)1938年整个防空作战系统运行的研究

(3)1939年成立军事攻关小组，其主要研究内容为：

雷达布置与运作问题

反空袭系统的运行与控制

海军舰队的编制问题

潜艇问题

**

运筹学的发展1.1941年英国皇家陆、海、空三军均成立了O.R.小组

2.后来美国、前苏联等盟军也相继成立了O.R.小组

3.战后O.R.走向社会经济领域

4.50年代O.R.成为一门独立的学科

5.60年代O.R.迅速普及和发展

6.O.R.在中国的发展

**50年代O.R.成为一门独立的学科主要标志：大量O.R.学会的成立和相应期刊的问世

1.英国1948年创立O.R.学会

2.美国1952年成立O.R.学会

1953年成立管理科学研究所刊物分别为“运筹学”和“管理科学”

3.1956~1959有10个国家成立O.R.学会，并有6种期刊问世

4.1959年国际O.R.学会成立

5.1986年已有38个国家有O.R.学会

**60年代O.R.迅速普及和发展

主要标志:

计算机的普及与发展方法理论成熟使O.R.成本降低高校普遍开设的重要课程

**O.R.在中国的发展1.50年代中期钱学森、华罗庚、许国志等著名学者将O.R.从西方引入我国2.1956年将O.R.直译为“运用学”3.1957年将O.R.意译为“运筹学”4.1956年成立O.R.小组5.1958年成立O.R.研究室6.1960年召开全国O.R.会议7.1980年成立O.R.学会

**

运筹学的基本内涵1.英国O.R.学会的定义

2.美国O.R.学会的定义

3.我国辞海的释义

4.中国企业管理百科全书的释义

5.概括性定义

**英国O.R.学会的定义

OperationalResearchistheapplicationofthemethodsofsciencetocomplexproblemsarisinginthedirectionandmanagementoflargesystemsofmen,machines,materials,andmoneyinindustry,business,government,anddefense.Thedistinctiveapproachistodevelopascientificmodelofthesystem,incorporatingmeasurementsoffactorssuchaschanceandrisk,withwhichtopredictandcomparetheoutcomesofalternativedecisions,strategiesorcontrols.Thepurposeistohelpmanagementdetermineitspolicyandactionsscientifically.**美国O.R.学会的定义

OperationalResearchisconcernedwithscientificallydecidinghowtobestdesignandoperateman-machinesystems,usuallyunderconditionsrequiringtheallocationofscarceresources.

**我国辞海的释义

运筹学：主要研究经济活动与军事活动中能用数量表达的有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力。

**中国企业管理百科全书的释义

运筹学：应用分析、试验、和量化的方法，对经济管理系统中人、财、物等有限资源统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

**

概括性定义

运筹学：通过建立、求解数学模型，规划、优化有限资源的利用方案，为决策者提供科学决策依据，以实现有限资源的合理利用的系统知识体系。**

运筹学模型1.模型的定义：模型是客观事物的简化和抽象，是研究者经过思维抽象后用文字、图表、符号、关系式及实物对客观事物的描述

2.模型的种类：形象模型、模拟模型和数学模型

3.数学模型：用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。

4.数学模型三要素：决策变量、目标函数和约束条件。

5.建立数学模型常用的假设**建立数学模型常用的假设(1)离散变量的连续性假设；

(2)非线性函数的线性假设；

(3)非主要因素的不相关假设；

(4)随机变量的确定性假设；

(5)灰数的白化假设。**运筹学的工作步骤提出和形成问题；建立模型；求解模型；解的检验与转译；解的实施。**

运筹学的基本内容

线性规划及其扩展非线性规划

动态规划存贮论

图论排队论

对策论

决策论

**2024/1/2171.线性规划问题及其数学模型2.线性规划的图解法3.线性规划问题的标准形式4.线性规划的解集特征5.线性规划的单纯形法6.单纯形法的进一步讨论第二章线性规划2024/1/218线性规划问题及其数学模型

资源合理利用问题：第5页例2-1质量检验问题：第6页例2-2线性规划数学模型的一般形式2024/1/219资源合理利用问题：第5页例2-1

1.决策变量：x1和x22.目标函数：max(2x1+3x2)3.约束条件：10

x1+20x2804x1

166x218

x1，x202024/1/220

质量检验问题：第6页例2-21.决策变量：x1和x22.目标函数：min(40

x1+36x2)

3.约束条件：5

x1+3x2

45

x1

8x2

10

x1，x202024/1/221线性规划数学模型的一般形式1.决策变量是非负变量；

2.目标函数是线性函数；

3.约束条件是线性等式或不等式组。一般形式为：

max(min)(c1

x1+c2

x2+…+

cnxn

)

a11

x1+a12

x2+…+a1nxn

(=,)b1

a21

x1+a22

x2+…+a2n

xn

(=,)b2

……

am1

x1+am2

x2+…+amnxn

(=,)bm

x1，

x2，

…，xn

0

2024/1/222

线性规划的图解法1.局限性：只能求解具有两个变量的线性规划问题。2.学习目的：图解法只能求解具有两个决策变量的线性规划问题，其应用具有很大的局限性，因此学习图解法的目的并非是要掌握一种线性规划问题的求解方法，而是要通过图解法揭示线性规划问题的内在规律，为学习线性规划问题的一般算法（单纯形法）奠定基础。3.线性规划有关解的几个概念4.图解法的基本步骤5.图解法所反映出的一般结论2024/1/223线性规划有关解的几个概念1.可行解：满足约束条件的一组决策变量的取值；

2.可行域：可行解所构成的集合；

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

4.最优值：与最优解相对应的目标函数的取值。2024/1/224图解法的基本步骤1.画出平面直角坐标系；

2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向；

3.找出可行域并反映出目标函数直线的斜率；

4.平移目标函数直线找出最优解。

5.例题：第7页例2-3：用图解法求解例2-16.习题：第8页例2-4：用图解法求解例2-2

2024/1/225用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/226用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/227用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/228用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/229用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/230用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/231用图解法求解例2-1x1x2

4

3

2

1

0123456782024/1/232用图解法求解例2-2x1x251015

15

10

5

02024/1/233图解法所反应出的一般结论1.线性规划问题的可行域是凸多边形；2.如果线性规划问题有最优解，其最优解一定可以在其可行域的顶点上得到，而不会在可行域的内部；3.如果线性规划问题在其可行域的两个顶点上得到最优解，那么两顶点连线上的所有点均为最优解点；4.线性规划问题的解可能有四种情况：唯一最优解；无穷多最优解；无界解和无可行解。2024/1/234线形规划问题的标准形式1.标准形式的基本条件：（1）决策变量非负；（2）目标函数极大化（或极小化）；（3）约束条件为严格等式，且右端项非负。2.标准形式的表示：

代数式；和式；向量式；矩阵式

3.

标准形式的转化2024/1/235线性规划的标准型：代数式minz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2………

am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,n2024/1/236线性规划的标准型：和式minz=∑cjxj

∑aijxj=bi

i=1,2,…,m

xj

≥0

j=1,2,…,nj=1nnj=12024/1/237线性规划的标准型：向量式minz=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,n

C=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=12024/1/238线性规划的标准型：矩阵式minz=CX

AX=b，X

≥0，

b≥0

其中：

b=(b1,b2,…,bm)T

a11

a12….a1n

A=a21

a22…a2n………

am1

am2…amn2024/1/239标准形式的转化1.无约束变量x的处理：

x=y-z,其中y,z02.负数变量x的处理：

x=-y,其中y03.目标函数极小化的处理：

MinCX=-Max(-CX)4.非等式约束条件的处理：加松弛变量或减剩余变量5.右端项为负：两端同乘“-1”2024/1/240线形规划的解集特征1.线性规划基与解的概念

(1)基、基列、基变量和非基变量

(2)基解、基可行解和可行基2.凸集的概念与解集的基本定理

(1)凸集的概念

(2)解集的基本定理2024/1/241线性规划基与解的概念1.基、基列、基变量和非基变量

(1)基：MaxCX,AX=b,X0,b0Amn其秩为m，B是Amn中的一个mm阶满秩矩阵，则称B是线性规划问题的一个基

(2)基列：基B中所包含的m个列向量

(3)基变量：基列所对应的决策变量

(4)非基变量：基变量以外的决策变量2.基解、基可行解、可行基

(1)基解：令所有的非基变量为零，所求得的一组解

(2)基可行解：所有分量均为非负的基解

(3)可行基：与基可行解所对应的基2024/1/242凸集的概念与解集的基本定理1.凸集的概念：设K是n维欧氏空间的一点集，若任意两点X(1)

k，X(2)

k的连线上的一切点

X(1)+(1-)X(2)

k，(0<<1)

则称k为凸集。2.解集的基本定理：

(1)若线性规划问题存在可行域，则其可行域是凸集；

(2)线性规划问题的基可行解对应其可行域的顶点；

(3)若线性规划问题存在最优解，则其最优解一定能在基可行解中找到。2024/1/243线性规划的单纯形法1.单纯形法的基本原理

(1)单纯形法的基本思路

(2)第12页例2-62.最优性检验与解的判别3.单纯形表4.单纯形法的基本步骤5.用单纯形法求解例2-66.课上习题2024/1/244单纯形法的基本思路1.找出一个初始的基可行解；2.判断其最优性；3.转移至另一个较优的基可行解；4.重复2、3两步直至最优。2024/1/245第12页例2-6Maxz=2x1+3x210x1+20x2+x3=804x1+x4=16

6x2+x5=18x1，

x2，

x3，

x4，

x50B=(p3，p4，p5)X(0)=(0，0，80，16，18)TZ(0)=0，z=2x1+3x2寻找相邻的基可行解2024/1/246例2-6Max(2，3)=3

x2入基Min(80/20，18/6)=3

x5出基B=(p3，p4，p2)10x1+x3-10/3x5=204x1+x4=16x2+1/6x5=3X(1)=(0，3，20，16，0)TZ(1)=9，z=9+2x1-1/2x52024/1/247例2-6Max(2)=2

x1入基Min(20/10，16/4)=2

x3出基B=(p1，p4，p2)x1+1/10x3-1/3x5=2-2/5x3+x4+4/3x5=8x2+1/6x5=3X(2)=(2，3，0，8，0)TZ(2)=13，z=13-1/5x3+1/6x52024/1/248例2-6Max(1/6)=1/6

x5入基Min(8/(4/3)，3/(1/6))=6

x4出基B=(p1，p5，p2)x1+1/4x4=4-3/10x3+3/4x4+x5=6x2+1/20x3-1/8x4=2X(3)=(4，2，0，0，6)TZ(3)=14，z=14-9/10

x3

-1/8x42024/1/249最优性检验与解的判别2024/1/250单纯形表2024/1/251单纯形法的基本步骤1.数学模型标准化、正规化；2.建立初始单纯形表；3.计算检验数并判断最优性，结束或继续；4.确定入基变量和出基变量，5.迭代运算；6.重复3、4、5步，直至结束。2024/1/252用单纯形法求解例2-62024/1/253用单纯形法求解例2-62024/1/254用单纯形法求解例2-62024/1/255用单纯形法求解例2-62024/1/256课上习题1.Maxz=2x1+4x2+x3+x4x1+3x2

+x48

2x1+x2

6x2

+x3

+x4

6x1

+x2

+x3

9x1~4

02.第17页例2-103.第19页例2-112024/1/257单纯形法的进一步讨论1.计算问题

(1)入基变量的选择

(2)解的退化2.人工变量与初始正规基

(1)大M法

(2)两阶段法2024/1/258入基变量的选择

入基变量是根据最大正检验数来选择的，这样做的目的是为了使目标函数得到最大的增量，因此当最大正检验数有多个时，可主观地选择它们中的任意一个作为入基变量。其实具有正检验数的所有非基变量都可作为入基变量。2024/1/259出基变量的选择与解的退化1.退化解：部分基变量的值为零的基可行解称为退化解。2.在选择出基变量时，如果最小比值不唯一，可主观确定出基变量，此时产生退化解。3.例2024/1/260例Maxz=2x4+(3/2)x6

x1+x4-x5=8

x2+2x4+x6=4

x3+x4+x5+x6=3

x1~602024/1/261例2024/1/262例2024/1/263例2024/1/264例2024/1/265例2024/1/266人工变量与初始正规基第21页例2-13:

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x30(1)标准化2024/1/267例2-13的标准化

Minz=-3x1+x2+x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1~50(2)正规化2024/1/268例2-13的正规化人工变量：为构造基变量（正规基）人为加入的变量

x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~70初始正规基B=(p4,p6,p7)=E2024/1/269大M法1.大M法：令人工变量的价值系数为“-M”(极大值)或“M”(极小值)的单纯形法即称为大M法；例如：

Minz=-3x1+x2+x3+Mx人1+Mx人2

Maxz=2x1+x2+4x3-Mx人1+Mx人22.例2-13的大M法3.习题（大M法）2024/1/270用大M法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x302024/1/271用大M法求解例1.13

Minz=-3x1+x2+x3+Mx6+Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~702024/1/272用大M法求解例1.132024/1/273用大M法求解例1.132024/1/274用大M法求解例1.132024/1/275用大M法求解例1.132024/1/276习题（用大M法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x302024/1/277习题（用大M法求解）

Maxz=2x1+4x2+x3-Mx7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~702024/1/278习题（用大M法求解）2024/1/279习题（用大M法求解）2024/1/280习题（用大M法求解）2024/1/281两阶段法1.两阶段法：第一阶段，在原约束条件下，求所有人工变量和的最小值；第一阶段的目的是获得问题的一个初始基可行解（人工变量和的最小值为零）或得出问题无可行解（人工变量和的最小值大于零）的结论；第二阶段，去掉人工变量，在原目标下从已得到的基可行解开始优化。2.例2-13的两阶段法3.习题（两阶段法）2024/1/282用两阶段法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x302024/1/283用两阶段法求解例2-13第一阶段：

Minz=x6+x7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~702024/1/284用两阶段法求解例2-132024/1/285用两阶段法求解例2-132024/1/286用两阶段法求解例2-132024/1/287用两阶段法求解例2-132024/1/288用两阶段法求解例2-132024/1/289习题（用两阶段法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x302024/1/290习题（用两阶段法求解）第一阶段：Minz=x7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~702024/1/291习题（用两阶段法求解）2024/1/292习题（用两阶段法求解）2024/1/293习题（用两阶段法求解）2024/1/21.对偶问题的提出2.对偶关系3.对偶性质4.对偶单纯形法5.灵敏度分析第三章线性规划的对偶理论2024/1/21.对偶问题的提出1.从数学角度提出对偶问题(1)正规化的线性规划数学模型(2)检验数与最优条件(3)对偶模型2.从经济学角度提出对偶问题(1)例1(2)例1的数学模型(3)例1的对偶模型2024/1/2正规化的线性规划数学模型Maxz=CXAX+EXs=bX,Xs

02024/1/2检验数与最优条件2024/1/2对偶模型2024/1/2例12024/1/2例1的数学模型Maxz=8x1+7x2x1+2x2

1004x1+3x2

2005x1+6x2

300x1，

x2

02024/1/2例1的对偶模型Minz=100x1+200x2+300x3x1+4x2+5x3

82x1+3x2+6x3

7x1，

x2

02024/1/22.对偶关系2024/1/23.对偶性质1.对称性:对偶问题的对偶是原问题；2.弱对偶性:CX

Yb,X和Y是可行解；3.无界性:原问题无界,对偶问题无可行解；4.最优性:CX=Yb,X和Y是最优解；5.对偶性:原问题与对偶问题同时具有最优解且最优值相等；6.互补松弛性；7.对应性。2024/1/2互补松弛性对于线性规划的最优解，若某一约束条件的对偶变量值大于零，则该约束条件取严格等式；反之，若约束条件取严格不等式，则其对应的对偶变量一定为零。2024/1/2对应性1.原问题：Maxz=CXAX+EXs=b，X，Xs

0

2.对偶问题：Minz=YbYA-EYs=C，Y，Ys

0

3.对应关系4.例2

2024/1/24.对偶单纯形法1.对偶单纯形法的内涵2.对偶单纯形法的优点和应用的前提条件3.对偶单纯形法的计算步骤

4.例3（例3-5）2024/1/2对偶单纯形法的内涵对偶单纯形法：在对偶可行基的基础上进行的单纯形法即为对偶单纯形法。单纯形法是在原问题可行的基础上，通过迭代使对偶问题达到可行，从而得到最优解。根据对偶问题的对称性，可这样考虑，若原问题不可行而对偶问题可行，那么在保持对偶问题可行的基础上，逐步迭代使原问题达到可行，也可得到最优解。2024/1/2对偶单纯形法的优点和

应用的前提条件对偶单纯形法的优点是原问题的初始解不要求是可行解，可以从非可行解开始迭代，从而省去了引入人工变量的麻烦。当然对偶单纯形法的应用也是有前提条件的，这一前提条件就是对偶问题的解是基可行解。2024/1/2对偶单纯形法的计算步骤1.根据对偶基可行解列初始单纯形表；2.最优性检验：若原问题也为基可行解，则已得到最优解，过程结束；否则，进入第3步。3.选择出基变量：Min{bi|

bi0}4.选择入基变量：Min{

j/aij

|

aij0}若所有的aij均大于零，则无可行解。5.迭代运算，重复1~4步。2024/1/2例2Maxz=2x1+x23x1+4x2+x3=186x1+2x2+x4

=24

x1+x2+x5

=6

x1~4

0

Minw=18y1+24y2+6y33y1+6y2+y3-y4=24y1+2y2+y3-y5=1y1~5

0

2024/1/2例2的求解结果2024/1/2例3（第35页例3-5）Minw=x1+4x2+3x4

x1+2x2-x3+x43-2x1-x2+4x3+x42

x1~40

转换成标准形式：Minw=x1+4x2+3x4

x1+2x2-x3+x4-x5=3-2x1-x2+4x3+x4-x6=2

x1~60

2024/1/2例3的求解过程

2024/1/2例3的求解过程

2024/1/2例3的求解过程2024/1/25.线性规划的灵敏度分析1.灵敏度分析的内涵2.灵敏度分析的处理方法3.资源系数变化的灵敏度分析4.价值系数变化的灵敏度分析

5.技术系数变化的灵敏度分析6.增加新变量的灵敏度分析7.增加新约束的灵敏度分析2024/1/2灵敏度分析的内涵灵敏度分析是对系统因环境变化显示出来的敏感程度的分析。在线性规划中讨论灵敏度分析，目的是描述一种能确定模型结构中元素变化对问题最优解影响的分析方法。灵敏度分析主要回答两方面问题：因素有一定量变化时，最优解有什么变化；因素在什么范围内变化时，最优解保持不变。2024/1/2灵敏度分析的处理方法2024/1/2资源系数变化的灵敏度分析1.基本原理(B|E)

(E|B-1)A

B-1A，XB=B-1(b+b)

j保持不变，XB

非负最优基不变。2.第37页例3-6

Maxz=5x1+12x2+4x3+0x4-Mx5x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

2024/1/2例3-6的求解

2024/1/2例3-6的求解

2024/1/2例3-6的求解

2024/1/2例3-6的求解2024/1/2价值系数变化的灵敏度分析1.原理：cj的变化只会影响

j2.第38页例3-7

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024/1/2第38页例3-7的求解

2024/1/2第38页例3-7的求解

2024/1/2第38页例3-7的求解

2024/1/2第39页例3-8的求解

2024/1/2第39页例3-8的求解

2024/1/2第39页例3-8的求解2024/1/2技术系数变化的灵敏度分析1.原理：同bi的变化，B-1pj

反映进最终单纯形表。2.Xj为非基变量3.Xj为基变量4.练习第41页例3-115.练习第41页例3-122024/1/2Xj为非基变量（例3-7）2024/1/2

Xj为基变量（例3-7）

2024/1/2

Xj为基变量（例3-7）2024/1/2第41页例3-11

Maxz=5x1+12x2+4x3x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

2024/1/2第41页例3-11

2024/1/2第41页例3-112024/1/2第41页例3-12

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024/1/2第41页例3-12

2024/1/2第41页例3-12

2024/1/2第41页例3-122024/1/2增加新变量的灵敏度分析1.步骤：(1)求

新，如果

新0，最优解不变；如果

新0，最优解有变化。(2)B-1p新

反映进最终单纯形表，并用单纯形法求解。2.例题：第42页例3-132024/1/2第42页例3-13

2024/1/2第42页例3-132024/1/2增加新约束的灵敏度分析1.步骤：(1)检验原最优解是否满足新增加的约束条件，如果满足，最优解不变；如果不满足，最优解变化；(2)将新约束反映进最终单纯形表；(3)基变量系数向量单位化；(4)用单纯形法、对偶单纯形法或引入人工变量求解。2.例题：第43页例3-142024/1/2第43页例3-14

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

2024/1/2第43页例3-14

2024/1/2第43页例3-14

2024/1/2第43页例3-14的求解

2024/1/2第43页例3-14的求解2024/1/21.运输问题的内涵：运输问题不仅仅是把某种商品从若干个产地运至若干个销地而使总运费最小的问题；从更广义上讲，运输问题是具有一定模型特征的线性规划问题。2.运输问题的数学模型

3.运输问题的求解

4.运输问题的拓展及应用第四章运输问题2024/1/22.

运输问题的数学模型

2024/1/2第46页例4-1

2024/1/2例4-1的数学模型2024/1/23.运输问题的求解1.求解方法：表上作业法2.表上作业法的基本步骤:(1)找出初始基可行解；(2)求检验数并判断最优性；(3)确定入基变量和出基变量；(4)调整运输方案；(5)重复2~4，直至最优。2024/1/2找出初始基可行解1.最小元素法(1)基本思想：就近供应(2)基本步骤(3)例4-12.伏格尔法(1)基本思想：机会成本(2)基本步骤(3)例4-12024/1/2最小元素法的基本步骤1.找出最小运价，确定供求关系，最大量的供应；2.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3.在剩余的运价表中重复1、2两步，直到得到初始基可行解。2024/1/2例4-1的最小元素法

2024/1/2例4-1的最小元素法

2024/1/2例4-1的最小元素法

2024/1/2例4-1的最小元素法

2024/1/2例4-1的最小元素法

2024/1/2例4-1的最小元素法2024/1/2伏格尔法的基本步骤1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。2024/1/2例4-1的伏格尔法

2024/1/2例4-1的伏格尔法

2024/1/2例4-1的伏格尔法

2024/1/2例4-1的伏格尔法

2024/1/2例4-1的伏格尔法

2024/1/2例4-1的伏格尔法2024/1/2求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变量）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（基变量）的回路。空格的闭合回路有且唯一，有数字格不存在闭合回路。2.位势法：行因子

i，列因子

j，使每一个基变量有cij

=

i

+

j。3.判断最优性：若所有的检验数均大于等于零，已得最优方案；否则，进行方案调整。2024/1/2闭合回路法的基本步骤1.找出某一空格的闭合回路；2.从该空格开始在闭合回路上给各个顶点进行”+“、”-“间隔标号；3.计算空格的检验数空格检验数=

cij(+)-

cij(-)

4.重复1~3，直至求得全部的检验数。

2024/1/2例4-1(最小元素法)

2024/1/2闭合回路法求检验数

2024/1/2闭合回路法求检验数

2024/1/2闭合回路法求检验数

2024/1/2例4-1(伏格尔法)

2024/1/2闭合回路法求检验数2024/1/2位势法的基本步骤1.把基变量对应的运价拿来；2.任意取一个位势因子并赋予一个任意值；3.余下的所有因子可根据基变量的运价cij

=

i

+

j来唯一确定；4.计算空格检验数

ij=cij-(

i

+

j)。

2024/1/2例4-1(最小元素法)

2024/1/2位势法求检验数

2024/1/2位势法求检验数

2024/1/2例1(伏格尔法)

2024/1/2位势法求检验数

2024/1/2位势法求检验数2024/1/2确定入基变量和出基变量1.确定入基变量：具有最大绝对值的负检验数所对应的变量即为入基变量。2.确定出基变量：在入基变量所处的闭合回路上，让入基变量增加，由于供求平衡关系，带“+”标号的基变量将随之增加；而带“-”标号的基变量将随之减少，最先减少为零的基变量即为出基变量。2024/1/2确定入基变量2024/1/2确定出基变量2024/1/2调整运输方案1.在入基变量所在的闭合回路上，带“+”标号的格增加x出，带“-”标号的格减少x出。注意：出基变量减少后的“0”不要保留在表格中，如果同时有多个而带“-”标号的格减少为零，可人为确定之一为出基变量，在表格中保留其它“0”。2.对调整后的方案求检验数并判断其最优性。3.重复1~2两步，直至得到最优方案。

2024/1/2运输方案

2024/1/2调整后的运输方案2024/1/2最优运输方案2024/1/24.运输问题的拓展及应用1.产销不平衡的运输问题(1)产大于销

(2)销大于产2.运输问题的应用(1)第59页例4-4(2)第60页例4-5(3)第62页习题6

(4)第60页例4-62024/1/2产大于销的运输问题

2024/1/2产大于销的运输问题2024/1/2销大于产的运输问题

2024/1/2销大于产的运输问题2024/1/2第59页例4-4

2024/1/2第59页例4-4

2024/1/2第59页例4-42024/1/2第60页例4-5

2024/1/2第60页例4-52024/1/2第62页习题6已知某厂每月可生产甲产品270吨，先运至A1、A2、A3三个仓库，然后在分别供应B1、B2、B3、B4、B5五个用户。已知仓库容量分别为50、100、150吨，各用户的需要量分别为25、105、60、30、70吨。已知从该厂经各仓库然后供应各用户的运费如下表所示，试确定一个使总运费最少的调运方案。

2024/1/2第62页习题6

2024/1/2第62页习题62024/1/2第60页例4-6

2024/1/2第60页例4-6

2024/1/2第60页例4-6

2024/1/2第60页例4-62024/1/21.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规划5.指派问题第五章整数规划2024/1/2整数规划的数学模型Max(Min)(c1

x1+c2x2+…+

cnxn)a11

x1+a12x2+…+a1nxn(=,)

b1a21

x1+a22x2+…+a2nxn(=,)

b2……...am1

x1+am2x2+…+amnxn(=,)

bmx1~n

0

且取整数纯整数规划:所有变量都有取整约束混合整数规划:只有部分变量有取整约束2024/1/2分枝定界法1.分枝定界法的基本思路2.第65页例5-13.练习题2024/1/2分枝定界法的基本思路

2024/1/2分枝定界法的基本思路2024/1/2第65页例5-1Maxz=40x1+90x29x1+7x2567x1+20x270x1，x20且取整

2024/1/2用分枝定界法解例5-11.求解相应的线性规划L0Maxz=40x1+90x29x1+7x2567x1+20x270x1，x20

2024/1/2用分枝定界法解例5-1

x259x1+7x2=564327x1+20x2=701012345678910x1L0:x*=(4.81,1.82),Z*=356

2024/1/2用分枝定界法解例5-12.将L0分解为L1和L2L1：

Maxz=40x1+90x29x1+7x2567x1+20x270

x1

4x1，x20L1：X*=(4,2.10),Z*=349

L2：X*=(5,1.57),Z*=341

L2：

Maxz=40x1+90x29x1+7x2567x1+20x270

x1

5x1，x202024/1/2用分枝定界法解例5-13.分解L1形成L3、L4，其中：

L3={L1,x22}L4={L1,x23}

L3:X*=(4,2),Z*=340

L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)舍弃L4

2024/1/2用分枝定界法解例5-14.分解L2形成L5、L6，其中：

L5={L2,x21}L6={L2,x22}

L5:X*=(5.44,1),Z*=308

L6:无可行解(1)舍弃L5、L6；(2)得最优解X*=(4,2),Z*=340。

2024/1/2例5-1求解过程示意图L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6无可行解2024/1/2练习题Maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2024/1/2求解练习题首先求解线性规划L0:Maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~60

2024/1/2求解练习题

2024/1/2求解练习题

2024/1/2求解练习题

2024/1/2求解练习题

L0（0，15/2，9/2）111/2

L1（0，7，5）55

L2无可行解2024/1/2割平面法1.割平面法的基本思路2.例3.练习题2024/1/2割平面法的基本思路同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。2024/1/2例Maxz=x1+x2-x1+x213x1+x24x1，x20且取整

2024/1/2用割平面法解例1.求解相应的线性规划L0Maxz=x1+x2-x1+x213x1+x24x1，x20

2024/1/2用割平面法解例非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、x2的余数均为3/4，不妨选取x2：x2+3/4x3+1/4x4=7/4

2024/1/2用割平面法解例x2+3/4x3+1/4x4=7/4现将各系数分成整数和非负真分数两部分，从而可得：(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)将整数部分的变量移至等式右端有：3/4x3+1/4x4=3/4+（1-x2）非负整数解(1-x2)为整数，左端非负故有：3/4x3+1/4x4=3/4+非负整数从而：3/4x3+1/4x4

3/4或x2

1以x2

1为割平面可使可行域减少一个包括A点在内的三角形。

2024/1/2x2A1

01x1用割平面法解例

2024/1/2用割平面法解例2024/1/2练习题Maxz=2x1+5x2+4x3x1+x2+x3

12x1+2x2154x1+5x326x1~30且取整

2024/1/2求解练习题

2024/1/2求解练习题选取x2：1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+（7-x2）

于是有割平面：1/2x1+1/2x5

1/2或

x27

2024/1/2求解练习题

2024/1/2求解练习题2024/1/20-1型整数规划1.0-1规划：0-1规划是整数规划的特例，是所有决策变量仅取0和1的整数规划问题。2.引例（1）第69页例5-3（2）引例23.0-1规划的隐枚举法（1）隐枚举法的基本步骤（2）第70页例5-4（3）第71页例5-52024/1/2第69页例5-3

某公司拟在东、西、南三个区建立销售门市部，拟议中有7个场点A1~7可供选择。东区的三个点A1~3最多选两个，西区的两个点A4~5最少选一个，南区的两个点A6~7最少选一个。如果建设Ai点，需要投资bi元，年可获利ci元，公司可筹集到的投资总额为B元，问应如何决策才能使年利潤最大。

2024/1/2例5-3

令xi=0或1，其中：

xi=0表示第I个点未被选取

xi=1表示第I个点被选取其数学模型为：

x1+x2+x32x4+x51

x6+x71

2024/1/2引例2

两种运输方式的限制条件分别为：6x1+4x2307x1+3x240互斥的约束统一于一个模型中：6x1+4x230+Mx37x1+3x240+M(1-x3)

其中x3为0-1变量。2024/1/2隐枚举法的基本步骤

1.目标函数极小化；2.目标函数系数非负化，如果xj的系数为负数，可令xj=1-xj

；3.决策变量按其目标函数系数的大小排列；4.令所有变量为“0”，检查该解的可行性，如果可行此解即为最优解，如果不可行进入下一步；5.按变量的顺序依次令各变量分别取“0”或“1”，根据分枝定界的原理进行剪枝，直至结束。2024/1/2第70页例5-4Maxz=3x1-2