运筹学习题

第一章. 线形规划及单纯形法习题

1. 某炼油厂根据计划每季度需供应合同单位汽油15万吨，煤油12万吨，重油12万

吨。该厂从A，B两处运回原油提炼，已知两处原油成分如下表所示。又如从A处采购原油每吨价格（包括运费，下同）为200元，B处原油每吨为300元。试求：1）选择该炼油厂采购原油的最优决策；2）如A处价格不变，B处降为290元/吨，则最优决策有何改变？ A/% B/% 含汽油 含煤油 含重油 15 20 50 50 30 15 15 5 其他 答：1）最优策略为：每季度从A处采购27.27万吨，从B处采购21.82万吨，总费用12218.2万元。

2）改为每季度从A处采购15万吨，从B处采购30万吨，总费用11700万元。

2. 已知线性规划问题： maxz?x1?3x2

下表中所列的解（a）— （f）均满足约束条件1-3，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。 x3x5x1x2x4序号 ?x1?x3?5?x?2x?x?10?24st.?1?x2?x5?4??x1,?,x5?01234(a) 2 4 3 0 (b) 10 0 -5 0 (c) 3 0 2 7 (d) 1 4.5 4 0 (e) 0 2 5 6 (f) 0 4 5 2 答：可行解有(a), (c), (e), (f); 基解有(a), (b), (f); 基可行解有(a) (f).

3. 已知某线性规划问题的约束条件为

0 4 4 -0.5 2 0 判断下列各点是否为该线性规划问题可行域的凸集的顶点：

2x1?x2?x3?25??x1?3x2?x4?30?st.??4x1?7x2?x3?2x4?x5?85?xj?0(j?1,?,5)?

（5，15，0，20，0）（a）X? （9，7，0，0，8） (b) X? （15，5，10，0，0） (c ) X?

答：

该线性规划问题中

?2???p1??1??4???（a） 因有?p1?p2?p4?0，故不是凸集顶点； （b） （9，7，0，0，8）为非可行域的点

?1???p2??3??7???

??1???p3??0???1????0??0?????p4???1?p5??0???2???1?????

（c） 因123线性相关，故非凸集的顶点。

4. 在单纯形法迭代中，任何从基变量中替换出来的变量在紧接着的下一次迭代中会不

会立即再进入基变量，为什么？

答：不可能，因刚从基中被替换出来的变量在下一个单纯形表中，其检验数一定为负。

5. 求解线性规划问题当某一变量

其中

p,p,pxj的取值无约束时，通常用

xj?xj?xj'''来替换，

xj?0'，

xj?0'''。试说明

''xj''，

xj''''能否在基变量中同时出现，为什么？

答：不可能，因为，故

6. 下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为

pj??pjpj?pj?0maxz?5x1?3x2，约束形式为?，x3,x4为松弛变量，表中解代入目标函数后得

z?10. x1x3 2 a b b x20 e -1 x3x4x1 a cj?zj1 0 f 1/5 1 g (a) 求a---g 的值 (b) 表中给出的解是否为最优解。

答：a=2, b=0, c=0, d=1, e=4/5, f=0, g= -5,

表中给出的解为最优解。

*7. 线性规划问题maxz?CX，AX?b，X?0，如X是该问题的最优解，又

??0为某一常数，分别讨论下列情况时最优解的变化。 （a） 目标函数变为maxz??CX （b） 目标函数变为maxz?(C??)X

?，约束条件变为AX??b （c） 目标函数变为

*答：(a) X仍为最优解，maxz??CX

(b) 除C为常数向量外，一般X不再是问题的最优解

(c) 最优解变为?X，目标函数值不变。

*maxz?CX*

8. 试将下述问题改写成线性规划问题

mm??m??max?min??ai1xi,?ai2xi,?,?ainxi??xii?1i?1?i?1?? ??x1?x2???xm?1st.??xi?0,i?1,2,?,m答：令

maxz?v

v?min(?ai1xi,?ai2xi,?,?ainxi)i?1i?1i?1mm

m，则问题可化为

9. 线性回归是一种常用的数理统计方法，这个方法要求对图上的一系列点

?m??aijxi?v(j?1,?,m)?i?1m?st?xi?1?i?1??xi?0(i?1,?,m)? ?

（x1,y1)(x2,y2)?(xn,yn)选配一条合适的直线拟合。方法通常是先定直线方程为

y?a?bx，然后按某种准则求定a,b。通常这个准则为最小二乘法，但也可用其

他准则。试根据以下准则建立这个问题的线性规划模型：

min?yi?(a?bx)i?1n

答：令

ui?yi?(a?bxi)，ui可能为正，也可能为负

?y?(a?bx),当yi?a?bxi'ui??i0,当yi?a?bxi? 设 0,当yi?a?bxi?''ui???(a?bxi)?yi,当yi?a?bxi

'''u?u?yi?(a?bxi) ii?

所以这个问题的线性规划模型为：

ui?ui'?ui''ui'，ui''?0

?n?min??(ui'?ui'')??i?1?

?ui'?ui''?yi?(a?bxi)(i?1,2,?,n)?ui',ui''?0(i?1,2,?n)?

010．线性规划问题maxz?CX,AX?b,X?0,设X为问题的最优解，若目标函数中用

C*代替C后，问题的最优解变为X*，求证：

（C*?C）（X*?X0）?0

*00*?C(X?X)?0 （1） ?CX?CX证明：

***0**0?0 (2) 又CX?CX， 有C（X?X）（C*?C）（X*?X0）?0 (2)–(1)得

11.某医院昼夜24H各时段内需要的护士数量如下：2:00~6:00 10人，6：00~10：00 15人，10：00~14：00 25人，14：00~18：00 20人，18：00~22：00 18人，22：00~2：00 12人。护士分别于2：00，6：00，10：00，14：00，18：00，22：00分6批上班，并连续工作8H。 试确定：

（a） 该医院至少应设多少名护士，才能满足值班需要

（b） 若医院可聘用合同工护士，上班时间同正式工护士。若正式工护士报酬为10元/H，

合同工护士为15元/H，问医院是否应聘用合同工护士及聘多少名？

6分别代表于早上2：答：（a）设1200，6：00直至晚上22：00开始上班的护士数，

则可建立如下数学模型：

x,x,?,x

?x6?x1?10x3?x4?20?x?x?15x?x?18?1245st.??x2?x3?25x5?x6?12?(j?1,?,6)?xj?0

x?0,x2?15,x3?10,x4?16,x5?2,x6?10，总计需53名护士。 解得 1x',x',?,x6'分别为早上2：00，6：00直至晚上22：00开

（b）在(a)的基础上设12minz?x1?x2?x3?x4?x5?x6

始上班的合同工护士数，则有：

minz?80?xj?120?xj'j?1j?166?x6?x6'?x1?x1'?10x3?x3'?x4?x4'?20?x?x'?x?x'?15x?x'?x?x'?18?11224455st.??x2?x2'?x3?x3'?25x5?x5'?x6?x6'?12?xj,xj'?0(j?1,?,6) ?

x'?0(j?1,?,6)x1至x6解得j，的数字同上。

12. 某人有一笔30万元的资金，在今后的三年内有以下投资项目：

（1） 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年

的投资；

（2） 只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资

额不超过15万元；

（3） 于三年内第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类

投资限额20万元；

（4） 于三年内的第三年初允许投资，一年回收，可获利40%，投资限额为10万元。 试为该人确定一个使第三年末本利和为最大的投资计划。 答：设

xij为第i年初投放到j项目的资金数，其数学模型为

maxz?1.2x31?1.6x23?1.4x34