运筹学上机实验(09级).pdf

文档介绍：该【运筹学上机实验(09级) 】是由【lajie】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【运筹学上机实验(09级) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。****题一
1。1用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷多最优解、无界
解还是无可行解。
(a)无穷多最优解最优解为点(3/4,1/2)到点(3/2,0)之间线段上的所有点。
minz2x3x
12
4x6x6
12
.4x2x4
12
x,x0
12
(b)无可行解
(c)唯一最优解X=(10,6)最优值Z=16
(d)无界解
1。2对下述线性规划问题找出所有基解,指出哪些是基可行解,并确定最优解。
maxz3xx2x
123
12x3x6x3x9
1234
(a)8xx4x2x10
.1235
3xx0
16
x0(j1,,6)
j
P1P2P3P4P5P6
1236300
A814020

300001
基解可行目标
基
否值
X1X2X3X4X5X6
P1P2P3016/3-7/6000否3
P1P2P40100—700否10
P1P2P503007/20是3
P1P2P67/4—400021/4否5/4
P1P3P400-5/2800否-5
P1P3P5003/2080是3
P1P3P610—1/2003否2
P1P4P5000350是0
P1P4P65/400-2015/4否15/4
P1P5P63/400029/4是9/4
P2P3P6016/3—7/6000否3
P2P4P60100—700否10
P2P5P603007/20是3
P3P4P600-5/2800否—5
P3P5P6003/2080是3
P4P5P6000350是0
基解16个,基可行解7个,最优解4个,最优值是3。
minz5x2x3x2x
1234
x2x3x4x7
(b)1234
.2x2xx2x3
1234
x0(j1,,4)
j
P1P2P3P4
1234
A
2212
基解
基可行否目标值
X1X2X3X4
P1P2-411/200否-31
P1P32/5011/50是43/5
P1P4—1/30011/6否2
P2P301/220是5
P2P40—1/202否5
P3P40011是5
基可行解3个,最优解2个,最优值5。
,并对照指出单纯形表中的各基可行解
分别对应图解法中可行域的哪一顶点。
(a)
maxz10x5x0x0x
1234
3x4xx9
123
5x2xx8
124
x0(j1,2,3,4)
j
,并列出初始单纯形表。
(a)
minz3x5xx
123
x2xx6
123
(b)2xx3x16
.123
xx5x10
123
x,x0,x无约束
123
解:添加剩余变量和松弛变量,划为:
x4x5
minz3x5xx
123
x2xxx6
1234
2xx3xx16
.1235
xx5x10
123
x,x,x,x0,x无约束
12453
令—,≥≥标准形式为
w=zx3=x3’-x3’’,x3’0,x3’’0,
maxw3x5xx'x''
1233
x2xx'x''x6
12334
2xx3x'3x''x16
.12335
xx5x'5x''10
1233
x,x,x',x'',x,x0
123345
再引入人工变量,问题划为:
x6x7,
maxw3x5xxx''MxMx
123'367
x2xx'x''xx6
123346
2xx3x'3x''x16
.12335
xx5x'5x''x10
12337
x,x,x',x'',x,x,x,x0
12334567
初始单纯形表为:
———
CJ-351100-MM
CBXBbX1X2X3’X3’’X4X5X6X7
—
-MX661211-1010
—
0X51621330100
—
X10115-50001
M7
3M—
2M-36M+1-6M-1—M000
5
,并指出属哪一类解。
(a)maxz2xx2x
123
xxx6
123
2xx2
.13
2xx0
23
x,x,x0
123
解:化为标准形为:
maxz2xx2xMxMxMx
123789
xx2xxx6
1347
2xxxx2
.1358
2xxxx0
2369
x0,(j1,,9)
j
—
C2—12000-M—M
JMθ
CBXBbX1X2X3X4X5X6X7X8X9
——
X6111001006
M71
—
——
X2-2010-10010
M8-
—
—
X002—100-10010
M9
——
2—M2+M-M—M000
1+3MM
—
-MX6103/201/210-1/24
71
-MX82-2010-100102
-
——
X001—1/200-1/2001/2
12—
-
—(1-3M)
2-M0(3+5M)/2—M(M-1)/200
M/2
———
X34003/21/21-1/23/4
M713/2
-
—
2X2-2010-10010
3—
—
--
———
-1X2111001/2-1/201/21/2
-
(M-1)(1-3M)
5+4M00-M(3M+3)0(M—
/2/23)/2/2
—
2X100-1/43/81/8-1/8
13/41/43/8
——
2X37/2001-1/41/41/21/41/4
1/2
——
-1X27/40101/8-3/81/41/83/8
1/4
——
0005/4—3/8-9/8-M+9/8
M-1M+3/8
该问题有无界解,因为σ,但终表中对应的列向量为,—,),全部小于
4=5/4P4(-1/41/2-1/4
0.
(见表1-23)和用单纯形法迭代后得到的表(见表
1—24)如下,试求括弧中未知数a~l的值。
表1-23
X1X2X3X4X5
(())
X46b)c(d10
—)
X5113(e01
()
cj-zja-1200
表1-24
X1X2X3X4X5
()(
X1fg)2-11/20
()(
X54hi)11/21
—()()
cj-zj07j)(kl
解:
a=3-1200
X1X2X3X4X5
(((
0X46b)=2c)=4d)=-210
)
0X51-13(e=201
—()—
cjzja=31200
a-1200
X1X2X3X4X5
)—
a=3X1(f=3(g)=1211/20
)
0X54(h)=0(i=511/21
—)()
cjzj0-7(j=5(k)=-3/2l=0
l=0,g=1,h=0
σ2=—1-2a=-7a=3
j=2+a=2+3=5
k=0-a/2=-3/2
1/20
B1
1/21
f1/206
b'B1b
41/211
f3
1/20b1
P1'B1P1
1/2110
b2
1/20c2
P2'B1P2
1/213i
c4
i5
1/20d1
P3'B1P3
1/21e1
d2
e2
1。12已知线性规划问题
maxzcxcxcx
112233
x2xxb
123
.2xx3x2b
123
x0(j1,2,3)
j
用最终单纯形法求解得最终单纯形表见表1—25,表中x4,x5为松弛变量
表1-25
X1X2X3X4X5
X211/5103/5-1/5
X333/5011/52/5
cj-zj—7/1000-3/5-4/5
试计算确定、、和的值。
c1c2c3b
解:
c1c2c300
X1X2X3X4X5
C2X211/5103/5-1/5
C3X333/5011/52/5
cj—zj-7/1000-3/5-4/5
σ—**—
1=C1c21/5-c33/5=7/10
σ—
4=0-c2*3/5-c3*1/5=3/5
σ*——
5=0+c21/5c3*2/5=4/5
c1=-7/10c2=2/7c3=15/7
3/51/5b1
b'B1b
1/52/52b3
b5
。已知各月份所需仓库面积数字列于表1-26。
仓库租借费用随合同期定,期限越长折扣越大,具体数字见表1—
都可办理,每份合同具体规定租用面积数和期限。因此该厂可根据需要,在任何一个月初办
理租借合同。每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,总目标
是使所付租借费用最小。试建立上述问题的线性规划模型.
表1—26
月份1234
所需仓库面积
15102012
(100m2)
表1-27
合同租借期限1个月2个月3个月4个月
合同期内的租费
2800450060007300
(元/100m2)
解:设为第个月初签订的租用期为个月的合同中规定的面积数(2),,,…j
Xijij100mij=1,4,i+
≤5。
minz2800(xxxx)4500(xxx)6000(xx)7300x
11213141122232132314
xxxx15
11121314
xxxxxx10
121314212223
.xxxxxx20
131422233132
xxxx12
14233241
x0,i,j1,,4,ij5
ij
注:以上模型是考虑了“租了不用就不应该租”而建立的,所以有i+j≤5的限制。
1。14某厂生产Ⅰ、Ⅱ、Ⅲ三种产品,都分别经A、B两道工序加工。加工单位产
品所需工序时间及其他各项数据见表1-28,试安排最优生产计划,使该厂获利
最大。
表1—28
产品设备有加工费
设备
ⅠⅡⅢ效台时(元/h)
A51060000。05
1
A7912100000。03
2

1
B41170000。11
2
B740000。05
3
原料费(元/件)0。250。350。50
售价(元/件)。80
解:设xij表示第i种设备上加工第j种产品的数量,
maxz()(xx)(2)(xx)()x
1121122223
(5x10x)(7x9x12x)(6x8x)
11122122233132
(4x11x)7x
414351
xxxxx
1121313233
xxx
122232
xx
2343
5x10x6000
1112
.7x9x12x10000
212223
6x8x4000
3132
4x11x7000
4143
7x4000
51
x为非负整数
ij