现在的位置: 首页 > 综合 > 正文

线性规划 单纯形算法

2013年10月07日 ⁄ 综合 ⁄ 共 4999字 ⁄ 字号 小 中 大 ⁄ 评论关闭
线性规划 单纯形算法

根据单联通区域求极值的想法得来的算法思想，故而叫做simplex algorithm。
暂且将写下的程序贴出，做个备份。
具体算法分析待看完证明后贴出。

此算法实现完全是对《算法导论》上算法框架的实现。
注：要使用g++编译器，vc要将变量定义做一些更改。

  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <ctime>
  5. #include <climits>
  6. #include <cmath>
  8. using namespace std;
  10. int const BUF = 100;
  12. set<int> N,B;
  13. set<int>::iterator p,q;
  15. double bi[BUF];
  16. double ci[BUF];
  17. double v;
  18. double A[BUF][BUF];
  19. double res[BUF];
  21. int Num;
  23. //question:
  24. //      request: max v+ci*x (ci=0,if and only if x[i] not in N)
  25. //      constraint: y = bi+A*x (x[i] is in B and y[i] is in B)
  26. //      solution: res and v
  29. //  output the form of the question's equalities.
  30. //  you can invoke this function after "pivot" function to see the changes.
  31. void output()
  32. {
  33.     set<int>::iterator pt;
  35.     printf("z    = %.2lf ",v);
  36.     
  37.     p = N.begin();
  38.     
  39.     while(p!=N.end()){
  40.         pt = p;
  41.         pt++;
  43.         if(pt!=N.end()){
  44.             if(ci[*p]>0)
  45.                 printf(" + %.2lf*x(%d) ",ci[*p],*p);
  46.             else 
  47.                 printf(" - %.2lf*x(%d) ",fabs(ci[*p]),*p);
  48.         }else {
  49.             if(ci[*p]>0)
  50.                 printf(" + %.2lf*x(%d)/n",ci[*p],*p);
  51.             else 
  52.                 printf(" - %.2lf*x(%d)/n",fabs(ci[*p]),*p);
  53.         }
  54.         p++;
  55.     }
  56.     
  57.     for(p=B.begin();p!=B.end();p++){
  58.         
  59.         printf("x(%d) = %.2lf ",*p,bi[*p]);
  60.         
  61.         q = N.begin();
  62.         
  63.         while(q!=N.end()){
  64.             pt = q;
  65.             pt++;
  66.             if(pt!=N.end()){
  67.                 if(A[*p][*q]>0)
  68.                     printf(" - %.2lf*x(%d)",A[*p][*q],*q);
  69.                 else 
  70.                     printf(" + %.2lf*x(%d)",fabs(A[*p][*q]),*q);
  71.             }else {
  72.                 if(A[*p][*q]>0)
  73.                     printf(" - %.2lf*x(%d)/n",A[*p][*q],*q);
  74.                 else 
  75.                     printf(" + %.2lf*x(%d)/n",fabs(A[*p][*q]),*q);
  76.             }
  77.             q++;
  78.         }
  79.     }
  80.     printf("/n");
  81. }
  83. // input format:
  84. //      first line one number Num representing
  85. //      the num of all variables including the elements of N and B
  86. //      next Num lines representing A[i][j] which is the coefficient of x[i]
  87. //      next two lines each includes Num numbers --- the ci and bi respectively
  88. //  for example
  89. /*
  91. input:@file = "t.in"
  92.     
  93. 6
  94. 0 0 0 0 0 0 
  95. 0 0 0 0 0 0
  96. 0 0 0 0 0 0
  97. 1 1 3 0 0 0
  98. 2 2 5 0 0 0
  99. 4 1 2 0 0 0
  100. 3 1 2 0 0 0
  101. 0 0 0 30 24 36
  102. 0
  104. representing the standard format:
  106. z    = 3*x(0)  + x(1)  + 2*x(2)
  107. x(3) = 30  - 1*x(0) - x(1) - 3*x(2)
  108. x(4) = 24  - 2*x(0) - 2*x(1) - 5*x(2)
  109. x(5) = 36  - 4*x(0) - *x(1) - 2*x(2)
  110. */
  112. void init()
  113. {
  114.     freopen("t.in","r",stdin);
  115.     freopen("t.out","w",stdout);
  116.     
  117.     scanf("%d",&Num);
  118.         
  119.     for(int i=0;i<Num;i++)
  120.         for(int j=0;j<Num;j++)
  121.             scanf("%lf",&A[i][j]);
  122.     
  123.     
  124.     for(int i=0;i<Num;i++)
  125.         scanf("%lf",&ci[i]);
  126.         
  127.     for(int i=0;i<Num;i++)
  128.         scanf("%lf",&bi[i]);
  129.         
  130.     scanf("%lf",&v);
  131.     
  132.     for(int i=0;i<Num;i++)
  133.         ci[i]!=0 ? N.insert(i):B.insert(i);
  134.     
  135.     output();
  136.     
  137.     srand((unsigned)clock());
  138. }
  140. // relex each x[i]'s coefficient the main part of this algorithm.
  141. //x[e] is the new basic variable. x[l] is changed into nonbasic variable.
  143. void pivot(int l,int e) 
  144. {
  145.     bi[e] = bi[l]/A[l][e];
  146.     
  147.     for(p=N.begin();p!=N.end();p++)
  148.         A[e][*p] = A[l][*p]/A[l][e];
  149.     
  150.     A[e][l] = 1/A[l][e];
  151.     
  152.     for(p=B.begin();p!=B.end();p++){
  153.         
  154.         if(*p==l)continue;
  155.         
  156.         bi[*p] -= A[*p][e]*bi[e];
  157.         
  158.         for(q=N.begin();q!=N.end();q++)
  159.             if(*q!=e)
  160.                 A[*p][*q] -= A[*p][e]*A[e][*q];
  161.         
  162.         A[*p][l] = -1*A[*p][e]*A[e][l];
  163.     }
  164.     
  165.     v += ci[e]*bi[e];
  166.     
  167.     for(p=N.begin();p!=N.end();p++)
  168.         if(*p!=e)
  169.             ci[*p] -= ci[e]*A[e][*p];
  170.         
  171.     ci[l] = -1*ci[e]*A[e][l];
  172.     
  173.     N.insert(l),N.erase(e);
  174.     B.insert(e),B.erase(l);
  175. }
  177. //  basing a little random selection on selecting
  178. //  which x[i] will be changed into basic variables
  179. void simplex()
  180. {
  181.     double temp = INT_MAX;
  182.     
  183.     vector<int> v;
  184.     
  185.     while(1){
  186.         
  187.         temp = INT_MAX;
  188.         
  189.         v.clear();
  190.         
  191.         for(p=N.begin();p!=N.end();p++)
  192.             if(ci[*p]>0)
  193.                 v.push_back(*p);
  194.         
  195.         if(v.size()==0){
  196.             temp = 0;
  197.             break;
  198.         }
  199.         
  200.         int t = rand()%v.size();
  201.         
  202.         int tn;
  203.         
  204.         for(q=B.begin();q!=B.end();q++)
  205.             if(A[*q][t]>0){
  206.                 
  207.                 double tk = bi[*q]/A[*q][t];
  208.             
  209.                 if(temp>tk)temp=tk,tn=*q;
  210.             }
  211.         
  212.         printf("l = %d  e = %d/n",tn,t);
  213.         
  214.         if(temp==INT_MAX)
  215.             break;
  216.         else 
  217.             pivot(tn,t);
  218.             
  219.         output();
  220.         
  221.     }
  222.     
  223.     if(temp==INT_MAX){
  224.         printf("no answer/n"); 
  225.         //which means unbounded,i.e. the question has no answer
  226.         exit(0);
  227.     }
  228. }
  229.     
  230. void result()
  231. {
  232.     printf("/n");
  233.     
  234.     for(p=B.begin();p!=B.end();p++)
  235.         res[*p] = bi[*p];
  236.     
  237.     printf("ans seq: ");
  238.     for(int i=0;i<Num;i++)
  239.         printf("%.2lf ",res[i]);
  240.         
  241.     printf("/nmax: %.2lf/n",v);
  242. }
  244. int main()
  245. {
  246.     init();
  247.     
  248.     simplex();
  249.     
  250.     result();
  251.     
  252.     return 0;
  253. }
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞