求运筹学0-1整数规划问题程序

fanweny

求运筹学0-1整数规划问题程序
谢谢！ fanweny1@163.com

风花雪月

用元素分配法求解0-1整数规划问题，VC程序

1. // ElementAlloc.cpp: implementation of the CElementAlloc class.
   
2. //
   
3. //////////////////////////////////////////////////////////////////////
   
4. 
   
5. #include "stdafx.h"
   
6. #include "..\..\INCLUDE\ElementAlloc.h"
   
7. #include "..\..\INCLUDE\TianjiDataType.h"
   
8. 
   
9. #ifdef _DEBUG
   
10. #undef THIS_FILE
    
11. static char THIS_FILE[]=__FILE__;
    
12. #define new DEBUG_NEW
    
13. #endif
    
14. 
    
15. //////////////////////////////////////////////////////////////////////
    
16. // Construction/Destruction
    
17. //////////////////////////////////////////////////////////////////////
    
18. 
    
19. CElementAlloc::CElementAlloc()
    
20. {
    
21. 
    
22. }
    
23. 
    
24. CElementAlloc::~CElementAlloc()
    
25. {
    
26. 
    
27. }
    
28. 
    
29. /****************************求检验数函数，未加入对异常值的处理**************************************/
    
30. void CElementAlloc::ReckonVerify(int nWorkNum, int nWorkerNum, double* ptValue, int* ptVerify)
    
31. {
    
32.     int i = 0, j = 0, k = 0, l = 0;
    
33.     for(i = 0; i < nWorkerNum; i++)
    
34.     {
    
35.         for(j = 0; j < nWorkNum; j++)
    
36.         {
    
37.             int ndx = 0;
    
38.             for(l = (-1) * i; l < nWorkerNum - i; l++)
    
39.             {
    
40.                 if(l)
    
41.                 {
    
42.                     for(k = (-1) * j; k < nWorkNum - j; k++)
    
43.                     {
    
44.                         /*************求每个元素的检验数************/
    
45.                         if(k && (ptValue[i * nWorkNum + j] + ptValue[(i + l) * nWorkNum + j + k]
    
46.                             - ptValue[i * nWorkNum + j + k] - ptValue[(i + l) * nWorkNum + j] < 0))
    
47.                             ndx++;
    
48.                     }
    
49.                 }
    
50.             }
    
51.             ptVerify[i * nWorkNum + j] = ndx;
    
52.         }
    
53.     }
    
54. }
    
55. 
    
56. /************************************根据检验数求指派问题的解********************************************************/
    
57. void CElementAlloc::ElementAlloc(int nWorkNum, int nWorkerNum,double* ptValue, struct ALLOCPROJECT* ptAllocProject)
    
58. {
    
59.     int i = 0, j = 0, nProjectNum = 0, nTemp = 0;
    
60.     double ftTemp = 1000.0;
    
61.     int* ptVerify = new int[nWorkNum * nWorkerNum];
    
62. 
    
63.     ReckonVerify(nWorkNum, nWorkerNum, ptValue, ptVerify);
    
64. 
    
65.     nProjectNum = nWorkNum;
    
66.     if(nWorkNum > nWorkerNum)nProjectNum = nWorkerNum;
    
67.     for(int k = 0; k < nProjectNum; k++)
    
68.     {
    
69.         nTemp = 0;
    
70.         ftTemp = 1000.0;
    
71.         for(i = 0; i < nWorkerNum; i++)
    
72.         {
    
73.             for(j = 0; j < nWorkNum; j++)
    
74.             {
    
75.                 if(nTemp <= ptVerify[i * nWorkNum + j])nTemp = ptVerify[i * nWorkNum + j]; //找出值最大的检验数
    
76.             }
    
77.         }
    
78.         for(i = 0; i < nWorkerNum; i++)
    
79.         {
    
80.             for(j = 0; j < nWorkNum; j++)
    
81.             {
    
82.                 if(nTemp == ptVerify[i * nWorkNum + j])
    
83.                 {
    
84.                     //若有多个同时为最大的检验数，则选择消费值最小的
    
85.                     if(ftTemp > ptValue[i * nWorkNum + j])
    
86.                     {
    
87.                         ptAllocProject[k].nWorkNO = j;
    
88.                         ptAllocProject[k].nWorkerNO = i;
    
89.                         ftTemp = ptValue[i * nWorkNum + j];
    
90.                     }
    
91.                 }
    
92.             }
    
93.         }
    
94.         /***********************将找出的检验数对应的行和列划去************************/
    
95.         for(i = 0; i < nWorkerNum; i++)
    
96.             ptVerify[i * nWorkNum + ptAllocProject[k].nWorkNO] = -1;
    
97.         for(j = 0; j < nWorkNum; j++)
    
98.             ptVerify[ptAllocProject[k].nWorkerNO * nWorkNum + j] = -1;
    
99.     }
    
100.     delete []ptVerify;
     
101. 
     
102. }

复制代码