运筹学习题

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

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

?x11?x12?300000?x21?x23?1.2x11??x31?x34?1.2x21?1.5x12?x12?150000st.??x23?200000?x34?100000??xij?0?

,.7, x12?133333.3，x21?0，x23?200000，x31?100000解得 x11?166666x34?100000，第三年末本利总和为580000元。

13.某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如表所示。 甲 乙 丙 原料成本/元/KG 每月限制用量/KG A B C 加工费/元/KG 2.00 ≥60% ≥15% 1.50 ≤20% ≤60% ≤50% 1.00 0.50 0.40 0.30 2000 2500 1200 3.40 2.85 2.25 售价/元/KG 问该厂每月生产这三种牌号各多少KG，使得到的利润为最大？试建立这个问题的线性规划数学模型。

答：设

xij为生产i种糖果所使用的j种原材料数，i?1,2,3分别代表甲、乙、丙，

j?1,2,3分别代表A，B，C。其数学模型为：

maxz?(3.4?0.5)(x11?x12?x13)?(2.85?0.4)(x21?x22?x23)?(2.25?0.3)(x31?x32?x33)?2.0(x11?x21?x31)?1.5(x12?x22?x32)?1.0(x13?x23?x33)

?x11?x21?x31?2000?x?x?x?25002232?12?x13?x23?x33?1200?x11x21?0.6?0.15?st.?x11?x12?x13x21?x22?x23?x13x23?0.2?0.6?x21?x22?x23?x11?x12?x13x33?xij?0?x?x?x?0.53233?31

14. 某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质，30g矿物质，100mg维生素。现有五种饲料可供选用，各种饲料每KG营养成分含量及单价如表所示 饲料 蛋白质/g 矿物质/g 维生素/mg 价格/元/kg 1 2 3 4 3 2 1 6 1 0.5 0.2 2 0.5 1.0 0.2 2 0.2 0.7 0.4 0.3

CZ?Y*b

x4,x5为松弛变量，问题的约束

4. 已知下表为求解某线性规划问题的最终单纯形表，表中

条件为?形式。 x10 1 0 x2x31 0 0 x4x5x3 5/2 x1 5/2 cj?zj1/2 -1/2 -4 1/2 -1/6 -4 0 1/3 -2 (a)写出原线性规划问题 (b) 直接由表写出对偶问题的最优解。 答：（a）原线形规划问题如下：

maxz?6x1?2x2?10x3?x2?2x3?5?st.?3x1?x2?x3?10?x,x,x?0?123?

(b )对偶问题最优解为

5. 已知线性规划问题：

Y?(4,2)

maxz?5x1?3x2?6x3?x1?2x2?x3?18?2x?x?3x?16?123st.??x1?x2?x3?10?x1,x2?0,x3无约束 ?（a） 写出其对偶问题

（b） 已知原问题用两阶段法求解时得到的最终单纯形表如下 试写出其对偶问题的最优解。 5 3 6 －6 0 x10 x2 1 2 1 x3'x3'' 0 0 1 x4 1 0 0 x4 8 x5 1 14 －6 xs'' 4 0 1 0 0 0 －1 cj?zj0 －1 0 0 0 答： （a） 其对偶问题为

minw?18y1?16y2?10y3(1)?y1?2y2?y3?5?2y?y?y?3(2)?123st.?(3)?y1?3y2?y3?6??y1?0,y2,y3无约束

y第y（b） 设第（1）个约束条件的松弛变量为s1，（2）个约束条件的松弛变量为s2，

由原问题用两阶段法求得之最终单纯形表知

约束条件（1）~(3)有

ys1?0,ys2?1,y1?0，代入

?y1?2y2?y3?5??2y1?y2?y3?1?3?y?3y?y?623?1

(y,y,y)?(0,1,3)

解得：123

6.已知线性规划问题：

minz?2x1?x2?2x3??x1?x2?x3?4?st.??x1?x2?kx3?6?x?0,x?0,x无约束23?1

其最优解为

x1??5,x2?0,x3??1（a）求k的值；

（b）写出并求其对偶问题的最优解。 解：先写出其对偶问题如下：

maxw?4y1?6Y2

?y?y?2?12?y?y??1?12st.??y1?ky2?2??y1无约束,y2?0

由

z*?y*机互补松弛性质得

??y1?y2?2??4y1?6y2?12

解得y1?0,y2??2,代入求得k?1.

7.已知线性规划问题maxz?CX,AX?b,X?0,分别说明发生下列情况

时，其对偶问题的解的变化：

； (a)问题的第k个约束条件乘上常数?（??0）

(b)将第k个约束条件乘上常数?（??0）后加到第?个约束条件乘

上；

； (c)目标函数改变为maxz??CX（??0）

x1用3x1/(d)模型中全部

解：

代换。

?1Y?CBB?1,k?（a）对偶变量第个约束条件乘上常数?，即B的k列

1将为变化前的?，由此对偶问题变化后的解

1//(y1/,y2,...yk/,...ym)?(y1,y2,...yk,...ym);（b）与前类似，（c）（d）

?

bryr/?yr,yi/?yi(i?r);br??br

yi/??yi(i?1,...,m);

yi(i?1,...,m)不变。

8.已知线性规划问题：

max??cjxjj?1n?n??aijxj?bi(i?1,...,m)st.?j?1?x?0(j?1,...,n)?i

若（

***y1,y2,...,ym)为其对偶问题的最优解。又若原问题约束条件的，这时原问题的最优解变为（

//x1/,x2,...,xm)右端项变换为明

bibi/，试证

?j?1ncjx??bi/yi*/ji?1m

bi/解：原问题右端项变为后，其对偶问题为：

minz??bi/yii?1m

???aijyi?cj(j?1,...,n)st.?i?1?y?0(i?1,...,m)?im

必为上述问题的可行解。根据对

由于约束条件不变，（偶理论有：

***y1,y2,...,ym)?j?1ncjx??bi/yi*/ji?1m

9.已知线性规划问题：

maxz?x1?x2

??x1?x2?x3?2?st.??2x1?x2?x3?1?x,x,x?0?123

试应用对偶理论证明上述线性规划问题无最优解。

解：该问题存在可行解，如X?(0,0,0)；又上述问题的对偶问题为：

minw?2y1?y2??y1?2y2?1?y?y?1?2st.?1?y1?y2?0??y1,y2?0

解。

由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优

10．已知线性规划问题：

maxz?x1?2x2?3x3?4x4?x1?2x2?2x3?3x4?20?st.?2x1?x2?3x3?2x4?20?x,x,x,x?0?1234

其对偶问题最优解为y1?1.2,y2?0.2,试根据对偶理论求出原问题的最优解。

*X?(0,0,4,4)解：写出对偶问题并根据互补松弛性质可求得原问题最优解为

2.11 已知某实际问题的线性规划模型为：

maxz??cjXjj?1n

若第i资源的影子价格为yi，

?naijXj?bi(i?1,2....m)???st:?j?1?Xj?0?(i?1,2....n???

（a） 若第一个约束条件两端乘以2，变为 约束条件的影子价格，求

?(2aj?1n1j)Xj?2bi ，

Y1 是对应这个新的

Y1与y1的关系；

x'?3x1 用 (x1'/3)替换模型中所有的x1，问影子价格yi是否变化？若x不可

（b） 令 11

x'能在最优基中出现，问1有否可能在最优基中出现；

（c） 如目标函数变为 解：（a）

maxz??2cjXjj?1n ，问影子价格有何变化？

yxx'Y1=1/2y1；

（b） 影子价格i不变，又1不在最优解中出现， 1也不可能在

y最优解中出现，（c）影子价格i也增大两倍。

2.12 下述线性规划问题

maxz?8x1?4x2?6x3?3x4?9x5?x1?2x2?3x3?3x4?3x5?180(资源1）?（资源2）?x1?2x2?3x3?3x4?3x5?270st.?（资源3）?x1?3x2?2x3?x4?3x5?180?x?0(j=1.2...5)?j

已知最优解中的基变量为

x3 x1 x5 且已知

A1 A2 A3 销地销量 产地 1 2 3 销量 5 4 5 6 3 5 2 11 11 8

解： (a) 可以作为(b) 中非零元素小于9（产地+销地-1），不能作为初始方

5 甲 20 10 M 200 9 9 乙 16 10 18 400 7 丙 24 8 10 300 产量 300 500 100 初始方案。 销地 产地 1 2 3 销量 甲 10 14 22 12 乙 16 22 24 8 丙 32 40 34 20 产量 15 7 16 案。

(c) 中存在以非零元素为顶点的回路，不能作为初始方案。

3.2 已知运输问题的产销地、产销量及各产销地之间的单位运价如表3-2(a),(b)所示，试据此分别列出其数学模型

销地 产地 1 2 3 甲 3 7 2 乙 2 5 5 丙 7 2 4 丁 6 3 5 产量 50 60 25 销量 60 40 20 15 表 3-2(a)

表 3-2(b)

3.3 已知运输问题的供需关系与单位运价表如表3-3所示，试用表上作业法求(a)-(d)的最优解（表中M代表任意大正数）。对其中的（b）（d）分别用伏格尔法直接给出近似最优解。

表 3－3（a）

表 3－3（b）

销地 产地 1 销地2 产地 3 1 销量 2 3 销量 销地 产地 1 2 3 销量 3（c）

表 3－3（d）

销地 产地 1 2 3 销量 解：

销地 产地 1 2 3 销量 表3A-1（a）

甲 18 5 17 50 乙 14 8 7 70 丙丙 17 13 12 60 丁 丁 戊 12 15 9 80 产量产量 100 100 150 甲 35 25 60 甲 乙 8 12 乙 10 2 丙 11 14 9 丁 10 11 丙 8 24 4 8 10 300 丁 7 4 6 20 戊 7 10 产量 7 300 5 500 100 戊 5 7 8 20 产量 5 7 6 表 3－ 产量 20 30 30 9 8 7 甲 2 20 10 M 16 5 10 18 400 丙 3 8 9 20 200 甲 乙 8 5 6 25 6 M 3 25 乙 15 25 40 丙 20 20 丁 15 15 产量 50 60 25 1 2 销地产地 3 1 销量2 3 销量 表3A-1（b）

销地 产地 1 2 3 销量 50 甲 乙 50 2 2 2 70 70 丙 5 5 50 10 60 丁 3 1 4 10 70 80 90 戊 3 90 2 5 100 100 产量150 5 7 6 2 甲 20 5 0 25 乙 25 25 丙 20 丁 10 20 戊 20 20 产量 20 30 30 20

表3A-1（c）

表3A-1（d）

3.4某一实际的运输问题可以叙述如下：有n个地区需要物资，需要量分别不少于bj(j=1,…,n)。这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别不大于ai（i＝1，…,m）,已知从i地区工厂至第j个需求地区单位物资的运价为Cij，又

mn?ai??bji?1j?1mn，试写出其对偶问题，并解释对偶变量的经济意义。

解：由题意其数学模型为

minz???cijxiji?1j?1?n??xij?ai(i?1,...,m)?j?1?mst??xij?bj(j?1,...,n)?i?1?xj?0??

(1) 式可以改写为

m??xij??aij?1n,则上述问题的对偶问题为：

maxw??bjvj??aiuij?1i?1m??vj?ui?cij(i?1,...,m;j?1,...,n)st???vj,ui?0

对偶变量 i,j的 经济意义分别为单位物资在i产地和 j销地的价格。对偶问题的经济意义为：如该公司欲自己公司物资运到各地销售，其差价不能超过两地之间的运价（否则买主将在 i 地购买自己运到j地）。在此条件下，希望获利最大。

3.5 已知某运输问题的产销平衡表，单位运价表及给出的一个调运方案分别见表3－4和3-5。判断所给出的调运方案是否为最优？如是，说明理由，如否，也说明理由。

表3－4 产销平衡表及某一调运方案 销地 产地 B1 B2 B3 B4 B5 B6 产量 A1 A2 A3 A4 销量 销地 产地 B1 B2 B3 B4 B5 B6 5 25 25 40 10 25 20 20 24 16 20 10 5 15 20 11 50 40 60 31 uv表3－5 单位运价表 A1 2 1 3 3 2 5 A2 3 2 2 4 3 4 A3 3 5 4 2 4 1 A4 4 2 2 1 2 2 解：题目中给出的调运方案有11个非零元素，不是基可行解，应先调整得到基可行解，然后求检验数，判别是否最优。

3.6 某地区有三个化肥厂，除供应外地区需要外，估计每年可以供本地区的数字为：花费厂A——7万t，B—8t，C—3t，。有四个产粮区需要这种化肥，需要量为：甲地区----6万t，乙地区——6万t，——丙地区——3万t，丁地区——3万t。已知从各化肥厂到个粮区的每t化肥的运价表如下（表中单位：元/t）。

产粮区 化肥厂 A B C 甲 5 4 8 乙 8 9 4 丙 7 10 2 丁 3 7 9 试者根据以上资料制定一个使得总的运费为最少的化肥调拨方案。

解：化肥的最优调拨方案如下表： 产粮区 化肥厂 甲 乙 丙 丁 A B C 需求量 6 6 4 2 0 3 3 3 3 3 7 8 3

3.7 某玩具公司分别生产三种新型玩具，每月可供量分别为1000件，2000件，2000件，他们分别被送到甲、乙、丙三个百货商店去销售，已知每月百货商店的各种玩具的预期销量为1500件，由于各方面的原因，各个商店的不同玩具的盈利额度不同，见下表，又知丙百货商店至少要供应C 玩具1000件，而拒绝进A 玩具。求满足上述条件下使得盈利额最大的供销分配方案。 甲 乙 丙 丁 A B C 5 16 12 4 8 10 9 11 1000 2000 2000 解：

增加一个假想需求部门丁，最优调拨方案如下，表中将A调拨给丁500件表明玩具A 有500件销售不出处。 甲 乙 丙 丁 可供量 A B C 销售量 1500 500 500 500 1500 1500 1500 1000 2000 2000 500 1000 2000 2000 1500 3.8 已知某运输公司问题的产销平衡表与单位运价表如图3－8所示

销地

产地 I II III 销量 A B 10 15 20 40 30 35 25 115 C 20 15 40 60 D 20 30 25 30 E 40 30 150 70 产量 50 100 150 表 3－8

（a） 求最优调拨方案；

（b） 如产地III的产量变为130，又B地区需要的115单位必须满足，试重新确定最优

调拨方案。

解：

（a） 最优调拨方案如下表：

销地

产地 A B C D E 产量

I 15 35 50

II 10 60 30 100 III 80 70 150

销量 25 115 60 30 70

（b） 根据题设条件重新列出这个问题的产销平衡表与单位运价表

销地

产地 A B C D E 产量

I 10 15 20 20 40 50

II 20 40 15 30 30 100 III 30 35 40 55 25 130

Ⅳ0 M 0 0 0 20 （假想） 销量 25 115 60 30 70 从新求出最优

调拨方案如下表：

销地

产地 A B C D E 产量

I 50 50

II 25 60 15 100 III 65 65 130

Ⅳ 15 5 20 （假想） 销量 25 115 60 30 70

3.9某运输问题的产销平衡表和单位运价表3－9所示

表3－9 销地 B1 B2 B3 B4 产地 A1 A2 A3 A4 销量 2 4 3 4 30 1 2 5 2 50 3 2 4 2 20 3 4 2 1 40 B5 3 4 4 2 30 B6 5 4 1 2 11 产量 50 40 60 31 （a ）求最优的运输调拨方案； （c） 价表中的C12 ，C35， C41分别在什么范围内变化时，上面求出的最优调方案不变化。

解：最优的运输调拨方案如下： 销地 B1 B2 B3 B4 B5 B6 产量 产地 A1 A2 A3 A4 销量 20 10 30 30 20 20 39 1 40 30 30 11 11 50 40 60 31 50 20

（c） 保持最优调拨方案不变的Cij变化范围是：C13≥1，C35≥3，C41≥2

3.10 已知某运输问题的产销平衡表，最优调运方案及单位运价表分别为3－10和表3－11所示。由于从产地2至销地B的道路因故暂时封闭，故需对表3－10中的调运方案进行修正。试用尽可能方便的方法重新找出最优调运方案。 表3－10

销地

产地 A B C D E 产量

1 4 5 9

2 4 4 3 3 1 1 3 8

销量 3 5 4 6 3

表3－11

销地 产地 A B C D E 1 2 3 10 20 2 10 1 20 5 10 7 9 30 10 10 6 4

解：将2→B的单位运价该为M，，计算检验数并进行整理，其新的最优方案见下表：

销地

产地 A B C D E 产量

1 4 5 9

2 3 1 4 3 5 1 2 8

销量 3 5 4 6 3

3.11已知某运输公司问题的产销平衡表，单位运价表及给出的一个最优调运方案分别见表3－12和表3－13，试确定表3－13中k的取值范围。 表 3－12

销地

产地 B1 B2 B3 B4 产量

A1 5 10 15

A2 0 10 15 25 A3 5 5

销量 5 15 15 10 表3－13

销地

产地 B1 B2 B3 B4

A1 10 1 20 11

A2 12 k 9 20 A3 2 14 16 18

解:

根据上表求出各个空格地方的检验数如下表：

销地

产地 B1 B2 B3 B4

A1 k- K+10

A2 3 10-k A3 24-k 17 18-k

使得表中的检验数都全部大于等于零时有3≤k≤10。

3.12表3－14和表3－15分别是一个具有无穷多最优解的运输问题的产销平衡表、单位运价表。表3－14给出了一个最优解，要求再找出两个不同的最优解。 表3－14

销地

产地 B1 B2 B3 B4 产量

A1 4 14 18

A2 24 24 A3 2 4 6

A4 7 5 12 销量 6 14 35 30 表3－15

销地

产地 B1 B2 B3 B4

A1 9 8 13 14

A2 10 10 12 14 A3 8 9 11 13

A4 10 7 11 12 解：因（A4，B2）格

检验数为0，从该空格寻找闭回路调整可以得到最优解，将两个不同最优解对应数字相加除以2，变得到第三个最优解。

3.13 已知某运输问题的供需关系及单位运价表如表3－16及3－17所示。 表3－16

销地

产地 B1 B2 B3 产量

A1 8

A2 7 A3 4

销量 4 8 5 表3－

17

销地

产地 B1 B2 B3

A1 4 2 5

A2 3 5 3 A3 1 3 2

要求：

（a） 用表上作业法找出最优调运方案；

（b） 分析从A1到B1的单位运价C11的可能变化范围，使上面的最优调运方案不变。 （c） 分析使该最优方案不变时从A2到B3的单位运价C23的变化范围。

解：（a）增加一个假想销地，得到最优方案如下表：

销地 产地 A1 A2 A3 销量 B1 4 4 B2 8 0 8 B3 5 0 5 B4 2 2 产量 8 7 4

（b）

c11?0;

23(c)

3．14给出某运输问题的产销平衡表，单位运价表及最优调运方案分别如表3－18，表3－19所示。 销地 产地 B1 B2 B3 B4 B5 B6 产量 2?c?4A1 A2 A3 A4 销量 20 10 30 20 20 20 39 1 40 30 30 11 11 50 40 60 31 30 50 表3－19 单位运价表

试确定单位运价表中的C12，C35和C41分别再什么范围内变动时，表3－18中给出的最优销地 产地 B1 B2 B3 B4 B5 B6 A1 A2 A3 A4 调运方案不变。 2 4 3 4 1 2 5 2 3 2 4 2 3 4 2 1 3 4 4 2 5 4 1 2 12解：，41，35。

3.15 如表3－20所示的问题中，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为5，4，3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。 表3－20

2?c?2c?2c?3销地 产地 1 2 3 A 1 1 2 B 2 4 3 C 2 5 3 产量 20 40 30

3 2 1 0

1 2 3 4 5 6 x1 【例3】有如下目标规划模型 minz= p1 (d1- + d1+ )+ p1 d2-

x1≤ 6

2 x1 -x2 + d1- - d1+ =2 2 x1 -3x2 + d2- - d2+ =6 xi≤≥0; di- , di+ ≥0

试用单纯形法求其满意解，若有多个满意解，求出其中的两个出来。 解 如表5.1所示求解过程 Cj 0 0 0 xi≤ xi≤ xi≤ xi≤ CB XB 6 0 x3 6 p1 d1- 2 0 d2- 6 cj - zj p1 p2 0 x3 5 0 x1 1 0 d2- 4 cj - zj p1 p2 0 x2 10 0 x1 6 0 d2- 24 x1 x2 x3 d1- d1+ d2- d2+ 1 0 1 0 0 0 0 [2 ] -1 0 1 -1 0 0 2 -3 0 0 0 1 -1 -2 1 2 1 0 [1/2 ] 1 -1/2 1/2 0 0 1 -1/2 0 1/2 -1/2 0 0 0 -2 0 -1 1 1 -1 0 1 1 1 0 1 2 -1 1 0 0 1 0 1 0 0 0 0 0 0 4 -3 3 1 -1 cj - zj p1 0 1 1 1 p2 所以两个满意解为（1，0），（6，10）。Zmin=0

【例4】某种牌号的酒系由三种等级的酒兑制而成。已知各种等级酒的每天供应量和单位成本如下：

等级ⅰ：供应量1500单位/天，成本6元/单位； 等级ⅱ：供应量2000单位/天，成本4.5元/单位； 等级ⅲ：供应量1000单位/天，成本3元/单位； 该种牌号的酒有三种商标（红、黄、蓝），各种商标酒的混合及售价如表5.2所示。

表5.2 商 标 总制配比要求 单位售价/元 红 黄 ⅲ 少于10% ⅰ多于50% ⅲ 少于70% ⅰ少于20% 5.5 5.0 蓝 ⅲ 少于50% ⅰ多于10% 4.8

为保持声誉，确定经营目标为： p1 兑制要求配比必须严格满足； p2 企业获取尽可能多的利润；

p3 红色商标酒每天量不低于2000单位。 试对该问题建立目标规划模型；

解 设j=1,2,3分别代表红、黄、蓝三种商标的离序号，则 Xij ——第i等级酒在第j种商标酒中所占数量； yj ——第j等商标酒的生产数量 可建立目标规划数学模型如下：

minz= p1 (d1- + d1+ + d2- + d2+ + d3- + d3+ + d4- + d4++ d5- + d5++ d6- + d6+)+ p2d7- + p3 d8- y1 = X11+X21 + X31

y2= X12+X22 + X32 （产量关系约束） y3 = X13+X23 + X33

X11+X12 + X13 ≤1500

X21+X22 + X23 ≤2000 （原料限制约束） X31+X32 + X33 ≤1000 p1 X 31+ d1- - d1+=10% y1

X 11+ d2- - d2+=50% y1 X 32+ d3- - d3+=70% y2

X 12+ d4- - d4+=20% y2 （配比限制） X 33+ d5- - d5+=50% y3 X 13+ d6- - d6+=10% y3

P2 5.5 y1 +5.0 y2+4.8 y3 + d7- - d7+ =5.5×4500 (利润限制) P3 y1 + d8- - d8+ =2000 (红色商标酒产量限制)

yj ≥0, Xij≥0, dk- ,dk+≥0,(i=1,2,3; j=1,2,3;k=1,2,3,…8) 【例5】已知某实际问题的线性规划模型为 max z=100 x1 +50 x2

10x1 +16 x2≤200 (资源1) 11x1 +3 x2≥25 (资源2) x1 ，x2≥0

假定重新确定这个问题的目标为： P1 ：z的值应不低于1900； P2：资源1必须全部利用。

将此问题转换为目标规划问题，列出数学模型。

解 这是将线性规划模型转化为目标规划模型的典型例子。转化后的模型为 max z= P1d2-+ P2 d1-

10x1 +16 x2+ d1- - d1+=200 11x1 +3 x2≥25

100x1 +50x2+ d2- - d2+=1900

x1 ，x2≥0，di- , di+≥0 (i=1,2)

【例6】已知目标规划问题

min z= p1 d1- + p2d2- + p3（5d3- + 3d4- ） + p4 d1+ x1 +2x2 + d1- - d1+ =6 x1 +2x2 + d2- - d2+ =9 x1 -2x2 + d3- - d3+ =4

x2 + d4- - d4+ =2

x1 ，x2≥0，di- , di+≥0 (i=1,2,3,4)

(a) 分别用图解法和单纯形法求解； (b) 分析目标函数分别变为①、②两种情况时（②中分析ω1 ，ω2 的比例变动）解的变 化。 ① min z= p1 d1- + p2d2+ + p3 d1++ p4（5d3+ + 3d4- ） ② min z= p1 d1- + p2d2+ + p3（ω1d3+ + ω2 d4- ）+ p4d1+

x2

5 d2+ 4

d2- 3

d4d3- + d1 +2

A d1- d4- d3+ 1 B 0

2 4 6 8 x1

图5.2 解 （a）如图5.2所示，用图解分析可得出满意解为A(13/2,5/4)，zmin =3 p3 d4- + p4 d1+，其中 d4- =3/4,d1+ =-3。其单纯形算法的单纯形表如表5.3所示。

（b）①当目标函数变为minz= p1 d1- + p2d2+ + p3 d1++ p4（5d3+ + 3d4- ）时，图上分析，其满

意解应在B点。用单纯形法可做灵敏度分析，如表5.4所示。其满意解为x1 =5，x2 =1/2。 ③ 当目标函数变为minz= p1 d1- + p2d2+ + p3（ω1d3+ + ω2 d4- ）+ p4d1+ 时，用单纯 形 法做灵敏度分析，如表5.5所示。 可见，当

1、 ω1 / ω2≥1/4（ω1 ，ω2 ）0 ）时，满意解为，x1 =13/2，x2 =5/4。 2、 ω1 / ω2≤1/4（ω1 ，ω2 ）0 ）时，满意解为，x1 =5，x2 =2。

表5.3 Cj 0 0 p1 p4 0 p2 5p3 0 3 p3 0 CB XB 6 p1 d1- 6 0 d2- 9 5p3 d3- 4 3p3 d4- 2 cj - zj p1 p2 p3 p4 p1 d1- 2 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 2 1 -1 0 0 0 0 0 0 1 2 0 0 1 -1 0 0 0 0 1 -2 0 0 0 0 1 -1 0 0 0 [1 ] 0 0 0 0 0 0 1 -1 -1 -2 1 1 -5 7 5 3 [1 ] 0 1 -1 0 0 0 0 -2 2 0 d2- 5 5p3 d3- 8 0 x2 2 cj - zj p1 p2 p3 p4 0 x1 2 0 d2- 3 5p3 d3- 6 0 x2 2 cj - zj p1 p2 p3 p4 0 x1 5 0 d2- 3 3p3 d4- 3/2 0 x2 1/2 cj - zj p1 p2 p3 p4 0 x1 13/2 p4 d1- 3 3p3 d4- 3/4 0 x2 5/4 cj - zj p1 p2 p3 p4 1 0 0 0 1 -1 0 0 -2 2 1 0 0 0 0 0 1 -1 2 -2 0 1 0 0 0 0 0 0 1 -1 -1 1 2 -2 1 -5 7 5 -7 10 1 0 1 -1 0 0 0 0 -2 2 0 0 -1 1 1 -1 0 0 0 0 0 0 -1 1 0 0 1 -1 [4] -4 0 1 0 0 0 0 0 0 1 -1 1 5 -5 1 5 -17 20 1 1 0 1/2 -1/2 0 0 1/2 -1/2 0 0 0 0 -1 [1 ] 1 -1 0 0 0 0 0 0 -1/4 1/4 0 0 1/4 -1/4 1 -1 0 1 1/4 -1/4 0 0 -1/4 1/4 0 0 1 1 3/4 -3/4 17/4 3/4 3 1 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1/4 1/4 1/4 -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 0 0 0 1 1 3/4 -1/4 17/4 3/4 3 1 -1 1 表5.4 0 0 p1 p3 0 p2 5p4 0 3 p4 0 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 [1 ] -1 0 0 0 0 0 0 0 0 -1/4 1/4 1/4 -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 1/4 0 0 1 1 1 -1 1 3/4 -3/4 17/4 3/4 3 1 0 1/2 -1/2 0 0 1/2 -1/2 0 0 Cj CB XB 6 0 x1 13/2 p3 d1+ 3 3p4 d4- 3/4 0 x2 5/4 cj - zj p1 p2 p3 p4 0 x1 5 0 d2- 3 0 0 -1 1 1 -1 0 0 0 0 3p4 d4- 3/2 0 0 -1/4 1/4 0 0 1/4 -1/4 1 -1 0 x2 1/2 0 1 1/4 -1/4 0 0 -1/4 1/4 0 0 cj - zj p1 p2 p3 p4 1

1 1 3/4 -3/4 17/4 3/4 3

表5.5 0 0 p1 p4 0 p2 ω1p3 0 ω2p3 0 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1/4 1/4 [1/4 ] -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 0 0 0 0 0 p1 p4 0 p2 ω1p3 0 ω2p3 0 1 1 ω2 /4 -ω2 /4 4ω1-ω2 /4 ω2 /4 ω2 /4 ω2 1 -1 1 1 0 0 0 1 -1 0 0 -2 2 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1 1 1 -1 4 -4 0 1 0 0 0 0 0 0 1 -1 1

1 ω1 -ω1 ω1 ω2 -4ω1 4ω1

1 -1 1 Cj CB XB 6 0 x1 13/2 p4 d1+ 3 - ω2p3 d43/4 0 x2 5/4 Cj cj - zj p1 p2 p3 p4 0 x1 5 p4 d1+ 3 - ω1p3 d33 0 x2 2 cj - zj p1 p2 p3 p4 第五章 整数规划习题

5.1 考虑下列数学模型

minz?f1(x1)?f2(x2) 且满足约束条件

（1）或x1?10，或x2?10； （2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

x?x2?0（3）1或5或10 （4）x1?0，x2?0

本文来源：https://www.bwwdw.com/article/mm4.html