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

运筹学习题选解

1

第一章 线性规划及单纯形法

1、 （生产计划问题） 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表 1-12.. 若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低. 试建立线性规划模型.

表1-12 季度1 2 3 4

j 生产能力aj（吨） 30 40 20 10 生产成本dj（万元/吨） 15．0 14．0 15．3 14．8 需求量bj（吨） 20 20 30 10 解: 现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型.

（1）设工厂第j季度生产产品xj吨

首先，考虑约束条件：第一季度末工厂需交货20吨，故应有x120；第一季度末交货后积余（x120）吨；第二季度末工厂需交货20吨，故应有x120x220；类似地，应有

x1x240x330；第四季度末供货后工厂不能积压产品，故应有x1x2x370x410；又考虑到工厂每个季度的生产能力，故应有0xjaj.

其次，考虑目标函数：第一季度工厂的生产费用为15.0x1，第二季度工厂生产的费用包括生产费用14x2及积压产品的存贮费0.2(x120)；类似地，第三季度费用为

15.3x30.2(x1x240)，第四季度费用为14.8x40.2(x1x2x370). 工厂一年的费用

即为这四个季度费用之和. 整理后，得下列线性规划模型： min z15.6x114.4x215.5x314.8x426 s.t. x1x2 40 x1x2x3 70 x1x2x3x480

20x130，0x240，0x320，0x410.

（2）设第j季度工厂生产的产品为xj吨，第j季度初存贮的产品为yj吨（显然，y10）. 因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：

x120y2， y2x220y3， y3x330y4， y4x410；

同时，每季度的生产量不能超过生产能力：xjaj；而工厂四个季度的总费用由每季的 生产费用与存贮费用组成，于是得线性规划：

min z15.0x10.2y214x20.2y315.3x30.2y414.8x4

2

s.t. x1y220 y2x2y320

y3x3y430 y4x410 0x130 0x240 0x320 0x410 yj0， j2，3，4.

（3） 设第i季度生产而用于第j季度末交货的产品数量为xij吨.

根据合同要求，必须有：

x1120， x12x2220，

x13x23x3330， x14x24x34x4410.

又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力， 故应有：

x11x12x13x1430， x22x23x2440， x33x3420， x4410.

第i季度生产的用于第j季度交货的每吨产品的费用cijdi0.2(ji)，于是，有线性规划模型：

min z = 15.0x1115.2x1215.4x1315.6x14

14x2214.2x2314.4x24

15.3x3315.5x3414.8x44

s.t. x1120

x12x2220

x13x23x3330

x14x24x34x4410 x11x12x13x1430 x22x23x2440

x33x3420 x4410

xij0 i1，…，4；j1，…，4，ji.

2、（合理下料问题）某工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料最省？

解: 分析：利用7.4m长的圆钢截成2.9m、2.1m、1.5m的圆钢共有如表1-13所示的8种下料方案.

表1-13 下料方案表 方案 毛坯/m 2．9 2．1

2 0 1 2 1 1 1 0 3

0 3 0 2 0 1 0 0 方案1 方案2 方案3 方案4 方案5 方案6 方案7 方案8 1．5 合计 剩余料头 1 7．3 0．1 0 7．1 0．3 1 6．5 0．9 3 7．4 0．0 0 6．3 1．1 2 7．2 0．2 3 6．6 0．8 4 6．0 1．4

一般情况下，我们可以设x1,x2,x3,x4,x5,x6,x7,x8分别为上面8种方案下料的原材料根数.根据目标的要求，可以建立两种形式的目标函数： 材料根数最少：

min z = x1x2x3x4x5x6x7x8 (1.27)

剩余料头最少：

min z = 0.1x10.3x20.9x30x41.1x50.2x60.8x71.4x8 （1.28）

约束是要满足各种方案剪裁得到的2.9m、2.1m、1.5m三种圆钢各自不少于100个，即 2.9m : 2x1x2x3x4 100 2.1m : 2x2x3 3x52x6x7 100 1.5m : x1 x33x4 2x63x74x8100 非负条件 x1， x2，x3， x4，x5，x6，x7， x80 这样我们用目标函数（1.27）可建立如下数学模型： min zx1x2x3x4x5x6x7x8

s.t. 2x1x2x3x4 100 2x2x3 3x52x6x7 100 x1 x33x4 2x63x74x8100 x1， x2，x3， x4，x5，x6，x7， x80

利用线性规划单纯形法求解可得：x*=（10，50，0，30，0，0，0，0）T，最少使用的材料为90（根），各种圆钢数均正好100个.

如果用目标函数（1.28），可建立如下数学模型：

min z0.1x10.3x20.9x30x41.1x50.2x60.8x71.4x8

s.t. 2x1x2x3x4 100 2x2x3 3x52x6x7 100 x1 x33x4 2x63x74x8100 x1， x2，x3， x4，x5，x6，x7， x80

利用线性规划单纯形法求解可得：x*=（0，0，0，100，0，50，0，0），最少的剩余料头为

T

10m. 这时2.9m和2.1m的圆钢数正好100个，而1.5m的圆钢数多300个. 显然，这不是最优解，为什么会出现误差呢？仔细观察一下会发现，原因出现在方案4的剩余料头为零，求解过程中目标函数最小对它失去了作用. 由此提示我们，在实际使用线性规划解决问题时，隐含的逻辑错误往往很难发现，必须进行解的分析才能够找出问题.

3 、（多阶段投资问题）某企业现有资金200万元，计划在今后5年内给A，B，C，D ，4个项目投资。根据有关情况的分析得知：

项目A：从第一年到第五年每年年初都可进行投资，当年末就能收回本利110%；

项目B：从第一年到第四年每年年初都可进行投资，当年末能收回本利125%，但是要求每年最大投资额不能超过30万元；

4

项目C：若投资则必须在第三年年初投资，到第五年末能收回本利140%，但是最大投资额不能超过80万元；

项目D：若投资则需在第二年年初投资，到第五年末能收回本利155%，但是规定最大投资额不能超过100万元；

根据测定每万元每次投资的风险指数为：项目A为1，项目B为3，项目C为4，项目D为5.5. 问题：

（1） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ （2） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础

上保证其投资的总风险系数最小？ 解: 首先考虑问题（1）：

1）确定决策变量. 本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量.

设xij（i1，2，3，4，5；j1，2，3，4）表示第i年初投资于项目A（j1）、项目B（j2）、项目C（j3）、项目D（j4）的金额. 根据题意，我们建立如下决策变量：

第一年年初 第二年年初 第三年年初 第四年年初 第五年年初

项目A x11 x21 x31 x41 x51 项目B x12 x22 x32 x42 项目C x33 项目D x24

2）考虑约束条件. 由于项目A的投资当年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是最优的. 下面我们分年来考虑：

第一年年初：由于只有项目A和项目B可以投资，又应把全部200万元资金投出去，于是有 x11x12200

第二年年初：由于项目B要次年末才可收回投资，故第二年年初的资金只有第一年年初对项目A投资后，在年末收回的本利110%x11，而投资项目为A，B和D，于是有：

x21x22x241.1x11

整理后得：

1.1x11x21x22x240

第三年年初：年初的资金为第二年年初对项目A投资后，在年末收回的本利110%x21以 及第一年年初对项目B投资后，在年末收回的本利125%x12. 可投资项目有A，B和C，于是有：

x31x32x331.1x211.25x12 整理后得：

1.1x211.25x12x31x32x330

第四年年初：年初的资金为第三年年初对项目A投资后，在年末收回的本利110%x31以及第二年年初对项目B投资后，在年末收回的本利125%x22. 可投资项目只有A和B，于是有：

x41x421.1x311.25x22 整理后得：

1.1x311.25x22x41x420

第五年年初：年初的资金为第四年年初对项目A投资后，在年末收回的本利110%x41以及第三

5

年年初对项目B投资后，在年末收回的本利125%x32. 可投资项目只有A，于是有：

x511.1x411.25x32

整理后得：

1.1x411.25x32x510

其他的还有项目B，C，D的投资以及各决策变量的非负约束： 项目B的投资： xi230（i1，2，3，4） 项目C的投资： x3380 项目D的投资： x24100

各决策变量的非负约束：xi1，xj2，x33，x240（i1，2，3，4，5；j1，2，3，4） 3）建立目标函数. 问题要求在第五年末公司这200万元用于4个项目投资的运作获得本利最大，而第五年末的本利获得有4项：

第五年年初对项目A投资后，在年末收回的本利110%x51； 第四年年初对项目B投资后，在年末收回的本利125%x42； 第三年年初对项目C投资后，在年末收回的本利140%x33； 第二年年初对项目D投资后，在年末收回的本利155%x24. 于是得到目标函数为：

z1.1x511.25x421.4x331.55x24 根据上面的分析得到线性规划模型：

max z1.1x511.25x421.4x331.55x24 s.t. x11x12200

1.1x11x21x22x240

1.1x211.25x12x31x32x330 1.1x311.25x22x41x420 1.1x411.25x32x510 xi230(i1，2，3，4) x3380 x24100

xi1，xj2，x33，x240 （i1，2，3，4，5;j1，2，3，4） 考虑问题（2）：

据题意，问题（2）的决策变量设置与问题（1）的设置1）完全相同；而问题（2）的约束设置除与问题（1）的设置2）完全相同外，还增加一约束，就是考虑要使第五年末拥有资金的本利在330万元上，即

1.1x511.25x421.4x331.55x24330

问题（2）的主要区别在于目标不同，是要使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数为最小. 因此，目标函数为各年各项目的风险系数之和，而风险系数等于投资数乘以相应风险指数. 于是得到下列目标函数：

z(x11x21x31x41x51)3(x12x22x32x42)4x335.5x24

综合以上分析，问题（2）的线性规划模型为：

min z(x11x21x31x41x51)3(x12x22x32x42)4x335.5x24

6

s.t. x11x21200

1.1x11x21x22x240

1.1x211.25x12x31x32x330 1.1x311.25x22x41x420 1.1x411.25x32x510

xi230(i1，2，3，4) x3380

x24100

1.1x511.25x421.4x331.55x24330

xi1，xj2，x33，x240 （i1，2，3，4，5;j1，2，3，4）

此例属于动态规划问题，它既可以建立上述模型用线性规划求解，也可以用动态规划的方法求解. 很多运筹学问题是可以用多种方法求解的，不同方法求解在理论上得到的结果应是一致的，但是由于方法本身的特征，不同算法可以得到不同的附带信息. 例如利用线性规划求解除了可得到最优解和最优植之外，还可通过分析得到下面将要介绍的影子价格（对偶价格）、灵敏度分析结果等. 另外，不同方法求解同一个问题时，计算量、复杂性、精确度等都会有差异.因此，读者在学习中了解掌握多种建摸思路，学会多种求解方法，对于提高解决实际问题的能力和水平是十分重要的.

4、（场地租借问题）某厂在今后四个月内需租用仓库堆存货物. 已知各个月所需的仓库面积数如表1-14. 又知，当租借合同期限越长时，场地租借费用享受的折扣优待越大，有关数据如表1-15.

表1-14

月份i 所场地面积（百米） 21 2 3 4 15 10 20 12

表1-15 合同租借期限 租借费用（元/百米） 21个月 2个月 3个月 4个月 2800 4500 6000 7300

租借仓库的合同每月都可办理，每份合同应具体说明租借的场地面积和租借期限. 工厂在任何一个月初办理签约时，可签一份，也可同时签若干份租借场地面积数和租借期限不同的合同. 为使所付的场地总租借费用最小，试建立一个线性规划模型.

解： 设xij为第i个月初签订的租借期限为j个月的合同租借面积（单位：百米）.

2

于是，有下列决策变量：

一月签订：x11 x12 x13 x14

二月签订： x21 x22 x23 三月签订： x31 x32 四月签订： x41

各个月生效的合同的租借面积为： 第一个月：x11+x12+x13+x14

第二个月：x12+x13+x14+x21+x22+x23

7

第三个月：x13+x14+x22+x23+x31+x32 第四个月：x14+x23+x32+x41 从而，我们得如下线性规划摸型：

min z =2800432xi1i14500xi26000xi37300x14

i1i1s.t. x11+x12+x13+x1415， x12+x13+x14+x21+x22+x2310， x13+x14+x22+x23+x31+x3220， x14+x23+x32+x4112 x1j0, j1，…，4 x2j0，j 1，2，3 x310, x320， x410.

5、（分配问题）甲方战略轰炸机队指挥官得到了摧毁乙方坦克生产能力的命令. 根据情报，乙方有三个生产坦克部件的工厂，位于不同的地点. 只要破坏其中任一个工厂的生产设施就可以有效地停止乙方坦克的生产.

该轰炸机队现有重型和中型两种轰炸机，其数量和燃油耗量如表1-16.

表1-16 编号i 1 2 ###飞机类型 重型 中型 每公里耗油量（加仑） 1/2 1/3 飞机架数 40 28

根据情报分析，空军基地与各工厂的距离和各类型飞机命中目标的概率如1-17表.

表1-17 工厂###j#摧毁目标概率 距离（公里） 450 480 570 重型（1） 0.10 0.20 0.15 #中型（2） 0.08 0.16 0.12 #1 2 3 甲方为完成此项任务至多能提供48000加仑汽油. 而对于任何类型飞机，不论去轰炸那一个工厂，都必须有足够往返的燃料和100加仑备用燃料.

试问指挥官为执行任务应向三个工厂派遣每种类型的飞机个多少架，才能使成功的概率最大？ 解 设xij为i型飞机被派遣去j工厂执行任务的架数.

#

#

甲方的目标是希望事件“至少摧毁一个工厂”的概率最大. 这相当于希望事件“不摧毁任何工厂”的概率f最小. 我们有：

f(10.10)x11(10.20)x12(10.15)x13(10.08)x21(10.16)x22(10.12)x23

它不是线性的，为此将上式改写为

8

zlogfx11log0.9x12log0.8x13log0.85x21log0.92x22log0.84x23log0.88

于是，模型的目标函数为

z0.0457x110.0969x120.0704x130.0362x210.0656x220.0554x23

关于燃料的约束条件为：

24502480257024502480x11x12x13x21x2222233 232570x23100xij480003i1j1经过整理，即为

550x11580x12670x13400x21420x22480x2348000. 飞机数量约束：

xj131j40 ，x2j28

j13综上所述，本问题的线性规划模型为：

max z = 0.0457x110.0969x120.0704x130.0362x210.0656x220.0554x23 s.t. 550x11580x12670x13400x21420x22480x2348000 x11x12x1340 x21x22x2328

xij0， i1，2；j1，2，3.

6、（选址问题）设有A1、A2和A3三个原料产地，其原料要在工厂加工，制成成品后再在销地销售，A1与A2两地又是销地. 设4吨原料可以加工成1吨成品，A1与A2间距离为150公里，A2 与A3间距离为200公里，A1与A3间距离为100公里. 原料运费每万吨公里为3千元，成品运费每万吨公里为2.5千元。现考虑在这三个地点建厂：若在A2建厂，生产规模为每年生产的成品不能超过5万吨，而在A1或A3建厂，生产规模不受. 有关数据由表1-18给出.

表1-18

地点 （万吨/年） （万吨/年） 7 13 — （千元/万吨） 5．5 4 3 原料产量 成品销售量 成品加工费 A1 A2 A3

30 26 24 试问在那几个地点建厂，生产规模如何，才能使生产成本最小？（这里为简化问题，仅考虑原料费用、成品运费和成品加工费，其它如原料单价、建厂投资费等未加考虑.）

解: 在建立模型以前，让我们先来分析一下问题中所给数据是否产销平衡？

A1、A2和A3每年原料的生产量总和为80万吨，A1和A2每年对成品的销售量总和为20万吨，

9

由于每4吨原料可加工为1吨成品，所以产销平衡.

设xij为每年由产地Ai运往建厂地Aj的原料数量（万吨）（i1，2，3）；yjk为每年由建厂地

Aj运往销地Ak的成品数量（万吨）（i1，2，3；k1，2）.

第一组约束条件为：若在Ai地建厂，则其所具有的原料数量（本地生产的原料数量与其它两地运来的原料数量之和）应等于该地设厂生产的成品数量的4倍. 例如对A1来说，应有

30x21x31x12x134(y11y12)

上式中既出现x21又出现x12，初看起来是矛盾的. 但是在研究建厂规划时，事先并不能知道哪一个方向是合理的，只好把两种可能的方向都考虑进去. 由于目标函数是要求生产成本最小，因此在最优解中不可能产生对流运输. 类似地，有

26x12x32x21x23(y21y22)

24x13x23x31x324(y31y32)

第二组约束条件为：各地工厂运到销地的成品数应恰为销地的需求量：

y11y21y317

y12y22y3213 第三组约束条件为A2产地设厂的生产规模约束： y21y225 目标函数为

z5.5(y11y12)4(y21y22)3(y31y32) 3[150(x12x21)200(x23x32)100(x13x31)]

2.5[150(y12y21)200y32100y31]因此，本问题的线性规划模型为：

minz5.5y11380.5y12379y214y22253y31 503y32450x12450x21600x23600x32

300x13300x31 s.t. 4y114y12x21x31x12x1330 4y214y22x12x32x21x2326 4y314y32x13x23x31x3224 y11y21y317 y12y22y3213 y21y225

xij0， i,j 1，2，3，ij yjk0， j1，2，3； k1，2.

用单纯形法对此模型求解，若得最优解xij（i,j1，2，3；ij），yjk（j1，2，3；k1，2），则A1地设厂的生产规模为y11y12，A2地设厂的生产规模为y21y22，A3地设厂的规模为

**y31y32. 若Aj求得的生产规模为零，则在Aj地不设厂.

******

7、某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素. 现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如表1-19所示：

表1-19

10

饲 料 1 2 3 4 5 蛋白质（g） 3 2 1 6 18 矿物质（g） 1 0.5 0.2 2 0.5 维生素（mg） 0.5 1.0 0.2 2 0.8 价格（元/kg） 0.2 0.7 0.4 0.3 0.8 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案. 建立这个问题的线性规划模型.

解：用Xj（j=1.2…5）分别代表5中饲料的采购数，线性规划模型：

minz0.2x10.7x20.4x30.3x40.8x5st.　　3x12x2x36x4　+18x5　　700 　　x10.5x20.2x3+2x4x5　　30

　　0.5x1x20.2x3+2x4　0.8x5　100　　xj(j1,2,3,4,5,6)0

8、某医院护士值班班次、每班工作时间及各班所需护士数如表1-20所示. 每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要，建立线性规划模型.

1 2 3 4 5 6 表1-20 班次 工作时间 6:00～10:00 10:00～14:00 14:00～18:00 18:00～22:00 22:00～2:00 2:00～6:00 所需护士数（人） 60 70 60 50 20 30 .

解：设x1x2x3x4x5x6x表示在第i个时期初开始工作的护士人数，z表示所需的总人数，则

minzx1x2x3x4x5x6st.　x1x660　　x　1x270　　x2x360　　x3x450　　x4x520　　x5x630　　xi(i1,2.3.4.5.6)0

11

9、一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-21所示. 现有三种货物待运，书籍有关数据列于表1-22. 又为了船运安全，前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系. 具体要求：前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%. 问该货轮应装载A,B,C各多少件运费收入才最大？试建立这个问题的线性规划模型.

表1-21 最大允许载重量（t） 容积（m） 表1-22 每件体积每件重量运价 商品 数量（件） 3（m/件） （t/件） （元/件） A B C 600 1000 800 10 5 7 8 6 5 1000 700 600 3前舱 2000 4000 中舱 3000 5400 后舱 1500 1500 解：设用i=1，2，3分别表示商品A，B，C，j=1，2，3分别代表前，中，后舱，Xij表示装于j舱的i种商品的数量，Z表示总运费收入则：

maxz1000(x11x12x13)700(x21x22x23)600(x31x32x33)

st.　x11x12x13600

x21x22x231000 x31x32x33800

10x115x217x31400　　　10x125x227x325400　　　10x135x237x331500 　　　8x116x215x312000　　　8x126x225x323000　　　8x136x235x331500 　　　　8x116x215x310.158x126x225x328x6x235x33　　　130.158x126x225x328x6x215x31　　　110.18x136x235x33　　　xij0(i1,2.3.j1,2,3)10、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解.

12

（1）minz2x13x2 s.t. 4x16x26 2x12x24 x1,x20 解：

Z = 4

（2）maxzx1x2 s.t. 6x110x2120 5x110

3x28

解：如图：由图可得：

x*(10,6)T　；　Z*16

即该问题具有唯一最优解x*(10,6)T

（3）maxz3x12x2 s.t. 2x1x22 3x14x212 x1,x20

13

无可行解

（4）maxz5x16x2 s.t. 2x1x22 2x13x22 x1,x20

解：如图

由图知，该问题具有无界解。

11、将下述线性规划问题化成标准形式

（1）minz3x14x22x35x4

s.t. 2x1x22x3x42

14

x1x2x32x414 2x13x2x3x42

x1,x2,x30 , x4无约束

解：

maxz'3x14x22x35x'45x\"40x50xst.　-2x1x22x3x'4x\"4　　　　　26　　　x1x2x32x'42x\"4　+x5　　　14 　　-2x13x2x3x'4x\"4-x6　　　6x1，x2，x3，x'4，x\"4，x'5，x60

（2）minz2x12x23x3

s.t. x1x2x34

2x1x2x36 x10，x20，x3无约束

解：

maxz'2x1'2x23x'33x\"30x　　　2xx2x3x+x4　　6x1，x2，x'3，x\"3，x40'1'\"34st.　x1'x2x'3x\"3　　　　　4

12、对下述线性规划问题找出所有基本解，指出哪些是基本可行解，并确定最优解

（1）maxz3x1x22x3

St 12x13x26x33x49

8x1x24x32x510 3x1x60 xj0解：

(j1,,6)

123638140系数矩阵A：30003C620种组合002　　0＝（p1 p2 p3 p4 p5 p6) 01

1236B1P　P　P381454；∴0可构成基。B1123求B1的基本解，00

15

12（B，b）=833106409110＝000010001016/3 -7/6∴ y1=（0，16/3，-7/6，0，0，0）T

同理y2=（0，10，0，-7，0，0）T y3=（0， 3，0，0，7/2，0）T y4=（7/4，-4，0，0，0，21/4）T y5=（0，0，-5/2，8，0，0）T

y6=（0，0，3/2，0，8，0）T y7=（1，0，-1/2，0，0，3）T y8=（0，0，0，3，5，0）T y9=（5/4，0，0，-2，0，15/4）T

y10=（0， 3，-7/6，0，0，0）T y11=（0，0，-5/2，8，0，0）T

y12=（0，0，-5/2，3，5，0）T y13=（4/3，0，0，0，2，3/4）T

y14=（0，10，0，-7，0，0）T y15=（0， 3，0，0，7/3，0）T

y16=（0，0，3/2，0，8，0）T

基可行解：（每个x值都大于0），（y3，y6，y8，y12，y13，y15，y16） 最优解：（y3，y6， y15，y16） Zmax=3

[p2 p3 p4]，[p2 p3 p5]，[p3 p4 p5]，[p2 p4 p5]为奇异，∴只有16个基。

（2）minz5x12x23x32x4 x12x23x34x47 2x12x2x32x43 xj0(j1,,4)

2C46解：该线性问题最多有 1 ○2 ○3 ○3 ○4 ○5 ○6 ○

个基本解。

基本解 Z 基本可行解 最优解 X1 -4 X2 X3 X4 0 ∨ ∨ ∨ ∨ ∨ 11/2 0 2/5 0 -1/3 0 0 0 0 1/2 11/5 0 0 2 11/6 0 2 1 -1/2 0 0 1 13、设某线性规划问题的约束系数矩阵A和右端常数向量b分别为

103561 A21413，b4.

312042

16

试问x1,x2,x5所对应的列向量能否构成基？若能，写出B,N，并求出B所对应的基本解.

解：

1基的定义 B2011635 0 ∴X1 X2 X3所对应的列向量可以构成基 43106 B 由 X1 X2 X3 列向量构成 = 213 31435 N 由 非基变量对应的向量构成 = 41 20106１100-13/5 010　　　37/5（B，b）= 213　４3/5314２001∴B对应的基解：（-13/5，37/5，0，0，3/5）

14、分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基本可行解对应图解法中可行域的哪一顶点.（1）maxz10x15x2

s.t. 3x14x29

5x12x28

x1,x20

解：（1）

由图知：

x*(1,3/2)T；　Z*35/2;

单纯形法：化为标准形如下：

17

maxz10x15x2st.　　3x14x2x39　　　5x12x2x48　　xi(i1,2,3,4)0

C CB XB 0 X3 0 XR 检验数 0 X3 10 X1 检验数 5 X2 10 X1 检验数 10 X1 3 5 10 0 1 0 0 1 0 5 X2 4 2 5 14/5 2/5 1 1 0 0 0 X3 1 0 0 1 0 0 5/14 -1/7 -5/14 0 XR 0 1 0 -3/5 -1/5 -2 -3/14 3/7 -25/14 b 9 8 0 21/5 8/5 -16 3/2 0 -35/2 所以：x*(1,3/2)T；　Z*35/2; 其中：

对应（0,0,9,8)TA(0,0)对应（8/5,0,21/5,0)TB(8/5,0)对应T 1,3/2,0,0)（C(1,3/2)

（2）maxz2x1x2

s.t. 3x15x215 6x12x224 x1,x20 解：

∴A点最大 Z= 8

maxz2x1x20x30x4化为标准形：

st.　　3x15x2x3　　　15　　6x12x2x4　　24　　xi(i1,2,3,4)0

18

C 0 0 2 X3 3 X4 6 2 X3 0 X1 1 0 -1 5 2 -1 4 -1 0 1 0 0 1 0 0 0 1 0 1/6 b 15 24 0 4 CB XB X1 X2 X3 X4 检验数 -1/2 3 -1/3 -8 1/3 0

0点（0，0，15，24）

A点（4，0，3，0） Zmax=8

检验数

15、上题（1）中，若目标函数变为maxzcx1dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优.

解1）要使A（0，0）成为最优解则需C0且d0； 2）要使B（8/5，0）成为最优解则

C0且d=0或C>0且d<0或C/d5/2且Cd>0； 3）要使C（1，3/2）成为最优解则

-5/2-C/d-3/4且Cd>0；即5/2C/d3/4且Cd>0；

4）要使D（0，9/4）成为最优解则 C<0且d>0或C=0，d>0

16、用单纯形法求解下列线性规划问题 （1）maxz2x1x2x3

s.t. 3x1x2x360

x1x22x310 x1x2x320

xj0(j1,2,3)

解：化为标准型：

maxzx21x2x3st.　　3x1x2x3x　　　604 　　x1x22x　　10 3x5　　　　x1x2x　　　　x6　203　　xj(i1,2,3,4,5,6)0C CB XB 0 X4 0 X5 0 X6 检验数 0 X4 2 X1 0 X6 检验数

2 X1 3 1 1 2 0 1 0 0 -1 X2 1 -1 1 -1 4 -1 2 1 1 X3 1 2 -1 1 -5 2 -3 -3 0 X4 1 0 0 0 1 0 0 0 0 X5 0 1 0 0 -3 1 -1 -2 0 X6 0 0 1 0 0 0 1 0 b 60 10 20 0 30 10 10 -20 19

0 X4 2 X1 -1 X2 检验数 0 1 0 0 0 0 1 0 1 1/2 -3/2 -3/2 1 0 0 0 -1 1/2 -1/2 -3/2 -2 1/2 1/2 -1/2 10 15 5 -25 x*(15,5，0)T；　Z*25;

（2）maxz2x13x25x3 s.t. 2x12x23x312

x12x22x38 4x16x316

4x23x312 xj0,解：

(j1,2,3)

maxz2x13x25x30x40x50x60x7st.　　2x12x23x3x4　　　12　　x12x22x3　　x5　　8　　4x16x3　　　　x6　　16　　　　4x23x3　　　　x712　　xi(i1,2,3...7)0C 0 0 0 0 0 0 5 0 0 0 5 3 0 2 5 3

2 X4 2 X5 1 X6 4 X7 0 2 X4 0 X3 2/3 X7 -2 X4 1 X5 2/3 X3 2/3 1/6 3 2 2 0 4 3 2 0 4 0 0 0 0 0 0 0 1 5 3 2 6 3 5 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 2/3 -1 3/4 0 X6 0 0 1 0 0 -1/2 -1/3 1/6 -1/2 -5/6 -1/4 -1/12 1/6 -1/8 0 X7 0 0 0 1 0 0 0 0 1 0 b 12 8 16 12 0 4 3/8 3/8 4 -40/3 CB XB X1 X2 X3 X4 X5 检验数 X5 -1/3 2 检验数 -4/3 3 -1/2 2 -1/2 2/3 0 1/4 1/4 1/2 8/3 1 1 2 X2 -1/2 1 X4 0 X1 1 X3 0 X2 0 检验数 -11/24 -3/4 -49/3 -1/8 1/4 -3/16 -3/4 1 -1/8 3/2 20

-2/3 -1/8 检验数 0 0 0 0 -1/4 -7/16 -5/8 -33/2 x*(1,3/2，1，1，0，0)T；　Z*33/2;

（3）maxz3x15x2

s.t. x14

2x212 3x12x218

x1,x20

解：标准型： maxz3x15x23st.　x1　x3　　　　4　　　　2x2　　x4　　12 　　3x12x2　　x5　18　　xi(i1,2,3,4,5,)0C CB XB 0 X3 0 X4 0 X5 检验数 X3 X2 X5 检验数 X3 X2 X1 检验数 3 X1 1 0 3 3 1 0 3 3 0 0 1 0 5 X2 0 2 2 5 0 1 0 0 0 1 0 0 0 X3 1 0 0 0 1 0 0 0 1 0 0 0 0 X4 0 1 0 0 0 1/2 -1 -5/2 1/3 1/2 -1/3 -3/2 0 X5 0 0 1 0 0 0 1 0 -1/3 0 1/3 -1 b 4 12 18 0 4 6 6 -30 2 6 2 -36 x*(2，6)T；　Z*36;

（4）minzx1x2x3x4x5x6 s.t. x1x46x69

3x1x24x32x62

x12x3x52x66

xj0,(j1,2,,6)

解：标准型

21

maxz'x1x2x3x'4x\"4x'5x\"5x'6x\"6x7Mx8Mx90x10st.　x1x'4x\"4x'6x\"6x7　　　　　9　　　3x1x24x32x'62x\"6x8　　　2　　x12x3x5x2x62x6x9　　6　　　4x23x3　　　　　　　　　　x10　12x1，x2，x3，x'4，x\"4，x'5，x\"5，x'6，x\"6，x7，x8，x9，x100 C CB XB -1 X1 1 3 1 0 5M-1 0 1 0 0 0 1 X2 0 1 . 4 M+1 -1/3 1/3 -1/3 4 4/3 -2/3M -M X7 -1 -1 0 X1 X3 X10 0 1 0 0 0 -1/5 1/5 -1/10 43/10 -1/5M +11/10 -1 X3 0 -4 2 3 -1-2M 4/3 -4/3 10/3 3 14/5M -7/3 0 0 1 0 0 1 0 0 0 -1 0 0 0 2/5 -2/5 -3/10 9/10 2/5M -17/10 -2/5 2/5 3/10 -9/10 -2/5M +17/10 -1 X41 0 0 0 ‘ '\"5'\"

1 X40 0 0 “ -1 X50 0 -1 0 M+1 0 0 -1 0 M-1 ‘ 1 X50 0 1 0 1+M 0 0 1 0 M+1 “ -1 X61 2 2 0 5M-1 1/3 2/3 4/3 0 5/3M -1/3 -1/5 6/5 2/5 -6/5 3/5 -1/5M ‘ 1 X6“ -M -M X7 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 X8 0 1 0 0 0 -1/3 1/3 -1/3 0 -5/3M +1/3 -1/5 1/5 -1/10 3/10 -6/5M -M X9 0 0 1 0 0 0 0 1 0 0 -2/5 2/5 3/10 -9/10 -7/5M 0 X10 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 b -M X7 -M X8 -M X9 0 X10 检验数 -M X7 -1 0 X1 X10 -M X9 检验数 -1 -1 -2 -2 0 1-5M -1/3 -2/3 -4/3 0 -5/3M +1/3 1/5 -6/5 -2/5 6/5 1/5M -3/5 9 2 6 12 17M 28/3 2/3 16/3 12 -41/3M -2/3 31/5 14/5 8/5 36/5 -31M/5 -22/5 M-1 1-M 1 0 0 0 -1 0 0 0 M-1 1-M 检验数 M-1 1-M

（5）maxz6x12x210x38x4 s.t. 5x16x24x34x420

3x13x22x38x425

4x12x2x33x410

xj0,

(j1,2,3,4)

解：标准化：

maxz6x12x210x38x4st.　　5x16x24x34x4　x520　　5x13x22x3　8x4x625 　　4x12x2x3　3x4　x710　　xj(j1,2,3,4,5,6,7)0

22

C CB XB 0 X5 0 X6 0 X7 检验数 0 X5 0 X6 10 X3 检验数 0 X5 2 X2 10 X3 检验数 6 X1 5 3 4 6 21 -5 4 -34 11 -5 -6 76 2 X2 6 -3 -2 2 -2 1 -2 22 0 1 0 0 10 X3 -4 2 1 10 0 0 1 0 0 0 1 0 8 X4 -4 8 3 8 8 2 3 -22 12 2 7 -66 0 X5 1 0 0 0 1 0 0 0 1 0 0 0 0 X6 0 1 0 0 1 0 0 0 2 1 2 -22 0 X7 0 0 1 0 4 -2 1 -10 0 -2 -3 34 b 20 25 10 0 60 5 10 -100 70 5 20 -210 '0因此问题的解无界。 由表可得， 7且pk

（6）minzxx1x2x3

s.t. x14x42x65

x22x43x5x63 x32x45x56x65

xj0,‘

解：化为:标准形：Z=-Z

‘maxzxx1x2x3(j1,2,,6)T

st.　x14x4-2x6　　　 5　　 x22x4　3x5+x6　 3 　　 x3　2x4　-x5　6x6　5　　xi(i1,2,3,4,5,6)0（I） C -x -1 0 1 0 0 -1 0 0 0 1 0 -4 2 2 0 0 0 -2 b 5 3 5 CB XB X1 X2 X3 X4 -X X1 1 -1 -1 X2 0 X3 0 0 X5 X6 -3 1 -5 6 检验数 4-4x -8 7-2x 5x+8 44x0x1x7/2 如图： 72x044x72xx2/3 23

1. X≥7/2 时，检验数≤0 ，∴最优解：（5，3，5，0，0）T 2. 1≤X<7/2时，4-4X<0,-2X+7>0

由（I）得： C -x -1 0 1 0 0 -1 1/3 -1/6 1/6 0 X4 -10/3 5/3 1/3 0 X5 -5/3 -13/6 -5/6 0 X6 0 0 1 20/3 13/6 5/6 20X/3+13/6 b CB XB X1 X2 X3 -X X1 1 -1 0 X2 0 X6 0 0 检验数 X/3-7/6 -10X/3+5/3 -5X/3-13/6 0 x*(20/313/，6，0，0，0，5/6)T；　Z*20X/313/6;

3. X <-3/2时 4-4X>-2X+7>0

C -x -1 2 1/2 -1 -1 0 0 0 1 0 1 0 0 0 -6 -3/2 -2 0 X6 0 5 11 2 11X+2 1/2 3/2 b CB XB X1 X2 -X X1 1 -1 -1 X2 0 X3 0 0 X3 X4 X5 检验数 2x-2 0 -6X-2 5 检验数>0，列系数≤0，所以解无界。

4.-3/2≤X<1； -2X+7>4-4X>0 C -x -1 0 1 0 -1 0 0 1 0 X4 -10/3 5/3 1/3 0 X5 -5/3 -13/6 -5/6 0 X6 0 0 1 20/3 13/6 5/6 20X/3+13/6 b CB XB X1 X2 X3 -X X1 1 -1 -1 X2 0 X6 0 检验数 X/3-7/6 -10X/3+5/3 -5X/3-13/6 判断检验数的符号： 10x/35/30x1/25x/313/60x13/10 10x/35/35x/313/6x2.3

24

1)1/2≤X< 1 ，所有检验数 <0

∴x(20/3,13/6,0,0,0,5/6)；　Z20X/313/6;（1/2≤X< 2）-1.3≤X<1/2时 表（A） C -x -1 2 3/5 -1/5 -1 X3 0 1/5 0 0 0 0 0 -6 -2/5 -6X 0 X6 00 11 11 2/5 0 11X b CB XB X1 X2 -X X1 1 0 0 X4 0 X6 0 0 X4 X5 *T*-1/10 1 -13/10 00 13/10 检验数 2X-1 -1 对-6X讨论，令-6X=0  X=0 1 0≤X<1/2时， 检验数<0 ○

∴x(11,0,0,13/10,0,2/5)；　Z11X;（0≤X≤1/2）

2-1.3≤X<0时， -6X>0 ○

又 X5列的系数< 0 ，所以解无界 3） -1.5≤X<-1.3时，

*T* 同表（A）

-6X>0 ，又 X5的列的系数<0，所以解无界

（7）maxzx16x24x3

s.t. x12x22x313

4x14x2x320

x12x2x317

x11,x22,x33

解：化为标准形：

25

maxzx16x24x3Mx10Mx11Mx12st.　　x12x22x3x4　　　　　　　　13　　4x1x2x3　　　　x5　　　　　　　20　　x12x2x3　　　　　x6　　　　　　17　　x1　　　　　　　　　　x7x10　　　　1　　　x2　　　　　　　　　　x8x11　　　2　　　　x3　　　　　　　　　　　x9x123　　xi0(i1,2,3...11) C CB XB 0 X4 0 X5 0 X6 -M X10 -M X11 -M X12 检验数 0 X4 0 X5 0 X6 -M X10 6 X2 -M X12 检验数 0 X4 0 X5 0 X6 -M X10 6 X2 4 X3 检验数 0 X4 0 X5 0 X6 1 X1 6 X2 4 X3 检验数 0 X8 0 X5 0 X6

1 X1 -1 4 1 1 0 0 1+M -1 4 1 1 0 0 1+M -1 4 1 1 0 0 1+M 0 0 0 1 0 0 0 0 0 0 6 X2 2 -4 2 0 1 0 6+M 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 4 X3 2 1 1 0 0 1 4+M 2 1 1 0 0 1 4+M 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 X4 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1/2 2 -1 0 X5 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 X6 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 00 1 0 0 0 0 0 0 1 26

0 X7 0 0 1 0 0 0 -M 0 0 0 -1 0 0 -M 0 0 0 -1 0 0 -M -1 4 1 -1 0 0 1 -1/2 2 2 0 X8 0 0 0 0 -1 0 -M 2 -4 2 0 -1 0 6 2 -4 2 0 -1 0 6 2 -4 2 0 -1 0 6 1 0 0 0 X9 0 0 0 0 0 -1 -M 0 0 0 0 0 -1 -M 2 1 1 0 0 -1 4 2 1 1 0 0 -1 4 1 5 -1 -M X10 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 10 1 -4 -1 1 0 0 — 1/2 -2 -2 -M X11 0 0 0 0 1 0 0 -2 4 -2 0 1 0 -6-M -2 4 -2 0 1 0 -6-M -2 4 -2 0 1 0 — -1 0 0 -M X12 0 0 0 0 0 1 0 0 0 0 0 0 1 0 -2 -1 -1 0 0 1 -4-M -2 -1 -1 0 0 1 — -1 -5 1 b 13 20 17 1 2 3 9 26 13 1 2 3 3 25 10 1 2 3 4 21 9 1 2 3 2 29 5 1 X1 6 X2 4 X3 检验数 0 X8 0 X5 0 X7 1 X1 6 X2 4 X3 检验数 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1/2 0 -3 1/4 3 -1/2 -1/2 1/4 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1/4 -1 1/2 1/2 1/4 0 -2 -1 -1/2 0 4 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 -1 -2 3/4 6 -1/2 -1/2 3/4 -1 0 1 1/2 0 — 0 0 -1 0 0 0 — 0 1/2 0 — -1 0 0 0 0 0 — 0 -1 1 — -3/4 -6 1/2 1/2 -3/4 1 — 1 4 3 13/4 24 5/2 7/2 21/4 3 -47 即：x*(7/2,21/4，3)T；　Z*47;

为最优解，但该问题具有无穷多最优解

（8）maxzx1x2x33x4x5x63x7 s.t. 3x3x5x66 x22x3x410 x1x60 x3x6x76 xj0,

(j1,2,,7)

解：化为标准形：

maxzx1x2x33x3x5x63x7Mx８Mx9Mx10Mx11st.　　3x3x5x6x８　　　6　　x22x3　x4　　x9　　10　　　x1x6　　　　x10　0　　x3x6x7　　　　x11　6　　　xj(i1,2,...11)0

C CB XB -M X8 -M X9 -M X10 -M X11 检验数 1 X3 -M X9 -M X10

1 X1 0 0 -1 0 1-M 0 0 -1 -1 X2 0 1 0 0 M-1 0 1 0 1 X3 3 2 0 1 6M+1 1 0 0 -3 X4 0 -1 0 0 -M-3 -1 0 1 X5 1 0 0 0 1+M 1/3 -2/3 0 27

-1 X6 1 0 1 1 -1+3M 1/3 -2/3 1 -3 X7 0 0 0 1 3+M 0 0 0 -M X8 1 0 0 0 0 1/3 -2/3 0 -M X9 0 1 0 0 0 0 1 0 -M X10 0 0 1 0 0 0 0 1 -M X11 0 0 0 1 0 0 0 0 b 6 10 0 6 2 6 0 -M X11 检验数 1 X3 -1 X2 -M X10 -M X11 检验数 1 X3 -1 X2 -M X10 1 X6 检验数 1 X3 -1 X2 1 X5 -1 X6 检验数 0 1-M 0 0 -1 0 1-M 0 0 -1 0 1-M 1 -2 -2 -1 -1 0 M-1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 -M-3 0 -1 0 0 -4 0 -1 0 0 -4 0 -1 0 0 -4 -1/3 2/3-M 1/3 -2/3 0 -1/3 — 1/2 -1 1/2 -1/2 1/2M-1 0 0 1 0 0 2//3 M-1/3 1/3 -2/3 1 2//3 5/3M-2 0 0 0 1 0 0 0 0 1 0 1 M-3 0 0 0 1 M-3 -1/2 1 -3/2 3/2 — 1 -2 -3 -3 -1/3 — 1/3 0 -2/3 -1/3 — 1/2 -1 1/2 -1/2 — 0 0 1 0 — 0 0 0 1 0 0 — 0 1 0 0 — 0 1 0 0 — 0 0 0 0 1 0 0 0 0 1 0 0 -1 2 2 1 — 1 0 0 0 0 1 0 -1/2 1 -1/2 3/2 — 1 -2 -3 0 — 4 2 6 0 4 0 10 -6 6 0 -2 -12 0 x*(0,2,6,0,12,0,0))T；　Z*4;

17、分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解

（1）maxz2x1x22x3 s.t. x1x2x36 2x1x32 2x2x30 x1,x2,x30 解：标准形： 1 ○

maxz2x1x22x3Mx7Mx8Mx9st.　x1x2x3x4　x7　　6　　　x1x3　　x5x8　　2　　2x2x3x6　　　　x9　0　　xj(i1,2,3...9)0C 2 -1 X2 1 0 2 0 0 1 0 2 X3 1 1 -1 3/2 1 -1/2 0 X4 -1 0 0 -M -1 0 0 0 X5 0 -1 0 -M 0 -1 0 -M 28

0 X6 0 0 -1 -M 1/2 0 -1/2 -M -M X7 1 0 0 0 1 0 0 X8 0 1 0 0 0 1 0 0 -M X9 0 0 1 0 0 1/2 — b 6 2 0 2 0 CB XB X1 -M X7 1 -M X8 -1 -M X9 0 检验数 2 -M X7 1 -M X8 -1 -1 X2 0 2 检验数

-1+3M 2+M -1/2 6 5/2M+3/2 -M 1/2M-1/2 0 -M X7 5/2 2 -1 2 2 -1 X3 -1 X2 -1 X1 1 X3 0 X2 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 -1 0 0 -M 3/2 -1 -1/2 1/2 0 -1/2 1/5 1/5 -2/5 -6/5 1 0 0 0 -3/2 -1/2 3 1 1/2 — 0 1/2 — 2 1 检验数 5/2M+7/2 0 3/2M 1/2M -2/5 3/5 -2/5 -2/5 -1/5 -1/5 7/5 -3/5 2/5 -3/5 -1/5 6/5 2/5 2/5 1/5 1/5 — — -1/5 16/5 2/5 — 8/5 检验数 由表可知此题解无界。 2得一辅助问题： ○

maxwMx7Mx8Mx9st.　x1x2x3x4　x7　　6　　　x1x3　　x5x8　　2 　　2x2x3x6　　　　x9　0　　xj(i1,2,3...9)0 C -1 -1 -1 -1 -1 0 -1 0 0 0 0 0 0 X7 1 X8 -1 X9 0 0 X7 1 X8 -1 X2 0 0 0 1 0 2 3 0 0 1 0 0 1 0 0 1 0 0 1 1 -1 1 3/2 1 5/2 0 1 0 0 0 1 0 0 0 X4 -1 0 0 -1 -1 0 -1 -1 0 0 -1 0 X5 0 -1 0 -1 0 -1 0 -1 3/2 -1 3/2 0 X6 0 0 -1 -1 1/2 0 1/2 1/2 0 — 1/5 -1 X7 1 0 0 0 1 0 0 1 0 0 -1 X8 0 1 0 0 0 1 0 0 1 1/2 — -1 X9 0 0 1 0 0 1/2 6 2 0 2 0 b CB XB X1 X2 X3 检验数 -1/2 6 -1/2 0 -1/2 0 检验数 -3/2 0 1/2 — 2 1 X7 5/2 0 X3 -1 X2 -1 X1 1 X3 0 X2 0 0 -3/2 -1/2 3 -1/2 -1/2 0 检验数 5/2 0 -2/5 3/5 2/5 -3/5 -1/5 6/5 2/5 2/5 -1 -1 -1/5 16/5 2/5 -1 8/5 0

-2/5 -2/5 1/5 0 0 0 -1/5 -1/5 -2/5 1/5 1/5 检验数 ********其最优解为x16/5,x216/5,x38/5,x4x5x7x8x90;w*0;其原问题的初始基本解可行解x(6/5,16/5,8/5,0,0,0)C 2 -1 2 2 X1 1 X3 0 X2 0 0 -1 0 0 1 -3 2 0 1 0 3 0 0 X5 0 X6 1/5 b CB XB X1 X2 X3 X4 T-2/5 3/5 -2/5 -2/5 1/5 -1/5 -1/5 -2/5 4/5 — — 检验数

29

由表知此题属于解无界

（2）minz4x1x2

s.t. x1x23 4x13x2x36 x12x2x44

(j1,,4)

解：大M法，先化为标准形：Z‘=-Z

‘maxz4x1x20x30x4Mx5Mx6 xj0,st.　x12x4x4　　　 4　　 x1x2　 x5　 3　　 4x1　3x2-x3　x6　6　　xi(i1,2,3,4,5,6)0C 0 -4 X4 1 -1 X2 2 1 3 5/4 1/4 3/4 1 0 0 0 1 0 0 0 0 X3 0 0 -1 -M 1/4 1/4 -1/4 1/5 1/5 -2/5 0 1 0 0 0 X4 1 0 0 0 1 0 0 0 4/5 -1/5 -3/5 1 -1 -1 -3 -M -M b X5 X6 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 4 3 6 9M 5/2 3/2 3/2 3M/2+6 2 1 0 M+2 1 5 2 9 CB XB X1 -M X5 1 -M X6 4 检验数 0 -4 -1 -4 -1 0 -4 X4 0 X1 1 0 X2 0 X1 1 0 X2 0 X3 0 X1 1 0

5M-4 4M-1 -M X5 0 检验数 M/4+2 M/4-1 -M X5 0 检验数 M/5-7/5 -M/5-8/5 0 ∴ 原问题唯一最优解

二阶段法：引入人工变量 X5 X6 得原问题的一个辅助问题：

maxwx5x6st.　x12x4x4　　　 4　　 x1x2　 x5　 3 　　 4x1　3x2-x3　x6　6　　xi(i1,2,3,4,5,6)0

30

C 0 0 X4 1 0 2 1 3 4 0 X3 0 0 -1 -1 0 X4 1 0 0 0 1 0 0 4/5 -1 -1 X5 X6 0 1 0 0 0 1 0 0 0 0 0 1 0 b 4 3 6 9 5/2 3/2 3/2 3/2 2 1 0 1 1 5 2 0

CB XB X1 X2 -M X5 1 -M X6 4 检验数 0 -4 -1 -4 -1 0 -4 5 X4 0 X1 1 0 X2 0 X1 1 0 X2 0 X3 0 X1 1 0 5/4 1/4 1/4 1/4 1/4 1/4 1 0 0 0 1 0 0 0 1/5 1/5 1/5 0 1 0 0 -M X5 0 检验数 3/4 -1/4 0 -M X5 0 检验数 -1/5 1 -1/5 0 1 -1 -1 -1 -2/5 -3/5 0 检验数 ******其最优解为x12,x21,x35,x4x5x60;w*0;其原问题的初始基本解可行解x(2,1,5,0,0,0) C -1 0 -4

（3）minz2x13x2x3

s.t. x14x22x38 3x12x26 x1,x2,x30 解： 标准形：

-4 -1 X2 0 X3 0 X1 1 0 0 1 0 0 0 1 0 0 0 0 -1 1 -1 -3 b 5 1 2 9 CB XB X1 X2 X3 X4 T检验数 minz'2x13x2x3Mx7Mx8st.　x14x22x3x4x7　　8　　3x12x2x5　x8　　6　　xj(j1,2,3...8)0

31

C -2 3 X2 4 2 1 0 1 0 0 1 0 0 -1 X3 2 0 1/2 -1 3/5 -2/5 -18/5 0 -2 -1 0 X4 -1 0 -M -1/4 1/2 -3/10 1/5 13/10 0 1 0 0 X5 0 -1 -M 0 -1 0 0 0 0 0 0 0 -M 1 0 0 1/4 — -M X8 0 1 0 0 0 b 8 6 2 2 4/5 3 4 CB XB X1 -M X7 1 -M X8 3 检验数 3 -2-4M X2 1/4 X6 X7 6M+3 2M-1 -M X8 5/2 检验数 3 -2 3 0 X2 0 X1 1 0 X2 5/2 X4 5 — -1/2 1 5/2M-11/4 0 -M-5/2 1/2M+3/4 -M 1/10 0 -2/5 0 — -2 3/2 0 0 0 -1/2 0 3/10 -1/10 9/5 -1/5 2/5 — 0 -1 -M — 1/2 2 -M 检验数 检验数 由表知此题解无界； （2）两阶段法：

maxzx7x8st.　x14x22x3x4x7　　8　　3x12x2x5　x8　　6　　xj(j1,2,3...8)0C -1 -1 0 -1 0 0 0 X7 1 X8 3 4 X2 1/4 X8 5/2 X2 0 X1 1 0 0 4 2 6 1 0 1 0 0 0 2 0 2 1/2 -1 3/5 -2/5 0 0 X4 -1 0 -1 -1/4 1/2 -3/10 1/5 0 0 X5 0 -1 -1 0 -1 0 0 0 0 0 0 0 -1 1 0 0 1/4 — -1 X8 0 1 0 0 0 8 6 2 2 4/5 b CB XB X1 X2 X3 X6 X7

检验数 -1/2 1 检验数 5/2M-11/4 0 -M-5/2 1/2M+3/4 -M 1/10 0 -2/5 0 0 0 3/10 -1/10 9/5 -1/5 2/5 -1 -1 检验数 *******其最优解为x14/5,x29/5,x3x4x5x7x80;w*0;

C 3 -2 3 0 -2 X2 0 X1 1 0 3 1 0 0 0 0 -1 3/5 -2/5 0 -2 -1 0 X4 1/5 0 1 0 0 X5 0 X6 b 9/5 4/5 3 4 CB XB X1 X2 X3 -3/10 1/10 0 -2/5 0 0 0 0 -1/2 0 -2 3/2 检验数 -18/5 13/10 — X2 5/2 1 X4 5 — 检验数

由表知此题为解无界；

32

（4）maxz10x115x212x3

s. 5x13x2x39 5x16x215x315 2x2x2x35 x1,x2,x30 解：化为标准形：

maxz10x115x212x3Mx7st.　　5x13x2x3　x4　　　9　　5x16x215x3x5　　15 　　2x1x2x3x6x7　　5　　xj(i1,2,3...7)0C 0 0 0 10 X4 5 X5 -5 15 X2 3 6 1 3/5 9 -1/5 — 39/80 9/16 — 12 X3 1 15 1 1/5 16 3/5 3/5M 0 1 0 0 X4 1 0 0 1/5 1 -2/5 — 15/80 1/16 — 0 X5 0 1 0 0 0 1 0 0 1/16 — 0 X6 0 0 -1 0 0 -1 -M b X7 0 0 1 0 0 1 0 0 1 9 15 5 9/5 24 2/5 15/10 3/2 1/2 CB XB X1 -M X7 2 10 X1 1 X5 0 0 -M X7 0 10 X1 1 12 X3 0 -M X7 0

2M+10 M+15 12+M 0 -M 0 — 0 0 -1/80 0 -43/80 0 -35/80 -3/80 -1 0 — 0 33

18、某一求目标函数极大值的线性规划问题，用单纯形法求解得最终单纯形表1-24. 其中常数1,2,3,d和1未知，且不含人工变量. 问应如何这些参数，使得下列结论成立：

（1）现有解为唯一最优解；

（2）现有解为最优解，但目标函数无界； （3）存在可行解，但目标函数无界. 解：（1）10　　；b0 （2）10　，10,20 （3）10,10,20,d0

表1-24 xB x1 x2 x3 x3 -1 3 1 x4 1 -4 0 x5 2 3 0 z x4 0 1 0 0 x5 0 0 1 0 b 4 1 d 1 -2 0 19、已知某线性规划问题用单纯形法计算时，得到的初始单纯形表及最终单纯形表如表1-25. 请将表中空白处数字填上。

表1-25

2 -1 1 0 0 0 cB xB x1 x2 x3 x4 x5 x6 x4 3 1 1 1 0 0 0 x5 1 -1 2 0 1 0 0 x6 1 1 -1 0 0 1 0 z 0 2 -1 2 -1 1 0 0 -1 0 -2 b 60 10 20 0  x4 x1 x2 z  1 0 0 1/2 1/2 -1/2 1/2 解： C 0 0 0 0 2 0 0 2 -1

2 -1 1 -1 1 -1 4 -1 2 1 0 0 1 1 1 2 -1 1 -5 2 -3 -3 1 1/2 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 -3 1 -1 -2 -1 1/2 0 X6 0 0 1 0 0 0 1 0 -2 1/2 b 60 10 20 30 10 10 10 15 5 34

CB XB X1 X2 X3 X4 3 X5 1 X6 0 2 X4 0 X1 1 X6 0 0 X4 0 X1 1 X2 0 X4 X5 -3/2 0 -1/2 1/2

0 0 -3/2 0 -3/2 -1/2 -25 20、已知某线性规划问题用单纯形法迭代时，得到的中间某两步的单纯形表如表1-26. 请将表中空白处的数字填上.

C 0 0 0 -1 1 0

21、已知某线性规划问题的目标函数为maxz5x13x2，约束形式为≤，设x3,x4为松弛变量，用单纯形法计算时某一步的表格如表1-27所示.

（1）求a～g的值；

（2）表中给出的解是否为最优解. 表1-27 5 3 0 0 0 0 表1-26 2 -1 1 0 0 0 cB 5 xB x1 x2 x5 x6 z x2 x3 x4 x5 0 1 0 x6 0 0 1 0

b 2/3 1 0 1/3 -4/3 0 5 02/3 5/3 0 4 -5/3 -1/3 0 4 -5/3 8/3 14/3 29/3

0 8/41  xx

 解： 2 X2 2/3 X5 -4/3 X6 5/3 -1/3 X2 2/3 -1 1 0 0 0 1 1 0 5 4 0 1 0 0 0 1/3 2/3 -5/3 1/3 2/15 3/15 0 X5 x0 1 0 0 0 1/5 0 X6 0 0 1 0 0 0 b 8/3 14/3 29/3 8/3 14/15 84/15 CB XB X1 X2 X3 X4 -4 -5/3 X3 -4/15 0 X6 41/15 0 44/15 0 -33/15 -4/5 1 -1/5 0

cB xB x1 x2 x3 x4 x3 c 0 1 1/5 0 解5 x1 d e 0 1 ：

b 2 a -10 z b -1 f g 35

x1,x3是基，c=0,d=15[0051]bb0[025a]10a2 0[01/551]gg50[0150]ff03[005e]1e4/5

22、已知某线性规划问题的目标函数为maxz28x4x52x6，约束条件为≤，设

x1,x2,x3为松弛变量，用单纯形法计算时某一步的表格如表1-28所示.

（1）求a～g的值；

（2）表中给出的解是否为最优解.

表1-28

0 0 0 28 1 2 b a 5 0 cB xB x1 x2 x6 3 0 2 x2 6 d 0 28 x4 0 e z b c x3 -14/3 2 x4 x5 x6 0 0 1 0 1 52 0 -1 1 0 0 f 0 g -14 解：由表知：（1） d=1，e=0，b=-6，f=1/3，g=0，a=7；

（2）由表知所有70,所以表中给出的是最优解。

23、线性规划问题maxzcx,Ax=b，x≥0，设x为问题的最优解. 若目标函数中用c代

0

*

替c后，问题的最优解变为x，求证

(cc)(xx)≥0

**0*

解：

∵x0为问题的最优解maxzcx,∴cx0cx*∴c(x*x0)0(1)∵x*为问题maixzc*x的最优解∴cxcx***0

即c*(x*x0)0(2)由（2）－（）得：1(c*c)(x*x0)0即得证。

*

24、线性规划问题maxzcx，Ax=b，x≥0，如x是该问题的最优解，又0为某一常

数，分别讨论下列情况时最优解的变化.

（1）目标函数变为maxzcx； （2）目标函数变为maxz(c)x；

36

（3）目标函数变为maxzcx，约束条件变为Axb.

解（1）

maxzλcx, ∵x*是maxzcx的最优解，即z*x*c 又∵λ>0为某一常数∴λz*＝x*λc 即x*使问题maxw=λcx的最优解 即maxzλcx的最优解为x*(2)maxz(cλ)xz*=(c+λ)x*cx*+λx*

37