线性规划基础样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

第一章 线性规划基础

一．判断正误
1．线性规划问题的一般模型中不能出现等式约束。
2．在线性规划模型的标准型中,bj ( j=1, 2, …m) 一定是非负的。
3．线性规划一般模型中的变量不一定是非负的。
4．用图解法求最优解时, 只需求出可行域顶点对应的目标值, 经过比较大小, 就能找
出最优解。
5．一般情况下, 松弛变量和多余变量的目标函数系数为零。
二．简答题
1．简述线性规划问题数学模型的组成部分及其特征。
2．简述建立线性规划问题数学模型的步骤。
3．简述化一般线性规划模型为标准型的方法。
三．解答题
1．判断下列模型是否为线性规划模型 ( 其中a, b, c均为常数)
( 1) min Z =cjxj ( 2) max Z = cjxj
aijxj ≤ bi aijxj ≤ bi
xj ≥0 x5, …, xn≥0
i=1, 2, … , m; j=1, 2, …, n. x1 ~ x4无约束
i=1, 2, … , m; j=1, 2, …, n.
( 3) min Z =ai2xi+bj2yj ( 4) max Z= ci2xi - aj2yj
xi + yj≤cij2 xi( ai-yj) ≤bij
i=1, 2, … , m; j=1, 2, …, n. i=1, 2, … , m; j=1, 2, …, n.
2．将下列线性规划模型化为标准型。
( 1) min Z =2x1+x2-2x3 ( 2) max Z=2x1+x2+3x3+x4
-x1+x2+x3 =4 x1 + x2 + x3+ x4≤7
-x1+x2-x3 ≤6 2x1 -3x2 +5x3 =-8
x1 ≤0, x2 ≥0, x3无约束 x1 -2x3+2x4≥1
x1 , x3≥0, x2≤0, x4无约束
( 3) min Z =3x1 -4x2 +2x3 -5x4
4x1 -x2 +2x3 -x4 ≥2
x1 +x2 +3x3 +4x4≤20 x1≤0, x2≥0, x3≥0, x4无约束
( 4) max Z= cijxij
xij ≤ai
xij = bj xij ≥ 0,( i=1, 2, … , m; j=1, 2, …, n)
3．用图解法解下列线性规划问题。
( 1) max Z =10x1+5x2 ( 2) min Z =-x1 +2x2
3x1 +4x2 ≤9 x1 +x2≤5
5x1 +2x2 ≤8 2x1 +3x2≥6
x1 , x2 ≥0 -x1 +x2≤3
x1 , x2 ≥0
( 3) max Z = x1 +2x2 ( 4) min Z = x1 +3x2
-x1 +2x2 ≤4 x1 +x2≤1
x1 , x2 ≥0 x1 +2x2≥4
x2 ≥0
4．给定线性规划问题
max Z =2x1 +3x2
x1 + x2 ≤2
4x1 +6x2≤9 x1 , x2 ≥0
( 1) 指出可行域上的两个最优顶点及最优值。
( 2) 写出全部最优解的集合。
5．建立下列问题的线性规划模型并化为标准型
( 1) 、 某工厂生产A1、 A2两种产品, 有关的信息由下表给出, 建立制定最优生产计划的模型( 利润最大) 。
每件产品所用资源
定额aij
产品Aj
资源上限bi
A1
A2
资
源
i
资源1
9
4
3600
资源2
4
5

资源3
3
10
3000
利润Cj
70
120

( 2) 、 某厂车间有B1、 B2两个工段, 可生产A1、 A2和A3三种产品。各工段开工一天的产量和成本以及合同对三种产品的最低需求量由下表给出。建立求使成本最低并能满足需求的开工计划的模型。

生产定额( 吨/天)
工段Bj
合同每周最低需
求量( 吨)
B1
B2
产
品
Ai
A1
1
1
5
A2
3
1
9
A3
1
3
9
成本( 元/天)
1000

( 3) 、 假定市场上有i种食品, 单位售价是ci, 有m种营养成分。为达到营养平衡, 每人每天必须摄取不少于bj个单位的第j种营养成分。第i种食品的每个单位含有aij个单位的第j种营养, 建立确定最佳饮食水平的模型( i=1, 2, …, m; j=1, 2, …, n) 。
( 4) 、 某工厂生产A、 B两种产品, 已知生产A每公斤要用煤9吨、 电4度、 劳动力3个; 生产B每公斤要用煤4吨、 电5度、 劳动力10个。又知每公斤A、 B的利润分别为7万元和12万元。现在该工厂只有煤360吨、 电200度、 劳动力300个。问在这种情况下, 各生产A、 B多少公斤, 才能获最大利润, 请建立模型。
( 5) 、 某工厂生产A、 B两种产品, 每公斤的产值分别为600元和400元。又知每生产1公斤A需要电2度、 煤4吨; 生产1公斤B需要电3度、 煤2吨, 该厂的电力供应不超过100度, 煤最多只有120吨, 问如何生产以取得最大产值? 建立模型, 用图解法求解。

第二章 单纯形法

一．填空题
1．若基本可行解中非0变量的个数 于约束条件的个数时, 就会出现退化解。
2．线性规划问题若有最优解, 一定能够在可行域的 达到。
3．确定初始基本可行解时, 对大于型的约束, 应当引入 变量。
4．目标函数中人工变量前面的系数±M( M是充分大的正数) 的作用是 。
5．解包含人工变量线性规划问题的单纯形法有 有 。
二．判断正误
1．线性规划问题的基本解一定是基本可行解。
2．线性规划问题的最优解只能在可行域的顶点上达到。
3．图解法与单纯形法求解的形式不同, 但从几何上理解, 两者是一致的。
4．单纯形法计算中, 选取最大正检验数对应的变量作为换入变量, 将使目标函数的值增加更快。
5、 用单纯形法求解标准型线性规划问题时, 与检验数大于0相对应的变量都可被选作换入变量。
三．简答题
1．针对不同形式的约束( ≥, =, ≤) 简述初始基本可行解的选取方法。
2．简述如何在单纯型表上判别问题是否具有唯一解、 无穷多解、 无界解或无可行解。
3．简述若标准型变为求目标函数最小, 则用单纯形法计算时, 如何判别问题已取得最优解。
四、 解答题
1．找出下列线性规划问题的一组可行解和基本可行解。
( 1) max Z = 40x1 +45x2 +24x3 ( 2) min Z = x1 -2x2 +x3 -3x4
2x1 +3x2 +x3 ≤ 100 x1 +x2 +3x3 +x4=6
3x1 +3x2 +2x3≤ 120 -2x2 +x3 +x4 ≤3
xj ≥ 0 j=1, 2, 3 -x2 +6x3 -x4≤4
xj ≥ 0 j=1, 2, 3 , 4
( 3) min Z = 4x1 +x2 +x3 ( 4) min Z = 6x1 +4x2
2x1 +x2 +2x3=4 2x1 +x2 ≥1
3x1 +3x2 +x3=3 3x1 +4x2 ≥1.5
xj ≥ 0 j=1, 2, 3 xj ≥ 0 j=1, 2
2．给定线性规划问题, 判断下列向量是否能作为可行解。
min Z = 4x1 +5x2-2x3
x1 +x2 +x3 =1
2x1 +3x2 =1
xj ≥ 0 j=1, 2, 3
(1). X=(2,-1,0) (2). X=(0,1/3,2/3) (3). X=(1/2,0,1/2) (4). X=(5,-3,-1)
3．已知单纯形表如下, 其中x1,x2,x3表示三种产品的产量, x4,x5是松弛变量( 目标函数为max Z)
Cj
40
45
24
0
0
CB
XB
b
x1
x2
x3
x4
x5
45
x2
100/3
2/3
1
1/3
1/3
0
0
x5
20
1
0
1
-1
1
Zj
30
45
15
15
0
Cj-Zj
10
0
9
-15
0

( 1) 、 写出此时生产方案, 并判断是否最优生产方案。
( 2) 、 该生产方案下每种产品的机会费用。
( 3) 、 以此表为基础, 请求出最优生产方案。
4．根据单纯形表判断解的类型。
( 1)
Cj
0
0
0
0
-1
CB
XB
b
x1
x2
x3
x4
x5
0
x1
10
1
1
1
0
0
-1
x5
20
0
-1
-2
-1
1
Zj
0
1
2
1
-1
Cj-Zj
0
-1
-2
-1
0
其中x5为人工变量, 目标为max Z 。
( 2)
Cj
15
20
25/ 3
0
0
CB
XB
b
x1
x2
x3
x4
x5
20
x2
20
0
1
-1/3
1
-2/3
15
x1
20
1
0
1
-1
1
Zj
15
20
25/3
5
5/3
Cj-Zj
0
0
0
- 5
-5/3
其中x4, x5为松弛变量, 目标为max Z
( 3)
已知单纯形表, 请确定a12,a22,a32满足什么条件时, 此问题有无限界解。

Cj
1
1
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x3
8
0
a12
1
2
0
1
x1
2
1
a22
0
1
0
0
x5
9
0
a32
0
3
1
Zj
1
Z2
0
1
0
Cj-Zj
0
C2-Z2
0
-1
0

5．求出单纯形表中未知数的值, 并判断解是否最优解。
( 1) 、 目标函数为max Z =5x1+3x2, 约束形式为”≤”, 且x3,x4为松弛变量, 表中的解代入目标函数中得Z=10, 求出a~g的值。

Cj
5
3
0
0
CB
XB
b
x1
x2
x3
x4
0
x3
2
c
0
1
1/5
5
x1
a
d
e
0
1
Cj-Zj
b
-1
f
g
( 2) 、 目标函数为max Z =28x4+x5+2x6, 约束形式为”≤”, 且x1, x2, x3为松弛变量,
表中的解代入目标函数中得Z=14, 求出a~g的值, 并判断是否最优解。

Cj
0
0
0
28
1
2
CB
XB
b
x1
x2
x3
x4
x5
x6
1
x6
a
3
0
-14/3
0
1
1
0
x2
5
6
d
2
0
5/2
0
28
x4
0
0
e
f
1
0
0
Cj-Zj
b
c
0
0
-1
g

6．用单纯形法求解下列线性规划。
( 1) min Z =-5x1 -4x2 ( 2) max Z =5x1 +2x2 +3x3 -x4 +x5
x1 +2x2 ≤6 x1 +2x2 +2x3 +x4=8
2x1 -x2 ≤4 3x1+ 4x2 +x3 +x5=7
5x1 +3x2 ≤15 xj≥0, i=1, 2, …5
x1 , x2 ≥0
( 3) min Z = 3x1 -x2 ( 4) max Z = 3x1 +5x2
-x1 +3x2 ≤3 x1 ≤4
-2x1 -3x2 ≤6 2x2 ≤12
2x1 +x2 ≤2 3x1 +2x2 ≤18
x1, x2 无约束 x1, x2≥0
7．分别用大法和两阶段法求解下列线性规划。
( 1) max Z = 4x1 +6x2 ( 2) min Z = -3x1 +x2
2x1 +4x2 ≤16 -x1 +2x2 ≤2
x1 +x2 = 6 4x1 +x2 ≥4
x1, x2≥0 x1, x2 ≥0
8．求解第一章解答题5中的( 1) 、 ( 2) 、 ( 4) 。

第三章 线性规划模型的建立

一．判断正误
1．同一问题的线性规划模型是唯一的。
2．由应用问题建立的线性规划模型中, 其约束方程有多种形式。
二．简答题
1．简述本章范围内线性规划所能解决的实际问题的类型及建模方法。
三．解答题
1．建立下列应用问题的线性规划模型
( 1) 、 某饲养厂饲养动物出售, 设每头动物每天至少需700克蛋白质、 30克矿物质和100毫克维生素, 现有三种饲料可供选择, 各饲料每公斤的营养成分和单价如下表所示:

饲料
蛋白质( 克)
矿物质( 克)
维生素( 毫克)
价格( 元/千克)
1
3
1
0.5
0.2
2
2
0.5
1
0.7
3
1
0.2
0.2
0.4
要求确定既满足动物生长要求, 又使费用最少的选用饲料方案。
( 2) 、 某工厂机械加工车间, 要在2种不同类型的机床上加工1号、 2号两种零件, 并要求两种零件的数量保持1: 1 的配套比例。机床台数和生产效率由下表给出, 请安排机床5日内的加工任务, 使成套产品的数量达到最大。

机车类型
机车台数
日产1号零件( 千件/台)
日产2号零件( 千件/台)
1
30
15
20
2
10
30
55

( 3) 、 某化工厂生产宽度为60个单位长的标准玻璃纸, 现需将这种玻璃纸截成宽度分别为28、 20和15个单位长的三种规格的产品。已知它们的市场需求分别为30、 60和80卷, 问应以怎样的方法裁剪, 可使消耗的标准玻璃纸最少而又能满足市场需要。
( 4) 、 一家昼夜服务的饭店, 24小时需要的服务员人数如下表所示:

起讫时间
需要服务员的最少人数
2 ~ 6
4
6 ~ 10
8
10 ~ 14
10
14 ~ 18
7
18 ~ 22
12
22 ~ 2
4
每个服务员每天连续工作8个小时, 且在时段开始上班。求满足上述要求的最少上班人数, 请建立线性规划模型。
( 5) 、 有A、 B两种产品, 都需要经过前后两道化学反应过程。生产每一单位A、 B所需时间的消耗如下表所示:

时间消耗
前道过程
后道过程
A
2
3
B
3
4
可利用时间
16
24
在不增加任何费用的情况下, 每生产一个单位的B会产生2单位的副产品C; C能够出售赢利, 其余只能加以销毁。出售每单位A能赢利4元, 每单位B能赢利10元, 每单位C赢利3元, 若卖不出, 每单位C的销毁费用是2元, 预测表明, 最多能够出售5个单位的副产品C。要求确定使总利润达到最大的A和B的产量, 建立线性规划模型。
2．建立模型并求解。
( 1) 、 某厂生产甲、 乙、 丙三种产品, 已知有关数据如下表所示:

消耗 产品
原料
甲
乙
丙
原料量
A
6
3
5
45
B
3
4
5
30
单件利润
4
1
5

求使该厂获利最大的生产计划。

( 2) 、 从M1、 M2、 M3三种矿石中提炼A、 B两种金属。已知每吨矿石中金属A、 B的含量和各种矿石的价格如下表所示:

金属品种
矿石中金属含量( 克/ 吨)
M1
M2
M3
A
300
200
60
B
200
240
320
矿石价格( 元/ 吨)
60
48
56
如需金属A为 48千克, B为 56千克, 问用各种矿石多少吨, 可使总的费用最少。

第四章 对偶问题及对偶单纯形法

一．填空:
1．对偶单纯形法与单纯形法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 约束。
2．若原问题有最优解, 那么对偶问题 有最优解, 且原问题与对偶问题的最优
相等。
3．原问题可行, 而对偶问题不可行, 则原问题 界。
4．对偶问题的对偶问题是 问题。
5．若原问题中第i个约束条件是”=”型约束, 那么对偶问题的变量qi应是 变量。
二．判断正误
1．任何线性规划问题存在并具有唯一的对偶问题。
2．对偶问题的对偶不一定是原问题。
3．若原问题可行, 而对偶问题不可行, 则原问题无界。
4．若原问题有无穷多最优解, 则其对偶问题也一定有无穷多最优解。
5． yi为对偶问题的最优解, 若yi>0, 说明在最优生产计划中第i种资源已完全耗尽。
三．简答题
1．简述对偶单纯形法的计算过程及它的优点。
2．怎样根据最优单纯形表找出原问题与对偶问题的变量、 最优解及检验数之间的对应关系。
四．解答题
1．根据对偶规则填表:

原问题
对偶问题
A
约束系数矩阵

b
约束条件右端向量

C
目标函数中的价格系数向量

目标函数
Max Z = CX
W=
约束条件
AX≤b

决策变量
X≥0
Q≥0

2．已知某规划的最优单纯形表如下。x3、 x4、 x5为原问题的松弛变量, 对偶问题的变量为q1、 q2、 q3、 q4、 q5, 其中q4、 q5为剩余变量。用qi填表并指出对偶问题的解。

XB
b
x1
x2
x3
x4
x5
x3
15/2
0
0
1
5/4
-15/2
x1
7/2
1
0
0
1/4
-1/2
x2
3/2
0
1
0
-1/4
3/2
Ci-Zj
0
0
0
-1/4
-1/2
填上qi

3．已知下表为求解线性规划问题的最终单纯形表, 表中x4、 x5为松弛变量, 问题的约束为”≤”, 请写出对偶问题的最优解。

XB
b
x1
x2
x3
x4
x5
x3
5/2
0
1/2
1
1/2
0
x1
5/2
1
-1/2
0
-1/6
1/3
Cj-Zj
0
-4
0
-4
-2

4．根据对偶单纯形表( x4, x5, x6为松弛变量) 判断是否取得了最优解? 若不是, 请分别求出原问题与对偶问题的最优解。

Cj
40
45
24
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
45
x2
20
0
1
-1/3
1
-2/3
0
40
x1
20
1
0
1
-1
1
0
0
x6
-5
0
0
-1
1
-1
1
Zj
40
45
25
5
10
0
Cj-Zj
0
0
-1
-5
-10
0

5．写出下列线性规划问题的对偶问题并求出最优解, 并指出原问题的最优解。
( 1) min Z = 60x1 +40x2 +80x3 ( 2) max Z =2x1 +3x2
3x1 +2x2 +x3 ≥2 x1 +2x2≤2
4x1 +x2 +3x3 ≥4 2x1 -x2≤3
2x1 +2x2 +2x3 ≥3 3x1 +x2≤5
xj ≥0 , j=1, 2, 3 x1 -3x2≤6
x1 , x2≥0
( 3) min Z = 20x1 +20x2
x1 +2x2 ≥1
2x1 +x2 ≥2
2x1 +3x2≥3
3x1 +2x2≥4 x1 , x2 , x3 , x4≥0
6．已知某线性规划问题的最优单纯形表如下, 求出增加了约束条件的最优解。

Cj
6
4
0
0
CB
XB
b
x1
x2
x3
x4
4
x2
2
0
1
1/3
-1/3
6
x1
5/2
1
0
-1/6
2/3
Zj
6
4
1/3
8/3
Cj-Zj
0
0
-1/3
-8/3
( 1) x1≤2 ( 2) x2≥3

五．证明若X是原问题的可行解, Q是对偶问题的可行解, 则C X≤Q, 其中C, b 满足:
max Z = CX , AX ≤ b, X ≥0 。
第六章 运输问题

一．判断正误
1．运输问题的求解结果可能出现下列4种情况之一: 有唯一解; 有无穷多最优解; 无界解; 可行解。
2．在运输问题中, 只要给出一组含有( m + n -1) 个非零的xij且满足全部约束, 就能够作为基本可行解。
3．按最小元素法给出的初始基本可行解, 从每一个空格出发仅能找出唯一的闭回路。
4．表上作业法中, 任何一种确定初始基本可行解的方法都必须保证有( m + n -1) 个变量。
5．当所有产量和销量均为整数值时, 运输问题的最优解也为整数解。
二．简答题
1．简述西北角法、 最小元素法、 差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。
2．简述把产销不平衡化为产销平衡问题的基本过程。
3．简述运输方案的调整过程。
三．解答题
1．判断表( 1) ( 2) ( 3) ( 4) 中给出的调运方案能否作为表上作业法的初始解, 为什么?
( 1)
销地
产地

B1

B2

B3

B4

B5

B6

产量
A1
20
10

30
A2

30
20

50
A3

10
10
50
5
75
A4

20
20
销量
20
40
30
10
50
25

( 2)
销地
产地

B1

B2

B3

B4

B5

B6

产量
A1

30

30
A2
20
30

50
A3

10
30
10

25
75
A4

20

20
销量
20
40
30
10
20
25

( 3)
销地
产地

B1

B2

B3

B4

产量
A1

6
5
11
A2
5
4

2
11
A3

5
3

8
销量
5
9
9
7

( 4)
销地
产地

B1

B2

B3

B4

产量
A1
2
9

7
9
A2

2
5
A3

4
2

7
销量
3
8
4
6

2．根据表判断是否已取得了最优解, 为什么?
( 1)
销地
产地

B1

B2

B3

B4

产量

A1
(3)
2
(6)
9

10

7

9

A2

1
(2)
3
(3)
4

2

5

A3

8

4
(1)
2
(6)
5

7
销量
3
8
4
6

( 2)
销地
产地

B1

B2

B3

B4

产量

A1
(3)
2

9

10
(6)
7

9

A2

1
(5)
3

4
(0)
2

5

A3

8
(3)
4
(4)
2

5

7
销量
3
8
4
6

( 3)
销地
产地

B1

B2

B3

产量

A1
(1)
1

2

2

1

A2

3
(2)
1

3

2

A3
(0)
2
(0)
3
(4)
1

4
销量
1
2
4

( 4)
根据所给的表和一组解判断是否最优解, 若不是, 请求出最优解。
( x13, x14, x21, x22, x32, x34) =( 5, 2, 3, 1, 5, 4)

销地
产地

B1

B2

B3

B4

产量

A1

3

11

3

10

7

A2

1

9

2

8

4

A3

7

4

10

5

9
销量
3
6
5
6

3．分别用西北角法、 最小元素法、 差值法确定出下列运输问题作业表中的一组初始基本可行解, 并求出( 1) ,( 2) ,( 3) 的最优解。
( 1)
销地
产地

B1

B2

B3

B4

产量
A1
3
2
7
6
50
A2
7
5
2
3
60
A3
2
5
4
5
25
销量
60
40
20
15

( 2)
销地
产地

B1

B2

B3

B4

产量
A1
18
14
17
12
100
A2
5
8
13
15
100
A3
17
7
12
9
150
销量
50
70
60
80

( 3)
销地
产地

B1

B2

B3

B4

产量
A1
5
5
9
12
40
A2
11
8
13
13
30
A3
15
18
16
20
30
销量
5
15
35
50

( 4)
销地
产地

B1

B2

B3

B4

B5

产量
A1
10
20
5
9
10
9
A2
2
10
8
30
6
4
A3
1
20
7
10
4
8
销量
3
5
4
6
3

4．建立下列实际问题的产销平衡表, 并找出一组初始可行解、 求出最优解。
A、 B 两个煤矿生产优质煤供应D、 E、 F三个电厂, 单位运价( 元/吨) 表如下:
另外, 电厂D不能缺煤, 电厂E、 F每缺1吨煤, 煤矿将被分别罚款2、 3元。
求使总费用最少的调运计划。

电厂
煤矿

D

E

F
A
3
11
3
B
1
9
2

( 1) 、 若A、 B的月产量分别为7万吨, 电厂的需求量依次为3、 6、 5万吨。
( 2) 、 若A、 B的月产量分别为23、 17万吨, 电厂的需求量依次为16、 10、 9万吨。
( 3) 、 若A、 B的月产量分别为20、 25万吨, 电厂的需求量依次为18、 17、 15万吨,
5．求下列与系数矩阵对应的标准指派问题的最优解。
( 1) 、
2 15　1３ 7 9 10 12
10 4 10 13 12 16 17
9 14 16 15 16 14 15
11 12 15 16

7．有一份说明书, 要分别译成英、 日、 德、 俄四种文字( 分别用E、 J、 G、 R表示) , 由甲、 乙、 丙、 丁四人去完成。每个人完成任务所需时间见表所示。问怎样安排, 才能使所用的时间最少?

人员
任务

E

J

G

R
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9

第七章 整数规划
一．填空
1．若某线性规划中只有一部分变量限制为整数, 则称该规划为 规划。
2．全部变量都是0—1变量的规划问题称为 规划。
3．对max Z型整数规划, 若最优非整数解对应的目标函数值为Zc, 最优整数解对应的目标值为Zd, 那么一定有 ≥ 。
4．如果一种产品, 要么不生产, 要么产量大于K, 设产量为xk( xk≥0) , 那么满足上述约束条件的方程为 和 。
5.若是否采用j项目的0-1变量为xj, 那么J个项目中至多只能选择一个项目的约束方