转跳到内容

这波啊,这波是最优化


只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

@ZERC大佬弄了个每日数学挑战, @Xchara大佬也做了个逻辑分析https://sstm.moe/topic/252606-数学做累了?那就来试试这个简单的逻辑分析题吧/ 诶,莫非我也能用这种方式水节操?

我也来蹭蹭热度!

这道题是从一个老旧PPT上扒来的问题,名字叫“港口调度问题”(名字估计也是瞎起的,反正我百度这个名字百度不出啥来)。这道题题目如下:

港口调度问题

已知若干货轮(C1~Cn)要在港口停泊卸货。港口具有:

  • 2个相同的泊位M1、M2
  • 2个相同的起吊设备T1、T2
  • 2辆相同的运输车V1、V2
  • 3个仓库S1~S3

起吊设备不与泊位绑定。起吊设备在一个泊位起吊完成后,移动到另一泊位(若需要)的时间忽略不计。运输车空闲时停留在港口缓冲区等待被吊车运送至此的货物。运送到目的仓库后,运输车立刻返回缓冲区等待下次运输。

船上的货物首先要随船入港,之后被起吊设备运送到港口缓冲区,随后被运输车运送到指定仓库。每个货物起吊时间不一定相同,货轮出入泊位时间也不一定相同。4艘货轮均在0时刻抵达,现要规划入泊、吊送货物方案,通过设置合理的轮船出入泊位、吊车吊运货物和运输车运输顺序,使总的调度用时尽可能短。

“总的调度用时”的定义:从0时刻各货轮抵达起至最后一个货物进入仓库、货船全部离港且运输车全部返回缓冲区为止所花费的时间。

作为数据,货轮、货物和仓库的相关信息列如下。

表1:货轮信息表

货轮序号 入港用时 离港用时
C1 26 20
C2 15 10
C3 30 24
C4 40 26
C5 50 25

表2:货物信息表

编号 所属货轮 目的仓库 起吊用时
P11 C1 S1 15
P12 C1 S1 26
P13 C1 S2 37
P14 C1 S3 9
P15 C1 S2 32
       
P21 C2 S3 8
P22 C2 S2 9
P23 C2 S3 27
P24 C2 S1 11
P25 C2 S2 4
P26 C2 S3 5
       
P31 C3 S3 8
P32 C3 S1 51
P33 C3 S2 27
P34 C3 S1 13
P35 C3 S3 29
       
P41 C4 S1 10
P42 C4 S2 22
P43 C4 S1 25
       
P51 C5 S1 17
P52 C5 S3 26
P53 C5 S3 7
P54 C5 S2 30
P55 C5 S2 43

表3 仓库信息表

编号 往返时间
C1 16
C2 20
C3 24

构造出各位认为总用时足够短的调度方案,说明轮船、货物起吊、运输车的调度顺序并推算出方案的调度时间,相应定义见题干。

由于数据是我瞎编的,我也不知道准确的最短用时是多少(被打死)。因此,从现在到明天(即4月7日)21点为止为有效时间,将会选出得出调度时间最短的解的作者,给予我自掏腰包的100节操奖励!(多人给出的解均为最优的,奖励只颁给第一个给出已知最优解的作者;同一个人的多个解以最优的为准;奖励颁发之后给出的解很遗憾是无效的)

p.s. 这道题是个NP-完全问题,大家可以说说为什么?(不要求严谨的证明,思路也可;证明无奖励)

,由Mr.K 018修改
注释
摸鱼奇才咖啡喵 摸鱼奇才咖啡喵 110.00节操 次海鲜罐头喵~
链接到点评
9 小时前, 萨卡 说道:

不想算...但扫了一眼..这不就类似用dijkstra算法么, 只有最坏项式所以是NP

这个题可以证明是个NP完全,所以Dijkstra这种多项式时间的算法肯定是不行的。

证明的大概思路:这个问题可以规约到若干种不同的NP完全问题。例如,当船的出港时间为0,也没有货物要起吊(就是说只需要入港即可)的情况下,这个问题就退化成多机调度问题。众所周知,多机调度问题是个NP完全问题,因此本题也是一个NP完全问题。假设能找到本题的多项式时间算法,相当于证明了P=NP

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款