运筹学习题选解
第一章 线性规划及单纯形法
1、 （生产计划问题） 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表 1-12.. 若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低. 试建立线性规划模型.
解: 现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型.
（1）设工厂第j 季度生产产品j x 吨
首先，考虑约束条件：第一季度末工厂需交货20吨，故应有201≥x ；第一季度末交货后积余（201-x ）吨；第二季度末工厂需交货20吨，故应有202021≥+-x x ；类似地，应有
3034021≥+-+x x x ；第四季度末供货后工厂不能积压产品，故应有10704321=+-++x x x x ；又考虑到工厂每个季度的生产能力，故应有j j a x ≤≤0.
其次，考虑目标函数：第一季度工厂的生产费用为15.01x ，第二季度工厂生产的费用包括生产费用142x 及积压产品的存贮费)20(2.01-x ；类似地，第三季度费用为
)40(2.03.15213-++x x x ，第四季度费用为)70(2.08.143214-+++x x x x . 工厂一年的费用
即为这四个季度费用之和. 整理后，得下列线性规划模型： min 268.145.154.146.154321-+++=x x x x z s .t . 21x x + 40≥ 321x x x ++ 70≥ 804321=+++x x x x
30201≤≤x ，4002≤≤x ，2003≤≤x ，1004≤≤x .
（2）设第j 季度工厂生产的产品为j x 吨，第j 季度初存贮的产品为j y 吨（显然，01=y ）. 因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：
2120y x =-， 32220y x y =-+， 43330y x y =-+， 1044=+x y ；
同时，每季度的生产量不能超过生产能力：j j a x ≤；而工厂四个季度的总费用由每季的 生产费用与存贮费用组成，于是得线性规划：
8.142.03.152.0142.00.15x y x y x y x z ++++++=
s .t . 2021=-y x 20322=-+y x y
30433=-+y x y 1044=+x y 3001≤≤x 4002≤≤x 2003≤≤x 1004≤≤x 0≥j y ， =j 2，3，4.
（3） 设第i 季度生产而用于第j 季度末交货的产品数量为j i x 吨.
根据合同要求，必须有：
2011=x ， 202212=+x x ，
30332313=++x x x ， 1044342414=+++x x x x .
又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力， 故应有：
3014131211≤+++x x x x ， 40242322≤++x x x ， 203433≤+x x ， 1044≤x .
第i 季度生产的用于第j 季度交货的每吨产品的费用)(2.0i j d c i ij -+=，于是，有线性规划模型：
min z = 141312116.154.152.150.15x x x x +++
2423224.142.1414x x x +++
4434338.145.153.15x x x +++
s.t. 2011=x
202212=+x x
30332313=++x x x
1044342414=+++x x x x 3014131211≤+++x x x x 40242322≤++x x x
203433≤+x x 1044≤x
0≥j i x =i 1，…，4；=j 1，…，4，i j ≥.
2、（合理下料问题）某工厂要制作100套专用钢架，每套钢架需要用长为2.9m 、2.1m 和1.5m 的圆钢各一根。已知原料每根长7.4m ，现考虑应如何下料，可使所用原料最省？
解: 分析：利用7.4m 长的圆钢截成2.9m 、2.1m 、1.5m 的圆钢共有如表1-13所示的8种下料方案.
表1-13 下料方案表
一般情况下，我们可以设87654321,,,,,,,x x x x x x x x 分别为上面8种方案下料的原材料根数.根据目标的要求，可以建立两种形式的目标函数： 材料根数最少：
min z = 87654321x x x x x x x x +++++++ (1.27)
剩余料头最少：
min z = 876543214.18.02.01.109.03.01.0x x x x x x x x +++++++ （1.28）
约束是要满足各种方案剪裁得到的2.9m 、2.1m 、1.5m 三种圆钢各自不少于100个，即 2.9m : 43212x x x x +++ 100≥ 2.1m : 322x x + 76523x x x +++ 100≥ 1.5m : 1x 433x x ++ 100432876≥+++x x x 非负条件 1x ， 2x ，3x ， 4x ，5x ，6x ，7x ， 08≥x 这样我们用目标函数（1.27）可建立如下数学模型： min 87654321x x x x x x x x z +++++++=
s.t. 43212x x x x +++ 100≥ 322x x + 76523x x x +++ 100≥ 1x 433x x ++ 100432876≥+++x x x 1x ， 2x ，3x ， 4x ，5x ，6x ，7x ， 08≥x
利用线性规划单纯形法求解可得：*x =（10，50，0，30，0，0，0，0）T ，最少使用的材料为90（根），各种圆钢数均正好100个.
如果用目标函数（1.28），可建立如下数学模型：
min 876543214.18.02.01.109.03.01.0x x x x x x x x z +++++++=
s.t. 43212x x x x +++ 100≥ 322x x + 76523x x x +++ 100≥ 1x 433x x ++ 100432876≥+++x x x 1x ， 2x ，3x ， 4x ，5x ，6x ，7x ， 08≥x
利用线性规划单纯形法求解可得：*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万元；
项目C ：若投资则必须在第三年年初投资，到第五年末能收回本利140%，但是限制最大投资额不能超过80万元；
项目D ：若投资则需在第二年年初投资，到第五年末能收回本利155%，但是规定最大投资额不能超过100万元；
根据测定每万元每次投资的风险指数为：项目A 为1，项目B 为3，项目C 为4，项目D 为5.5. 问题：
（1） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ （2） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础
上保证其投资的总风险系数最小？ 解: 首先考虑问题（1）：
1）确定决策变量. 本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量.
设ij x （=i 1，2，3，4，5；=j 1，2，3，4）表示第i 年初投资于项目A （1=j ）、项目B （2=j ）、项目C （3=j ）、项目D （4=j ）的金额. 根据题意，我们建立如下决策变量：
第一年年初 第二年年初 第三年年初 第四年年初 第五年年初
项目A 11x 21x 31x 41x 51x 项目B 12x 22x 32x 42x 项目C 33x 项目D 24x
2）考虑约束条件. 由于项目A 的投资当年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是最优的. 下面我们分年来考虑：
第一年年初：由于只有项目A 和项目B 可以投资，又应把全部200万元资金投出去，于是有 2001211=+x x
第二年年初：由于项目B 要次年末才可收回投资，故第二年年初的资金只有第一年年初对项目A 投资后，在年末收回的本利110%11x ，而投资项目为A ，B 和D ，于是有：
112422211.1x x x x =++
整理后得：
01.124222111=+++-x x x x
第三年年初：年初的资金为第二年年初对项目A 投资后，在年末收回的本利110%21x 以 及第一年年初对项目B 投资后，在年末收回的本利125%12x . 可投资项目有A ，B 和C ，于是有：
122133323125.11.1x x x x x +=++ 整理后得：
025.11.133********=+++--x x x x x
第四年年初：年初的资金为第三年年初对项目A 投资后，在年末收回的本利110%31x 以及第二年年初对项目B 投资后，在年末收回的本利125%22x . 可投资项目只有A 和B ，于是有：
2231424125.11.1x x x x +=+ 整理后得：
025.11.142412231=++--x x x x
第五年年初：年初的资金为第四年年初对项目A 投资后，在年末收回的本利110%41x 以及第三
年年初对项目B 投资后，在年末收回的本利125%32x . 可投资项目只有A ，于是有：
32415125.11.1x x x +=
整理后得：
025.11.1513241=+--x x x
其他的还有项目B ，C ，D 的投资限制以及各决策变量的非负约束： 项目B 的投资限制： 302≤i x （=i 1，2，3，4） 项目C 的投资限制： 8033≤x 项目D 的投资限制： 10024≤x
各决策变量的非负约束：1i x ，2j x ，33x ，024≥x （=i 1，2，3，4，5；=j 1，2，3，4） 3）建立目标函数. 问题要求在第五年末公司这200万元用于4个项目投资的运作获得本利最大，而第五年末的本利获得有4项：
第五年年初对项目A 投资后，在年末收回的本利110%51x ； 第四年年初对项目B 投资后，在年末收回的本利125%42x ； 第三年年初对项目C 投资后，在年末收回的本利140%33x ； 第二年年初对项目D 投资后，在年末收回的本利155%24x . 于是得到目标函数为：
2433425155.14.125.11.1x x x x z +++= 根据上面的分析得到线性规划模型：
max 2433425155.14.125.11.1x x x x z +++= s.t. 2001211=+x x
01.124222111=+++-x x x x
025.11.133********=+++--x x x x x 025.11.142412231=++--x x x x 025.11.1513241=+--x x x 302≤i x (=i 1，2，3，4) 8033≤x 10024≤x
1i x ，2j x ，33x ，024≥x （=i 1，2，3，4，5;=j 1，2，3，4） 考虑问题（2）：
据题意，问题（2）的决策变量设置与问题（1）的设置1）完全相同；而问题（2）的约束设置除与问题（1）的设置2）完全相同外，还增加一约束，就是考虑要使第五年末拥有资金的本利在330万元上，即
33055.14.125.11.124334251≥+++x x x x
问题（2）的主要区别在于目标不同，是要使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数为最小. 因此，目标函数为各年各项目的风险系数之和，而风险系数等于投资数乘以相应风险指数. 于是得到下列目标函数：
24334232221251413121115.54)(3)(x x x x x x x x x x x z ++++++++++=
综合以上分析，问题（2）的线性规划模型为：
min 24334232221251413121115.54)(3)(x x x x x x x x x x x z ++++++++++=
s.t. 2002111=+x x
01.124222111=+++-x x x x
025.11.133********=+++--x x x x x 025.11.142412231=++--x x x x 025.11.1513241=+--x x x
302≤i x (=i 1，2，3，4) 8033≤x
10024≤x
33055.14.125.11.124334251≥+++x x x x
1i x ，2j x ，33x ，024≥x （=i 1，2，3，4，5;=j 1，2，3，4）
此例属于动态规划问题，它既可以建立上述模型用线性规划求解，也可以用动态规划的方法求解. 很多运筹学问题是可以用多种方法求解的，不同方法求解在理论上得到的结果应是一致的，但是由于方法本身的特征，不同算法可以得到不同的附带信息. 例如利用线性规划求解除了可得到最优解和最优植之外，还可通过分析得到下面将要介绍的影子价格（对偶价格）、灵敏度分析结果等. 另外，不同方法求解同一个问题时，计算量、复杂性、精确度等都会有差异.因此，读者在学习中了解掌握多种建摸思路，学会多种求解方法，对于提高解决实际问题的能力和水平是十分重要的.
4、（场地租借问题）某厂在今后四个月内需租用仓库堆存货物. 已知各个月所需的仓库面积数如表1-14. 又知，当租借合同期限越长时，场地租借费用享受的折扣优待越大，有关数据如表1-15.
表1-14
租借仓库的合同每月都可办理，每份合同应具体说明租借的场地面积和租借期限. 工厂在任何一个月初办理签约时，可签一份，也可同时签若干份租借场地面积数和租借期限不同的合同. 为使所付的场地总租借费用最小，试建立一个线性规划模型.
解： 设ij x 为第i 个月初签订的租借期限为j 个月的合同租借面积（单位：百米2
）.
于是，有下列决策变量：
一月签订：11
x 12x 13x 14x
二月签订： 21x 22x 23x 三月签订： 13x 32x 四月签订： 41x
各个月生效的合同的租借面积为： 第一个月：11x +12x +13x +14x
第二个月：x +x +
x +x +x +x
第三个月：13x +14x +22x +23x +13x +32x 第四个月：14x +23x +32x +41x 从而，我们得如下线性规划摸型：
min z =143
1
2
1
324
1
1
7300600045002800
x x x x
i i i i i i +++∑∑∑===
s.t. 11x +12x +13x +14x 15≥， 12x +13x +14x +21x +22x +23x ≥10， 13x +14x +22x +23x +13x +32x ≥20， 14x +23x +32x +41x ≥12 ,01≥j x =j 1，…，4 02≥j x ，=j 1，2，3 ,031≥x 032≥x ， 041≥x .
5、（分配问题）甲方战略轰炸机队指挥官得到了摧毁乙方坦克生产能力的命令. 根据情报，乙方有三个生产坦克部件的工厂，位于不同的地点. 只要破坏其中任一个工厂的生产设施就可以有效地停止乙方坦克的生产.
该轰炸机队现有重型和中型两种轰炸机，其数量和燃油耗量如表1-16.
根据情报分析，空军基地与各工厂的距离和各类型飞机命中目标的概率如1-17表.
甲方为完成此项任务至多能提供48000加仑汽油. 而对于任何类型飞机，不论去轰炸那一个工厂，都必须有足够往返的燃料和100加仑备用燃料.
试问指挥官为执行任务应向三个工厂派遣每种类型的飞机个多少架，才能使成功的概率最大？ 解 设ij x 为i #
型飞机被派遣去j #
工厂执行任务的架数.
甲方的目标是希望事件“至少摧毁一个工厂”的概率最大. 这相当于希望事件“不摧毁任何工厂”的概率f 最小. 我们有：
232221131211)12.01()16.01()08.01()15.01()20.01()10.01(x x x x x x f ------=
它不是线性的，为此将上式改写为
88
.0log 84.0log 92.0log 85.0log 8.0log 9.0log log 232221131211x x x x x x f z +++++==
于是，模型的目标函数为
23
22211312110554.00656.00362.00704.00969.00457.0x x x x x x z +++++=
关于燃料的约束条件为：
∑∑==≤+?+?+?+?+?+?213
1
2322
2113121148000
100357023
480
234502257022480224502i j ij x x x x x x x 经过整理，即为
48000480420400670580550232221131211≤+++++x x x x x x . 飞机数量约束：
∑=≤3
1
140j j
x
，283
1
2≤∑=j j x
综上所述，本问题的线性规划模型为：
max z = 1312110704.00969.00457.0x x x ++2322210554.00656.00362.0x x x +++ s.t. 48000480420400670580550232221131211≤+++++x x x x x x 40131211≤++x x x 28232221≤++x x x
0≥ij x ， =i 1，2；=j 1，2，3.
6、（选址问题）设有A 1、A 2和A 3三个原料产地，其原料要在工厂加工，制成成品后再在销地销售，A 1与A 2两地又是销地. 设4吨原料可以加工成1吨成品，A 1与A 2间距离为150公里，A 2 与A 3间距离为200公里，A 1与A 3间距离为100公里. 原料运费每万吨公里为3千元，成品运费每万吨公里为2.5千元。现考虑在这三个地点建厂：若在A 2建厂，生产规模为每年生产的成品不能超过5万吨，而在A 1或A 3建厂，生产规模不受限制. 有关数据由表1-18给出.
表1-18
试问在那几个地点建厂，生产规模如何，才能使生产成本最小？（这里为简化问题，仅考虑原料费用、成品运费和成品加工费，其它如原料单价、建厂投资费等未加考虑.）
解: 在建立模型以前，让我们先来分析一下问题中所给数据是否产销平衡？
A 、A 和A 每年原料的生产量总和为80万吨，A 和A 每年对成品的销售量总和为20万吨，
由于每4吨原料可加工为1吨成品，所以产销平衡.
设ij x 为每年由产地i A 运往建厂地j A 的原料数量（万吨）（=i 1，2，3）；jk y 为每年由建厂地
j A 运往销地k A 的成品数量（万吨）（=i 1，2，3；=k 1，2）.
第一组约束条件为：若在i A 地建厂，则其所具有的原料数量（本地生产的原料数量与其它两地运来的原料数量之和）应等于该地设厂生产的成品数量的4倍. 例如对A 1来说，应有
)(430121113123121y y x x x x +=--++
上式中既出现21x 又出现12x ，初看起来是矛盾的. 但是在研究建厂规划时，事先并不能知道哪一个方向是合理的，只好把两种可能的方向都考虑进去. 由于目标函数是要求生产成本最小，因此在最优解中不可能产生对流运输. 类似地，有
)(26222123213212y y x x x x +=--++
)(424323132312313y y x x x x +=--++
第二组约束条件为：各地工厂运到销地的成品数应恰为销地的需求量：
7312111=++y y y
13322212=++y y y 第三组约束条件为2A 产地设厂的生产规模约束： 52221≤+y y 目标函数为
]
100200)(150[5.2)](100)(200)(150[3)
(3)(4)(5.531322112311332232112323122211211y y y y x x x x x x y y y y y y z +++++++++++++++=
因此，本问题的线性规划模型为：
31
1332
2321123231
2221121130030060060045045050325343795.3805.5min x x x x x x y y y y y y z +++++++++++=
s.t. 3044131231211211=++--+x x x x y y 2644232132122221=++--+x x x x y y 2444323123133231=++--+x x x x y y 7312111=++y y y 13322212=++y y y 52221≤+y y
0≥ij x ， =j i , 1，2，3，j i ≠ 0≥jk y ， =j 1，2，3； =k 1，2.
用单纯形法对此模型求解，若得最优解*ij x （=j i ,1，2，3；j i ≠），*
jk y （=j 1，2，3；=k 1，2），则1A 地设厂的生产规模为*12*11y y +，2A 地设厂的生产规模为*
22*21y y +，3A 地设厂的规模为
*32*31y y +. 若j A 求得的生产规模为零，则在j A 地不设厂.
7、某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素. 现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如表1-19所示：
要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案. 建立这个问题的线性规划模型.
解：用X j （j=1.2…5）分别代表5中饲料的采购数，线性规划模型：
12345123412341234min 0.20.70.40.30.8.326700
0.50.230
0.20.8100(1,2,3,4,5,6)0
j z x x x x x st x x x x x x x x x x x x x x x x j =+++++++≥+++≥+++≥=≥555 +18 +2 0.5+2
8、某医院护士值班班次、每班工作时间及各班所需护士数如表1-20所示. 每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要，建立线性规划模型
.
解：设123456x x x x x x x 表示在第i 个时期初开始工作的护士人数，z 表示所需的总人数，则
123456161223344556min .607060502030(1,2.3.4.5.6)0
i z x x x x x x st x x x x x x x x x x x x x i =++++++≥+≥+≥+≥+≥+≥=≥
9、一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-21所示. 现有三种货物待运，书籍有关数据列于表1-22. 又为了船运安全，前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系. 具体要求：前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%. 问该货轮应装载A,B,C 各多少件运费收入才最大？试建立这个问题的线性规划模型.
解：设用i=1，2，3分别表示商品A ，B ，C ，j=1，2，3分别代表前，中，后舱，Xij 表示装于j 舱的i 种商品的数量，Z 表示总运费收入则：
111213212223313233max 1000()700()600()z x x x x x x x x x =++++++++
111213.600st x x x ++≤
2122231000x x x ++≤ 313233800x x x ++≤
112131122232132333112131105740010575400105715008652000x x x x x x x x x x x x ++≤++≤++≤++≤
12223213233386530008651500x x x x x x ++≤++≤
112131
122232
132333
122232112131
1323338650.15
8658650.15
8658650.1
8650(1,2.3.1,2,3)
ij x x x x x x x x x x x x x x x x x x x i j ++≤++++≤++++≤++≥==
10、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解.
（1）2132m in x x z += s.t. 66421≥+x x 42221≥+x x 0,21≥x x 解：
Z = 4
（2）21m ax x x z += s.t. 12010621≤+x x 1051≤≤x
832≤≤x
解：如图：由图可得：
**(10,6)16T x Z == ；
即该问题具有唯一最优解*(10,6)T x =
（3）2123m ax x x z += s.t. 2221≤+x x 124321≥+x x 0,21≥x x
无可行解
（4）2165m ax x x z += s.t. 2221≥-x x 23221≤+-x x 0,21≥x x
解：如图
由图知，该问题具有无界解。
11、将下述线性规划问题化成标准形式
（1）43215243m in x x x x z +-+-=
s.t. 1234222x x x x -+-=-
1424321≤+-+x x x x 2324321≥-++-x x x x
0,,321≥x x x , 4x 无约束
解：
''"1234456
'"12344'"123445'"123446'"'1234456max 3425500.22
221436z x x x x x x x st x x x x x x x x x x x x x x x x x x x x x x x x =-+-++++-+-=+-+-=++-+=≥ -2 + -2- ，，，，，，0
（2）321322m in x x x z +-=
s.t. 4321=++-x x x
62321≤-+-x x x 32100x x x ，，≥≤无约束
解：
'''"12334
''"1233'
'
"1
233
4'"12334max 22330.4
6z x x x x x st x x x x x x x x x x x x x x =+-++++-=+-+=≥ 2+ ，，，，0
12、对下述线性规划问题找出所有基本解，指出哪些是基本可行解，并确定最优解
（1）32123max x x x z ++=
St 9363124321=+++x x x x
102485321=+-+x x x x 0361=-x x )6,,1(0
=≥j x j
解：
系数矩阵A ：364)
120C ??
?
- ? ?-??
=12345612363
00810
2 0＝（p p p p p p 3000
0种组合
112
311236
8145403
B P P P B ==-=-≠1 ；可构成基。求B 的基本解，
∴
（B ，b ）=040????
? ?-
? ? ? ??
???
123691008110＝0
116/330
00
1
-7/6 ∴ y 1=（0，16/3，-7/6，0，0，0）T
同理y 2=（0，10，0，-7，0，0）T y 3=（0， 3，0，0，7/2，0）T y 4=（7/4，-4，0，0，0，21/4）T y 5=（0，0，-5/2，8，0，0）T
y 6=（0，0，3/2，0，8，0）T y 7=（1，0，-1/2，0，0，3）T y 8=（0，0，0，3，5，0）T y 9=（5/4，0，0，-2，0，15/4）T
y 10=（0， 3，-7/6，0，0，0）T y 11=（0，0，-5/2，8，0，0）T
y 12=（0，0，-5/2，3，5，0）T y 13=（4/3，0，0，0，2，3/4）T
y 14=（0，10，0，-7，0，0）T y 15=（0， 3，0，0，7/3，0）T
y 16=（0，0，3/2，0，8，0）T
基可行解：（每个x 值都大于0），（y 3，y 6，y 8，y 12，y 13，y 15，y 16） 最优解：（y 3，y 6， y 15，y 16） Z max =3
[p 2 p 3 p 4]，[p 2 p 3 p 5]，[p 3 p 4 p 5]，[p 2 p 4 p 5]为奇异，∴只有16个基。
（2）43212325m in x x x x z ++-= 74324321=+++x x x x 32224321=+++x x x x )4,,1(0
=≥j x j
解：该线性问题最多有246
C =个基本解。
13、设某线性规划问题的约束系数矩阵A 和右端常数向量b 分别为
??? ?=3141265301A ，??
? ?=41b .
试问521,,x x x 所对应的列向量能否构成基？若能，写出B,N ，并求出B 所对应的基本解.
解：
基的定义 1
06
2
13503
1
4
B ==-≠ ∴X 1 X 2 X 3所对应的列向量可以构成基 B 由 X 1 X 2 X 3 列向量构成 = 106213314??
???????? N 由 非基变量对应的向量构成 = 354120??
???????? （B ，b ）= 106102131314??
??????→?
???????????
１0-13/5 ４ 00 37/5２0013/5 ∴B 对应的基解：（-13/5，37/5，0，0，3/5）
14、分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基本可行解对应图解法中可行域的哪一顶点.（1）21510m ax x x z +=
s.t. 94321≤+x x
82521≤+x x
0,21≥x x
解：（1）
由图知：
**(1,3/2)35/2;T x Z ==；
单纯形法：化为标准形如下：
12123124max 105.349528(1,2,3,4)0
i z x x st x x x x x x x i =+++=++==≥
所以：**(1,3/2)35/2;T x Z ==； 其中：
(0,0)(8/5,0)(1,3/2)
A B C ???→???→???→对应
T 对应T 对应T
（0,0,9,8)（8/5,0,21/5,0)（1,3/2,0,0)
（2）212m ax x x z +=
s.t. 155321≤+x x 242621≤+x x 0,21≥x x 解：
∴A 点最大 Z= 8
化为标准形：
1234
12312max 200.3515224(1,2,3,4)0
i z x x x x st x x x x x x x i =-++++=++==≥4 6
0点（0，0，15，24）
A 点（4，0，3，0） Zmax=8
15、上题（1）中，若目标函数变为21m ax dx cx z +=，讨论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）3212m ax x x x z +-=
s.t. 603321≤++x x x
102321≤+-x x x 20321≤-+x x x
)3,2,1(0=≥j x j
解：化为标准型：
123
1234
123123m a x 2.36021020(1,2,3,4,5,6)0j z x x x st x x x x x x x x x x x x x i =-++++=-++=+-+==≥56
**(,);T x Z ==155，0； 25
（2）321532m ax x x x z ++= s.t. 12322321≤++x x x
822321≤++x x x 166431≤+x x
123432≤+x x )3,2,1(,0=≥j x j
解：
123456712341231323max 235.223122286164312(1,2,3...7)0
i z x x x x x x x st x x x x x x x x x x x x x x x i =+++++++++=+++=++=++==≥5670000 4
单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z
j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。
运筹学教程（胡运权主编，清华第4版）部分习题答案（第一章）1.1 （1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。 （2）无可行解； （3）x* = (10,6)，z* = 16； （4）最优解无界。 1.2 （1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4 s.t. –4x1 + x2 – 2x3 + x’4– x’’4 = 2 x1 + x2 – x3 + 2x’4– 2x’’4 + x5 = 14 –2x1 + 3x2 + x3 – x’4+ x’’4– x6 = 2 x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0 （2）max z’ = 2x’1 + 2x2 – 3x’3 + 3x’’3 s.t. x’1 + x2 + x’3 – x’’3 = 4 2x’1 + x2 – x’3 + x’’3 + x4 = 6 x’1, x2, x’3, x’’3, x4, ≥ 0 1.3 （1）基解：(0, 16/3, -7/6, 0, 0, 0)； (0, 10, 0, -7, 0, 0)； (0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解； (7/4, -4, 0, 0, 0, 21/4)； (0, 16/3, -7/6, 0, 0, 0)； (0, 0, -5/2, 8, 0, 0)； (1, 0, -1/2, 0, 0, 3)； (0, 0, 0, 3, 5, 0)，是基可行解，z = 0； (5/4, 0, 0, -2, 0, 15/4)； (3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4； (0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。 （2）基解：(-4, 11/2, 0, 0)； (2/5, 0, 11/5, 0)，是基可行解，z = 43/5； (-1/3, 0, 0, 11/6)； (0, 1/2, 2, 0)，是基可行解，z = 5，是最优解；
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ）
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1
1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。
2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量， 选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
第1章 线性规划与单纯形法 1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 ??? ??≥≥+≥++=0 x x 42x 4x 66x 4x 3x 2x minz )a (21 21212 1， ?? ? ??≥≥+≤++=0 x ,x 124x 3x 2 x 2x 2x 3x maxz )b (2121212 1 ?? ???≤≤≤≤≤++=8x 310x 5120 10x 6x x x maxz )c (21 212 1 ?? ? ??≥≤+-≥-+=0 x ,x 23x 2x 2x 2x 6x 5x maxz )d (2121212 1 2、用单纯形法求解下列线性规划问题。 ?????≥ ≤+≤++=0 x ,x 82x 5x 94x 3x 5x 10x maxz )a (21 2 121 2 1 ????? ? ? ≥ ≤+≤+≤+=0 x ,x 5x x 242x 6x 155x x 2x maxz )b (2 1 212 122 1 3、用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 ??? ?? ??≥≥-≥+-≥+++-=0 x x x 0 x 2x 2x 2x 6 x x x 2x x 2x maxz )a (3 , 2,132 3 13213 21 ??? ??≥≥+≥++++=0 x , x ,x 6 2x 3x 82x 4x x x 3x 2x minz )b (3 21 2 1 3 21 3 21 4、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a ～l 的值。 表1
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020
使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1）将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ .： 1234123561371234567211 42321,,,,,,0x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表
由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表
例1 max z=2x1+3x2 （标准形式即所有的变量均为负、所有约束条件为等式、所有的右端项系数非负） a=(2,3) b1=(80,160,120) A2=NULL b2=NULL A3=NULL b3=NULL n.iter=n+2*m maxi=TRUE ● simplex(a=a,A1=A1,b1=b1,maxi=TRUE)： m1=3,m2=0,m3=0 m=3,n=2 a.o=a=(2,3) if(maxi) a=-a(-2,-3) if(m2+m3==0) a=(-2,-3,0,0,0) b=(80,160,120) init=(0,0,0,80,160,120) basic=(3,4,5) eps=1e -10 out1<-simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps) ? simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps): N=5,M=3 nonbasic=(1,2) if(stage==2) obfun=(-2,-3) it=1 ◆ while(!all(obfun > -eps) && (it <= n.iter))循环 pcol=3 if(stage==2) neg=(1,3) x1+2x2<=80 4x1<=160 4x2<=120 x1，x2>=0 A1= 1 2 4 0 0 4 A= 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 tableau= 80 -1 -2 160 -4 0 120 0 -4 tableau= 80 -1 -2 160 -4 0 120 0 -4 0 -2 -3 转化为标准形式 x1+2x2+x3=80 4x1+x4=160 4x2+x5=120 x1,x2,x3,x4,x5>=0
线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5 表1 由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为： ()1787811-=+-=???? ??-=z ()3)31(53111511=+--=???? ??--=-z c ()0)42(24211222=+--=???? ??--=-z c ()4)12(31211333=+--=??? ? ??--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。c j -z j 行中的4最大因而非基变量 X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。 为确定被换出的基变量，采用最小比值法。用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。第一行有最小比值，把它叫做旋转行。第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。 ()153123413=+=???? ??=z ()1455/2/2113511=-=???? ??-=-z c ()-4623113222=-=???? ??-=-z c ()-21-11/2-21/13-133=-=??? ? ??-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。c j -z j 行中的1最大因而非基变 量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行 void PrintAnswer();数不合法"< 单纯形法的解题步骤 三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定 （2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14 （3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 单纯形法例题讲解 基可行解 单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。 min cx f = （1） s.t b Ax = （2） 0≥x （3） 其中 T m mn m m n n T n n b b b b a a a a a a a a a A x x x x c c c c )...,(,............ ... ..., ),...,,(),,...,(212 1 22221112 112121=??? ???????????=== 假设1≥≥m n ，并设系数矩阵A 的秩为m ，即 设约束方程（2）中没有多余的方程，用j p 表示A 的第j 列，于是（2可写成 b p x m k j j =∑=1 （4） 矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若 ),...,(21jm j j p p p B = （5） 是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为 b p x m k jk jk =∑=1 （6） 由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为T jn j j x x x ) ,...,,()0() 0(2) 0(1于是按分量 {}{}),...,,\,...2,1(0) ,....3,2,1(21) 0(m j jk jk j j j n j x m k x x ∈=== 所构成的向量) 0(x 是约束方程组b Ax =的一个 解，称此)0(x 为LP 的对应于基B 的基解 （或基本解），也可称为方程组b Ax =的一个基解，如果) 0(x 为一基解，且满足 0)0(≥x 即它的所有分量都非负，则称此) 0(x 是LP 的一个基可行解，基可行解对应的基 称为可行基。单纯形法的解题步骤
最新单纯形法例题讲解
相关主题
文本预览