线性规划例题

导读：　　　适当的试题能让考生很好的掌握考试节奏，下面是中国招生考试网www chinazhaokao com 小编为大家带来的线性规划例题，希望能帮助到大家 ...

　　适当的试题能让考生很好的掌握考试节奏，下面是中国招生考试网www.chinazhaokao.com 小编为大家带来的线性规划例题，希望能帮助到大家!

　　线性规划例题(1)

　　1. 一个毛纺厂用羊毛和兔毛生产A,B,C三种混纺毛料,生产1单位产品需要的原料如下表所示.三种产品的单位利润分别是4,1,5.每月可购进的原料限额为羊毛8000单位,兔毛3000单位,问此毛纺厂应如何安排生产能获得最大利润?

　　ABC

　　羊毛314

　　兔毛214

　　解：设生产A,B,C三种产品的量分别是

，则模型为

 

　　

 

　　2. 某饲料厂生产的一种饲料由6种配料混合配成.每种配料中所含营养成分A,B以及单位配料购入价由下表所示.每单位饲料中至少含9单位的A,19单位的B.问饲料厂如何配方,使得饲料成本最低且满足要求?

　　123456

　　A102212

　　B013132

　　配料原价353060502712

　　解：设每单位饲料中每种配料所需的量为

，则有

 

　　

 

　　4. 某产品的一个完整单位包括四个A零件和三个B零件.这两种零件(A和B)由两种不同的原料制成,而这两种原料可利用的数量分别是100单位和200单位.三个车间进行生产,而每个车间制造零件的方法各不相同.下表中给出每个生产班组的原料耗用量和每一种零件的产量.目标是要确定每一个车间的生产班组数使得产品的配套数达到最大.

　　车间每班进料每班产量/个数

　　原料1原料2零件A零件B

　　18675

　　25969

　　33884

　　解：设每个车间的生产组数分别为

，则可生产

 

　　

个单位产品，则线性规划如下：

 

　　

 

　　6. 设

三地各有某种纺织原料90,30,70吨,需要调运给 五地,后者各需要80,10,30,50,20吨.从 到 的路程(千米)如下表所示.现要求设计一个调拨方案,使得总运输吨公里数最少.

 

　　线性规划例题(2)

　　解: 设从

运往 的运量为 ，则线性规划模型为如下形式，其中 表示从 到 的运价。

 

　　

 

　　10. 某昼夜服务的公交线路每天各时间区段内所需司机和售票员数如下表

　　班次123456

　　时间6~1010~1414~1818~2222~22~6

　　所需人数607060502030

　　设司机和售票员分别在各时间区段一开始上班，并连续工作8小时，问至少配多少名司机和售票员?

　　解：设各个时间段

开始上班的人数为 人，则

 

　　

 

　　13. 今运到两批木板，需要锯成两种规格的木料，其中一种木料长为2米，另一种木料长为1.25米，第一批木板共有50块，每块长为6.5米;第二批木板共有200块，每块长为4米。

　　6.5米长的木板可用下列方式锯开：

　　(1) 2米长的三段;

　　(2) 2米长的两段,1.25米长的一段;

　　(3) 2米长的一段,1.25米长的三段;

　　(4) 1.25米长的四段.

　　4米长的一块木板可用下列方式锯开:

　　(1) 2米长的两端;

　　(2) 2米长的一段,1.25米长的一段;

　　(3) 1.25米长的三段.

　　两段两米和一段1.25米长的木料组成一套,应如何锯开这两批木板可使取得的木料的套数最多.

　　解：设6.5米长的木板用各种方法锯开的木料分别为

根，4米长的木板用各种方法锯开的木料为 。则可以生产的套数为

 

　　

 

　　线性规划问题为

　　

 

　　19. 试将下列线性规划问题化为标准型,并用向量形式给出.

　　(1)

(2)

 

　　解：(1)令

，则原规划转化为

 

　　

 

　　记

　　

 

　　

 

　　则向量形式为

　　

 

　　(2) 令

，则标准型为

 

　　

 

　　记

 

　　

 

　　则向量形式为

　　

 

　　线性规划例题(3)

　　试用图解法求下列线性规划问题的解。

　　(1)

　　

 

　　解： 最优解为

，最优值=35。

 

　　21. 已知线性规划问题

　　

 

　　下表中所列的解均满足约束条件(1)~(3),试指出表中哪些解是可行解，哪些是基本解，哪些是基本可行解?

　　序号X1X2X3X4X5

　　(a)24300

　　(b)100-504

　　(c)30274

　　解：

 

　　(a)

满足约束条件，且 线性无关，并且 ，故为基本可行解。

 

　　(b)

，故不是可行解，但 线性无关，故为基本解。

 

　　(c) 有四个正分量，所以不是基本可行解，但是是可行解。

　　23. 用单纯形法解下列线性规划问题。

　　(1)

 

　　解：化为标准型为

　　

 

　　

1-21-3000

 

　　

 

　　

611311006

 

　　

30-21[1]0103

 

　　

40-16-1001

 

　　-z 1-21-3000

　　

31[3]201-101

 

　　

30-211010

 

　　

70-370011

 

　　-z 1-840030

　　

11/312/301/3-1/30

 

　　

52/307/312/31/30

 

　　

101090101

 

　　11/3028/308/31/30

　　所以最优解

，最优值=-17

 

　　(12)

　　

 

　　解：化为标准型为如下形式，其中M为任意大的正数：

　　

 

　　单纯形表如下

　　

-1-5-3M

 

　　

 

　　

312103

 

　　

42-1012

 

　　2-2M1+M00

　　

105/21-1/2

 

　　

21-1/201/2

 

　　020M-1

　　因为人工变量在上表中都处于非基变量的位置，所以原问题中最优解存在，为

，最优值=5.

 

　　25. 下表为求某个极小值线性规划问题的初始单纯形表以及迭代后的表格，

为松弛变量，试求表中a,b,c,d,e,f,g,h,i,j,k,l的值以及各变量下表m,n,s,t的值。

 

　　

 

　　

bcd10 6

 

　　

-13e011

 

　　a1-200

　　

g2-11/20 f

 

　　

hi11/214

 

　　07jkl

　　解：由单纯形表中基变量的对应关系可以得到m=4,n=5.而迭代后的表格中显然

依然为基变量，而另一个基变量只有 有可能，所以t=5,s=1.又因为 是基变量，则g=1,h=0.也就是说b为主元素。

 

　　因为(I)行÷b=(IV)行，由

所对应的元素，知道b=2g=2，c=4，d=-2，f=3。

 

　　因为上表是前后两次迭代的结果，即(I)行÷b+(II)行=(V)行。

　　于是e=2，i=5。

　　同上分析还可得，(I)行÷b×(-a)+(III)行=(VI)行。

　　所以由

可得，7=1+c×(-a/b)，所以a=-3。

 

　　同样的可以计算得j=-5,k=3/2,l=0.

　　习题二 P.74

　　1. 写出下列线性规划问题的对偶问题.

　　(3)

　　

 

　　解：对偶问题为

　　

 

　　(4)

　　

 

　　解：对偶问题为

　　

 

　　4. 已知线性规划问题

　　

 

　　其最优解为

 

　　(1) 求k的值;

　　(2) 写出对偶规划并求其最优解.

　　解：写出对偶问题

　　

 

　　因为LP问题的最优解为

所以DP问题中第一个不等式成等式关系，即： 。

 

　　同时由LP与DP的最优解的性质，即最优解所对应的最优值相等的关系可以得到

。

 

　　上述两个等式联立可解得：

。

 

　　再将上述结果代入到DP问题的第三个等式中得k=1。

　　8. 用对偶单纯形法求解下列线性规划问题.

　　(1)

 

　　解：将约束方程两边同时乘以

，再添加松弛变量 ，可得：

 

　　

 

　　利用对偶单纯形法求解：

　　

23400

 

　　

 

　　

−3−1−2−110

 

　　

−4[−2]1−301

 

　　23400

　　

−10[−5/2]1/21−1/2

 

　　

21−1/23/20−1/2

 

　　04101

　　

2/501−1/5−2/51/5

 

　　

11/5107/5−1/5−2/5

 

　　009/58/51/5

　　则最优解为

，最优值为 .

 

　　(2)

 

　　解：将约束方程两边同时乘以

，再添加松弛变量 ，可得：

 

　　

 

　　利用对偶单纯形法求解：

　　

4121800

 

　　

 

　　

−3−10−310

 

　　

−50[−2]−201

 

　　4121800

　　

−3−10[−3]10

 

　　

5/20110−1/2

 

　　40606

　　

11/301−1/30

 

　　

3/2−1/3101/3−1/2

 

　　20026

　　则最优解为

.

 

　　《最优化方法》P.179

　　1.5 用单纯形法求解下列线性规划问题，并指出问题的解属于哪一类?

　　(1)

 

　　解： 首先添加松弛变量将线性规划模型化为标准型。

　　

 

　　建立单纯形表如下：

　　

-3-5000

 

　　

 

　　

410100

 

　　

120[2]0106

 

　　

18320019

 

　　

-3-5000

 

　　

4101004

 

　　

60101/20

 

　　

6[3]00-112

 

　　

-3005/20

 

　　

20011/3-1/3

 

　　

60101/20

 

　　

2100-1/31/3

 

　　

0003/21

 

　　因此最优解为

，最优值为36，且是唯一最优解。

 

　　(2)

 

　　解： 首先添加松弛变量将线性规划模型化为标准型。

　　

 

　　做单纯形表如下：

　　

-6-2-10-8000

 

　　

 

　　

2056-4-4100

 

　　

253-32801025/2

 

　　

104-2[1]300110

 

　　

-6-2-10-8000

 

　　

6021-208104

 

　　

5-5[1]0201-25

 

　　

104-213001

 

　　

34-220220010

 

　　

70110012120

 

　　

5-510201-2

 

　　

20-601702-3

 

　　

-760066022-34

 

　　因为

，故有无界解。

 

　　(3)

 

　　解：做变换

，然后化为标准型：

 

　　

 

　　建立初始单纯形表：

　　

-1-6-4000

 

　　

 

　　

4-1[2]21002

 

　　

214-41010

 

　　

91210019/2

 

　　

-1-6-4000

 

　　

2-1/2111/200

 

　　

920521029/2

 

　　

5[2]0-1-1015/2

 

　　

-402300

 

　　

13/4013/41/401/4

 

　　

2400631-1

 

　　

5/210-1/2-1/201/2

 

　　

000102

 

　　因为非基变量

的检验数 ，又所有的 ，所以本题有无穷多解。其中之一是 ，最优值为47

 

　　1.6 用大M法求解下列线性规划问题：

　　(1)

 

　　解：化为带人工变量的标准型:

　　

 

　　做单纯形表如下：

　　

-1-2-31MM

 

　　

 

　　

151230105

 

　　

2021[5]0014

 

　　

1012110010

 

　　

-2-3M-4-3M-4-8M000

 

　　

3-1/5[7/5]001-3/515/7

 

　　

42/51/51001/520

 

　　

63/59/5010-1/510/3

 

　　

(M-2)/5-(7M+16)/5000(8M+4)/5

 

　　

15/7-1/71005/7-3/7

 

　　

25/73/7010-1/72/725/3

 

　　

15/7[6/7]001-9/74/75/2

 

　　

-6/7000(7M+16)/7(4-7M)/7

 

　　

5/2010-1/61/2-1/3

 

　　

5/2001-1/21/20

 

　　

5/21007/6-3/22/3

 

　　

0001M+1M

 

　　故最优解为

，最优值为15。

 

　　1.7 用两阶段法求解上题。

　　第一阶段的LP问题为：

 

　　则第一阶段的单纯形表为：

　　

0000111

 

　　

 

　　

1512301005

 

　　

2021[5]00104

 

　　

10121100110

 

　　

-4-5-9-1000

 

　　

3-1/5[7/5]001-3/5015/7

 

　　

42/51/51001/5020

 

　　

63/59/5010-1/5110/3

 

　　

-2/5-16/50009/50

 

　　

15/7-1/71005/7-3/70

 

　　

25/73/7010-1/72/70

 

　　

15/76/700[1]-9/74/71

 

　　

-6/700-116/73/70

 

　　

15/7-1/71005/7-3/70

 

　　

25/73/7010-1/702/70

 

　　

15/76/7001-9/74/71

 

　　

0000111

 

　　第二阶段LP模型

 

　　

-1-2-31

 

　　

 

　　

15/7-1/7100

 

　　

25/73/701025/3

 

　　

15/7[6/7]0015/2

 

　　

-6/7000

 

　　

5/20101/6

 

　　

5/2001-1/2

 

　　

5/21007/6

 

　　

0001

 

　　最优解为

，最优值为15。

 

　　1.10 下表为某求最小化线性规划问题的初始单纯形表以及迭代后的表，

为松弛变量。试求表中a至l的值以及各变量下表m至t的值：

 

　　

 

　　

 

　　

6bcd10

 

　　

1-13e01

 

　　-z a1-200

　　

fg2-11/20

 

　　

4hi11/21

 

　　-z 07jkl

　　1.21 已知线性规划问题

　　

 

　　用单纯形法求得最终单纯形表如下表所示：

　　

-10-500

 

　　

 

　　-5

3/2015/14-3/14

 

　　-10

110-1/72/7

 

　　-z35/2005/1425/14

　　试用灵敏度分析的方法分别判断：

　　(1) 目标函数中价值系数

或者 分别在什么范围内变动，上述最优解不变。

 

　　(2) 约束条件右端项

当一个保持不变时，另一个在什么范围内变化时，原问题的最优基保持不变。

 

　　(3) 问题的目标函数变为

时，最优解如何变化?

 

　　(4) 约束条件右端项由

变为 时，最优解为多少?

 

　　解：(1) 由最终单纯形表可知

(为什么?)

 

　　要使得最优解不变，则需保持新的检验数

。

 

　　下设只有

变化时。

 

　　

 

　　即有

 

　　

 

　　即有

 

　　也就是说

保持在 之间变化时，最优解不会变化。

 

　　同理

在 变化时，最优解保持不变。

 

　　(2) 根据灵敏度分析可知只要保持

即可。

 

　　假设

变化， 保持不变。则有下列要求：

 

　　

 

　　因此当

保持不变时， 在区间 上变化时，最优基不变。

 

　　同样的当

不变时， 在区间 上变化时，最优基不变。

 

　　(1) 问题的目标函数变为

，也就是说价值系数变成为 ，计算新的检验数可得：

 

　　

 

　　即

得新检验数 ，以 为进基变量进行迭代.

 

　　

-12-400

 

　　

 

　　

3/201[5/14]-3/14

 

　　

110-1/72/7

 

　　00-2/718/7

　　

21/5014/51-3/5

 

　　

8/512/501/5

 

　　04/5012/5

　　最优解为

。

 

　　(4)

 

　　则利用对偶单纯形法进行迭代。

　　

-10-500

 

　　

 

　　

-1/7015/14[-3/14]

 

　　

27/710-1/72/7

 

　　005/1425/14

　　

2/30-14/3-5/31

 

　　

11/314/31/30

 

　　025/310/30

　　则最优解为

。

 

　　1.22 已知线性规划问题

　　

 

　　用单纯形表求解得最终单纯形表如下所示：

　　

-21-100

 

　　

 

　　-2

611110

 

　　0

1003111

 

　　-z1203120

　　当增加一个新的约束条件：

时，求新的最优解。

 

　　解： 在新的约束条件两边同时乘以(-1)，则约束条件变为

，添加松弛变量 可得 。则在原最终单纯形表的基础上添加一行(新的约束方程)和一列( 列)得：

 

　　

-21-1000

 

　　

 

　　-2

6111100

 

　　0

10031110

 

　　0

-210-2001

 

　　031200

　　因为

是基变量，所以要将 所对应的列向量通过初等行变换变为单位矩阵的列向量，也就是将第一行元素×(-1)加到第三行的对应元素，然后用对偶单纯形法进行迭代。即有下列表格：

 

　　

-21-1000

 

　　

 

　　-2

6111100

 

　　0

10031110

 

　　0

-80-1[-3]-101

 

　　-z 031200

　　-2

10/312/302/301/3

 

　　0

22/308/302/311/3

 

　　-1

8/301/311/30-1/3

 

　　-z 03/805/301/3

　　则新的最优解为

 

　　《最优化方法》P.242

　　习题2

　　2.1 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使得总的钻探费用最小. 若10个井位的代号为

，相应的钻探费用为 ，并且井位选择要满足下列限制条件：

 

　　(1) 或选择

和 ，或选择钻探 ;

 

　　(2) 选择了

或 ，就不能选择 ，或反过来也是一样;

 

　　(3) 在

中最多能选择两个。

 

　　试建立这个问题的整数规划模型(不必求解)。

　　解：引入0-1变量，当

时表示钻井队不在 处钻井， 时表示钻井队在 处钻井，则线性规划如下：

 

　　

 

　　2.2 用分支定界法求解下列整数规划问题：

　　(1)

(2)

 

　　解：(1) 设原规划问题为

，去掉整数条件之后得到的伴随规划记为 ，即为如下形式：

 

　　

 

　　可用图解法或者单纯形法求解，得最优解以及最优值分别：

　　

.则确立初始上界 ，下界 不妨令其为零。 都不是整数，任选其一进行分枝，不妨选取 ，则在问题 中分别添加约束条件： 和 ，得到问题 和问题 :

 

　　

 

　　分别求解可得问题

的最优解为： ，最优值为 ;问题 的最优解为： ，最优值为 .

 

　　此时，修改上界为

，由于没有求得整数可行解所以下界不用修改。这时，问题 和问题 都需要继续进行分枝，选取目标函数值较大的问题 进行分枝。添加约束条件： 和 ，得到问题 和问题 :

 

　　

 

　　同样，利用图解法或者单纯形法求得问题

的最优解为： ，最优值为 ;问题 无可行解. 此时，修改上界为 ，由于没有求得整数可行解，所以下界不用修改。对问题 进行分枝。添加约束条件： 和 ，得到问题 和问题 :

 

　　

 

　　分别求得问题

的最优解为： ，最优值为 ;问题 的最优解为： ，最优值为 .因为求得整数可行解，所以修改下界 。此时问题 的所有分枝都已查明，考虑对问题 进行分枝。但由于 ，所以不用再对问题 分枝。

 

　　故最优解为

和 ，最优值为4。

 

　　(2)设原规划问题为

，去掉整数条件之后得到的伴随规划记为 ，即为如下形式：

 

　　

 

　　可用图解法或者单纯形法求解，得最优解以及最优值分别：

　　

.则确立初始上界 ，下界 不妨令其为零。 都不是整数，任选其一进行分枝均可，不妨选取 ，则在问题 中分别添加约束条件： 和 ，得到问题 和问题 :

 

　　

 

　　分别求解可得问题

的最优解为： ，最优值为 ;问题 的最优解为： ，最优值为 .

 

　　此时，修改上界为

，修改下界为 。这时，问题 都需要继续进行分枝，添加约束条件： 和 后得到问题 和问题 :

 

　　

 

　　分别求解可得问题

的最优解为： ，最优值为 ;问题 无可行解. 此时，修改上界为 。对问题 进行分枝，添加约束： 和 ，得到问题 和问题 :

 

　　

 

　　分别求得问题

的最优解为： ，最优值为 ;问题 的最优解为： ，最优值为 .因为求得整数可行解，所以修改下界 。此时上界 等于下界 ，结束计算。

 

　　故最优解为

、 和 ，最优值为5。

 

　　2.3 用割平面法求解整数规划：

　　

 

　　解：首先求解整数规划的伴随规划

，将其标准化可得：

 

　　

 

　　用单纯形法可以求得：

　　

−7−900

 

　　

 

　　

6−1[3]102

 

　　

35710135

 

　　−7−900

　　

2−1/311/30

 

　　

33[22/3]0−1/319/2

 

　　−10030

　　

7/2017/221/22

 

　　

9/210−1/223/22

 

　　0028/1115/11

　　则最优解为

，最优值为63.

 

　　选择

做割平面方程，则由 ，可得

 

　　

，由于方程右边为大于等于零的数，所以得到割平面方程为 。方程两边同时乘以−1，再标准化之后可得 ，将其加入到伴随规划 中，构成新的伴随规划 并用对偶单纯形法求解：

 

　　

 

　　

−7−9000

 

　　

 

　　

7/2017/221/220

 

　　

9/210−1/223/220

 

　　

−1/200[−7/22]−1/221

 

　　0028/1115/110

　　

301001

 

　　

32/71001/7−1/7

 

　　

11/70011/722/7

 

　　00018

　　故最优解为

，对 割平面方程为： 。同上面的做法可得 ，将得到的割平面方程加入到伴随规划 中，可得问题 ：

 

　　

 

　　再次用对偶单纯形法求解：

　　

−7−90000

 

　　

 

　　

3010010

 

　　

32/71001/7−1/70

 

　　

11/70011/722/70

 

　　

−4/7000−1/7−6/71

 

　　000180

　　

3010010

 

　　

41000−11

 

　　

1001016/71

 

　　

400016−7

 

　　000027

　　所以最优解为：

，最优值为55

 

　　2.5 用匈牙利法求解下述指派问题，已知效率矩阵分别如下：

　　(1)

(2)

 

　　(1)解：

 

　　

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为1， 因此打 行都减去1，打 列都加上1. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为2， 因此打 行都减去2，打 列都加上2. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　因此决策变量矩阵为

　　

 

　　最优值为 48.

　　(2)解：

　　

 

　　

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为2， 因此打 行都减去2，打 列都加上2. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　因此决策变量矩阵为

　　

 

　　最优值为 21.

　　2.6 分配A,B,C,D 4个人去完成5项任务：Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ，每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可以完成两项任务，其余3人每人完成1项任务，试确定总花费时间最少的指派方案。

　　任务

　　人员ⅠⅡⅢⅣⅤ

　　A2529314237

　　B3938262033

　　C3427284032

　　D2442362345

　　解： 因为人数比任务书少，所以设有假想的人员E。假想人员E做工作Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ的时间分别为A,B,C,D四人中做工作Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ的时间最少者。即有下表：

　　任务

　　人员ⅠⅡⅢⅣⅤ

　　A2529314237

　　B3938262033

　　C3427284032

　　D2442362345

　　E2427262032

　　则效率矩阵为：

　　

 

　　

将上述矩阵记作 ， 则 中未被覆盖部分元素最小值为1， 因此打 行都减去1，打 列都加上1. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为4， 因此打 行都减去4，打 列都加上4. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　因此决策变量矩阵为

　　

 

　　即有A做工作Ⅱ，B做工作Ⅲ，C做工作Ⅴ，D做工作Ⅰ，假想人员E做工作Ⅳ，而A,B,C,D四人当中B做工作Ⅳ用时最少，所以B做工作Ⅲ和Ⅳ。总时间花费为131.

　　2.7 现有A,B,C,D,E 5个人，挑选其中4个人去完成4项工作。已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担第Ⅳ项工作，问应如何分配，才能使完成4项工作总的花费时间最少?

　　人

　　工作ABCDE

　　Ⅰ1023159

　　Ⅱ5101524

　　Ⅲ15514715

　　Ⅳ20151368

　　解：由于人员数大于工作数，故设有假想的工作Ⅴ。因为A必须有工作，即表示A不能做工作Ⅴ，所以设A做工作Ⅴ的时间为M，其中M表示任意大的正数。同理D做工作Ⅳ的时间也为M。则有效率矩阵：

　　

 

　　

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为1， 因此打 行都减去1，打 列都加上1. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　因此决策变量矩阵为

　　

 

　　即有A做工作Ⅱ，B做工作Ⅲ，C做工作Ⅰ，D不做工作， E做工作Ⅳ。总时间花费为21.

　　2.8 用4台机器加工4种不同零件，由于各机床性能不同，加工每一零件时，单位时间获得利润也不同，其效率如下表所示，求利润最大的分配方案。

　　零件

　　机床

 

　　

35272837

 

　　

28342940

 

　　

35243233

 

　　

24322528

 

　　解：这是一个求最大化的整数规划问题，有效率表中可知

　　

，故作 得矩阵：

 

　　

 

　　

 

　　

 

　　

 

　　将上述矩阵记作

， 则 中未被覆盖部分元素最小值为2， 因此打 行都减去2，打 列都加上2. 得到矩阵 。再用圈0法找到 中独立零元素组。

 

　　

 

　　因此决策变量矩阵为

　　

 

　　即用机床

生产零件 ，机床 生产零件 ，机床 生产零件 ，机床 生产零件 。此时利润为139。
http://img.chinazhaokao.com/uploadfile/2016/0818/20160818024617843.doc

线性规划例题相关热词搜索：例题