simplex.c

本程序是为解决线性规划的标准优化问题

// Simplex optimization algorithm


#include <stdlib.h>
#include <stdio.h>

void pivot(int N, int M, double **a, int p, int q) 
{
  int j, k;

  for (j = 0; j < N; j++) 
    for (k = M-1; k >= 1; k--)
      if (j != p && k != q)
        a[j][k] -= a[p][k] * a[j][q] / a[p][q];

  for (j = 0; j < N; j++)
    if (j != p) 
      a[j][q] = 0.0;

  for (k = 1; k < M; k++)
    if (k != q)
      a[p][k] /= a[p][q];

  a[p][q] = 1.0;
}

int simplex(int N, int M, double **a) 
{
  int i, p, q;

  do {
    // find negative value in row 0
    q = 0;
    while (q < M && a[0][q] >= 0.0) q++;

    //
    p = 1;
    while (p < N && a[p][q] <= 0.0) p++;

    for (i = p + 1; i < N; i++)
      if (a[i][q] > 0.0)
        if (a[i][M - 1] / a[i][q] < a[p][M - 1] / a[p][q])
          p = i;

    if (q < M  && p < N )
      pivot(N, M, a, p, q);

  } while (q < M  && p < N );

  return q == M;
}

int main(int argc, char *arvg[]) 
{
  int i, j;
#define N 6
#define M 9
double **a;

  a = malloc(N * sizeof(double *));
  for (i = 0; i < N; i++) 
  {
    a[i] = malloc(M * sizeof(double));
    for (j = 0; j < M; j++)
      a[i][j] = 0.0;
  }

  a[0][0] = -1.0;
  a[0][1] = -1.0;
  a[0][2] = -1.0; 
  a[1][0] = -1.0;
  a[1][1] = 1.0;
  a[1][3] = 1.0;
  a[1][8] = 5.0;
  a[2][0] = 1.0;
  a[2][1] = 4.0;
  a[2][4] = 1.0;
  a[2][8] = 45.0;
  a[3][0] = 2.0;
  a[3][1] = 1.0;
  a[3][5] = 1.0;
  a[3][8] = 27.0;
  a[4][0] = 3.0;
  a[4][1] = -4.0;
  a[4][6] = 1.0;
  a[4][8] = 24.0;
  a[5][2] = 1.0;
  a[5][7] = 1.0;
  a[5][8] = 4.0;

  if (simplex(N, M, a)) 
  {
    printf("opt.: %f, %f %f %f\n", a[0][M-1], a[N-3][M-1], a[N-2][M-1], a[N-1][M-1]);
  }

  exit(0);
}