通用問題,Sorry,第二個高度也是3CM.數據算法里我帖了,但沒人解呀/

解决方案 »

  1.   

    漏了高3CM吧。理论上不难,这是个单目标最优化问题,不过多年没用,恐怕已
    还给老师了。试着写个思路:
        这道题实际就是求一个大盒怎样装二種小盒才最满的问题。
        设可装入的小盒分别为x1,x2. 
        目标函数:min(z)=(100*50*50-(3*@*1)*x1-(5*4*3)*x2)
        约束条件:x1        <=1000
                  x2       <=1000
                  3x1+5x2  <=100
                  2x1+4x2  <=50
                   x1_3x2  <=50
        目标误差=min(3*2*1,5*4*3)
        用松弛因子x3,x4,x5将上述约束变为等式,然后用“单纯型法”求解,
        这个“单纯型法”有通用的算法程序,你找找看吧,不用自己编。
    ---------------------------------------------------------------
    可能写得不对,但思路是绝对正确的,请懂这个的指正。
        
                  
      

  2.   

    我這是沒想就假設出數字來了,沒考慮清楚。
    就按haiwer說的改成兩種小盒各10000個吧。
    高手快支招呀!!!
      

  3.   

    这是很典型的运筹学的线性规划问题,学经济、管理,还有我的水文专业
    都有这们课程,学数学的就更不用说了。恐怕无法在这里一下说得很清楚,
    大意上用的是叠代算法,使松弛因子达到最小吧,因为加入松弛因子后,就变成。怎么求解多元方程组的问题了,怎么解,就是所谓的“单纯型法”。惭愧,都忘得差不多了,只能说这么多,要是按钮在就好了。还是找本运筹学的书看看吧。再找“单纯型法”的程序。前面写法有点儿毛病,应该是:
    -----------------------------------------
    目标函数:min(z)=(100*50*50-(3*2*1)*x1-(5*4*3)*x2) 
    约束条件:x1 <=10000 
              x2 <=10000 
         3x1+5x2 <=100 
         2x1+4x2 <=50 
          x1+3x2 <=50 
      

  4.   

    这个问题挺有意思,不过我觉得也是挺难的。我只说说我的看法。net_steven(吃素的狼) 思路不错。不过我觉得这个问题用简单的线性规划可能解决不了。因为做线性规划是有前提的:1、资源有限,各个因素需要抢夺资源。这个问题表面上看来资源有限,其实也不一定,因为没有规定最后有几个大盒子。若换成是求在一个大盒子里能装的最多各种盒子的个数可能还可以。2、各个因素有明确的相关的关系。这个我想了想好象也不好用数学式来表达。用长宽高的和不大于总长宽高,可能是不对的。一个大盒里放A类盒的数量与放B类盒的数量当然有关系,但是我还没想出可以用线性方程来表达。因为盒子的放置可以是任意方面的。若这个问题是不考虑体积,只是考虑重量的话,就可以用达到这个要求了。约束条件用
    X1*a_SingleWeight+X2*b_SingleWeight<=SumWeight
    就可以了。所以这个条件也不好满足。若这两个前提不能满足,就不能用线性规划来逼近最优解。我自己考虑了一个思路,可以得出解,但不知道是不是最优解。我的思路是:
    1、先在大盒(100*50*50)中放置A类盒(5*4*3),最多可以放
       int(100/5)*int(50/4)*int(50/3)=20*12*16=3840
    或 int(100/4)*int(50/3)*int(50/5)=25*16*10=4000
    或 int(100/3)*int(50/4)*int(50/5)=33*12*10=3940
    最大值为4000,所以按第二种方法放置。2、第一步完成后,大盒中会产生一个未被占用的空间,可以知道规格是100*2*50。用第一步中的方法,可以知道最多可以在其中放1650个B类盒(3*2*1)。3、10000=2*4000+2000
       10000=2*1650+6700
      所以按前两步的放置方法可以放两个盒子,最后还余下2000个A类盒和6700个B类盒。继续前两步的方法,判断需要几个盒子。结论是一个盒子可以放得下。所以最后答案是需要三个盒子。现在关键问题是我不知道这样得到的是不是最优解。因为我的前提是同一种盒子在一个空间中摆放方向都是一样的,这样是不是比摆放方向不一样能放进更多的盒子,我不知道怎么用数学方法来证明它正确或者错误。严格意义上是需证明才能有说服力。
      

  5.   


        好多年前我就想过这个问题了。 用在如: "装货柜" 前计算体积之类的功能上.
     
        HE HE ~ 好难啊 ! 让我来 UP ------
      

  6.   

    用ILOG软件吧,(不过我没有)。
    我这里有一个其他的运筹软件,你要的话我可以发给你。
    我劝你不要想怎么做了,因为这个东西是别人软件的一个功能模块
      

  7.   

    哈, icevi和我的分析差不多,对了, icevi我发现你少了一个余下空间还有:1*50*2没有放3*2*1的小盒子,所以结果是1650个,如果放了就是1666个!(50/3)*(2/2)*(1/1)=16个
      

  8.   

    csdn是怎么了,不自动换行,好多内容看不到!
      

  9.   

    这是著名的“集装箱问题”(Container Loading Problem或者称为Bin Packing Problem),又称为“三维背包问题”( 3-D Knapsack Problem)
    众所周知一维的背包问题(0-1背包问题)可用动态规划解决
    可惜的是二维三维的背包问题是NP完全问题 :-(
    至今还没有找到多项式时间的算法,而且很可能根本没有多项式时间的算法
    这类问题通常用近似算法或一些随机化算法
    然而,最近的一些研究表明,不可能找到一个多项式时间的近似算法,使得该算法所得到的较优解与实际最优解的比值以一个常数为界;换句话说任何多项式时间的近似算法都无法保证与最优解近似的程度;(我记得这是上次听朱宏老师的讲座听到的,具体出自何处还有待考证)
    另一种解决途径是随机化算法或遗传算法或神经网络,然而这些算法要么是不能保证得到最优解(也不能保证近似程度),要么是不能保证多项式时间的复杂度。所以这个问题是很难的,不要妄图找到最优解的算法了,还是考虑近似算法吧~下面的网站有一些相关资源:
    http://cs.ua.edu/reu/1998_stuff/German/index.html下面的论文提出了一种启发式搜索算法:A tree-search heuristic for the container loading problem, David Pisinger, Dept. of Computer Science, University of CopenhagenAbstract
    We consider the container loading problem where a number of rectangular boxes should be loaded into a container of fixed dimensions. In order to develop an effective heuristic, we restrict out problem to consider loadings which are guillotine cuttable, i.e. where the container may be filled by dividing it into layers and subdividing each layer into strips, a strip usually being a sequence of boxes. This restriction implies tha every strip may be optimally filled by solving a knapsack problem with capacity equal to the length of the strip. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored. 
    Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.这篇论文可以在http://cora.whizbang.com/ 搜索到 (搜索关键字“container loading”)我建议你看看这篇论文,该文所提出的算法也许对你有所帮助。
    PS: 线性规划、整数规划、非线性规划等等统筹学中的规划算法都是指数时间复杂度的算法,这个问题的最大难度在于计算复杂度随着问题规模的增加而急剧的增加。与其用这些规划算法来解,还不如编程序搜索呢,只要剪枝得当,搜索的效率要比这些规划算法要高得多。PS又PS:
    如果不一定要求最优解,而可以允许较优解的话,这个问题要简单的多。
      

  10.   

    同意 rwq_(风云浪子) ,是算漏了:P同意 starfish(海星) 的观点,其实很多问题都是没有最优解的,或者说寻找最优解的代价过高。所以我觉得有一个合适的可实际操作的算法,能得到可行解,达到一定程度上的优化就可以了。
      

  11.   

    to starfish(海星)
    这个问题有它的特殊性,就是只有两种box。不要因为是NP就认为解不出,举个例子,如果Hamilton路只有2个点,怎么做都做得出。另外,这个问题中大多数据都已经指明,应该可以找出好的,有针对性的算法(不要看我,我可找不出)。
      

  12.   

    斑竹说得对,starfish(海星)的确对算法很有造诣.其实两年前我就遇到这个问题,
    我们是货运公司,上头想找一个优化集装箱、货柜的方法,我觉得麻烦一句“做不了”就推了——呵呵,的确作不了。
      

  13.   

    TO: aliceZOOZ
    我以为顶楼的兄弟所提出的数据只是一个用来说明问题的例子
    他的实际应用中应该不会只有两种盒子
    退一步,就算只有两种盒子
    这个问题还是很难解
    你所举的哈密尔顿回路的例子并不恰当
    因为哈密尔顿回路问题中图的顶点数就唯一地确定了问题的规模
    但是决定这个问题的规模的并不仅仅是盒子的种类数目
    而是与盒子本身的数目,以及小盒子、大盒子体积的比例等因素有关
    如果盒子本身的数目很大的话(比如只有两种小盒子,但是每种都有100万个)
    这个问题还是很难解的不过,我所提到的那篇论文中的搜索算法还是挺不错的,可能在实际应用中有一定的价值
      

  14.   

    >>但是决定这个问题的规模的并不仅仅是盒子的种类数目
    我之所以这么说,是因为
    Computational experiments involving up to 120 boxes are reported, showing tha several loading problems from the literature are solved to optimality in reasonable time, achieving an average filling of 91% of the container volume.注意到这里面只提到了一个 120 boxes,也就是说,这个算法可以对 120 boxes做很好的近似,而不管小盒子、大盒子体积的比例等因素。
    如果只有 2 boxes的话,那么这个算法的速度,近似程度就会发生质变,甚至有可能出现最优解的“有效”算法。
    再说,你凭什么认为决定这个问题的规模的并不仅仅是盒子的种类数目。虽然感觉上是这样,而我最初也是这么认为的。不过看了上面引用的这段论文而产生了前面的想法。