运筹学习题集

判断题判断正误，如果错误请更正第五章运输与指派问题1.运输问题中用位势法求得的检验数不唯一。

2.产地数为3，销地数围的平衡运输中，变量组｛X11，X13，X22，X33，X34｝可作为一组基变量。

3.不平衡运输问题不一定有最优解。

4.m+n-1个变量构成基变量组的充要条件是它们不包含闭合回路。

5.运输问题中的位势就是其对偶变量。

6.含有孤立点的变量组不包含有闭回路。

7.不包含任何闭回路的变量组必有孤立点。

8.产地个数为m销地个数为 n的平衡运输问题的对偶问题有m+n个约束。

9.运输问题的检验数就是对偶问题的松弛变量的值。

10.产地个数为m销地个数为 n的平衡运输问题的系数矩阵为A，则有r(A)〈=m+n-1。

11.用一个常数k加到运价C的某列的所有元素上，则最优解不变。

12.令虚设的产地或销地对应的运价为一任意大于0的常数C（C>0），则最优解不变。

13.若运输问题中的产量或销量为整数则其最优解也一定为整数。

14.运输问题中的单位运价表的每一行都分别乘以一个非0常数，则最优解不变。

15.按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。

16.在指派问题的效率表的某行乘以一个大于零的数最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第五章运输与指派问题1.下列变量组是一个闭回路的有A{x21,x11,x12,x32,x33,x23} B{x11,x12,x23,x34,x41,x13} C {x21,x13,x34,x41,x12} D{x12,x32,x33,x23,x21,x11} D{x12,x22,x32,x33,x23,x21}2.具有M个产地N个销地的平衡运输问题模型具有特征A有MN个变量M+N个约束B有M+N个变量MN个约束C 有MN个变量M+N-1个约束D 有M+N-1个基变量MN-M-N+1个非基变量E 系数矩阵的秩等于M+N-13.下列说法正确的有A 运输问题的运价表第r行的每个cij 同时加上一个非0常数k，其最优调运方案不变。

判断题判断正误，如果错误请更正第五章运输与指派问题1.运输问题中用位势法求得的检验数不唯一。

2.产地数为3，销地数围的平衡运输中，变量组｛X11，X13，X22，X33，X34｝可作为一组基变量。

3.不平衡运输问题不一定有最优解。

4.m+n-1个变量构成基变量组的充要条件是它们不包含闭合回路。

5.运输问题中的位势就是其对偶变量。

6.含有孤立点的变量组不包含有闭回路。

7.不包含任何闭回路的变量组必有孤立点。

8.产地个数为m销地个数为n的平衡运输问题的对偶问题有m+n个约束。

9.运输问题的检验数就是对偶问题的松弛变量的值。

10.产地个数为m销地个数为n的平衡运输问题的系数矩阵为A，则有r(A)〈=m+n-1。

11.用一个常数k加到运价C的某列的所有元素上，则最优解不变。

12.令虚设的产地或销地对应的运价为一任意大于0的常数C（C>0），则最优解不变。

13.若运输问题中的产量或销量为整数则其最优解也一定为整数。

14.运输问题中的单位运价表的每一行都分别乘以一个非0常数，则最优解不变。

15.按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。

16.在指派问题的效率表的某行乘以一个大于零的数最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第五章运输与指派问题1.下列变量组是一个闭回路的有A{x21,x11,x12,x32,x33,x23} B {x11,x12,x23,x34,x41,x13}C {x21,x13,x34,x41,x12} D{x12,x32,x33,x23,x21,x11} D{x12,x22,x32,x33,x23,x21}2.具有M个产地N个销地的平衡运输问题模型具有特征A有MN个变量M+N个约束B有M+N个变量MN个约束 C 有MN个变量M+N-1个约束 D 有M+N-1个基变量MN-M-N+1个非基变量E 系数矩阵的秩等于M+N-13.下列说法正确的有A 运输问题的运价表第r行的每个cij 同时加上一个非0常数k，其最优调运方案不变。

判断题判断正误，如果错误请更正第二章线形规划的对偶理论1.原问题第i个约束是<=约束,则对偶变量yi>=0.2.互为对偶问题,或则同时都有最优解,或则同时都无最优解.3.原问题有多重解,对偶问题也有多重解.4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.5.原问题无最优解,则对偶问题无可行解.6.设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝和｛maxw=Yb｜YA<=C,Y>=0｝的可行解,则有(1)CX<=Yb;(2)CX是w的上界;(3)当X,Y为最优解,CX=Yb;(4)当CX=Yb 时,有YXs+YsX=0;(5)X为最优解且B是最优基时,则Y=C B B-1是最优解;(6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优解.7.原问题与对偶问题都可行,则都有最优解.8.原问题具有无界解,则对偶问题可行.9.若X,Y是原问题与对偶问题的最优解.则X=Y.10.若某种资源影子价格为0,则该资源一定有剩余.11影子价格就是资源的价格.12.原问题可行对偶问题不可行,可用对偶单纯形法计算.13.对偶单纯形法比值失效说明原问题具有无界解.14.对偶单纯形法是直接解对偶问题的一种解法.15.减少一个约束,目标值不会比原来变差.16.增加一个约束,目标值不会比原来变好.17增加一个变量, 目标值不会比原来变差.18.减少一个非基变量, 目标值不变.19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第二章线性规划的对偶理论1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划A约束条件相同B目标函数相同C最优目标函数值相同D以上结论都不对2.对偶单纯形法的最小比值规则是为了保证A使原问题保持可行B使对偶问题保持可行C逐步消除原问题不可行性D逐步消除对偶问题不可行性3.互为对偶的两个线性规划问题的解存在关系A若最优解存在，则最优解相同B原问题无可行解，则对偶问题也无可行解C对偶问题无可行解，原问题可能无可行解D一个问题无界，则另一个问题无可行解E一个问题无可行解，则另一个问题具有无界解4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为A—（λ1，λ2，……λn）B （λ1，λ2，……λn）C —（λn+1,λn+2,……λn+m）D（λn+1,λn+2,……λn+m）5.原问题与对偶问题都有可行解，则A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解计算题线性规划问题和对偶问题2.1 对于如下的线性规划问题min z = 3x1 + 2x2 +x3s.t. x1+ x2+ x3 ≤15 (1)2x1- x2+ x3≥9 (2)-x1+ 2x2+2x3≤8 (3)x1x2x3 ≥01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3s.t. y1+ 2y2- y3 ≤ 3 (1)y1- y2+ 2y3≤ 2 (2)y1+ y2+ 2y3≤ 1 (3)y1≤0、y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3s.t. x1+ x2+ x3 + x4 = 15 (1)-2x1+ x2- x3+ x5= -9 (2)-x1+ 2x2+2x3+x6 = 8 (3)原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11 2.2 对于以下线性规划问题max z = -x1 - 2x2s.t. -2x1 + 3x2≤12 (1)-3x1 + x2≤ 6 (2)x1 + 3x2≥ 3 (3)x1≤0，x2≥01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。

表3-3
销地
产地
1
2
3
产量
1
5
1
8
12
2
2
4
1
14
3
3
6
7
4
销量
9
10
11
表3-4
销地
产地
1
2
3
4
5
产量
1
10
2
3
15
9
25
2
5
20
15
2
4
30
3
15
5
14
7
15
20
4
20
15
13
M
8
30
销量
20
20
30
10
25
解：
（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到：
+ = + +
+ =
建立数学模型：
Max z=(1.25-0.25)*( + )+(2-0.35)*( + )+(2.8-0.5) -(5 +10 )300/6000-(7 +9 +12 )321/10000-(6 +8 )250/4000-(4 +11 )783/7000-7 *200/4000
s.t
2.确定 的范围,使最优解不变;取 ,求最优解;
3.确定 的范围,使最优基不变,取 求最优解;
4.引入 求最优解;
解1.由单纯形方法得
即,原问题的最优解为
例求下面运输问题的最小值解：
1

二、填空选择题：（每空格2分，共16分）1、线性规划的解有划的唯一最优解、无穷多最优解、无界解和无可行解四种。

2、在求运费最少的调度划的运划的输问题中，如划的果某划的一非基变量的检验数为4，则说明如果在该空格中增加一个运量运费将增加划的4 。

3、“如果线性规划的原问题存在可行解，则其对划的偶问题一定存在可行解”，这句话对还是划的错？错4、如果某一整数规划：MaxZ=X划的1+X2划的X1+9/1划的2≤1/3X1,X2≥0且均为整数所对应的线性规划（松弛问题）的最优划的解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在划的要对X1进行分枝，划的应该分为X1≤1和X1≥2。

5、在用逆向解法求动态规划时，f k(s k)的含义是：从第k个阶段到第n个阶段的最优解。

6.假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D 和B的关系为 D 包含 B7.已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条问：（1）写出B-1=⎪⎪⎪⎭⎫⎝⎛---13/20.3/1312(2)对偶问题的最优解： Y＝（5，0，23，0，0）T8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________；10. 若整数规划的松驰问题的最优解不符合整数要求，假设Xi =bi不符合整数要求，INT（bi ）是不超过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1 和 Xi≤INT（bi），分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。

11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛611401102二、计算题（60分）1、已知线性规划（20分）MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤81,X 2≥02）若C 2从4变成5，最优解是否会发生改变，为什么？3）若b 2的量从12上升到15，最优解是否会发生变化，为什么？4）如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产？为什么？ 解：1)对偶问题为Minw=5y1+12y2+8y3 y1+2y2+3y 3≥3y1+4y2+2y 3≥4 y1,y2≥02)当C 2从4变成5时， σ4=-9/8 σ5=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。

运筹学习题集（第一章）判断题判断正误，如果错误请更正第1章线性规划1.任何线形规划一定有最优解。

2.若线形规划有最优解，则一定有基本最优解。

3.线形规划可行域无界，则具有无界解。

4.在基本可行解中非基变量一定为0。

5.检验数λj表示非基变量Xj增加一个单位时目标函数值的改变量。

6.minZ=6X1+4X2｜X1-2X｜︳<=10 是一个线形规划模型X1+X2=100X1>=0,X2>=07.可行解集非空时,则在极点上至少有一点达到最优解.8.任何线形规划都可以化为下列标准型Min Z=∑C j X j∑a ij x j=b1, i=1,2,3……，mX j>=0,j=1,2,3,……，n:b i>=0,i=1,2,3,……m9.基本解对应的基是可行基.10.任何线形规划总可用大M 单纯形法求解.11.任何线形规划总可用两阶段单纯形法求解。

12.若线形规划存在两个不同的最优解，则必有无穷多个最优解。

13.两阶段中第一阶段问题必有最优解。

14.两阶段法中第一阶段问题最优解中基变量全部非人工变量，则原问题有最优解。

15.人工变量一旦出基就不会再进基。

16.普通单纯形法比值规则失效说明问题无界。

17.最小比值规则是保证从一个可行基得到另一个可行基。

18.将检验数表示为λ=C B B-1A-的形式，则求极大值问题时基本可行解是最优解的充要条件为λ》=0。

19.若矩阵B为一可行基，则｜B｜≠0。

20.当最优解中存在为0的基变量时，则线形规划具有多重最优解。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第1章线性规划1.线形规划具有无界解是指：A可行解集合无界B有相同的最小比值C存在某个检验数λk>0且a ik<=0（i=1，2，3，……，m） D 最优表中所有非基变量的检验数非0。

2.线形规划具有多重最优解是指：A 目标函数系数与某约束系数对应成比例B最优表中存在非基变量的检验数为0 C 可行解集合无界 D 存在基变量等于03. 使函数Z=-X1+X2-4X3增加的最快的方向是：A （-1，1，-4）B （-1，-1，-4）C （1，1，4）D （1，-1，-4-）4. 当线形规划的可行解集合非空时一定A 包含原点X=（0，0，0……） B 有界C 无界D 是凸集5. 线形规划的退化基本可行解是指 A 基本可行解中存在为0的基变量 B 非基变量为C非基变量的检验数为0 D 最小比值为06. 线形规划无可行解是指 A 进基列系数非正 B 有两个相同的最小比值 C 第一阶段目标函数值大于0 D 用大M 法求解时最优解中含有非0的人工变量 E可行域无界7. 若线性规划存在可行基，则 A 一定有最优解 B 一定有可行解 C 可能无可行解 D 可能具有无界解 E 全部约束是〈=的形式8. 线性规划可行域的顶点是 A 可行解 B 非基本解 C 基本可行解 D 最优解 E 基本解9. minZ=X1-2X2，-X1+2X2〈=5，2X1+X2〈=8，X1，X2〉=0，则 A 有惟一最优解 B 有多重最优解 C 有无界解 D 无可行解 E 存在最优解10.线性规划的约束条件为 X1+X2+X3=32X1+2X2+X4=4X1，X2，X3，X4〉=0 则基本可行解是 A （0，0，4，3）B （0，0，3，4）C （3，4，0，0）D （3，0，0，-2）计算题1.1 对于如下的线性规划问题MinZ= X 1+2X 2s.t. X 1+ X 2≤4-X 1+ X 2≥1X 2≤3X 1, X 2≥0的图解如图所示。

4x1＋6x2≥－12 2x1＋2x2≥4
2x2≥4 x1, x2≥0
x1, x2≥0
(5) max z ＝3x1＋9x2 (6) max z ＝3x1＋4x2
st. x1＋3x2≤22 st. －x1＋2x2≤8
1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。
问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线性规划的数学模型。
甲 乙 丙 原料成本(元/千克) 每月限量（千克）
x1，x3≥0，x2，x4无约束
(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3
st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15
x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20
5
6 8 7
3 5
1.9. 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：
班 次 时 间 所需人数
1 6:00-10:00 60
2 10:00-14:00 70
3 14:00-18:00 60
4 18:00-22:00 50
5 22:00-2:00 20
6 2:00-6:00 30
st. 8x1＋6x2≥24 st. x1＋2x2＋3x3＝15
4x1＋6x2≥－12 2x1＋ x2＋5x3＝20
2x2≥4 x1＋2x2＋ x3＋ x4＝10
x1, x2≥0 xj ≥0 （j＝1,…,4）

判断题判断正误，如果错误请更正第四章目标规划1.正偏差变量大于等于0，负偏差变量小于等于0。

2.系统约束中最多含有一个正或负的偏差变量。

3.目标约束一定是等式约束。

4.一对正负偏差变量至少一个大于0。

5.一对正负偏差变量至少一个等于0。

6.要求至少到达目标值的目标函数是maxZ=d+。

7.要求不超过目标值的目标函数是minZ=d+。

8.目标规划没有系统约束时，不一定存在满意解。

9.超过目标的差值称为正偏差。

10.未达到目标的差值称为负偏差。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第四章目标规划1.要求不超过第一目标值，恰好完成第二目标值，目标函数是A minZ=P1d1-+P2(d2-+d2+)B minZ= P1d1++P2(d2-+d2+)C minZ=P1(d1-+d1+)+P2(d2-+d2-)D minZ=P1(d1-+d1+)+ P2d2-2.下列正确的目标规划的目标函数是 A minZ=P1d1-- P2d2- B maxZ= P1d1-+P2d2- CminZ=P1d1--+P2(d2--d2+) D minZ=P1(d1-+d1+)+P2(d2-+d2-) E minZ=P1d1- +P2d2+3.下列线性规划与目标规划之间正确的关系是A线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成 B 线性规划模型不包含目标约束，目标规划模型不包含系统约束C线性规划求最优解，目标规划求满意解。

D 线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束 E 线性规划求最大值和最小值，目标规划只求最小值4.目标函数minZ= P1(d1-+d2-)+ P2d3- 的含义是A第一和第二目标恰好达到目标值，第三目标不超过目标值。

B第一、第二和第三目标同时不超过目标值。

C首先第一和第二同时不超过目标值，然后第三目标不超过目标值。

《运筹学》习题集目录第一章线性规划 (1)第二章运输问题 (9)第三章整数规划 (14)第四章目标规划 (20)第五章动态规划 (21)第六章图与网络分析 (24)第七章存储论 (27)第八章对策论 (28)第一章 线性规划1、将下列线性规划问题化为标准型(1) max Z = 3x 1+ 5x 2- 4x 3+ 2x 4⎪⎪⎩⎪⎪⎨⎧≥=+≥+≤++0x , x , x 9 5x -3x -4x x -13 2x -2x 3x -x 18 3x x -6x 2x s.t.421432143214321 (2) min f = 3x1+ x2+ 4x3+ 2x4 ≤ 1⎪⎪⎩⎪⎪⎨⎧≤≥=++≥+≤+0 x 0, x , x15 2x 3x -4x 2x 7- x -2x 2x -3x 51- 2x - x -3x 2x s.t. 4214214321 43213 (3) min F=x1+x2+x3+x4⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+≥+0x ,x ,x ,x 7x x 8x x 6x x 5x x s.t.432143222141 (4) 3213min x x x F -+=⎪⎪⎩⎪⎪⎨⎧≤≤≥≥0x ,x ,x 4x +5x +x -22x +x -3x +x +x ..32132121321t s 2、求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：⎪⎩⎪⎨⎧≥≥++≥++0 x ,x ,x 12 4x 3x 2x -6 3x 3x 2x 321321321３、用图解法求解下列线性规划问题⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+=0x ,x 3 x 122x +3x 6 x -2x ..max )1(211212121t s X X Z⎪⎩⎪⎨⎧≥≥≥++-=0 x ,x 155x -3x 56 7x 4x ..3min )2(21212121t s x x Z４、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。

运筹学期末复习题一、判断题：1、任何线性规划一定有最优解。

（）2、若线性规划有最优解，则一定有基本最优解。

（）3、线性规划可行域无界，则具有无界解。

（）4、基本解对应的基是可行基。

（）5、在基本可行解中非基变量一定为零。

（）6、变量取0或1的规划是整数规划。

（）7、运输问题中应用位势法求得的检验数不唯一。

（）8、产地数为3，销地数为4的平衡运输中，变量组{X11，X13，X22，X33，X34}可作为一组基变量。

（）9、不平衡运输问题不一定有最优解。

（）10、m+n-1个变量构成基变量组的充要条件是它们不包含闭回路。

（）11、含有孤立点的变量组不包含有闭回路。

（）12、不包含任何闭回路的变量组必有孤立点。

（）13、产地个数为m销地个数为n的平衡运输问题的系数距阵为A，则有r(A)≤m+n-1（）14、用一个常数k加到运价矩阵C的某列的所有元素上,则最优解不变。

（）15、匈牙利法是求解最小值分配问题的一种方法。

（）16、连通图G的部分树是取图G的点和G的所有边组成的树。

（）17、求最小树可用破圈法。

（）18、Dijkstra算法要求边的长度非负。

（）19、Floyd算法要求边的长度非负。

（）20、在最短路问题中，发点到收点的最短路长是唯一的。

（）21、连通图一定有支撑树。

（）22、网络计划中的总工期等于各工序时间之和。

（）23、网络计划中，总时差为0的工序称为关键工序。

（）24、在网络图中，关键路线一定存在。

（）25、紧前工序是前道工序。

（）26、后续工序是紧后工序。

（）27、虚工序是虚设的,不需要时间,费用和资源,并不表示任何关系的工序。

（）28、动态规划是求解多阶段决策问题的一种思路，同时是一种算法。

（）29、求最短路径的结果是唯一的。

（）30、在不确定型决策中，最小机会损失准则比等可能性则保守性更强。

（）31、决策树比决策矩阵更适于描述序列决策过程。

（）32、在股票市场中，有的股东赚钱，有的股东赔钱，则赚钱的总金额与赔钱的总金额相等，因此称这一现象为零和现象。

运筹学复习题1. 某一求目标函数极大值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下：当现行解为唯一最优解时有 。

A. ª1≥0 a 5＞0 a 3＞0B. a 3≥0 a 5＝0 a 6＝0C. ª2＝0 a 5≥0 a 6≥0D. a 1≥0 a 6＜0 a 5＜0 答案：（ ）2. 单纯形乘子是指 。

A ．1-BC B B.b B C B 1- C.A B C B 1- D.b B C C 1B -- 答案：（ ）3．在满足下列条件 时，增加资源是有利的。

A ．单位资源代价大于资源的影子价格 B ．单位资源代价小于资源的影子价格 C ．单位资源代价等于资源的影子价格D ．单位资源代价不等于资源的影子价格 答案：（ ）4．线性规划的灵敏度分析应在⎽⎽⎽⎽⎽⎽的基础上，分析系数的变化对最优解产生的影响。

A ．初始单纯形表 B. 最优单纯形表 C. 对偶问题初始单纯形表 D. 对偶问题的最优单纯形表 答案：（ ）5．一个图G 中,奇点的个数为 。

A.偶奇数 B.偶数 C.奇数或偶数 D. 不能确定 答案：（ ）6．若运输问题已求得最优解，此时所求出的检验数一定是全部 。

A ．大于或等于零B ．大于零C ．小于零D ．小于或等于零 答案：（ ）7. 线性规划一般模型中，自由变量可以用两个非负变量的 代换。

A ．和 B ．差 C ．积 D ．商 答案：( )8．目标规划中，对于优先级别，则下列说法正确的是 。

A ．P k ×P k+1=0B ．P k <<P k+1C ．P k >>P k+1D ．P k =P k+1 答案：（ ）9．求解指派问题的匈牙利方法要求系数矩阵中每个元素都是 。

A ．非负的B ．大于零C ．无约束D ．非零常数 答案：（ ）10．若运输网络G 中发点到收点不存在流f 的增广链，则称流f 为G 的 。

A ．最小流 B ．零流 C ．最大流 D ．无法确定 答案：（ ）11.运输问题中，闭合回路的数字格分布在每行每列的个数必定为 。

运筹学习题集1. 线性规划1.1. 案例题题目：一家制造公司生产甲、乙两种产品。

每个产品需要经过两个部门加工再次合并，最后得到最终产品。

已知甲产品在第一个部门加工1个小时，乙产品在第一个部门加工1.5个小时。

合并的时间都是0.5小时。

在每个部门的加工之前都需要准备工作，分别需要0.2小时和0.3小时。

总共有16小时的加工时间，10小时的准备时间。

如果甲产品的利润是每个单位产品1000元，乙产品的利润是每个单位产品1500元，如何制定生产计划以最大化利润？解答：首先，我们可以定义两个变量，x和x，分别表示生产甲和乙产品的数量。

问题可以用以下线性规划模型来描述：最大化x=1000x+1500x约束条件：•$x \\geq 0$•$y \\geq 0$•$1x + 1.5y \\leq 16$•$0.2x + 0.3y \\leq 10$根据以上模型，我们可以使用线性规划求解器来求解最优解。

对于这个问题，最优解为x=6.4，x=5.6，利润最大化为x=21,400元。

1.2. 理论题题目：什么是线性规划？线性规划的应用领域有哪些？解答：线性规划是一种数学优化方法，用于求解满足一定约束条件下的线性目标函数的最优解。

线性规划的目标函数和约束条件都是线性的。

线性规划的应用领域非常广泛，包括但不限于以下几个方面：•生产计划：优化生产计划，最大化产量或利润。

•供应链管理：优化物流和运输成本，最小化供应链成本。

•资源分配：优化资源利用，最大化效益。

•资产配置：优化投资组合，最大化收益或降低风险。

•运输问题：优化货物运输路径和调度，最小化运输成本。

2. 排队论2.1. 案例题题目：一个餐厅有一个服务员负责接待顾客并安排座位。

顾客到达的时间服从指数分布，平均每10分钟有一位顾客到达。

一个顾客在餐厅用餐的时间服从正态分布，平均时间为30分钟，标准差为10分钟。

如果一个顾客到达后没有空位可坐，则该顾客将离开。

请问该餐厅的平均顾客等待时间是多少？解答：根据排队论的基本原理，我们可以使用M/M/1排队模型来解决这个问题。

运筹学习题库一、线性规划1．某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。

工厂每天可利用的工时为12个，可供应的原材料为15公斤。

1）试确定使总利润为最大的日生产计划和最大利润。

2）若由于原材料涨价，使得产品丙的单位利润比原来减少了2元，问原来的最优生产计划变否？若不变，说明为什么；若变，请求出新的最优生产计划和最优利润。

3）在保持现行最优基不变的情况下，若要增加一种资源量，应首先考虑增加哪种资源？为什么？单位资源增量所支付的费用是多少才合算？为什么？2．给出一线性规划问题如下：max z = 3x1 + x2x1 + x2≤4－x1 + x2≤26x1 + 2x2≤18x１，x2≥0试用对偶理论判断该问题是否存在以x１、x2和x3为基变量的最优解？3．用单纯形法求解某个目标函数为max，约束为≤形式，x4、x5为松弛变量的线性规划问题的最终表如下：试用改进单纯形法原理求该问题的数学模型。

4．给出一个线性规划问题如下：max z = x1 +2 x2 +3 x3x1 + 2x2 + 3x3≤84x1+ 5x3≤12x1，x2 ，x3 ≥0已知其对偶问题的最优解为Y* = (1，0 )，试用对偶理论求上述问题的最优解和最优值。

5．试用大M法求下述线性规划问题的最优解和最优值（不能用图解法）：max z = 3x 1 – 3 x 2x1 + x2 ≥1 2x 1 + 3x 2 ≤6x 1，x 2 ≥06．已知一线性规划问题如下：max z = 5x 1 + 2 x 2 + 4 x 3 3 x 1 + x 2 + 2 x 3 ≤ 46 x 1 + 3 x 2 + 5 x 3 ≤ 10 x 1，x 2，x 3 ≥ 0试用松紧定理判断X = ( 0，0，2 )T 是否是该问题的最优解，若不是，说明为什么；若是， 请求出相应的目标函数值。

12、已知线性规划123123123max 3421022160,1,2,3jz x x x x x x x x x x j =++⎧++≤⎪++≤⎨⎪≥=⎩ 的最优解为*(6,2,0)T X =，试利用互补松弛定理，求对偶问题的最优解。

解：原问题的对偶问题为：1212121212min 1016232241,0w y y y y y y y y y y =++≥⎧⎪+≥⎪⎨+≥⎪⎪≥⎩將*(6,2,0)T X =代入原问题的约束条件，可得：*1*262*210 02*62*216 0y y ⎧+=⇒≥⎪⎨+=⇒≥⎪⎩ （1） 又由***112***212***1120 230 2240 1x y y x y y x y y ⎧>⇒+=⎪>⇒+=⎨⎪=⇒+≥⎩ （2） 将结论（1）和（2）结合起来，可解得**121y y ==。

13、已知线性规划问题12341341234max 25628..222120, 1,2,3,4jz x x x x x x x s t x x x x x j =+++⎧++≤⎪+++≤⎨⎪≥=⎩ 其对偶问题的最优解为*14y =、*21y =，试用对偶理论求解原问题的最优解。

解：原问题的对偶问题为：12122121212min 81222221..526,0w y y y y y s t y y y y y y =++≥⎧⎪≥⎪⎪+≥⎨⎪+≥⎪⎪≥⎩ 将对偶问题的最优解代入约束条件，可得：*1*2*3*42*42*1 2 02*4 1 041 5 042*1 6 0x x x x ⎧+>⇒=⎪>⇒=⎪⎨+=⇒≥⎪⎪+=⇒≥⎩（1）又由****1134*****212340 280 22212y x x x y x x x x ⎧>⇒++⎪⎨>⇒+++⎪⎩ ＝＝（2） 将结论（1）和（2）结合起来，可得：**34**348212x x x x ⎧+⎪⎨+⎪⎩＝＝，解得 *3*444x x ⎧=⎪⎨=⎪⎩ 即原问题的最优解为*(0,0,4,4)T X =。

数学建模1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而解：设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有线性规划模型如下：max f (x )=(168-42)x 1 +(140-28)x 2 +(1050-350)x 3 +(406-140)x 4=126 x 1 +112 x 2 +700 x 3 +266 x 4s.t. ⎪⎩⎪⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。

两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。

从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。

环保要求河流中工业污水含量不能大于0.2%。

两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。

现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。

列出线性规划模型。

解：设x 1、2标可描述为min z =1000x 1+800x 2 x 1 ≥10.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥03、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。

为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）127星期日开始上班的人数。

min x 1+x 2+x 3+x 4+x 5+x 6+x 7x 3+x 4+x 5+x 6+x 7≥28 x 4+x 5+x 6+x 7+x 1≥15 x 5+x 6+x 7+x 1+x 2≥24 x 6+x 7+x 1+x 2+x 3≥25 x 7+x 1+x 2+x 3+ x 4≥19 x 1+x 2+x 3+x 4+x 5≥31 x 2+x 3+x 4+x 5+x 6≥28x 1、x 2、x 3、x 4、x 5、x 6、x 7≥04、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的i ⎩⎨⎧=i ii x x x 不携带物品携带物品01 （i ＝1，…，7） 则0－1规划模型为：max z ＝20x 1＋15x 2＋16x 3＋14x 4＋8x 5＋14x 6＋9x 7 s.t. 5x 1＋5x 2＋2x 3＋5x 4＋10x 5＋2x 6＋3x 7≤25x i ＝0或1，i ＝1，0，…，7标准化问题1、将下列线性规划化为标准形式⎪⎪⎩⎪⎪⎨⎧±≤≥≤-+=+--≥-++-=不限321321321321321 ,0 ,019|1210|15736 10 ..235)(min x x x x x x x x x x x x t s x x x x f ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥''''≤+''-'+'+-≤+''+'-'-=''-'+'+≤+''-'+'+-''+-'--=-0,,,,,,191210191210157736 10 ..2'235)](max[654332163321533213321433213321x x x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x f 2、化下列线性规划为标准形 ma x z =2x 1+2x 2－4x 3 x 1 + 3x 2－3x 3 ≥30 x 1 + 2x 2－4x 3≤80 x 1、x 2≥0，x 3无限制解：按照上述方法处理，得该线性规划问题的标准形为 ma x z =2x 1+2x 2－4x 31+4x 32x 1 + 3x 2－3x 31 + 3x 32－x 4 = 30 x 1 + 2x 2－4x 31 + 4x 32 + x 5 = 80 x 1、x 2，x 31，x 32，x 4，x 5 ≥0图解法1、用图解法求解下面线性规划。