运筹学复习例题

1、线性规划的表格单纯形法 一工厂生产A、B、C三种产品所需的劳力分别为6、3和5个工作日单位，所消耗的原材料分别为3、4和5kg，各单位产品的收益分别为2、1和5元，工厂每日能提供的劳力数为100人，材料量为80kg。问该工厂应如何安排生产才能使总的收益达到最大。（1） 建立线性规划的数学模型；（2） 用表格单纯形法求解；（3） 当劳力数增加10人，材料量增加20kg时新的最优方案；（4） 写出对偶问题和对偶问题的最优解。（5） 求x1的价值系数在什么范围变化最优解不变解：(1)设A、B、C三种产品的产量分别为，则数学模型为(2)化为标准型cj21500CBXBbx1x2x3x4x500x4x5

2、1008063345510012016cj-zj2150005x4x3201633/5-14/50110-11/5cj-zj-1-300-1最优解为x1= x2=0，x3=16，最大的利润z=80元。(3)由上表知最优基矩阵的逆，cj21500CBXBbx1x2x3x4x505x4x3102033/5-14/50110-11/5cj-zj-1-300-1所以新的最优解为x1= x2=0，x3=20，最大的利润z=100元。(4)对偶问题为对偶问题的最优解y1=0,y2=1.互补松弛性的应用该问题的对偶问题为s.t. 由互补松弛性：若分别是原问题和对偶问题的可行解，那么，当且仅当为最优解。设为原

3、问题的最优解。其中为原问题约束条件的松弛变量。而 为对偶问题的最优解。其中为与(1)(2)(3)(4)相对应的松弛变量。 且 (3)(4)为等式，故(1)(2)为不等式，故由即得由即得即原问题的约束条件应取等号 解得所以，原问题的最优解为目标函数最优值运输问题例题设有产量分别是8，9的两个原料产地A1, A2, 欲将原料运往需求量分别为6，5，8的三个销地，单位运价表如下，试写出该问题的数学模型并求运费最省的调运方案。(20分)销地产地B1 B2 B3产量A1A11 2 36 5 468销量6 5 8解：因总产量为17，总销量为19，所以是产小于销的运输问题，增加一个产地转化为产销平衡的运输问

4、题为： 销地产地B1 B2 B3 产量 A11 2 3 6 A26 5 4 8A30 0 0 5销量6 5 8 按表上作业法，首先用伏格尔法求得初始基可行解如下表：销地产地B1B2B3产量A1628A2549A322销量658用位势法求得检验数为：销地产地B1B2B3A1000U1=8A2500U2 =6A3530U3 =0V1=-5V2=-3V3=0由于检验数全部非负，则该初始基可行解即为最优解，最优值为53.数学模型为用分枝定界法求解下面的整数规划：已知其放松的线性规划的最优单纯形表：cj321000CBXBbx1x2x3x4x5x6213x2x3x111/34/350011000101/

5、3-1/121/21/31/601/35/121/2cj-zj000-25/12-5/6-31/12解：由线性规划的最优单纯形表知其最优解为x1=5，x2=11/3，x3=4/3非整数解，最优值z0=71/3, x1=0，x2=0，x3=0为一整数可行解，目标函数值为z=0,定界。分枝，相应的问题设为，解如下表：cj3210000CBXBbx1x2x3x4x5x6x72130x2x3x1x711/34/3530010100101001/3-1/121/201/31/6001/35/121/200001cj-zj000-25/12-5/6-31/1202130x2x3x1x711/34/35-2

6、/30010100001001/3-1/121/2-1/31/31/60-1/31/35/121/2-1/30001cj-zj000-25/12-5/6-31/1202130x2x3x1x531520010100001000-1/41/21000101/41/2111/20-3cj-zj000-5/40-7/4-5/2得到一个整数最优解x1=5，x2=3，x3=1，最优值为22，因该最优解是满足整数条件，所以该整数规划的下界z=22。同理求解另一个线性规划问题(要写出求解的单纯形表)，因无可行解，因此该整数规划的上界也为22，所以整数规划的最优值为22，上面的这个解即为最优解。指派问题题解某公

7、司有五个经理分别派往五项五个地区负责市场开拓，预计相应的净收益如下表(单位：百万元)，试求使总收益最大的分派方案并写出该问题的数学模型（每人只负责一个地区）。任务人员12345111776122975863103817411513810565538解：数学模型为minmin 2 1 min1,3,5,5,2,1,3,4=1,则最优解为，最优值为48。线性规划与灵敏度分析题解一工厂生产A、B、C三种产品所需的劳力分别为6、3和5个工作日单位，所消耗的原材料分别为3、4和5kg，各单位产品的收益分别为2、1和5元，工厂每日能提供的劳力数为100人，材料量为80kg。问该工厂应如何安排生产才能使总的

8、收益达到最大。（6） 建立线性规划的数学模型；（7） 用表格单纯形法求解；（8） 当劳力数增加10人，材料量增加20kg时新的最优方案；（9） 写出对偶问题和对偶问题的最优解。解：(1)设A、B、C三种产品的产量分别为，则数学模型为(2)化为标准型cj21500CBXBbx1x2x3x4x500x4x5100806334551001cj-zj2150005x4x3201633/5-14/50110-11/5cj-zj-1-300-1最优解为x1= x2=0，x3=16，最大的利润z=80元。(3)由上表知最优基矩阵的逆，cj21500CBXBbx1x2x3x4x505x4x3102033/5-

9、14/50110-11/5cj-zj-1-300-1所以新的最优解为x1= x2=0，x3=20，最大的利润z=100元。(4)对偶问题为对偶问题的最优解y1=0,y2=1.最大流的标号法用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（cij,fij）。 . 解：(1) 首先,给vs标上(0,) (2) 检查vs，给vs为起点的未饱和弧的未标号的终点v2标号(vs,),其中其它点不符合标号条件。(3) 检查，给为终点的非零流弧的未标号的起点标号(,),其中其它点不符合标号条件。(4) 检查，给为起点的未饱和弧的未标号的终点标号(,)、

10、(,)其中，其它点不符合标号条件。(5) 检查，给为起点的未饱和弧的未标号的终点标号(,)其中，其它点不符合标号条件。由于已标号，反向搜索可得增广链，在该增广链的前相弧上增加，在后向弧上减去，其它弧上的流量不变，则可得一流量的新的可行流如下图。 v2 （5,5） v5 （6,6） (2,2) （12,7） （15,11） vs （4,0） (4,4) vt (5,4) v4 (4,4) （9,9) (10,9) v3 (5,5) v6 重新开始标号：(6) 首先,给vs标上(0,) (7) 检查vs，给vs为起点的未饱和弧的未标号的终点v2标号(vs,),其中其它点不符合标号条件。(8) 检查，没有以为起点的未饱和弧的未标号终点和以为终点的非零流弧的未标号起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流,最大流的流量为v(f)=20。事实上，可令，则最小截集的截量。最短路的标号法用Dijkstra标号法求vs到vt的最短路及最短路线 v2 6 vt 10 2 5 vs 5 12 v4 3 v3 解：i=0,给vs标上(,),其余各点均为T标号点，,t，记。i=1,考察以vs为起点的弧的终点v2、v3，由于、，修改v2、v3的T标号分别为。计算，将v3的T标号改为P标号，即记i=2,考察以v3为起点的弧的终点v2、v4，由