线性规划课后题答案(张干宗).doc
《线性规划课后题答案(张干宗).doc》由会员分享，可在线阅读，更多相关《线性规划课后题答案(张干宗).doc（56页珍藏版）》请在冰点文库上搜索。
P11.3
（1）将下列线性规划模型化成标准形式：
解：
令，代入上面的线性规划，得标准形式
P14:
1、用图解法求解下列线性规划问题：
利用图解法：
于是得最优解为（4,1）,最优值为-10。
P15：
2
解：
利用图解法
于是最优解为（6，0），最优值为36。
P15.3
解：
利用图解法求得
有无穷多最优解，都落在一个线段上，该线段的两个端点是：
于是全部的最优解可以表示成与的凸组合，即
最优值都是-21。
P16:
1、解：
设表示第台机床加工第类产品的产量，于是可得数学模型
P16:
2、解：
设表示第食品的采购量，于是可得数学模型
P18:
9
（2）将下列线性规划问题变换成标准形式：
解：
令，则得
P18:
9（4）将下列线性规划问题变换成标准形式：
解：
此题关键是将目标函数中的绝对值去掉。
令
则有
因此都是非负变量。
于是原规划可以化成标准形式：
P19
13、某养鸡场有一万只鸡，用动物饲料和谷物饲料混合喂养，每天每只鸡平均吃混合饲料0.5公斤，其中动物饲料占的比例不得少于1/5。
动物饲料每公斤0.2元，谷物饲料每公斤0.16元。
饲料公司每周只保证供应谷物饲料21000公斤。
问饲料应怎样混合，才能使每天的总成本最低？
试建立问题的数学模型并求解（图解法）。
解：
设养鸡场每天用动物饲料和谷物饲料分别为公斤，则问题模型为
用图解法:
求得其最优解为
。
P19:
14
解:
设甲乙厂各处理万立方米/天；总费用元/天；考虑工厂1与工厂2所在的两点：
工厂1：
工厂2：
于是建立数学模型为：
目标函数
利用图解法，画图
求得其最优解为：
最优值为：
P37:
1
解：
线性规划问题
由第一个约束的3倍减去第二个约束的2倍，得
即
（1）
根据上式得到，再带回第一个约束，整理得
（2）
由
（1）、
（2）表示出，带入目标函数，整理得
于是整理得基对应的典式为：
根据典式，得基的基可行解是
同样根据典式，得基可行解的非基变量的检验数是
由于，因此不是最优解。
P37:
3
证明：
先化成标准形式
这个显然是可行基对应的典式，注意到，
因此该线性规划目标值趋于负无穷，原线性规划目标函数趋于正无穷，即没有最优解。
证毕。
P46:
1、用单纯形法求解下列线性规划问题：
（1）
解：
先转化成标准形式
选为初始的基变量组，得单纯形表
X1
X2
X3
X4
X5
X6
f
0
-1
1
-1
0
0
0
X4
X5
X6
2
3
4
1
2
-1
1
1
0
-2
1
1
1
0
0
0
1
0
0
0
1
f
-2
-2
0
1
-1
0
0
X2
X5
X6
2
1
4
1
1
-1
1
0
0
-2
3
1
1
-1
0
0
1
0
0
0
1
f
-7/3
-7/3
0
0
-2/3
-1/3
0
X2
X3
X6
8/3
1/3
11/3
5/3
1/3
-4/3
1
0
0
0
1
0
1/3
-1/3
1/3
2/3
1/3
-1/3
0
0
1
最后一个单纯形表的检验数全部非正，得最优解为
最优值为
（2）
解：
选为初始的基变量组，化为典式：
得单纯形表
X1
X2
X3
X4
f
3
0
3
-1
0
X1
X4
1/2
7
1
0
1/2
1
-1/2
3
0
1
f
0
-6
0
2
0
X2
X4
1
6
2
-2
1
0
-1
4
0
1
f
-3
-5
0
0
-1/2
X2
X3
5/2
3/2
3/2
-1/2
1
0
0
1
1/4
1/4
最后一个单纯形表的检验数全部非正，得最优解为
最优值为
P63：
1.用两阶段法解下列线性规划问题：
解：
首先化成标准形式
由于上面的规划的系数矩阵中存在一个单位向量，因此只需要在添加一个人工变量，构造辅助问题：
选为初始基变量组，化成典式：
于是初始单纯形表为：
X1
X2
X3
X4
z
4
2
-1
0
0
X3
X4
3
4
1
2
2
-1
1
0
0
1
X1
X2
X3
X4
z
0
0
0
0
-1
X3
X1
1
2
0
1
5/2
-1/2
1
0
-1/2
1/2
得辅助问题的最优解，且此时人工变量已经出基，因此得原问题的一个初始可行基及其不完全形式的典式（去掉上表中的人工变量列及检验数行）：
根据约束条件得，带入目标函数中，得典式：
由于检验数，因此应用得到原问题的一个最优解
原问题的最优值为
P63：
3.用两阶段法解下列线性规划问题：
解：
先转化成标准形式
然后加入人工变量，构造辅助问题：
选为初始的基变量组，化成典式：
得单纯形表:
X1
X2
X3
X4
X5
X6
z
5
1
-2
-1
-1
0
0
X5
X6
2
3
2
-1
-3
1
-1
0
0
-1
1
0
0
1
z
4
0
-1/2
-1/2
-1
-3/2
0
X1
X6
1
4
1
0
-3/2
-1/2
-1/2
-1/2
0
-1
1/2
1/2
0
1
于是得到辅助问题的最优解为：
最优值为
由于，因此原问题无可行解。
P75：
1.对线性规划问题
验证是否为可行基？
如果是，求出其典式。
解：
对于来说，为基变量，为非基变量。
令，代入问题的约束中，得，于是得基解
由于0，因此是一个可行基。
下面将问题化成基的典式。
约束条件
转换成。
转换成，即。
转换成。
目标函数。
于是，基的典式为：
P76：
5
（1）用单纯形法求解下列线性规划问题：
解：
将模型化为
选为初始的基变量组，化成典式：
单纯形表为：
X1
X2
X3
X4
X5
z
23
0
0
2
-4
-3
X1
X2
2
5
1
0
0
1
[1]
2
-1
0
0
-1
z
19
-2
0
0
-2
-3
X3
X2
2
1
1
-2
0
1
1
0
-1
2
0
－1
最后一个单纯形表的检验数全部非正，得最优解为x＝（0,1,2）；最优值为f＝19。
P76：
5
（2）用单纯形法求解下列线性规划问题：
解：
选作为初始的基变量组，根据第二个约束求出，带入目标函数，整理得标准形式：
于是，得单纯形表：
X1
X2
X3
X4
X5
f
150
69/2
0
71
0
0
X4
X5
2
3
1/2
3/4
-2/3
0
1/2
3/2
1
0
0
1
X1
X2
X3
X4
X5
f
8
-1
0
0
0
-142/3
X4
X3
1
2
1/4
1/2
-2/3
0
0
1
1
0
-1/3
2/3
最后一个单纯形表的检验数全部非正，得最优解为
最优值为
P79
19对线性规划问题：
不经单纯形迭代，证明为其最优基，并求出最优解。
解：
先标准化：
令，则
于是
因此对应的基可行解为
检验数为：
因此为其最优基，即为最优解。
P99第4题：
判断下列关于对偶问题的说法是否正确：
（1）若原问题存在可行解，则其对偶问题必定存在可行解；（错误，因为对偶问题也可能无可行解）
（2）若对偶问题无可行解，则原问题必定无可行解；（错误，因为对偶问题也可能无界解，当然此时对偶问题一定无最优解）
（3）若原问题和对偶问题都有可行解，则两者必都有最优解。
（正确）
P99第5题：
设LP有最优解，并设（LP）’：
有可行解。
试利用对偶理论证明：
（LP）’必有最优解。
证：
首先根据LP有最优解及对偶理论知：
一定存在最优解，因此一定有可行解。
又（LP）’的对偶问题是
其约束与LP对偶规划的约束一样，因此根据LP的对偶存在可行解推知，其也存在可行解。
结合对偶理论和（LP）’存在可行解知，（LP）’必有最优解。
证毕。
P99第6题：
解：
所给线性规划问题的对偶规划是：
由于对偶规划只有两个决策变量，因此可以利用比单纯形法更简单的图解法来求解。
利用图解法求得：
对偶问题的最优解为：
下面利用互补松弛性求解原问题的最优解。
由于
因此它们的互补约束均为紧约束，即
（1）
又由于
于是其对偶约束也是紧约束，即
（2）
将
（2）带入
（1），得
求解该方程得：
于是原问题的最优解为：
P99：
7、
解：
设分别表示A型，B型产品的产量，则所给问题的数学模型为：
其对偶规划为：
先将原问题化成标准形式：
选为初始的基变量组，做表如下：
x1
x2
x3
x4
x5
f’
0
5
4
0
0
0
x3
90
1
3
1
0
0
x4
80
2
1
0
1
0
x5
45
1
1
0
0
1
f’
-200
0
3/2
0
-5/2
0
x3
50
0
5/2
1/2
-1/2
0
x1
40
1
1/2
0
1/2
0
x5
5
0
1/2
0
-1/2
1
f’
-215
0
0
0
-1
-3
x3
25
0
0
1/2
2
-5
x1
35
1
0
0
1
-1
x2
10
0
1
0
-1
2
于是所求问题的最优解为：
对偶问题的最优解为：
最优值都是：
P105:
1、用对偶单纯形法求解下列线性规划问题：
解：
先将所给线性规划问题转化成：
选作为初始基变量，作出如下初始单纯形表：
x1
x2
x3
x4
x5
f
0
-5
-2
-4
0
0
x4
-4
-3
-1
-2
1
0
x5
-10
-6
-3
-5
0
1
x1
x2
x3
x4
x5
f
20/3
-1
0
-2/3
0
-2/3
x4
-2/3
-1
0
-1/3
1
-1/3
x2
10/3
2
1
5/3
0
-1/3
x1
x2
x3
x4
x5
f
22/3
0
0
-1/3
-1
-1/3
X1
2/3
1
0
1/3
-1
1/3
X2
2
0
1
1
2
-1
于是所求问题的最优解为：
最优值为：
P105:
2、用对偶单纯形法求解下列线性规划问题：
解：
先将所给线性规划问题转化成：
选作为初始基变量，作出如下初始单纯形表：
x1
x2
x3
x4
x5
x6
f
0
-3
-2
-1
0
0
0
x4
6
1
1
1
1
0
0
x5
-4
-1
0
1
0
1
0
X6
-3
0
-1
1
0
0
1
x1
x2
x3
x4
x5
x6
f
12
0
-2
-4
0
-3
0
x4
2
0
1
2
1
1
0
x1
4
1
0
-1
0
-1
0
X6
-3
0
-1
1
0
0
1
x1
x2
x3
x4
x5
x6
f
18
0
0
-6
0
-3
-2
x4
-1
0
0
3
1
1
1
x1
4
1
0
-1
0
-1
0
X2
3
0
1
-1
0
0
-1
由上面最后一个表格的第一行得方程：
显然上式与非负约束矛盾，因此该线性规划没有可行解。
P105:
3、用对偶单纯形法求解下列线性规划问题：
解：
先将所给线性规划问题转化成：
选作为初始基变量，作出如下初始单纯形表：
x1
x2
x3
x4
x5
x6
f
0
-1
-2
-3
0
0
0
x4
-4
-2
1
-1
1
0
0
x5
8
1
1
2
0
1
0
X6
-2
0
-1
1
0
0
1
f
2
0
-5/2
-5/2
-1/2
0
0
x1
2
1
-1/2
1/2
-1/2
0
0
x5
6
0
3/2
3/2
1/2
1
0
x6
-2
0
-1
1
0
0
1
f
7
0
0
-5
-1/2
0
-5/2
x1
3
1
0
-1
-1/2
0
-1/2
x5
3
0
0
3
1/2
1
3/2
X2
2
0
1
-1
0
0
-1
于是所求问题的最优解为：
最优值为：
P111:
1、解：
先化成标准形式
选做为初始基，建立扩充问题：
得如下单纯形表：
x1
x2
x3
x4
x5
x6
f
0
0
1
2
0
0
0
x1
4
1
-1
-1
0
0
0
x4
8
0
1
2
1
0
0
X5
-2
0
-1
1
0
1
0
X6
M
0
1
1
0
0
1
让x3进基，x6离基，得
x1
x2
x3
x4
x5
x6
f
-2M
0
-1
0
0
0
-2
x1
M+4
1
0
0
0
0
1
x4
8-2M
0
-1
0
1
0
-2
X5
-2-M
0
-2
0
0
1
-1
X3
M
0
1
1
0
0
1
得到扩充问题的一个正则解，继续用对偶单纯形法迭代，得：
x1
x2
x3
x4
x5
x6
f
-2M
0
-1
0
0
0
-2
x1
M+4
1
0
0
0
0
1
x4
8-2M
0
-1
0
1
0
-2
X5
-2-M
0
-2
0
0
1
-1
X3
M
0
1
1
0
0
1
f
-8
0
0
0
-1
0
0
X1
M+4
1
0
0
0
0
1
X2
-8+2M
0
1
0
-1
0
2
X5
-18+3M
0
0
0
-2
1
3
X3
8-M
0
0
1
1
0
-1
f
-8
0
0
0
-1
0
0
X1
12
1
0
1
1
0
0
X2
8
0
1
2
1
0
0
X4
6
0
0
3
1
1
0
X6
M-8
0
0
-1
-1
0
1
于是得最优解：
最优值：
该问题最优解不惟一，继续迭代得：
x1
x2
x3
x4
x5
x6
f
-8
0
0
0
-1
0
0
X1
12
1
0
1
1
0
0
X2
8
0
1
2
1
0
0
X4
6
0
0
3
1
1
0
X6
M-8
0
0
-1
-1
0
1
f
-8
0
0
0
-1
0
0
X1
10
1
0
0
2/3
-1/3
0
X2
4
0
1
0
1/3
-2/3
0
X3
2
0
0
1
1/3
1/3
0
X6
M-6
0
0
0
-2/3
1/3
1
于是得课后答案所给的最优解：
上面计算的Matlab程序为：
symsM
A=[0012000
41-1-1000
8012100
-20-11010
M011001];
fori=1:
4
A（i,:
）=A（i,:
）+A（5,:
）*（-A（i,4））;
end
A（3,:
）=-A（3,:
）;
fori=[1245]
A（i,:
）=A（i,:
）+A（3,:
）*（-A（i,3））;
end
A（5,:
）=-A（5,:
）;
fori=[1234]
A（i,:
）=A（i,:
）+A（5,:
）*（-A（i,7））;
end
A（4,:
）=A（4,:
）/3;
fori=[1235]
A（i,:
）=A（i,:
）+A（4,:
）*（-A（i,4））;
end
P111
2、
解：
添加人工约束，得到如下扩充问题
得如下单纯形表：
x1
x2
x3
x4
x5
x6
x7
x8
f
0
0
0
0
1
-2
-3
0
0
x1
17
1
0
0
5
-1
5
1
0
x2
-22
0
1
0
-1
2
-1
1
0
X3
-33
0
0
1
1
1
-1
1
0
X8
M
0
0
0
1
1
1
1
1
让x4进基，x8离基，得
x1
x2
x3
x4
x5
x6
x7
x8
f
-M
0
0
0
0
-3
-4
-1
-1
x1
17-5*M
1
0
0
0
-6
0
-4
-5
x2
M-22
0
1
0
0
3
0
2
1
X3
-M-33
0
0
1
0
0
-2
0
-1
X4
M
0
0
0
1
1
1
1
1
f
-17/5
-1/5
0
0
0
-9/5
-4
-1/5
0
x8
M-17/5
-1/5
0
0
0
6/5
0
4/5
1
x2
-93/5
1/5
1
0
0
9/5
0
6/5
0
X3
-182/5
-1/5
0
1
0
6/5,
2
4/5
0
X4
17/5
1/5
0
0
1
-1/5
1
1/5
0
于是根据x2行知，扩充问题没有可行解，于是原问题也没有可行解。
程序：
symsM
A=[00001-2-300
171005-1510
-22010-12-110
-3300111-110
M00011111];
fori=1:
4
A（i,:
）=A（i,:
）+A（5,:
）*（-A（i,5））;
end
k1=2;k2=9;
A（k1,:
）=A（k1,:
）/A（k1,k2）;
fori=[1345]
A（i,:
）=A（i,:
）+A（k1,:
）*（-A（i,k2））;
end
P112
3、
解：
添加人工约束，得到如下扩充问题
得如下表格：
x1
x2
x3
x4
x5
f
0
-1
2
0
0
0
x3
-1
-4
1
1
0
0
x
升级会员 