V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
arzterk
V2EX  ›  算法

求大佬帮忙算个题

  •  
  •   arzterk · 2018-09-29 12:13:20 +08:00 · 3725 次点击
    这是一个创建于 2007 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    40 条回复    2018-09-30 08:22:43 +08:00
    celeron533
        1
    celeron533  
       2018-09-29 12:14:13 +08:00 via Android
    运筹学
    Deville
        2
    Deville  
       2018-09-29 13:10:06 +08:00
    感觉好像初高中数学应用题。。。
    whileFalse
        3
    whileFalse  
       2018-09-29 13:16:27 +08:00
    所有组奇数天做衣服 偶数天做裤子就行了。。。
    Decouple
        4
    Decouple  
       2018-09-29 13:26:49 +08:00
    210 ?算出一天的最优解再乘 15,提供点思路,不知道对不对。代码: https://paste.ubuntu.com/p/2Sypz2vpzZ/
    newtype0092
        5
    newtype0092  
       2018-09-29 13:41:31 +08:00
    @whileFalse 这样每两天就浪费 4 条裤子的工作量吧。。。
    rabbbit
        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
    maichael
        7
    maichael  
       2018-09-29 13:47:21 +08:00
    @Decouple 一天的最优解乘以 15 未必是 15 天的最优解
    Decouple
        8
    Decouple  
       2018-09-29 13:48:12 +08:00
    @maichael 我也不太确定这点,可是为什么呢?能否举个反例
    Decouple
        9
    Decouple  
       2018-09-29 13:50:22 +08:00
    @rabbbit 每天都让乙和丁做衣服,甲和丙做裤子,这样会更优,14*15=210
    maichael
        10
    maichael  
       2018-09-29 13:51:11 +08:00
    @Decouple 按照题意来看,今天多缝制的裤子,明天也可以跟衣服配套。这么算的话肯定是比单纯算一天最优解要多一点的。
    newtype0092
        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 套。
    Kirscheis
        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
    Kirscheis
        13
    Kirscheis  
       2018-09-29 14:04:53 +08:00 via iPad
    当然这题有一个取整问题,不过题目条件刚好可以取到整数,如果取不到的话,需要向下取整
    arzterk
        14
    arzterk  
    OP
       2018-09-29 14:06:45 +08:00
    @Kirscheis 对的,化简为 max Z=4a+6b+7c+8d ,st 11a+13b+15c+17d = 450;


    @all 答案是 211 啊
    maichael
        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) 。选定甲组生产裤子,丁组生产衣服,然后只考虑乙和丙就好了。
    Valyrian
        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)),然后没有第一条约束
    Decouple
        17
    Decouple  
       2018-09-29 14:11:17 +08:00
    @newtype0092 原来如此,多谢!
    arzterk
        18
    arzterk  
    OP
       2018-09-29 14:11:48 +08:00
    @Valyrian 显示是求最大值吧
    这种多参数线性规划,有啥好的笔算思路,特么的考试又不能写 code。
    gaius
        19
    gaius  
       2018-09-29 14:13:29 +08:00
    211
    newtype0092
        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)
    Kirscheis
        21
    Kirscheis  
       2018-09-29 14:18:58 +08:00 via iPad
    虽然多参数,但是数据很规整啊。。你可以直接约化为 max (450-(a+b+c+d))/2 就很容易继续算了

    @Valyrian 是对的,不过在取整条件下两种描述似乎是等价的,我没有仔细求证
    arzterk
        22
    arzterk  
    OP
       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
        23
    arzterk  
    OP
       2018-09-29 14:27:32 +08:00
    @Kirscheis 那个等式应该搞错了,衣服裤子不需要完全配套,所以 @Valyrian 是对的。。
    Valyrian
        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
    Kirscheis
        25
    Kirscheis  
       2018-09-29 14:29:13 +08:00 via iPad   ❤️ 1
    @arzterk 根本不用暴力算啊。。单纯形法直接可以得到顶点
    0,0,13,15
    arzterk
        26
    arzterk  
    OP
       2018-09-29 14:30:10 +08:00
    arzterk
        27
    arzterk  
    OP
       2018-09-29 14:31:31 +08:00
    @Kirscheis (*^-^)ρ(*╯^╰)
    newtype0092
        28
    newtype0092  
       2018-09-29 14:38:29 +08:00
    @Kirscheis @gaius 你们的 211 没取整吧,液体之类的可以这么算,衣服不可能每天多个袖子或者领子吧。
    newtype0092
        29
    newtype0092  
       2018-09-29 14:46:48 +08:00
    @newtype0092 sorry,我算的有问题确实是 211。。。
    Kirscheis
        30
    Kirscheis  
       2018-09-29 14:47:09 +08:00 via iPad
    @newtype0092 我已经给出解了,在 25 楼,你可以验算一下

    @arzterk 线性规划条件下等式约束可以等价于最小值目标函数,因为可以保证单解或无穷多解。目标函数里面有 min 这种东西会导致你难以笔算。。
    ssynhtn
        31
    ssynhtn  
       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
    newtype0092
        32
    newtype0092  
       2018-09-29 15:08:11 +08:00
    @Kirscheis 线性代数已经还给老师了。。。借机会去复习复习。。。
    bucuoo
        33
    bucuoo  
       2018-09-29 15:09:33 +08:00
    212
    bucuoo
        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
    arzterk
        35
    arzterk  
    OP
       2018-09-29 16:31:55 +08:00
    @bucuoo 我知道有个 Karush – Kuhn – Tucker ( KKT )方法 是专门解决这类问题的,百度‘’广义 Lagrangian ‘ 可以转换这类为凸优化问题
    talen666
        36
    talen666  
       2018-09-29 17:29:43 +08:00
    题主考试只能笔算,用代码算的不审题吗
    siriussilen
        37
    siriussilen  
       2018-09-29 19:34:53 +08:00
    整数规划
    Fulcrum
        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
    Fulcrum
        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
    arzterk
        40
    arzterk  
    OP
       2018-09-30 08:22:43 +08:00
    @all @ssynhtn 只有这位老兄的算法考试用靠谱点。谢啦


    -------
    QED&结贴
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3948 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 10:22 · PVG 18:22 · LAX 03:22 · JFK 06:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.