运筹学练习22.docx
- 文档编号:10861740
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:15
- 大小:199.94KB
运筹学练习22.docx
《运筹学练习22.docx》由会员分享,可在线阅读,更多相关《运筹学练习22.docx(15页珍藏版)》请在冰点文库上搜索。
运筹学练习22
一、填空题:
(每空格2分,共16分)
1、线性规划的解有唯一最优解、无穷多最优解、和无可行解四种。
2、在求运费最少的调度运输问题中,如果某一非基变量的检验数为4,则说明
3、“如果线性规划的原问题存在可行解,贝U其对偶问题一定存在可行解”,这句话对还是错?
4、如果某一整数规划:
MaxZ=X+X2
X1+9/I4X2W51/14-2X1+X2W1/3
X1,X2>0且均为整数
所对应的线性规划(松弛问题)的最优解为X1=3/2,X2=10/3,MaxZ=6/29,我们现在要对X进行分枝,
应该分为和
5.在用逆向解法求动态规划时,fk(sk)的含义是:
6.假设某线性规划的可行解的集合为D,而其所对应的整数规划的可行解集合为B,那么D和B的关
系为
7.已知下表是制订生产计划问题的一张LP最优单纯形表(极大化问题,约束条件均为“W”型不等式)其中X3,X4,X5为松驰变量。
Xb
b
X
X2
X3
X
X
%
3
0
0
-2
1
3
X
4/3
1
0
-1/3
0
2/3
X2
1
0
1
0
0
-1
Cj-Zj1
0
0
-5
0
-23
问:
(1)写出B-1=
(2)对偶问题的最优解:
8.线性规划问题如果有无穷多最优解,则单纯形计算表的终表中必然有;
9.极大化的线性规划问题为无界解时,则对偶问题;
10.若整数规划的松驰问题的最优解不符合整数要求,假设X=b不符合整数要求,INT(bi)是不超
过bi的最大整数,则构造两个约束条件:
和,分别将其并入上述松驰问题中,
形成两个分支,即两个后继问题。
11.知下表是制订生产计划问题的一张LP最优单纯形表(极大化问题,约束条件均为“W”型不等式)其中X4,X5,X6为松驰变量。
Xb
b
X
X2
X3
X4
X5
X6
X
2
1
1
0
2
0
1
X3
2/3
0
0
1
1
0
4
%
1
0
-2
0
1
1
6
Cj-Zj
0
0
0
-4
0
-9
问:
(1)对偶问题的最优解:
(2)写出B-1=
二、计算题(60分)
1、已知线性规划(20分)
MaxZ=3X+4X/Xi+X2<5
2X1+4心12■<
3X1+2X><8
其最优解为:
基变量
X
X2
X3
%
X5
X3
3/2
0
0
1
-1/8
-1/4
X2
5/2
0
1
0
3/8
-1/4
X1
1
1
0
0
-1/4
1/2
Cj
0
0
0
-3/4
-1/2
1)
2)
3)
4)
写出该线性规划的对偶问题。
若C2从4变成5,最优解是否会发生改变,为什么?
若b2的量从12上升到15,最优解是否会发生变化,为什么?
如果增加一种产品X6,其F6=(2,3,1)T,C6=4该产品是否应该投产?
为什么?
3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者,规定每个承包商只能且必须承包一个项目,试在总费用最小的条件下确定各个项目的承包者,总费用为多少?
各承包商对工程的报价如表2所示:
(15分)
投标者
A
B
C
D
甲
15
18
21
24
乙
19
23
22
18
丙
26
17
16
19
丁
19
21
23
17
4.考虑如下线性规划问题(24分)
Maxz=-5x1+5x2+13x3
s.t.「X1+X2+3X3W20
J12x1+4x2+10x3<90
IX1,X2,x3>0
回答以下问题:
1)求最优解
2)
3)
4)
5)
求对偶问题的最优解
当bi由20变为45,最优解是否发生变化。
求新解增加一个变量X6,C6=10,ai6=3,826=5,对最优解是否有影响C2有5变为6,是否影响最优解。
B、C三种设备加工。
已知生产单位各种产品所需的设
(2分)
(3分)
I
n
m
设备能力(台.h)
A
1
1
1
100
B
10
4
5
600
C
2
2
6
300
单位产品利润
(元)
10
6
4
n、m三种产品分别经过
A、
8.某厂I、
备台时,设备的现有加工能力及每件产品的预期利润见表:
1)建立线性规划模型,求获利最大的产品生产计划。
(15分)
2)产品m每件的利润到多大时才值得安排生产?
如产品m每件利润增加到50/6元,求最优计划的
变化。
(4分)
3)产品I的利润在多大范围内变化时,原最优计划保持不变。
4)设备A的能力在什么范围内变化时,最优基变量不变。
5)如有一种新产品,加工一件需设备AB、C的台时各为1、4、3h,预期每件为8元,是否值得生产。
(3分)
6)如合同规定该厂至少生产10件产品m,试确定最优计划的变化。
(3分)
9.给出成性规划问题:
(15分)
Minz=2xi+3x2+6x3
>Xi+2X2+X3>2-2xi+X2+3x3<-3
'Xj>0j=1,,,4
要求:
(1)写出其对偶问题。
(5分)
⑵利用图解法求解对偶问题。
(5分)
(3)利用
(2)的结果,根据对偶问题性质写出原问题最优解。
(5分)
10.
里,
某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量,各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于下表中,要求研究产品如何调运才能使总运量最小?
(10分)
B
B2
BeB4
甘-a.产量
A
4
12
4
11
32
A
2
10
3
9
20
A
8
5
11
6
44
销量
16
28
28
24
96\96
11.求解下列0-1规划问题
maxz=3X+2xK5x3-2x4+3x5
‘X1+X2+X3+2X4+X5<4
7x1+3x3-4x4+3x5<8
11x1-6x2+3x4-3x5>3
Xj=0或1(j=1,,,5)
练习2答案
填空题
1.无界解
2.如果在该空格中增加一个运量运费将增加4
3.错
4.X1<1,X1>2
5.从第k个阶段到第n个阶段的最优解
6.D包含
7.—1/3
.0
2/3
Y=(5,0,23,0,0)T
8.某一个非基变量的检验数为0
9.无解
10.Xi>INT(bi)+1;Xi 11.Y=(4,0,9,0,0,0)T; I1 计算题 1.解: 1)对偶问题为 Minw=5y1+12y2+8y3 y1+2y2+3y3>3 y1+4y2+2y3>4 y1,y2>0 2)当C2从4变成5时, d4=-9/8 d5=-1/4 由于非基变量的检验数仍然都是小于0的,所以最优解不变。 3)当若b2的量从12上升到15 X=9/8 29/8 1/4 由于基变量的值仍然都是大于0的,所以最优解的基变量不会发生变化。 4)如果增加一种新的产品,则 P6'=(11/8,7/8,-1/4)T d6=3/8>0 所以对最优解有影响,该种产品应该生产 2.解: 初始解为 D B2 B3 产量/t A 15 15 A 11 11 A 18 1 1 20 销量/t 18 12 16 计算检验数 B1 B2 B3 产量/t A 5 13 0 15 A -2 0 0 11 A 0 0 0 20 销量/t 18 12 16 由于存在非基变量的检验数小于0,所以不是最优解,需调整调整为: B B2 B3 产量/t A 15 15 A 11 11 A 7 12 1 20 销量/t 18 12 16 重新计算检验数 B B2 B3 产量/t A 5 13 0 15 A 0 2 2 11 A 0 0 0 20 销量/t 18 12 16 所有的检验数都大于等于0,所以得到最优解 3.答最优解为: X=0100 1000 0010 000K 总费用为50 答: 最优解为 1) Cj -5 5 13 0 0 0 CBIXbIb X X. X4 X5 0 % 20 -1 1 3 1 0 20/3 0 90 12 4 10 0 1 9 Cj-Zj -5 5 13 0 0 13 X^ 20/3 -1/3 1/3 1 1/3 0 20 0 % 70/3 46/3 22/3 0 -10/3 1 70/22 Cj-Zj -2/3 2/3 0 -13/3 0 13 X3 185/33 -34/33 0 1 2/11 -1/22 5 X> 35/11 23/11 1 0 -5/11 3/22 -68/33 0 0 -1/11 -1/11 最优解为X=185/33,X3=35/11 2)对偶问题最优解为 丫=(1/22,1/11,68/33,0,0) 3) 当b1=45时 X=[45/11r -11/90」 由于X2的值小于0,所以最优解将发生变化 3)P6'=(3/11,-3/4)T (T6=217/20>0 所以对最优解有影响。 4)当C2=6 (T1=-137/33 (T4=4/11 (T5=-17/22 0所以对最优解有影响 由于(T4大于 6. Cj 3 1 4 0 0 CB Xb b X1 X2 X3 X4 X5 0 X4 9 6 3 5 1 0 0 1X5 8 3 4 5 0 1 Cj-Zj 3 1 4 0 0 0 X4 1 3 -1 0 1 -1 4 X3 8/5 3/5 4/5 1 0 1/5 Cj-Zj 3/5 -11/5 0 0 -4/5 3 X1 1/3 1 -1/3 0 1/3 -1/3 4 X3 7/5 0 1 1 -1/5 2/5 Cj-Zj 0 -2 0 -1/5 -3/5 最优解为X1=1/3,X3=7/5,Z=33/5 2)对偶问题为 Minw=9y1+8y2 6y1+3y2>3 J3y1+4y2>1 ]5y1+5y2>4 y1,y2>0 对偶问题最优解为y1=1/5,y2=3/5 3)若问题中X2列的系数变为(3,2)T 则R'=(1/3,1/5)T (T2=-4/5<0 所以对最优解没有影响 4)C2由1变为2 (T2=-1<0 所以对最优解没有影响 7.解: xj>0,j=1,2,3 获利最大的产品生产计划为: X*=(x1,x2,x3,x4,x5,x6) 2)产品rn每件利润到 X*=(x1,x2,x3,x4,x5,x6) x1+x2+x3w10010x1+4x2+5x3=6002x1+2x2+6x3W300 '=(100/3,200/3,0,0,0,100)'Z*=2200/3 20/3才值得生产。 如果产品m每件利润增加到50/6元,最优计划的变化为: '=(175/6,275/6,25,0,0,0)'Z*=775 3)产品I的利润在[6,15]变化时,原最优计划保持不变。 4)设备A的能力在[60,150]变化时,最优基变量不变。 5)新产品值得生产。 6)最优计划的变化为: X*=(x1,x2,x3,x4,x5,x6)'=(190/6,350/6,10,0,0,60)'Z*=706.7 9.解: 1)该问题的LD为: MaxW=2y1-3y2 y1-2y2<2 2y1+y2w3 y1+3y2<6 y1>0,y2<0 2) W*=19/5 用图解法求得LD的最优解为: 丫*=(y1,y2)'=(8/5,-1/5)' 3)由互补松弛定理: 原问题的最优解为: X*=(x1,x2,x3)'=(8/5,1/5,0)' 10.解: 最优调运方案为: A1-B3和B428t和4t A2-B1和B416t和4t A3-B2和B428t和16t 最小总运费为: 460元 11.解: 最优解为: x1=x2=1,其他为0,最优目标函数值为5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 练习 22