0

我已经实现了分支定界算法，算法如下：

  1. 找到放宽整数限制的线性规划模型的最优解。
  2. 在节点 1 处，放宽解为上限，向下取整的整数解为下限
  3. 选择具有最大小数部分的变量进行分支为此变量创建两个新约束，反映分区整数值。结果将是一个新的 <= 约束和一个新的 >= 约束。
  4. 创建两个新节点，一个用于 >= 约束，一个用于 <= 约束。
  5. 在每个节点处添加新约束来求解松弛线性规划。
  6. 松弛解是每个节点的上限，现有的最大整数解（在任何节点）是下限。
  7. 如果任何结束节点的最大上限值
  8. 返回步骤 3。

实现如下：

#include <stdio.h>
#include <math.h>
#include "time.h"
#include<sys/timeb.h>


#define CMAX  100  //max. number of variables in economic function
#define VMAX  100  //max. number of constraints


  int NC, NV, NOPTIMAL,P1,P2,XERR,NC1,NC2;
  double TS[CMAX][VMAX];


  void Data() 
  {
    double R1,R2;
    char R;
    int I,J;
    printf("\n LINEAR PROGRAMMING\n\n");
    printf(" MAXIMIZE (Y/N) ? "); 
    scanf_s("%c", &R);
     printf("\n");
  printf(" Number of variables in E.F.: "); scanf_s("%d", &NV);
  printf(" Number of <= inequalities..: "); scanf_s("%d", &NC);
  printf(" Number of >= inequalities..: "); scanf_s("%d", &NC1);
  printf(" Number of = equalities.....: "); scanf_s("%d", &NC2);
  /*  printf("\n NUMBER OF VARIABLES OF ECONOMIC FUNCTION ? "); 
    scanf_s("%d", &NV);
    printf("\n NUMBER OF CONSTRAINTS ? "); 
    scanf_s("%d", &NC);*/
    if (R == 'Y' || R=='y')
      R1 = 1;
    else
      R1 = -1;

    printf("\n INPUT COEFFICIENTS OF ECONOMIC FUNCTION:\n");
    for (J = 1; J<=NV; J++) 
    {
      printf("       x%d ?: ", J); 
      scanf_s("%lf", &R2);
      TS[1][J+1] = R2 * R1;
    }
    printf("       Right hand side ? "); 
    scanf_s("%lf", &R2);
    TS[1][1] = R2 * R1;
    for (I = 1; I<=NC; I++) 
    {
        printf("\n CONSTRAINT #%d:\n", I);
      for (J = 1; J<=NV; J++) 
      {
        printf("       x%d ?: ", J); 
        scanf_s("%lf", &R2);
        TS[I + 1][J + 1] = -R2;
      }
      printf("       Right hand side ?: "); 
      scanf_s("%lf", &TS[I+1][1]);
      }
    for (I = 1; I<=NC1; I++) 
    {
        printf("\n CONSTRAINT #%d:\n", I);
      for (J = 1; J<=NV; J++) 
      {
        printf("       x%d ?: ", J); 
        scanf_s("%lf", &R2);
        TS[I + 1][J + 1] = -R2;
      }
      printf("       Right hand side ?: "); 
      scanf_s("%lf", &TS[I+1][1]);
      }
    for (I = 1; I<=NC2; I++) 
    {
        printf("\n CONSTRAINT #%d:\n", I);
      for (J = 1; J<=NV; J++) 
      {
        printf("       x%d ?: ", J); 
        scanf_s("%lf", &R2);
        TS[I + 1][J + 1] = -R2;
      }
      printf("       Right hand side ?: "); 
      scanf_s("%lf", &TS[I+1][1]);
    }
    printf("\n\n RESULTS:\n\n");
    for(J=1; J<=NV; J++)
        TS[0][J+1] = J;
    for(I=NV+1; I<=NV+NC; I++)  
        TS[I-NV+1][0] = I;
  }

  void Pivot();
  void Formula();
  void Optimize();
  //void Branch_and_Bound();

  void Simplex() 
  {
e10: Pivot();
     Formula();
     Optimize();
     //Branch_and_Bound();
     if (NOPTIMAL == 1) goto e10;
  }

  void Pivot() 
  {

    double RAP,V,XMAX;
    int I,J;

    XMAX = 0;
    for(J=2; J<=NV+1; J++) 
    {
    if (TS[1][J] > 0 && TS[1][J] > XMAX) 
      {
        XMAX = TS[1][J];
        P2 = J;
      }
    }
    RAP = 999999;
    for (I=2; I<=NC+1; I++) 
    {
      if (TS[I][P2] >= 0) 
          goto e10;
      V = fabs(TS[I][1] / TS[I][P2]);
      if (V < RAP) 
      {
        RAP = V;
        P1 = I;
      }
e10:;
    }
    V = TS[0][P2]; 
    TS[0][P2] = TS[P1][0]; 
    TS[P1][0] = V;
  }

  void Formula() 
  {;
    //Labels: e60,e70,e100,e110;
    int I,J;

    for (I=1; I<=NC+1; I++) 
    {
      if (I == P1) goto e70;
      for (J=1; J<=NV+1; J++) 
      {
        if (J == P2) goto e60;
        TS[I][J] -= TS[P1][J] * TS[I][P2] / TS[P1][P2];
e60:;
      }
e70:;
    }
    TS[P1][P2] = 1 / TS[P1][P2];
    for (J=1; J<=NV+1; J++)
    {
      if (J == P2) goto e100;
      TS[P1][J] *=fabs(TS[P1][P2]);
e100:;
    }
    for (I=1; I<=NC+1; I++) 
    {
      if (I == P1) goto e110;
      TS[I][P2] *= TS[P1][P2];
e110:;
    }
  }   

  void Optimize() 
  {
    int I,J;
    for (I=2; I<=NC+1; I++)

      if (TS[I][1] < 0)  XERR = 1;
    NOPTIMAL = 0;
    if (XERR == 1)  return;
    for (J=2; J<=NV+1; J++)
      if (TS[1][J] > 0)  NOPTIMAL = 1;
  }
  /*void Branch_and_Bound()
  {
      int I,J;
 for (I=1; I<=NC+1; I++) 
    {
      if (I == P1) goto e70;
      for (J=1; J<=NV+1; J++) 
      {
        if (J == P2) goto e60;
        TS[I][J] -= TS[P1][J] * TS[I][P2] / TS[P1][P2];
e60:;
      }
e70:;
    }
    TS[P1][P2] = 1 / TS[P1][P2];
    for (J=1; J<=NV+1; J++)
    {
      if (J == P2) goto e100;
      TS[P1][J] *=fabs(TS[P1][P2]);
e100:;
    }
    for (I=1; I<=NC+1; I++) 
    {
      if (I == P1) goto e110;
      TS[I][P2] *= TS[P1][P2];
e110:;
    }
  } */ 

  void Results() 
  {
    //Labels: e30,e70,e100;
    int I,J;

    if (XERR == 0) goto e30;
    printf(" NO SOLUTION.\n"); goto e100;
e30:for (I=1; I<=NV; I++)
    for (J=2; J<=NC+1; J++) 
    {
      if (TS[J][0] != 1*I) goto e70;
      printf("       VARIABLE x%d: %f\n", I, TS[J][1]);
e70:  ;
    }
    printf("\n       ECONOMIC FUNCTION: %f\n", TS[1][1]);
e100:;printf("\n");
  }


void main()  
{

  Data();
  Simplex();
  //Branch_and_Bound();
  Results(); 
}

现在我必须在实施中做出一些改变。在步骤 3 中，如果正常分支定界方法中唯一的其他变化是在步骤 3，则一旦确定了具有最大小数部分的 xj 的变量，则从该变量开发的两个新约束是 xj=0 和 xj= 1. 这两个新约束将在每个节点处形成两个分支。

4

0 回答 0