运筹学简介及第一章

运筹学OperationalResearch绪论1、运筹学的发展历史（OperationalResearch）名称由来：“夫运筹帷幄之中，决胜千里之外”Lanchester战斗方程(1914)Erlang(1917)的排队论公式(源于电话通信问题)；存储论(1920)的最优批量公式第二次世界大战英国雷达布防高射炮火力的问题，武器库设置问题等防空作战系统运行研究（1938,7）——“operationalresearch”苏联学者康托洛维奇对列宁格勒胶合板厂的计划任务建立线性规划模型（1939）；美国数学家G.B.Dantzig,求解线性规划问题的单纯形法（1947）；60年代华罗庚“优选法、统筹法”，国防科技的计划评审技术;计算机→运筹学的发展→实际问题的最优与满意解。

美国：研究用科学方法来决定在资源不充分情况下如何最好地设计人——机系统并使之最好地运行。２、运筹学的定义：德国：从事决策模型的数学解法的一门科学。英国：运用科学方法解决工业、商业、政府部门、国防部门中有关人力、机器、物资、金钱等大型系统的指挥管理方面出现的问题，其目的是帮助管理者科学地决策其策略和行动。３、运筹学的内容和分支规划论：线性规划、非线性规划、整数规划、动态规划、多目标规划等决策论：决策的原则、决策的方法等对策论——齐王赛马，矩阵对策排队论库存理论（存贮论）图与网络分析４、运筹学的本质以定量的模型化方法来描述和解决问题５、基本过程分析和表达问题（可控变量及有关参数、目标、可能的约束）；建立模型——数学模型,图论模型,网络模型等；求解模型，即寻找方案；检验(对解的最优性进行检验)；方案的分析、评价；存储空间分配，不同排队规则对磁盘工作性能的影响；计算机网络分组交换、操作系统中的作业调度，排队论；满足某组需求的文件查找次序，整数规划；管理信息系统，决策支持系统。规划论、决策论、对策论等。６、运筹学应用——计算机与信息系统7、主要参考书

运筹学基础及应用（第四版）,胡运权主编,哈尔滨工业大学出版社运筹学（第三版）,《运筹学》教材编写组编，清华大学出版社

课件公用邮箱用户名 yunchouxue_bjut@密码 yunchouxue简介+线性规划3)单纯形法(3)对偶问题和灵敏度分析(6)运输问题(3)目标规划(3)整数规划(6)非线性规划(6)动态规划(6)排队论(6)对策论和单目标决策论(3)8、内容安排(54-3-3-3=45课时)省略内容：1图与网络分析2存储论3多目标决策论4启发式方法第一章线性规划（LinearProgramming）教学目的：本章重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。重点：线性规划问题的求解方法、解的基本性质以及对偶原理。难点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析

问题1：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？§1线性规划问题及其数学模型解：设x1，x2分别为甲、乙产品的数量，则有约束条件x1+2x2≤8

4x1≤16

4x2≤12

x1≥0，x2≥0，称x1，x2为决策变量目标函数maxz=2x1+3x2(图解法)问题2：运输问题的运价、产量、销量如下表，如何安排调运，运费最小？

销地产地

运价

123产量A

B

2132

24

50

30

销量401525解：设x1j为从产地A运往销地j的物资数量(j=1,2,3),x2j为从产地B运往销地j的物资数量(j=1,2,3), 则有，目标函数：

minz=2x11+x12+3x13+2x21+2x22+4x23

约束条件:x11+x12+x13≤

50x21+x22+x23≤

30x11+x21≤

40x12+x22 ≤

15x13+x23≤

25xij≥0i=1,2；j=1,2,3总结：线性规划三要素：决策变量、目标函数、约束条件线性规划的特点:

目标线性、约束条件为线性不等式或等式一般情况下，其值均是正的定义：线性规划（LP）的一般模型为

目标函数：max(min)z=c1x1+c2x2+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn=（≤、≥）b1

a21x1+a22x2+…+a2nxn=（≤、≥）b2

…

…

…

am1x1+am2x2+…+amnxn=（≤、≥）bm

x1≥0，x2≥0，…，xn≥0其中：

C—价值向量

A—系数矩阵

X－决策变量向量

b—资源向量其它表示形式：

形式：max(min)Z=cjxj

s.t.aijxj,=,bi，i=1,2,…,m

xj0，j=1,2,…,n

向量形式:max(min)Z=CXs.t.Pjxj,=,b

xj0，j=1,2,…,n

矩阵形式:max(min)Z=CXs.t.AX,=,bX0线性规划问题模型的标准型：分量形式：线性规划（LP）的标准型：目标函数：maxz=c1x1+c2x2+…+cnxn

约束条件：a11x1+a12x2+…+a1nxn=b1s.t.a21x1+a22x2+…+a2nxn=b2

…

…

…am1x1+am2x2+…+amnxn=bm

x1≥0，x2≥0，…，xn≥0

且bi≥0，若bi<0，则乘(-1)注:有些书中以min型目标函数为标准型∑(和)形式：目标函数maxz=∑cjxj

约束条件s.t.∑aijxj=bi，

i=1,…,mxj≥0，j=1,…,n向量形式:

目标函数maxz=∑cjxj

约束条件s.t.∑Pjxj=b

xj≥0，j=1,…,n矩阵形式:

目标函数maxz=CX

约束条件s.t.AX=b

X≥0任意线性规划模型转化为标准型的方法：1、目标最小化情况：minZ=max(―Z)=maxZ2、约束条件为不等式：“≥”：引进非负松弛变量xk≥0,不等式左端减去松弛变量,目标函数中xk对应的系数取为零。

“≤”：引进非负剩余变量（也叫松弛变量）xl≥0,不等式左端加上松弛变量,目标函数中xl对应的系数取为零。3、决策变量xk是自由变量(无非负限制)，或xj有上下界限制都可以引进新的变量，转化为变量≥0形式。例如xk是自由变量，引进xl≥0,xm≥0,新变量，令xk=xl-xm，对应的目标系数仍为ck

。4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”解：引进变量x3≥0、x4≥0，将自由变量换为x2=x3-x4

引进松弛变量x5≥0,松弛变量x6≥0得:maxZ’=-x1-2x3+2x4+0x5+0x6

2x1+3x3-3x4+x5=6s.t.x1+x3-x4-x6=4

x1-x3+x4=3

xj≥0,j=1,3,4,5,6例如：将下列线性规划问题化成标准型

minZ=x1+2x2

2x1+3x2≤6s.t.x1+x2≥4

x1-x2=3

x1≥0§2.1图解法

图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。

（用图解法求解,线性规划不需要化成标准型）图解法的步骤：

1、约束区域的确定

2、目标函数等值线

3、平移目标函数等值线求最优值§2线性规划图解法例1：maxz=2x1+3x2

s.t.x1+2x2≤84x1≤16x1,x2≥0有唯一解x1x2可行域(4,2)z=14目标函数等值线画图步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值有无穷多解线段Q1Q2上的任意点都是最优解x2x1x1+2x2=84x2=123x1=12例2maxz=2x1+4x2

s.t.x1+2x2≤84x2≤123x1≤12x1,x2≥0Q1Q2约束条件围不成区域(又称矛盾方程)无可行解例3：x1x2maxz=4x1+3x2

-3x1+2x2≤6

s.t.-x1+3x2≥18

x1,x2

≥0无有限最优解(无界解)x1x2例4：-3x1+2x2=6

图解法得出线性规划问题解的几种情况解的几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶点达到无穷多解在围成的区域边界上,至少在两个顶点处达到最优值目标和某一约束方程成比例无可行解(无解)围不成区域有矛盾方程无界解(无解)围成无界区域,且无有限最优值缺少一必要条件的方程列向量x=(x1，x2，…，xm）T为m维列向量。xRm线性相关一组向量v1,…,vn,如果有一组不全为零的系数α1,…,αn,使得:α1v1+…+αnvn=0，则称v1,…,vn是线性相关的.线性无关一组向量v1,…,vn,如果对于任何数α1,…,αn,若要满足:α1v1+…+αnvn=0,则必有系数α1=…=αn=0,(全为零)则称v1,…,vn线性无关(线性独立).矩阵A的秩设A为一个m×n阶矩阵(m<n)若矩阵中最大线性无关列向量个数为k,则称矩阵A的秩数为k,记为秩(A)=k.复习线性代数内容:设线性规划的标准形式：

maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)可行域：由约束条件(2)、(3)所围成的区域；可行解：满足(2)、(3)条件的解X=(x1，x2，…，xn)T为可行解；基：设A是约束条件方程组的m×n维系数矩阵,其秩为m，B是A中m×m阶非奇异子矩阵，则称B为线性规划问题的一个基。设§2.2线性规划问题解的概念B=

=(p1,p2,…,pm)

a11a12…a1m

a21a22…a2m

…

…

…

am1am2…amm

基向量、非基向量、基变量、非基变量：称pj(j=1,2,…,m）为基向量，其余称为非基向量；与基向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经常写成XN。基解：对给定基B,设XB是对应于这个基的基变量

XB=(x1，x2，…，xm)T；

令非基变量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T

称为基解。基可行解:所有决策变量满足非负条件(xj≥0)的基解,称作基可行解。可行基：基可行解所对应的基底称为可行基。基解的数目最多为Cnm个。基可行解的数目一般小于基解的数目;基解中非零分量的个数小于m个时，基解称为退化解。以后在不声明的情况下，均假设不出现退化情况。可行解基解基可行解非可行解解的关系：

凸集:（直观）图形中连接任意两点的线段全部都在图形区域内,称此图形是凸的。严格数学定义:设Ω为一n维欧氏空间的点集,若任意两点x1,x2∈Ω,有x=λx1+(1-λ)x2∈Ω，其中λ∈[0，1]，则称Ω为凸集。§2.3线性规划问题的几何意义•x1•x2•x1•x2凸组合：设x(1),x(2),…,x(k)是n维空间中的k个点,若存在μ1,μ2,…,μk(0≤μi≤1i=1,2,…k且Σμi=1)使x=μ1x(1)+μ2x(2)+…+μkx(k)成立,则称x为

x(1),x(2),…,x(k)

的凸组合。特别，平面上的两点x(1),x(2),连线上任一点x的坐标为x=αx(1)+(1-α)x(2)0≤α≤1.顶点：设K为凸集,x∈K并且x不能用K内不同的两点x(1),x(2)(x≠x(1),x≠x(2))的凸组合表示,则称x为顶点.

定理1:线性规划问题若存在可行域,则其必是凸集，亦即

D={X∣AX=b,xj≥0}={X∣,xj≥0}是凸集。凸集性质:设x(1)≠x(2)为D内任取两点，则Ax(1)=b,Ax(2)=b,x(1)≥0,x(2)≥0,令x为线段x(1),x(2)上任一点,即有x=μx(1)+(1-μ)x(2)(0≤μ≤1)则Ax=A[μx(1)+(1-μ)x(2)](0≤μ≤1)=μAx(1)+Ax(2)-μAx(2)=μb+b–μb=b

又因为x(1)

≥0,x(2)≥0,0≤μ≤1

所以x≥0即x∈D证毕证明：线性规划

maxz=CXs.t.AX=bX≥0

引理1.线性规划问题的可行解X为基可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的.证明:

必要性：已知X为线性规划的基可行解，要证X的正分量所对应的系数列向量线性独立。因为X还是可行解，所以其非零分量全为正；又因为X为基本解，由定义，其非零分量所对应的系数列向量线性独立。充分性：已知可行解X的正分量所对应的系数列向量线性独立，欲证X是线性规划的基可行解。

X正分量对应的系数向量P1,P2,…,Pk线性独立,则必有k≤m；当k=m时，它们恰构成一个基，从而X=（x1，x2,…,xk，0…0）为相应的基可行解。k<m时，则一定可以从其余的系数列向量中取出m-k个与P1,P2,…,Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解。

定理2：X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。）证明：不失一般性，假设基可行解X的前m个分量为正。故

充分性（顶点基可行解，用反证法）：由引理1，若X不是基可行解，则其正分量所对应的系数列向量P1,P2,…,Pm线性相关,即存在一组不全为零的数αi,i=1,2,…,m（1）令X(1)=[(x1-μα1),(x2-μα2),…,(xm-μαm),0,…,0]X(2)=[(x1+μα1),(x2+μα2),…,(xm+μαm),0,…,0]当μ充分小时,可保证xi±μαi≥0i=1,2,…,m,即X(1),X(2)是可行解。由X(1),X(2)

可以得到X=,即X是X(1),X(2)连线的中心。所以X不是可行域D的顶点.使得

α1P1+α2P2+…+αmPm=0