线性规划课后题答案(张干宗).doc
- 文档编号:14850964
- 上传时间:2023-06-27
- 格式:DOC
- 页数:56
- 大小:2.63MB
线性规划课后题答案(张干宗).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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 课后 答案 张干宗