求大佬帮忙算个题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2279 天前的主题，其中的信息可能已经有所发展或是发生改变。

软考有个题目，懵逼了：某服装店有甲、乙、丙、丁四个缝制小组。甲组每天能缝制 5 件上衣或 6 条裤子：乙组每天能缝制 6 件上农或 7 条裤子：丙组每天能缝制 7 件上衣或 8 条裤子；丁组每天能缝制 8 件上衣或 9 条裤子。每组每天要么缝制上衣，要么缝制裤子，不能弄混。订单要求上衣和裤子必须配套（每套衣服包括一件上衣和一条裤子）。做好合理安排，该服装店 15 天最多能缝制（）套衣服

缝制

裤子

上衣

服装店

40 条回复 • 2018-09-30 08:22:43 +08:00

celeron533

2018-09-29 12:14:13 +08:00 via Android

运筹学

Deville

2018-09-29 13:10:06 +08:00

感觉好像初高中数学应用题。。。

whileFalse

2018-09-29 13:16:27 +08:00

所有组奇数天做衣服偶数天做裤子就行了。。。

Decouple

2018-09-29 13:26:49 +08:00

210 ？算出一天的最优解再乘 15，提供点思路，不知道对不对。代码： https://paste.ubuntu.com/p/2Sypz2vpzZ/

newtype0092

2018-09-29 13:41:31 +08:00

@whileFalse 这样每两天就浪费 4 条裤子的工作量吧。。。

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

maichael

2018-09-29 13:47:21 +08:00

@Decouple 一天的最优解乘以 15 未必是 15 天的最优解

Decouple

2018-09-29 13:48:12 +08:00

@maichael 我也不太确定这点，可是为什么呢？能否举个反例

Decouple

2018-09-29 13:50:22 +08:00

@rabbbit 每天都让乙和丁做衣服，甲和丙做裤子，这样会更优，14*15=210

maichael

2018-09-29 13:51:11 +08:00

@Decouple 按照题意来看，今天多缝制的裤子，明天也可以跟衣服配套。这么算的话肯定是比单纯算一天最优解要多一点的。

newtype0092

2018-09-29 14:01:39 +08:00

@Decouple 这道题刚好甲丙做裤子(6+8)乙丁做衣服(6+8)一天能做 14 套整，每天的最优解恰好是任意天的最优解，如果不是这种数据的话，n 天的最优解可能都不一样。
假设有 3 个组，每个组的衣裤产力是（ 5,5),(3,3),(1,1)，这样一天的话一天的最优解是 4 套，而两天的最优解是 9 套。

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

Kirscheis

2018-09-29 14:04:53 +08:00 via iPad

当然这题有一个取整问题，不过题目条件刚好可以取到整数，如果取不到的话，需要向下取整

arzterk

2018-09-29 14:06:45 +08:00

@Kirscheis 对的，化简为 max Z=4a+6b+7c+8d ,st 11a+13b+15c+17d = 450;

@all 答案是 211 啊

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) 。选定甲组生产裤子，丁组生产衣服，然后只考虑乙和丙就好了。

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))，然后没有第一条约束

Decouple

2018-09-29 14:11:17 +08:00

@newtype0092 原来如此，多谢！

arzterk

2018-09-29 14:11:48 +08:00

@Valyrian 显示是求最大值吧
这种多参数线性规划，有啥好的笔算思路，特么的考试又不能写 code。

gaius

2018-09-29 14:13:29 +08:00

211

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)

Kirscheis

2018-09-29 14:18:58 +08:00 via iPad

虽然多参数，但是数据很规整啊。。你可以直接约化为 max (450-(a+b+c+d))/2 就很容易继续算了

@Valyrian 是对的，不过在取整条件下两种描述似乎是等价的，我没有仔细求证

arzterk

2018-09-29 14:21:43 +08:00

我用 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)

arzterk

2018-09-29 14:27:32 +08:00

@Kirscheis 那个等式应该搞错了，衣服裤子不需要完全配套，所以 @Valyrian 是对的。。

Valyrian

2018-09-29 14:29:05 +08:00

>>> 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

Kirscheis

2018-09-29 14:29:13 +08:00 via iPad

@arzterk 根本不用暴力算啊。。单纯形法直接可以得到顶点
0,0,13,15

arzterk

2018-09-29 14:30:10 +08:00

@Valyrian 666

arzterk

2018-09-29 14:31:31 +08:00

@Kirscheis (*^-^)ρ(*╯^╰)

newtype0092

2018-09-29 14:38:29 +08:00

@Kirscheis @gaius 你们的 211 没取整吧，液体之类的可以这么算，衣服不可能每天多个袖子或者领子吧。

newtype0092

2018-09-29 14:46:48 +08:00

@newtype0092 sorry，我算的有问题确实是 211。。。

Kirscheis

2018-09-29 14:47:09 +08:00 via iPad

@newtype0092 我已经给出解了，在 25 楼，你可以验算一下

@arzterk 线性规划条件下等式约束可以等价于最小值目标函数，因为可以保证单解或无穷多解。目标函数里面有 min 这种东西会导致你难以笔算。。

kx5d62Jn1J9MjoXP

2018-09-29 15:03:32 +08:00

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

newtype0092

2018-09-29 15:08:11 +08:00

@Kirscheis 线性代数已经还给老师了。。。借机会去复习复习。。。

bucuoo

2018-09-29 15:09:33 +08:00

212

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

arzterk

2018-09-29 16:31:55 +08:00

@bucuoo 我知道有个 Karush – Kuhn – Tucker （ KKT ）方法是专门解决这类问题的，百度‘’广义 Lagrangian ‘ 可以转换这类为凸优化问题

talen666

2018-09-29 17:29:43 +08:00

题主考试只能笔算，用代码算的不审题吗

siriussilen

2018-09-29 19:34:53 +08:00

整数规划

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

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

arzterk

2018-09-30 08:22:43 +08:00

@all @ssynhtn 只有这位老兄的算法考试用靠谱点。谢啦

-------
QED&结贴