高分求一算法！！！！！！！

Question

请问有谁做“一维下料优化计算”的，现在我也要做这个了，但无从下手，有做过的高手能教一下算法吗？有的可以发到.谢谢了

Answer 1

一维下料优化计算？什么概念啊？是不是ERP系统里啊？类似与多阶材料用量计算？还是BOM成本计算吗？

Answer 2

可以这样说，钢管、型材，棒材什么的都可切。
他的问题是这样的：给定m种长度的坯料l1,l2,...lm,所需的数量分别为b1,b2,...bm，已知原材料的长度L。以所需原材料最少，切割后余料最少为目标的算法。

Answer 3

很抱歉各位，因为太匆忙所以来不及说明，现在补充：“下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，要把源材料的利用率提得最高的一种优化算法，网上有很多这样的算法，比如，搜索树，分枝定界法，动态规划等等，但都是一些数学模型，苦于我的数学不好，没办法弄懂（要把程序编好，数学一定要学好！）
举个例子：给定一个原材料长度4000，来切割长度例里那些长度，要做到余料量最少，要用程序来算要怎么算。（用人工在Excel里算的公式是：切割数＝INT（原材料长度/（长度+5））;实用长度＝（长度+5）*切割数;余料＝原材料长度-实用长度）
长度 数量 切割数 实用长度 原材料长度  余料
463 100 8 3744 4000    256
405 200 9 3690 4000    310
324 200 12 3948 4000    52
256 200 15 3915 4000    85
182 200 21 3927 4000    73

Answer 4

to:Knight94(愚翁)
谢谢你的建议，我现在看看去

Answer 5

to:mobydick(敌伯威|我排著队拿著爱的号码牌) 
呃···那请问你有没有关于一维下料的俱体算法呢

Answer 6

#define MAX_MSG_SIZE 10
#define QUEUE_ID      16
#include<linux/msg.h>
struct msgbuf1{
long mtype;
int  mtext;
};
int main()
{
  //取得消息队列ID
  int queue_id = msgget(QUEUE_ID,0);
  if(queue_id == -1)
    {
      perror("main: msgget");
      exit(1);
    }  
  printf("Start Receiving\n");  
  int num =100;
  while(num>0)
    {
        //接收消息1
   struct msgbuf1* revmsg1 = (struct msgbuf1*)malloc(sizeof(struct msgbuf1));
   int rc = msgrcv(queue_id,revmsg1,sizeof(int),1,0);
   if(rc == -1)
      {
         perror("main: msgrcv");
           exit(1);
     }
  //接收消息2
   struct msgbuf1* revmsg2 = (struct msgbuf1*)malloc(sizeof(struct msgbuf1));
   rc = msgrcv(queue_id,revmsg2,sizeof(int),2,0);
   if(rc == -1)
     {
        perror("main: msgrcv");
        exit(1);
        }
       printf("%5d\t",revmsg1->mtext);
        printf("%5d",revmsg2->mtext);
        if(revmsg1->mtext - revmsg2->mtext ==1 ||revmsg1->mtext - revmsg2->mtext==-2)
        printf("Jia Win\n");
        else if(revmsg1->mtext == revmsg2->mtext)
        printf("Ping Ju\n");
        else 
        printf("Jia Lose\n");       num--;
//sleep(2000);
    }
  
  
  
  return 1;}
#define QUEUE_ID      16
#include<linux/msg.h>
#include<stdio.h>
#include<time.h>struct msgbuf1{
long mtype;
int  mtext;
};
int main()
{  //建立消息队列
  int queue_id = msgget(QUEUE_ID,IPC_CREAT | IPC_EXCL);
  //printf("%d",queue_id)
  if(queue_id == -1)
    {
      perror("main: msgget");
      exit(1);
    }    //取得消息队列ID
  queue_id = msgget(QUEUE_ID,0);
  if(queue_id == -1)
    {
      perror("main: msgget");
      exit(1);
    }    //建立消息  
  struct msgbuf1* msg = (struct msgbuf1*)malloc(sizeof(struct msgbuf1));     
   int num = 100;
   while(num>0)
    {
msg->mtype = 1;
srand(time(NULL) +num);
        msg->mtext = random()%3;
        // sprintf(msg->mtext,"Hello");
        //发送消息到队列
        int send = msgsnd(queue_id,msg,sizeof(int),0);
num--;
//sleep(2000);


    }
   
  
  return 1;
  //}
#define QUEUE_ID      16
#include<linux/msg.h>
#include<stdio.h>
#include<time.h>
struct msgbuf1{
long mtype;
int  mtext;
};
int main()
{  //建立消息队列
  int queue_id = msgget(QUEUE_ID,IPC_CREAT);
  //printf("%d",queue_id)
  if(queue_id == -1)
    {
      perror("main: msgget");
      exit(1);
    }    //取得消息队列ID
  queue_id = msgget(QUEUE_ID,0);
  if(queue_id == -1)
    {
      perror("main: msgget");
      exit(1);
    }    //建立消息  
  struct msgbuf1* msg = (struct msgbuf1*)malloc(sizeof(struct msgbuf1));
  
   msg->mtype = 2;
   int num = 100;
   while(num>0)
    {
srand(time(NULL)+num*2);
        msg->mtext = random()%3;
        // sprintf(msg->mtext,"Hello");        //发送消息到队列
        int send = msgsnd(queue_id,msg,sizeof(int),0);
num--;
//sleep(2000);
    }
  
  return 1;
  //}

Answer 7

TO:Zlstt(qq) 谢谢你的程序，我先看看。TO：xiaobaixu() 数学模型我看了，但就是没法根椐模型写出算法。

Answer 8

TO:Zlstt(qq)
我想问一下，上面你那段程序是说什么啊～～～
TO：mobydick(敌伯威|我排著队拿著爱的号码牌)
：)

Answer 9

很显然，这个问题就是求解 多元一次函数方程的最小值。如果想自己写这个算法，建议
看看线性规划(Linear programming)的书， 或者可以直接从网上下载 线性规划算法的源码。

Answer 10

To:coolcup(我是真的) 
谢谢回复，请问一下，在那能下载线性规划算法的源码。

Answer 11

To watersuperman() 
用google搜索 linear programming http://www-fp.mcs.anl.gov/otc/Tools/PCx/
这是其中一个，PCx is an interior-point predictor-corrector linear programming package.建议你买本书看看，最好能明白算法的思想。网上好像也有些关于用MATLAB进行linear programming的例子。

Answer 12

To:coolcup(我是真的) 
谢谢你的建议，但远水救不了近火，这个开料优化程序是迫在眉头的事，没有时间让我去慢慢去看线性规划什么的啦，如果有现成的相似的例子就好了．