运筹学重点题型

53.7已知线性规划问题

Max z=c1x1?c2x2?c3x3

?a11??a?x1??21??a12??a?x2??22??a13??a?x3??23??1??0?x4????b1??0?x=?1?5?b? ???2?xj?0,j?1,...,5

用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求a11，a12，a13，a21，a22，a23，b1，b2的值； （2） 求c1,c2,c3的值；

XB b 3/2 2 x1 x2 x3 x4 x5 x3 x2 cj?zj 1 1/2 -3 0 1 0 1 0 0 1/2 -1 0 -1/2 2 -4 解：

（1）初始单纯形表的增广矩阵是：

?a11C1=??a21a12a22a13a2310b1?

01b2??最终单纯形表的增广矩阵为

?1010.5?0.51.5?C2=? ?22??0.510?1C2是

C1作初等变换得来的，将的单位矩阵。有：

C2作初等变换，使得

C2的第四列和第五列

的矩阵成为

C2a11=9/2； a12=1； a13=4； a21=5/2； a22=1； a23=2； b1=8； b2=5

由检验计算得：

c1=7； c2=4；c3=8.

3.8已知线性规划问题 Max z=2x1+x2+5x3+6x4 s.t. 2x1+x3+x4?8 2x1+2x2+x3+2x4?12

xj?0，j=1,…4

*?1，试应用对偶问题对偶变量y1，y2，其对偶问题的最优解是y1*=4，y2的性质，求原问题的最优解。

解：

对偶问题是：

Min w=8y1+12y2 s.t. 2y1+2y2?2 2y2?1 y1+y2?5 y1+2y2?6 y1，y2?0

?是原问题和对偶问题的可行解，那么，Y?X=0?，Y互补松弛性可知，如XS?是最优解。 ?=0，当且仅当X?，Y和YSX设 X,Y是原问题和对偶问题的可行解，YS=（y3，有： Y

y4，y5，y6）

XS

=0; 且 YSX=0

x5=x6=0，原问题约束条件取等号，x3=4；x4=4

最优解X=（0，0，4，4)T 目标函数最优值为44。

2.9现有线性规划问题 max z=- 5x1+5x2+13x3 - x1+x2+3x3 ?20 12 x1+4x2+10x3 ?90

x1 ，x2， x3 ?0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

（1） 约束条件1的右端常数20变为30 （2） 约束条件2的右端常数90变为70

（3） 目标函数中x3的系数变为8

??1?（4） x1的系数向量变为??

?12?（5） 增加一个约束条件2x1+3x2+5x3?50 （6） 将约束条件2变为10x1+5x2+10x3?100 解：

把原问题化成标准型的：

Max z=-5 x1+5 x2+13 x3+0 x4+0 x5 s.t

- x1+ x2+3 x3+ x5=20 12 x1+4 x2+10 x3+ x5=90

x1，x2，x3，x4，x5?0

单纯形法解得： 最优解：

X=（0，20，0，0，10)T 目标函数最优值为100。

非基变量x1的检验数等于0，原线性问题有无穷多最优解。 （1）约束条件?的右端常数变为30 有 ?b??B?1?b 因此 b??b??b?

单纯形法解得： 最优解：

X=（0，0，9，3，0)T 目标函数最优值为117。

2右端常数变为70 （2）约束条件○有 ?b??B?1?b 因此 b??b??b?

单纯形法解得，最优解： X=（0，5，5，0，0)T 目标函数最优值为90。

（3）x3的系数变成8，x3是非基变量，检验数小于0，所以最优解不变。

?0?（4）x1的系数向量变为??

?5?x1是非基变量，检验数等于-5，所以最优解不变。

3 （5）解：加入约束条件○用对偶单纯形表计算得： X=（0，25/2，5/2，0，15，0)T 目标函数最优值为95。

（6）改变约束条件，P3,P4,P5没有变化，

线性规划问题的最优解不变。

3.5某百货公司去外地采购ABCD四种规格的服装，数量分别为：A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为：I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方案。 A B C D I 10 5 6 7 II 8 2 7 6 III 9 3 4 8 解：

因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字，此问题变成一个运输问题，见下表：

销地 A B C D 产量 产地 I 0 5 4 3 2500 II 2 8 3 4 2500 III 1 7 6 2 5000 销量 1500 2000 3000 3500 使用伏格尔法计算初始解： ○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。

○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。

○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。 销地 A B C D 产量 产地 I 1500 500 500 2500 II 2500 2500 III 1500 3500 5000 销量 1500 2000 3000 3500 使用位势法检验： 1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，在行中填入vj（j=1，2，3，4），先令u1=0，由

uiviu+=cij（i，j?B，）来确定iv和i.

2由?ij=○

cij-（

uivi+）（i，j?N）计算所有空格的检验数，并在每个格的右

上角填入单位运价。

如果没有得到最优解，用逼回路法进行改进。 盈利最大方案： 销地 A B C 产地 I 0 5 4 0 0 II 2 8 3 3 4 0 III 1 7 6 0 1 1 0 5 4 vi D ui3 0 2 4 4 2 1 1 -1 此时，总运费为28000元;最大盈利为72000元。 5.7有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表，问指派哪个人去完成哪种工作，可以使得总耗时最小？ 任务 A B C D 人员 甲 15 乙 19 丙 26 丁 19 解：系数矩阵C为： ?15?19??26??192124?232218?? 172619??212317?1818 23 17 21 21 22 16 23 24 18 19 17 ① 系数矩阵的每行元素减去该行的最小元素得矩阵B ② B矩阵的每列元素减去该列的最小元素得到矩阵A 此时，细数矩阵的每行每列都有元素0.

先给a11加圈，然后给a24加圈，划掉a44。给a32加圈，划掉a33得：

?0?1??10??2269?440?? 003??360?此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步， 给第四行打√号，给第四列打√号，给第二行打√号，将第一，第三行画一横线，将第四列画纵线，变换矩阵得到

?0?0??10??12610?330?? 004??250?给第一，第四列打√号，对第一，第二，第四行打√号，给第一，第四列画一纵线，第三行画一横线，变换矩阵得到

甲 乙 丙 丁

?0?0??12??10410?111?? 006??030?得到最优指派方案为： 甲—B；乙—A; 丙—C；丁—D。 所消耗的总时间是70.

本文来源：https://www.bwwdw.com/article/qz9d.html