第二章2.5 表2-3为用单纯形法计算时某一步的表格。

已知该线性规划的目标函数为12max 53z x x =+，约束形式为≤，34,x x 为松弛变量，表中解代入目标函数后得10z =。

(1)求a ~g 的值；(2)表中给出的解是否为最优解。

解：a=2,b=0,c=0,d=1,e=4/5,f=0,g=5；表中给出的解为最优解。

2.6 表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表，45,x x 为松弛变量，求表中a ~l 的值及各变量下标m ~t 的值。

解：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0；变量的下标为m —4,n —5,s —1,t —62.10下述线性规划问题：2.11某单位加工制作100套工架，每套工架需用长为2.9m 、2.1m 和1.5m 的圆钢各一根。

已知原材料长7.4m 。

问如何下料使得所用的原材料最省？解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm 和1.5m 的圆钢做成一套工架，每根原材料剩下料头0.9m ，要完成100套工架，就需要用100根原材料，共剩余90m 料头。

若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。

实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。

设按方案A,B,C,D,E 下料的原材料数分别为x 1,x 2,x 3,x 4,x 5，根据表2-5可以得到下面的线性规划模型123451243451235min 00.10.20.30.8210022100..3231000,1,2,3,4,5i z x x x x x x x x x x x s t x x x x x i =++++++=⎧⎪++=⎪⎨+++=⎪⎪≥=⎩用大M 法求解此模型的过程如表2-6所示，最优解为：x *=(0,40,30,20,0)T ，最优值为z *=16。

求解该问题的LINGO程序如下：model:sets:row/1..3/:b;arrange/1..5/:x,c;link(row,arrange):a;endsetsdata:b=100,100,100;c=1,0.1,0.2,0.3,0.8;a=1,2,0,1,0,0,0,2,2,1,3,1,2,0,3;enddatamin=@sum(arrange(j):c(j)*x(j));@for(row(i):@sum(arrange(j):a(i,j)*x(j))=b(i););end运行该程序后，也立即可以得到最优解为：x*=(0,40,30,20,0)T，最优值为z*=16。

即按方案B 下料40根，方案C 下料30根，方案D 下料20根，共需原材料90根就可以制作完成100套工架，剩余料头最少为16m 。

2.13某昼夜服务公交公司的公交线路每天各时段内所需要司机和乘务人员如表2-9所示。

设司机和乘务人员分别在各时段开始时上班并连续工作8小时。

问该公司公交线路应如何安排司机和乘务人员，使得既能满足工作需要，又使配备的总人数最少？（本科生仅需建立问题的数学模型）解：设x i 为安排从第i 班次开始时上班的人数，则该问题的数学模型为61611223344556min 607060..5020300,1,2,...,6ii i z x x x x x x x s t x x x x x x x i ==+≥⎧⎪+≥⎪⎪+≥⎪+≥⎨⎪+≥⎪⎪+≥⎪≥=⎩∑ 求解此模型得到最优解：**(40,30,30,20,0,30),150T x z ==。

2.18现有线性规划问题123123123123max 5513320..1241090,,0z x x x x x x s t x x x x x x =-++-++≤⎧⎪++≤⎨⎪≥⎩ 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）约束条件①的右端项系数由20变为30；（2）约束条件②的右端项系数由90变为70； （3）目标函数中3x 的系数由13变为8；解：在上述LP 问题的第①、②个约束条件中分别加入松弛变量x 4,x 5得123451234123512345max 551300320..1241090,,,,0z x x x x x x x x x s t x x x x x x x x x =-++++-+++=⎧⎪+++=⎨⎪≥⎩列出此问题的初始单纯形表并进行迭代运算，过程如表2-12所示。

① ②由表2-12中的计算结果可知，LP 问题的最优解X *=(0,20,0,0,10)T ，z *=5*20=100。

（1）约束条件①的右端项系数由20变为30，则有1103030419030B b -⎡⎤⎡⎤⎡⎤==⎢⎥⎢⎥⎢⎥--⎣⎦⎣⎦⎣⎦ 列出单纯形表，并利用对偶单纯形法求解，过程如表2-13所示。

由表2-13中计算结果可知，LP 问题的最优解变为**(0,0,9,3,0),139117T X z ==⨯=。

（2）约束条件②的右端常数由90变为70，则有1102020417010B b -⎛⎫⎛⎫⎛⎫== ⎪⎪ ⎪--⎝⎭⎝⎭⎝⎭列出单纯形表，并利用对偶单纯形法求解，结果如表2-14所示。

由表2-14结果知，LP 问题的最优解变为**(0,5,5,0,0),5513590T X z ==⨯+⨯=。

（3）目标函数中x 3的系数由13变为8，由于x 3是非基变量，其检验数变为38530(2)70σ=-⨯-⨯-=-< 所以LP 问题的最优解不变。

第三章3.5 某服装厂可生产三种服装，生产不同类型的服装要租用不同的设备，设备租金和其他经济数据见表3-4。

假定市场需求不成问题，服装厂每月可用人工2000小时，该厂如何安排生产可使每月的利润最大？试建立此问题的数学模型。

解：设i x 为第i 类服装的月产量，10i i y ⎧=⎨⎩生产第类服装否则123123max 12010100500020003000z x x x y y y =++---s.t. 12311223354200033000.548026000,01i i x x x x yx y x y x y or ++≤⎧⎪≤⎪⎪≤⎪⎨≤⎪⎪≥⎪=⎪⎩且为整数3.6某部队现有5种武器装备储存管理，存放量分别为a i (i =1,…,5)。

为了安全起见，拟分为8个仓库存放，各仓库的最大允许存放量分别为b j (j =1,…,8),且有5811i j i j a b ==≤∑∑。

一种武器装备可以分多个仓库存放，但每个仓库只能存放一种，也只能整件存放。

已知第i种武器装备每单位在第j 个仓库存放一年的费用为c ij 。

第j 个仓库固定费用为每年d j 元，但若仓库不存放则没有费用。

要求设计一个使总费用最小的存储方案，试建立相应的优化模型。

解：设x ij 为第i 种武器装备在仓库j 中存放的数量，1,0,ij i j y ⎧=⎨⎩第种武器装备存放在第个仓库中其他min*(*),,,..1,01,ijijj ij ji ijij ij j ij ij i ij ij c x d y x a i x b y i js t y j x y i j+⎧=∀⎪≤∀⎪⎨≤∀⎪⎪∀⎩∑∑∑∑∑∑为整数，且为或， 3.7某地准备投资D 元建民用住宅。

可以建住宅的地点有n 处：A 1、A 2、……、A n 。

A j 处每幢住宅的造价为d j ，最多可造a j 幢。

问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。

解：在A j 地所建住宅的数量为x j ，1,0,j j A y ⎧⎪=⎨⎪⎩在地建住宅否则则该问题的数学模型为11max ,01,njj j j jnj j j jj z x x a y d x D x y or j===⎧≤⎪⎪≤⎨⎪⎪=∀⎩∑∑为整数 3.9某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为吨)以及各工厂到各销售点的单位运价(元/吨)如表3-5所示，要求研究产品如何调运才能使得总运费最小。

试建立该问题的数学模型，并采用表上作业法求出最佳的调运方案（要求用最小元素法找到初始调运方案）。

解：数学模型：111213142122232431323334111213142122232431323334112131122232132333142434min 412411210398511616102281412140,,ijz x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x i j =++++++++++++++=⎧⎪+++=⎪⎪+++=⎪++=⎪⎨++=⎪⎪++=⎪++=⎪⎪≥∀⎩利用最小元素法，求得的初始解表3-6非基变量的检验数：表3-7由于非基变量x24的检验数为负，所以初始解不是最优解，x24进基，在闭回路{x24,x23,x13,x14}中进行运量调整，得到新的调运方案：重新计算检验数：表3-9计算得到的总运费为：12*4+4*11+8*2+2*9+14*5+8*6=244. 有多个最优解！3.14某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售。

各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3-20所示。

问该公司应如何调运产品，在满足各销售点的需要量前提下，使总的运费为最小。

解：（1）求初始调运方案①方法一：利用最小元素法求得的初始调运方案如表3-21所示。

②方法二：利用伏格尔法求得的初始调运方案如表3-22所示。

表3-22（2）最优解的判别得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。

因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于0时为最优解。

下面分别使用两种求空格检验数的方法。

①方法一：闭回路法对于表3-22所示的初始调运方案，利用闭回路法计算所有空格的检验数，如表3-23所示。

这时检验数均为正数，所以表3-22给出的方案即为最有调运方案。

②方法二：位势法联立方程：u1+v3=3, u1+v4=10, u2+v1=1, u2+v4=8, u3+v2=4, u3+v4=5令v4=0得1231085uuu=⎧⎪=⎨⎪=⎩，1234717vvvv=-⎧⎪=⎪⎨=-⎪⎪=⎩。

对于表3-22所示的初始调运方案，利用位势法计算所有空格的检验数，结果与用闭回路法得到的结果相同。