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 三种产品的产量分别为 ，则数学模型为321,x0,8543162max2
2、13xz(2)化为标准型 0, 854316ax213421xzcj 2 1 5 0 0CB XB b x1 x2 x3 x4 x500x4x51008063345510012016cj-zj 2 1 5 0 005x4x3201633/5-14/50110-11/5cj-zj -1 -3 0 0 -1最优解为 x1= x2=0，x 3=16，最大的利润 z=80元。(3)由上表知最优基矩阵的逆 5/01B， 2015/101bBcj 2 1 5 0 0CB XB b x1 x2 x3 x4 x505x4x3102033/5-14/50110-11/5cj-zj -1 -3 0 0 -1所以新
3、的最优解为 x1= x2=0，x 3=20，最大的利润 z=100元。(4)对偶问题为0,5143680min21212yyw对偶问题的最优解 y1=0,y2=1.互补松弛性的应用该问题的对偶问题为 218minyws.t.0,6251y4321由互补松弛性：若YX,分别是原问题和对偶问题的可行解，那么 0XYss和，当且仅当与为最优解。设 Tx*432*1,为原问题的最优解。sX65其中 ,x为原问题约束条件的松弛变量。而1,4,*21*yY为对偶问题的最优解。 6543,s其中 y为与(1)(2)(3)(4)相对应的松弛变量。 0XY*s 且 0*sY 1,421y(3)(4)为等式，故
4、65y(1)(2)为不等式，故 0,43由 0X*sY即0*4635*2413 xyxy得 0 ,21y由 XY*s即 06251xy得即原问题的约束条件应取等号 12843x 解得 43x所以，原问题的最优解为 TX,0*目标函数最优值 46512maxz运输问题例题设有产量分别是 8，9 的两个原料产地 A1, A2, 欲将原料运往需求量分别为 6，5，8 的三个销地，单位运价表如下，试写出该问题的数学模型并求运费最省的调运方案。(20分)销地产地 B1 B2 B3 产量A1A11 2 36 5 468销量 6 5 8解：因总产量为 17，总销量为 19，所以是产小于销的运输问题，增加一个
5、产地转化为产销平衡的运输问题为：销地产地B1 B2 B3 产量A1 1 2 3 6A2 6 5 4 8A3 0 0 0 5销量 6 5 8 按表上作业法，首先用伏格尔法求得初始基可行解如下表：销地产地 B1 B2 B3 产量A1 6 2 8A2 5 4 9A3 2 2销量 6 5 8用位势法求得检验数为：销地产地B1 B2 B3A1 0 0 0 U1=8A2 5 0 0 U2 =6A3 5 3 0 U3 =0V1=-5 V2=-3 V3=0由于检验数全部非负，则该初始基可行解即为最优解，最优值为 53.数学模型为用分枝定界法求解下面的整数规划： 为 整 数321321213321,0,46ma
6、xxxxz已知其放松的线性规划的最优单纯形表：cj 3 2 1 0 0 0CBXB b x1 x2 x3 x4 x5 x6213x2x3x111/34/350011000101/3-1/121/21/31/601/35/121/2cj-zj 0 0 0 -25/12 -5/6 -31/12解：由线性规划的最优单纯形表知其最优解为 x1=5，x 2=11/3，x 3=4/3非整数解，最优值z0=71/3, x1=0，x 2=0，x 3=0为一整数可行解，目标函数值为 z=0,定界 3/71z。分枝4,32或，相应的问题设为 21B或 ，解 1如下表：cj 3 2 1 0 0 0 0CB XB b
7、 x1 x2 x3 x4 x5 x6 x72130x2x3x1x711/34/3530010100101001/3-1/121/201/31/6001/35/121/200001cj-zj 0 0 0 -25/12-5/6 -31/1202130x2x3x1x711/34/35-2/30010100001001/3-1/121/2-1/31/31/60-1/31/35/121/2-1/30001cj-zj0 0 0 -25/12-5/6 -31/1202130x2x3x1x531520010100001000-1/41/21000101/41/2111/20-3cj-zj0 0 0 -5/4
8、0 -7/4 -5/2得到一个整数最优解 x1=5，x 2=3，x 3=1，最优值为 22，因该最优解是满足整数条件，所以该整数规划的下界 z=22。同理求解另一个线性规划问题(要写出求解的单纯形表) 2B，因无可行解，因此该整数规划的上界也为 22，所以整数规划的最优值为 22，上面的这个解即为最优解。指派问题题解某公司有五个经理分别派往五项五个地区负责市场开拓，预计相应的净收益如下表(单位：百万元) ，试求使总收益最大的分派方案并写出该问题的数学模型（每人只负责一个地区） 。解：数学模型为任务人员 1 2 3 4 51 11 7 7 6 122 9 7 5 8 63 10 3 8 1 74
9、 11 5 13 8 105 6 5 5 3 85,21ji,0x 1xx x 1x 1xx x8356 08135710 6579126zmax ij 5435215453251 44 33353 5243212242321 1155 454423432 22311 或 83561017067990532897140643126853min1,3,5,5,2,1,3,4=1,32146852则最优解为 01010，最优值为 48。线性规划与灵敏度分析题解一工厂生产 A、B、C 三种产品所需的劳力分别为 6、3 和 5个工作日单位，所消耗的原材料分别为 3、4 和 5kg，各单位产品的收益分别
10、为 2、1 和 5元，工厂每日能提供的劳力数为100人，材料量为 80kg。问该工厂应如何安排生产才能使总的收益达到最大。（6） 建立线性规划的数学模型；（7） 用表格单纯形法求解；（8） 当劳力数增加 10人，材料量增加 20kg时新的最优方案；（9） 写出对偶问题和对偶问题的最优解。解：(1)设 A、B、C 三种产品的产量分别为 ，则数学模型为321,x0,8543162max213xz(2)化为标准型min 2 1min0, 8543162max21341xzcj 2 1 5 0 0CB XB b x1 x2 x3 x4 x500x4x5100806334551001cj-zj 2 1
11、5 0 005x4x3201633/5-14/50110-11/5cj-zj -1 -3 0 0 -1最优解为 x1= x2=0，x 3=16，最大的利润 z=80元。(3)由上表知最优基矩阵的逆 5/01B， 2015/101bBcj 2 1 5 0 0CB XB b x1 x2 x3 x4 x505x4x3102033/5-14/50110-11/5cj-zj -1 -3 0 0 -1所以新的最优解为 x1= x2=0，x 3=20，最大的利润 z=100元。(4)对偶问题为 0,5143680min2121yyw对偶问题的最优解 y1=0,y2=1.最大流的标号法用标号法求下图所示的公路
12、交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流） ，其中，弧旁的数字是（c ij,fij） 。 .解：(1)首先,给 vs标上(0, ) (2)检查 vs，给 vs为起点的未饱和弧的未标号的终点 v2标号(v s, )(2vl),其中8715,min),(min)(22 ssfcll其它点不符合标号条件。(3)检查 2v，给 为终点的非零流弧的未标号的起点 3v标号( 2, )(3vl),其中4,8in),(in)(323 fvll其它点不符合标号条件。(4)检查 3v，给 为起点的未饱和弧的未标号的终点 64v、 标号( 4, )(vl)、( 6,)(6l)其中， 15,min
13、),(min)(3434 fcvll6v其它点不符合标号条件。(5)检查 6，给 为起点的未饱和弧的未标号的终点 tv标号( t, )(tvl)其中，4510,min),(min)(66 ttt fcvlvl其它点不符合标号条件。由于 t已标号，反向搜索可得增广链 ),(,),(,63232 ts vv，在该增广链的前相弧 ),(,),(632tsvv上增加 4)(tl，在后向弧 2上减去 4(tl，其它弧上的流量不变，则可得一流量 0f的新的可行流如下图。v2 （5,5） v 5 （6,6） (2,2) （12,7） （15,11） vs （4,0） (4,4) v t (5,4) v4 (
14、4,4) （9,9) (10,9) v3 (5,5) v6 重新开始标号：(6)首先,给 vs标上(0, ) (7)检查 vs，给 vs为起点的未饱和弧的未标号的终点 v2标号(v s, )(2l),其中415,min),(min)(22 ssfcll其它点不符合标号条件。(8) 检查 2v，没有以 2为起点的未饱和弧的未标号终点和以 2v为终点的非零流弧的未标号起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流,最大流的流量为 v(f)=20。事实上，可令 ,6543121 ts vvVv，则最小截集 ),(1V的截量)(09),(42531 fcVCs 。最短路的标号法用
15、Dijkstra标号法求 vs到 vt的最短路及最短路线v2 6 vt10 2 5vs 5 12 v43 v3 解：i=0,给 vs标上( 0)sP, )(s),其余各点均为 T标号点，432j,)(jjMT,t，记 sk,vSs0。i=1,考察以 vs为起点的弧的终点 v2、v 3，由于 01)(2swP、0)(3swP，修改 v2、v 3的 T标号分别为sTvT)(,)(,)(,1322 。计算 )(min3vTj，将 v3的 T标号改为P标号，即 ,3记 .31kvSsi=2,考察以 v3为起点的弧的终点 v2、v 4，由于 0185)(32wvP，52)(43w，修改 v2、v 4的
16、T标号分别为3)(,51)(,3)(,8)( 4422 vTvT。计算 )(min2vTj，将 v2的 T标号改为P标号，即 ，记 .2,2kSsi=3,考察以 v2为起点的弧的终点 v4、v t，由于 1468)(2twvP，1508)(42w，修改 t、v 4的 T标号为 2)v(,)tt ，)(,1vT。计算 )(minj，将 4v的 T标号改为 P标号，即)(4P，记 .,4233kvSsi=4,考察以 v4为起点的弧的终点 vt，由于 1430)(4twP，修改 tv的 T标号为 )(,1)(ttT，计算 intjvT，将 t的 T标号改为 P标号，即3tvP，记 k,St423s4 。由于 vt得到了 标号，所以得到了 vs到 vt的最短路 tsv,423，最短路的权为1)(t。
