《运筹学》清华大学出版社 复习资料及练习题

《运筹学试题与答案》一、判断题：在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“T”，错误者写“F”。

1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。

( )2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j≤0，则问题达到最优。

( )3. 若线性规划的可行域非空有界，则其顶点中必存在最优解。

( )4. 满足线性规划问题所有约束条件的解称为可行解。

( )5. 在线性规划问题的求解过程中，基变量和非机变量的个数是固定的。

( )6. 对偶问题的对偶是原问题。

( )7. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。

( )8. 运输问题的可行解中基变量的个数不一定遵循m＋n－1的规则。

( )9. 指派问题的解中基变量的个数为m＋n。

( )10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。

( )11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。

( )12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。

( )13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。

( )14. 单目标决策时，用不同方法确定的最佳方案往往是不一致的。

( )15. 动态规则中运用图解法的顺推方法和网络最短路径的标号法上是一致的。

( )二、单项选择题1、对于线性规划问题标准型：maxZ=CX, AX=b, X≥0, 利用单纯形法求解时，每作一次迭代，都能保证它相应的目标函数值Z必为（）。

A. 增大B. 不减少C. 减少D. 不增大2、若线性规划问题的最优解不唯一，则在最优单纯形表上（）。

A. 非基变量的检验数都为零B. 非基变量检验数必有为零C. 非基变量检验数不必有为零者D. 非基变量的检验数都小于零3、线性规划问题的数学模型由目标函数、约束条件和（）三个部分组成。

A. 非负条件B. 顶点集合C. 最优解D. 决策变量4、已知x1= ( 2, 4), x2=(4, 8)是某线性规划问题的两个最优解，则（）也是该线性规划问题的最优解。

第一部分线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。

2．图解法适用于含有两个变量的线性规划问题。

3．线性规划问题的可行解是指满足所有约束条件的解。

4．在线性规划问题的基本解中，所有的非基变量等于零。

5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。

7．线性规划问题有可行解，则必有基可行解。

8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。

9．满足非负条件的基本解称为基本可行解。

10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。

11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。

12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。

13．线性规划问题可分为目标函数求极大值和极小_值两类。

14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。

18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。

19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。

20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。

21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。

二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最为_C_。

运筹学教程（第⼆版）（胡运权）课后答案（清华⼤学出版社）运筹学教程（第⼆版）习题解答第⼀章习题解答运筹学教程1.1 ⽤图解法求解下列线性规划问题。

并指出问题具有惟⼀最优解、⽆穷多最优解、⽆界解还是⽆可⾏解。

1 2x , x ≥ 0 ? ≤ 2 2 1 ? .? 2 x 1 - x 2 ≥ 2st- 2 x + 3x (4) max Z = 5 x 1 + 6 x 2≤ 82 5 ≤ x ? 1 ? 5 ≤ x ≤ 10 .?max Z = x 1 + x 26 x 1 + 10 x 2 ≤ 120st ?(3) 1 2 x , x ≥ 0 ? 2 1 ? ? ? 4 x 1 + 6 x 2 ≥ 6st .?2 x + 2 x ≥ 4 (1) min Z = 2 x 1 +3 x 21 2 ? ≥ 12 2 1 ? x , x ≥ 0 .? ?2 x 1 + x 2 ≤ 2st ?3x + 4 x (2) max Z = 3x 1 + 2 x 2x , x ≥ 0 1 2该问题⽆解≥ 12 2 1 ? ? 2 x 1 + x 2 ≤ 2st .?3 x +4 x ( 2 ) max Z = 3 x 1 + 2 x 2第⼀章习题解答3 2 1x = 1, x = 1, Z = 3是⼀个最优解⽆穷多最优解，1 2x , x ≥ 0 ? 2 1 ? ? ? 4 x 1 + 6 x 2 ≥ 6st .?2 x + 2 x ≥ 4 (1) min Z = 2 x 1 +3 x 2该问题有⽆界解1 2x , x ≥ 0 ? ≤ 2 2 1 ? .? 2 x 1 - x 2 ≥ 2st- 2 x + 3x (4) max Z = 5x 1 + 6 x 2第⼀章习题解答唯⼀最优解， x 1 = 10, x 2 = 6, Z = 16 ≤ 82 5 ≤ x ?1 ? 5 ≤ x ≤ 10 .?max Z = x 1 + x 26 x 1 + 10 x 2 ≤ 120st ?(3)第⼀章习题解答运筹学教程1.2 将下述线性规划问题化成标准形式。

运筹学作业（5）
习题1、清华大学运筹学（第三版）P112 4.2（2）
用图解法找出以下目标规划问题的满意解。

习题2、清华大学运筹学（第三版）P282 10.4（a）
用破圈法和避圈法求图中的最小树。

习题3、清华大学运筹学（第三版）P283 10.7图10-40
用课上介绍的逆推方法，求v1到v11的最短路径，标明路径，求出路长。

习题4：已知条件如表所示
p1：每周总利润不得低于10000元；
p2：因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；
p3：希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。

试建立这个问题的目标规划模型并求解（可利用EXCEL求）。

思考题：在上题中，如果工序Ⅱ在加班时间内生产出来的产品，每台A型机减
少利润10元，每台B型机减少利润25元，并且工序Ⅱ的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型并求解。

（此题下周四前会给出参考答案）。

运筹学清华大学第四版答案【篇一：运筹学作业2(清华版第二章部分习题)答案】s=txt>2．1 题（p. 77）写出下列线性规划问题的对偶问题：????（1）?????maxz?2x1?2x2?4x3s.t.x1?3x2?4x3?22x1?x2?3x3?3x1?4x2? 3x3?5x1?0，x2?0,x3无约束；解：根据原—对偶关系表，可得原问题的对偶规划问题为：?maxw?2y1?3y2?5y3?s.t.y1?2y2?y3?2??3y1?y2?4y3?2 ? ?4y1?3y2?3y3?4?y1?0,y2?0,y3?0??mn?minz???cijxij?i?1j?1?n???cijxij?ai,i?1,?,m（2）? j?1?n??cijxij?bj,j?1,?,n?j?1???xij?0,i?1,?,m;j?1,?,n解：根据原—对偶关系表，可得原问题的对偶规划问题为：mn??maxw??aiui??bjvji?1j?1??ui?vj?cij ??i?1,?,m;j?1,?,n???ui无约束，vj无约束2．2判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错。

因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。

但，现实中肯定有一些问题是无最优解的，故本题说法不对。

maxz?3x1?x2例如原问题s.t.?x1?x2?1?x2?3??x?0,x?02?1有可行解，但其对偶问题minw?y1?3y2s.t.?3?y1?y2?1?y1??y?0,y?02?1无可行解。

（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。

（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。

答：错。

正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。

运筹学清华大学第四版答案【篇一：运筹学作业2(清华版第二章部分习题)答案】s=txt>2．1 题（p. 77）写出下列线性规划问题的对偶问题：????（1）?????maxz?2x1?2x2?4x3s.t.x1?3x2?4x3?22x1?x2?3x3?3x1?4x2? 3x3?5x1?0，x2?0,x3无约束；解：根据原—对偶关系表，可得原问题的对偶规划问题为：?maxw?2y1?3y2?5y3?s.t.y1?2y2?y3?2??3y1?y2?4y3?2 ? ?4y1?3y2?3y3?4?y1?0,y2?0,y3?0??mn?minz???cijxij?i?1j?1?n???cijxij?ai,i?1,?,m（2）? j?1?n??cijxij?bj,j?1,?,n?j?1???xij?0,i?1,?,m;j?1,?,n解：根据原—对偶关系表，可得原问题的对偶规划问题为：mn??maxw??aiui??bjvji?1j?1??ui?vj?cij ??i?1,?,m;j?1,?,n???ui无约束，vj无约束2．2判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错。

因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。

但，现实中肯定有一些问题是无最优解的，故本题说法不对。

maxz?3x1?x2例如原问题s.t.?x1?x2?1?x2?3??x?0,x?02?1有可行解，但其对偶问题minw?y1?3y2s.t.?3?y1?y2?1?y1??y?0,y?02?1无可行解。

（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。

（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。

答：错。

正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。

求解下述LP 问题解：依据单纯形理论，有以下计算：（1）令345,,x x x 为基变量、12,x x 为非基变量，可得1234512100840010160400112x x x x x ⎡⎤⎢⎥⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎢⎥⎢⎥⎣⎦， 解得312415282164124x x x x x x x =--⎧⎪=-⎨⎪=-⎩，代入目标函数，得12023z x x =++。

此时得到的解为(0,0,8,16,12)T X =，0z =。

由120z x ∂=>∂、230zx ∂=>∂可知，12,x x 取正值可使z 增大。

若令2x 取正值且1x 仍为0，由324528201601240x x x x x =-≥⎧⎪=≥⎨⎪=-≥⎩，可得2243x x ≤⎧⎨≤⎩，这说明2x 最大可以达到3，此时5x 将变为0，成为非变量。

（2）令234,,x x x 为基变量、15,x x 为非基变量，可得1234510101/22400101601001/43x x x x x ⎡⎤⎢⎥-⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎢⎥⎢⎥⎣⎦，解得25315413/42/2164x x x x x x x =-⎧⎪=-+⎨⎪=-⎩，目标函数变为153924z x x =+-。

此时得到的解为(0,3,2,16,0)T X =，9z =。

由120zx ∂=>∂可知，1x 取正值可使z 增大。

若令1x 取正值且5x 仍为0，由2314130201640x x x x x =≥⎧⎪=-≥⎨⎪=-≥⎩，可得1124x x ≤⎧⎨≤⎩，这说明1x 最大可以达到2，此时3x 将变为0，成为非基本变量。

（3）令124,,x x x 为基变量、35,x x 为非基变量，可得解(2,3,0,8,0)T X =，13z =。

此时3511324z x x =-+，可知此时应让5x 取正值，即进入基变量。

第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：图解法采用直角坐标求解：x1——横轴；x2——竖轴。

1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设x 1、x 2为生产甲、乙产品的数量。

max z = 70x 1+30x 2 s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+072039450555409321212121x x x x x x x x ，可行解域为oabcd0，最优解为b 点。

由方程组⎩⎨⎧=+=+72039450552121x x x x 解出x 1=75，x 2=15 ∴X *=⎪⎪⎭⎫⎝⎛21x x =（75，15）T∴max z =Z *= 70×75+30×15=5700⑴⑵ ⑶ ⑷ ⑸、⑹max z = 6x 1+4x 2 s.t.⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ， 解：可行解域为oabcd0，最优解为b 点。

由方程组⎩⎨⎧=+=+81022121x x x x 解出x 1=2，x 2=6 ∴X *=⎪⎪⎭⎫⎝⎛21x x =（2，6）T∴max z = 6×2+4×6=36⑴⑵ ⑶ ⑷ ⑸、⑹min z =－3x 1+x 2 s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤≤08212523421212121x x x x x x x x ， 解：可行解域为bcdefb ，最优解为b 点。

一、不定向选择1、若线性规划问题有可行解则：A其可行域可能无界B其可行域为凸集C至少有一个可行解为基本可行解D可行域边界上点都为基本可行解E一定存在某一可行解使目标函数达最优值F任一可行解均能表示为所有可行域顶点线性组合表示G某一可行解为最优解必要条件为它是一个基本解。

2、线性规划问题和其对偶问题关系：A对偶问题的对偶问题为原问题B若原问题无解，其对偶问题有无界解C若原问题无界解，其对偶问题无解或者无界解D即使原问题有最优解，其对偶问题也未必有最优解E原问题目标函数达到最大时，其对偶问题取最小值F只有原问题达最优解时，其对偶问题才有可行解G若原问题有无穷多最优解，其对偶问题有无界解。

二、已知线性规划问题，如下：max z=x1+x2-x3-x1+2x2+x3<=2st. -2x1+x2-x3<=3x1,x2,x3>=0据对偶理论分析此问题有解的情况（最优，无界或无解）三、已知线性规划问题max z=x1+4x2+x3+2x4x1+2x2 +x4<=8x2 +2x4<=6st. x2+x3+x4<=9x1+x2+x3 <=6x1,x2,x3,x4>=0最优解为（0,2,4,2）据对偶理论找出其对偶问题最优解四、单纯形法解下列线性规划问题max z=3x1+2x2x1+2x2<=6st. 2x1+x2<=8-x1+x2<=1x2<=2x1,x2>=01)第一、二、四约束的影子价格为多少？2)变量x1价值系数增加2，最优解是否变化？五、运输问题单价表如下，确定总运费最小的调运方案B1 B2 B3 B4 产量A1 3 10 3 11 14A2 2 8 1 9 8A3 10 6 7 4 18销量10 12 6 12 40六、设备更新题：某设备收益r（万元），维修保养费w（万元）更新费g（万元）与役龄t（年）关系如下：r(t)=10-1/2 tw(t)=1+5/4 tg(t)=1/2+4/5 t考虑资金占用利率I ,试建立10年更新计划动态规划模型。

运筹学清华第四版答案【篇一：清华_第三版_运筹学教程_课后答案~(_第一章_第五章部分)】文字]运筹学教程1. 某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。

现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1所示。

表1要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

解：设总费用为z。

i=1,2,3,4,5代表5种饲料。

xi表示满足动物生长的营养需要时，第i种饲料所需的数量。

则有：minz?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5?3x1?2x2?x3?6x4?8x5?700?x10.5x20.2x32x40.5x530s.t.0.5x1x20.2x32x40.8x5100x0,i1,2,3,4,5i2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。

每班护士值班开始时间向病房报道，试决定：（1）若护士上班后连续工作8h，该医院最少需要多少名护士，以满足轮班需要；（2）若除22:00上班的护士连续工作8h外（取消第6班），其他班次护士由医院排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。

表262:00～6:00 30解：（1）设x第i班开始上班的人数，i=1,2,3,4,5,6minz?x1?x2?x3?x4?x5?x6?x1x1?x2?s.t.?x3x4x5xix660x270x360x450x520x6300,i1,2,3,4,5,6且为整数解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。

则设设xi第i班开始上班的人数，i=1,2,3,4。

minz?x1?x2?x3?x4?30y11x1y21x2y31x3y41x460，第一班约束y111,y11y12y13y142yxyxyxyx70，第二班约束121222323424?y221，y21?y22?y23?y24?2?s.t.?y13x1?y23x2?y33x3?y43x4?60，第三班约束?y?1，y?y?y?y?23132333433y14x1y24x2y34x3y44x450，第四班约束?y441，y41?y42?y43?y44?2x0，y是0—1变量，i,j?1,2,3,4ij?i3. 要在长度为l的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n种，分别为aj（j=1,2，…n）。