求大佬帮忙算个题

[arzterk]

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

[celeron533]

运筹学

[Deville]

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

[whileFalse]

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

[Decouple]

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

[newtype0092]

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

[rabbbit]

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

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

[Decouple]

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

[Decouple]

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

[maichael]

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

[newtype0092]

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

[Kirscheis]

这是运筹学里最简单的线性规划啊。。

目标函数 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]

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

[arzterk]

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


@all 答案是 211 啊

[maichael]

设甲、乙、丙、丁生产上衣的天数为 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]

目标函数是 max z=min(5a+6b+7c+8d, 6(15-a)+7(15-b)+8(15-c)+9(15-d))，然后没有第一条约束

[Decouple]

@newtype0092 原来如此，多谢！

[arzterk]

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

[gaius]

211

[newtype0092]

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