求大佬帮忙算个题

运筹学

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

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

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

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

(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

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

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

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

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

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

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

目标函数 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 对的，化简为 max Z=4a+6b+7c+8d ,st 11a+13b+15c+17d = 450;


@all 答案是 211 啊

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

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

@newtype0092 原来如此，多谢！

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

211

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

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

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

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

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

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

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

@Valyrian 666

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

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

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

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

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

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

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

212

题意要求配套，所以要用等式，不能用 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

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

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

整数规划

整数规划
答案应该是 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

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

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


-------
QED&结贴