科学出版社《运筹学》教材
第一章引言
第二章线性规划，姜林
第三章对偶规划，姜林
第四章运输问题，姜林
第五章整数规划，姜林
第六章非线性规划，姜林
第七章动态规划，姜林
第八章多目标规划，姜林
第九章图与网络分析，熊贵武
第十章排队论，熊贵武
第十一章库存论，王勇
第十二章完全信息博弈，王勇
第十三章不完全信息博弈，王勇
第十四章决策论与影响图
第十五章运筹学模型的计算机求解
成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问
如何选择食品才能在满足营养的前提下使购买食品的费用最小？
食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14
鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2
营养需求量
2000
55
800
解：设需猪肉、鸡蛋、大米和白菜各需
x1,x2,x3,x4斤。则热量的需求量为：
2000
20090080010004
3
2
1
x x x x 蛋白质
某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原
料长12.3米，问应如何下料使需用的原材料最省。
解：假设从每根
12.3米的原材料上截取 3.5米、2.8米和2根2.4
米，则每根原材料需浪费 1.2米，做100套需浪费材料
120米，现
采用套裁的方法。
方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0
2 0 2
2 1 1
合计剩余
12
0.3 11.2
1.1
11.5 0.8
11.9 0.4
11.8 0.5
12.2 0.1
现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程：
minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6
约束条件：
x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200
,,,800
50030020040055
102060503000
2009008001000.
.23614min 4
3214
3
2
1
4
32
14
32
14321x x x x x x x x x x x x x x x x t s x x x x z
单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z
j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。
科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
单纯形法例题 1、例1、目标函数max z=2 * +3 禹+ 2x2 W 8' 4xi W 16 4x2 W 12 k Ki,财鼻0』 解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量, ；汁Hi吃：弋"審得到的标准形式为： max z=2~ +3-+ 0 勺+g +O 5 'xt + 2xj + x] = 8 1 4?i X4 =16 4x；+ 巧=12 11 巾弓^3j 乂4, ^5 $ ? 2 3 0 0 0 C R b *4 0 8 1 2 1 0 0 4 0 16 4 0 0 1 0 - 0 ◎12 0[E(|00 1 3 k - z) 2 3 0 0 0 引」一弋木日lk(i才I) 熙=') (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值, 否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后 的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2 ,故填入值应该为2。而「 则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然 后用b的值除以该换入变量所在的列的所有值，得到 约束条件:
由于在检验数中仍然存在大于等于的数，而且, 的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1,换入变量为|勒，换出 由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代（换入变 此时可以发现检验数中没有大于的数，表明已经得到了最优解，所以最优解是: (4,2,0,0,4 )，故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根,
例1 max z=2x1+3x2 （标准形式即所有的变量均为负、所有约束条件为等式、所有的右端项系数非负） a=(2,3) b1=(80,160,120) A2=NULL b2=NULL A3=NULL b3=NULL n.iter=n+2*m maxi=TRUE ● simplex(a=a,A1=A1,b1=b1,maxi=TRUE)： m1=3,m2=0,m3=0 m=3,n=2 a.o=a=(2,3) if(maxi) a=-a(-2,-3) if(m2+m3==0) a=(-2,-3,0,0,0) b=(80,160,120) init=(0,0,0,80,160,120) basic=(3,4,5) eps=1e -10 out1<-simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps) ? simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps): N=5,M=3 nonbasic=(1,2) if(stage==2) obfun=(-2,-3) it=1 ◆ while(!all(obfun > -eps) && (it <= n.iter))循环 pcol=3 if(stage==2) neg=(1,3) x1+2x2<=80 4x1<=160 4x2<=120 x1，x2>=0 A1= 1 2 4 0 0 4 A= 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 tableau= 80 -1 -2 160 -4 0 120 0 -4 tableau= 80 -1 -2 160 -4 0 120 0 -4 0 -2 -3 转化为标准形式 x1+2x2+x3=80 4x1+x4=160 4x2+x5=120 x1,x2,x3,x4,x5>=0
单纯形法例题 1、例1、目标函数 max z=2+3 约束条件： 解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量， .得到的标准形式为： max z=2+3+ 0+0+0 然后要将其初始的单纯形表画出来： 23000 b 08121004 01640010- 01200013 23000 由初始单纯形表可以看出，为换入变量，而为换出变量；然后根据：= (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到列的值。 23000 b 02010-1/22 016400104 3301001/4- 2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为，换出变量为，故得到的单纯形表如下：
23000 b 221010-1/2- 0800-414 3301001/412 00-201/4由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变 23000 b 241001/40 0400-21/21 32011/2-1/80 00-3/2-1/80 （4,2,0,0,4），故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根， 已知原料长，问应如何下料，使用的原材料最省； 解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要长的钢100根，的钢100根，的钢100根。而一份原料长度是， 长度/m 下料根数 截取方案 12345 112 212 3132所用长度 剩余长度0 方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来： 目标函数：min z=+++ 约束条件 首先可以写出线性方程组的矩阵形式：发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：，那么线性方程组可以
单纯形法例题讲解
基可行解 单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。 min cx f = （1） s.t b Ax = （2） 0≥x （3） 其中 T m mn m m n n T n n b b b b a a a a a a a a a A x x x x c c c c )...,(,............ ... ..., ),...,,(),,...,(212 1 22221112 112121=??? ???????????=== 假设1≥≥m n ，并设系数矩阵A 的秩为m ，即 设约束方程（2）中没有多余的方程，用j p 表示A 的第j 列，于是（2可写成 b p x m k j j =∑=1 （4） 矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若 ),...,(21jm j j p p p B = （5）
是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为 b p x m k jk jk =∑=1 （6） 由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为T jn j j x x x ) ,...,,()0() 0(2) 0(1于是按分量 {}{}),...,,\,...2,1(0) ,....3,2,1(21) 0(m j jk jk j j j n j x m k x x ∈=== 所构成的向量) 0(x 是约束方程组b Ax =的一个 解，称此)0(x 为LP 的对应于基B 的基解 （或基本解），也可称为方程组b Ax =的一个基解，如果) 0(x 为一基解，且满足 0)0(≥x 即它的所有分量都非负，则称此) 0(x 是LP 的一个基可行解，基可行解对应的基 称为可行基。
单纯形法的解题步骤
三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定
（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出