求大佬帮忙算个题

[arzterk]

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

[Kirscheis]

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

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

[arzterk]

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

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

[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

[Kirscheis]

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

[arzterk]

@Valyrian 666

[arzterk]

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

[newtype0092]

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

[newtype0092]

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

[Kirscheis]

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

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

[kx5d62Jn1J9MjoXP]

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]

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

[bucuoo]

212

[bucuoo]

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

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

[talen666]

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

[siriussilen]

整数规划

[Fulcrum]

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

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]

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


-------
QED&结贴