软考有个题目,懵逼了: 某服装店有甲、乙、丙、丁四个缝制小组。甲组每天能缝制 5 件上衣或 6 条裤子: 乙组每天能缝制 6 件上农或 7 条裤子:丙组每天能缝制 7 件上衣或 8 条裤子;丁组每天能缝制 8 件上衣或 9 条裤子。每组每天要么缝制上衣,要么缝制裤子,不能弄混。订单要求上衣和裤子必须配套(每套衣服包括一件上衣和一条裤子)。做好合理安排,该服装店 15 天最多能缝制( )套衣服
1
celeron533 2018-09-29 12:14:13 +08:00 via Android
运筹学
|
2
Deville 2018-09-29 13:10:06 +08:00
感觉好像初高中数学应用题。。。
|
3
whileFalse 2018-09-29 13:16:27 +08:00
所有组奇数天做衣服 偶数天做裤子就行了。。。
|
4
Decouple 2018-09-29 13:26:49 +08:00
210 ?算出一天的最优解再乘 15,提供点思路,不知道对不对。代码: https://paste.ubuntu.com/p/2Sypz2vpzZ/
|
5
newtype0092 2018-09-29 13:41:31 +08:00
@whileFalse 这样每两天就浪费 4 条裤子的工作量吧。。。
|
6
rabbbit 2018-09-29 13:46:51 +08:00
(5 + 6 + 7 + 8) * 8 = 208
(6 + 7 +8 + 9) * 7 = 210 (5 + 6 + 7 + 8) * 8 + 5 = 213 (6 + 7 +8 +9) * 7 - 6 = 204 答案 208 |
11
newtype0092 2018-09-29 14:01:39 +08:00 1
@Decouple 这道题刚好甲丙做裤子(6+8)乙丁做衣服(6+8)一天能做 14 套整,每天的最优解恰好是任意天的最优解,如果不是这种数据的话,n 天的最优解可能都不一样。
假设有 3 个组,每个组的衣裤产力是( 5,5),(3,3),(1,1),这样一天的话一天的最优解是 4 套,而两天的最优解是 9 套。 |
12
Kirscheis 2018-09-29 14:03:27 +08:00 via iPad
这是运筹学里最简单的线性规划啊。。
目标函数 max z=5a+6b+7c+8d 约束 6(15-a)+7(15-b)+8(15-c)+9(15-d)=5a+6b+7c+8d 15>=a>=0 15>=b>=0 15>=c>=0 15>=d>=0 |
13
Kirscheis 2018-09-29 14:04:53 +08:00 via iPad
当然这题有一个取整问题,不过题目条件刚好可以取到整数,如果取不到的话,需要向下取整
|
14
arzterk OP |
15
maichael 2018-09-29 14:08:28 +08:00
设甲、乙、丙、丁生产上衣的天数为 A、B、C、D 天,生产裤子为 15-A 天,以此类推。
可得生产上衣的数量为 A*5+B*6+C*7+D*8。 生产裤子的数量为(15-A)*6+(15-B)*7+(15-C)*8+(15-D)*9 穷举一遍。 还可根据 4 者的生产效率比 5/6、6/7、7/8、8/9,甲组生产裤子效率最高(5/6),丁组生产衣服效率最高(8/9) 。选定甲组生产裤子,丁组生产衣服,然后只考虑乙和丙就好了。 |
16
Valyrian 2018-09-29 14:09:47 +08:00
目标函数是 max z=min(5a+6b+7c+8d, 6(15-a)+7(15-b)+8(15-c)+9(15-d)),然后没有第一条约束
|
17
Decouple 2018-09-29 14:11:17 +08:00
@newtype0092 原来如此,多谢!
|
19
gaius 2018-09-29 14:13:29 +08:00
211
|
20
newtype0092 2018-09-29 14:15:24 +08:00
@Decouple 每天的最优解可能有三种情况:
1.衣裤正好配套,此种情况的单天最优解即是多天最优解 2.衣服多了 x 件 3.裤子多了 y 件 2 和 3 两种情况只有 xy 的最小公倍数 m 天才是效率最大的情况 f(m),而 1 到 m-1 天每天都有一个最优解 f(1)...f(m-1) 假设实际天数为 n,最优解就是 n < m: f(n) n = m: f(m) n > m: floor(n/m) * f(m) + f(n%m) |
21
Kirscheis 2018-09-29 14:18:58 +08:00 via iPad
|
22
arzterk OP 我用 python 暴力算了一把,也没有出现 211:
for a in range(0,15): for b in range(0,15): for c in range(0,15): for d in range(0,15): if (11*a + 13*b + 15*c + 17*d == 450): print(5*a+6*b+7*c+8*d) |
24
Valyrian 2018-09-29 14:29:05 +08:00 1
>>> def f(a,b,c,d): return min(5*a+6*b+7*c+8*d, 6*(15-a)+7*(15-b)+8*(15-c)+9*(15-d))
>>> max([f(a,b,c,d) for a in range(0, 16) for b in range(0, 16) for c in range(0,16) for d in range(0,16)]) 211 |
28
newtype0092 2018-09-29 14:38:29 +08:00
|
29
newtype0092 2018-09-29 14:46:48 +08:00
@newtype0092 sorry,我算的有问题确实是 211。。。
|
30
Kirscheis 2018-09-29 14:47:09 +08:00 via iPad
@newtype0092 我已经给出解了,在 25 楼,你可以验算一下
@arzterk 线性规划条件下等式约束可以等价于最小值目标函数,因为可以保证单解或无穷多解。目标函数里面有 min 这种东西会导致你难以笔算。。 |
31
kx5d62Jn1J9MjoXP 2018-09-29 15:03:32 +08:00 2
5/6 < 6/7 < 7/8 < 8/9 => 丙和丁制作上衣 /裤子的相对效率最高
8 + 7x = 8(1-x) + 7 + 6 // 丁全做上衣, 丙部分时间做上衣, 部分做裤子, 甲乙做裤子 15x = 13 x = 13/15 (8 + 7*13/15)* 15 = 120 + 91 = 211 |
32
newtype0092 2018-09-29 15:08:11 +08:00
@Kirscheis 线性代数已经还给老师了。。。借机会去复习复习。。。
|
33
bucuoo 2018-09-29 15:09:33 +08:00
212
|
34
bucuoo 2018-09-29 15:17:37 +08:00
题意要求配套,所以要用等式,不能用 min 取最小
推导 => A*5+B*6+C*7+D*8 = (15-A)*6+(15-B)*7+(15-C)*8+(15-D)*9 楼上提起的效率选取 A=15,D=0 代入 => 75+B*6+C*7=105-7*B+120-8*C+145 => 13*B+15*C=295 约束:15>=B>=0 && 15>=C>=0 B=0 or 5 or 10 or 15 满足取整约束的只有:B=10 && C=11 so A=15 B=10 C=11 D=0 Answer=A*5+B*6+C*7+D*8=212 谁帮我验证一下~ 为什么你们的答案是 211 |
35
arzterk OP @bucuoo 我知道有个 Karush – Kuhn – Tucker ( KKT )方法 是专门解决这类问题的,百度‘’广义 Lagrangian ‘ 可以转换这类为凸优化问题
|
36
talen666 2018-09-29 17:29:43 +08:00
题主考试只能笔算,用代码算的不审题吗
|
37
siriussilen 2018-09-29 19:34:53 +08:00
整数规划
|
38
Fulcrum 2018-09-29 21:00:42 +08:00
整数规划
答案应该是 211 你可以下个 LINGO 求解一下,这是 LINGO 求解代码 model: sets: day/1..15/:x,y,j,k,a,b,c,d; endsets max = @sum(day(i):5*x(i)+6*y(i)+7*j(i)+8*k(i)); @for(day(i):@bin(x)); @for(day(i):@bin(y)); @for(day(i):@bin(j)); @for(day(i):@bin(k)); @for(day(i):a=1-x(i)); @for(day(i):b=1-y(i)); @for(day(i):c=1-j(i)); @for(day(i):d=1-k(i)); @sum(day(i):5*x(i)+6*y(i)+7*j(i)+8*k(i))=@sum(day(i):6*a(i)+7*b(i)+8*c(i)+9*d(i)); end |
39
Fulcrum 2018-09-29 21:03:34 +08:00
value 为 1 则那天做那件事,x,y,j,k 是甲乙丙丁组分别做上衣,a,b,c,d 相反
Global optimal solution found. Objective value: 211.0000 Objective bound: 211.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X( 1) 0.000000 -5.000000 X( 2) 0.000000 -5.000000 X( 3) 0.000000 -5.000000 X( 4) 0.000000 -5.000000 X( 5) 0.000000 -5.000000 X( 6) 0.000000 -5.000000 X( 7) 0.000000 -5.000000 X( 8) 0.000000 -5.000000 X( 9) 0.000000 -5.000000 X( 10) 0.000000 -5.000000 X( 11) 0.000000 -5.000000 X( 12) 0.000000 -5.000000 X( 13) 0.000000 -5.000000 X( 14) 0.000000 -5.000000 X( 15) 0.000000 -5.000000 Y( 1) 0.000000 -6.000000 Y( 2) 0.000000 -6.000000 Y( 3) 0.000000 -6.000000 Y( 4) 0.000000 -6.000000 Y( 5) 0.000000 -6.000000 Y( 6) 0.000000 -6.000000 Y( 7) 0.000000 -6.000000 Y( 8) 0.000000 -6.000000 Y( 9) 0.000000 -6.000000 Y( 10) 0.000000 -6.000000 Y( 11) 0.000000 -6.000000 Y( 12) 0.000000 -6.000000 Y( 13) 0.000000 -6.000000 Y( 14) 0.000000 -6.000000 Y( 15) 0.000000 -6.000000 J( 1) 1.000000 -7.000000 J( 2) 1.000000 -7.000000 J( 3) 1.000000 -7.000000 J( 4) 1.000000 -7.000000 J( 5) 0.000000 -7.000000 J( 6) 1.000000 -7.000000 J( 7) 1.000000 -7.000000 J( 8) 1.000000 -7.000000 J( 9) 1.000000 -7.000000 J( 10) 1.000000 -7.000000 J( 11) 1.000000 -7.000000 J( 12) 1.000000 -7.000000 J( 13) 1.000000 -7.000000 J( 14) 0.000000 -7.000000 J( 15) 1.000000 -7.000000 K( 1) 1.000000 -8.000000 K( 2) 1.000000 -8.000000 K( 3) 1.000000 -8.000000 K( 4) 1.000000 -8.000000 K( 5) 1.000000 -8.000000 K( 6) 1.000000 -8.000000 K( 7) 1.000000 -8.000000 K( 8) 1.000000 -8.000000 K( 9) 1.000000 -8.000000 K( 10) 1.000000 -8.000000 K( 11) 1.000000 -8.000000 K( 12) 1.000000 -8.000000 K( 13) 1.000000 -8.000000 K( 14) 1.000000 -8.000000 K( 15) 1.000000 -8.000000 A( 1) 1.000000 0.000000 A( 2) 1.000000 0.000000 A( 3) 1.000000 0.000000 A( 4) 1.000000 0.000000 A( 5) 1.000000 0.000000 A( 6) 1.000000 0.000000 A( 7) 1.000000 0.000000 A( 8) 1.000000 0.000000 A( 9) 1.000000 0.000000 A( 10) 1.000000 0.000000 A( 11) 1.000000 0.000000 A( 12) 1.000000 0.000000 A( 13) 1.000000 0.000000 A( 14) 1.000000 0.000000 A( 15) 1.000000 0.000000 B( 1) 1.000000 0.000000 B( 2) 1.000000 0.000000 B( 3) 1.000000 0.000000 B( 4) 1.000000 0.000000 B( 5) 1.000000 0.000000 B( 6) 1.000000 0.000000 B( 7) 1.000000 0.000000 B( 8) 1.000000 0.000000 B( 9) 1.000000 0.000000 B( 10) 1.000000 0.000000 B( 11) 1.000000 0.000000 B( 12) 1.000000 0.000000 B( 13) 1.000000 0.000000 B( 14) 1.000000 0.000000 B( 15) 1.000000 0.000000 C( 1) 0.000000 0.000000 C( 2) 0.000000 0.000000 C( 3) 0.000000 0.000000 C( 4) 0.000000 0.000000 C( 5) 1.000000 0.000000 C( 6) 0.000000 0.000000 C( 7) 0.000000 0.000000 C( 8) 0.000000 0.000000 C( 9) 0.000000 0.000000 C( 10) 0.000000 0.000000 C( 11) 0.000000 0.000000 C( 12) 0.000000 0.000000 C( 13) 0.000000 0.000000 C( 14) 1.000000 0.000000 C( 15) 0.000000 0.000000 D( 1) 0.000000 0.000000 D( 2) 0.000000 0.000000 D( 3) 0.000000 0.000000 D( 4) 0.000000 0.000000 D( 5) 0.000000 0.000000 D( 6) 0.000000 0.000000 D( 7) 0.000000 0.000000 D( 8) 0.000000 0.000000 D( 9) 0.000000 0.000000 D( 10) 0.000000 0.000000 D( 11) 0.000000 0.000000 D( 12) 0.000000 0.000000 D( 13) 0.000000 0.000000 D( 14) 0.000000 0.000000 D( 15) 0.000000 0.000000 |