simplex是线性规划中十分经典的算法，以下为实现代码
头文件
#ifndef SIMPLEX_H_INCLUDED#define SIMPLEX_H_INCLUDED#include <stdio.h>#include <stdlib.h>#define MAX_VALUE 1.0e308int m ,n;typedef double Elemtype;typedef struct calcu_node{Elemtype **A;Elemtype *B;Elemtype *C;int *B1;/*基向量对应的位置*/Elemtype z;} calcu_node,*pcalcu_node;typedef struct result{Elemtype *x;Elemtype z;} result,*presult;pcalcu_node init_simplex(pcalcu_node calcu_node);presult simplex(Elemtype **input_A,Elemtype *input_B,Elemtype *input_C);Elemtype *calculate_x(pcalcu_node calcu_node);void pivot(pcalcu_node calcu_node,int l,int e);#endif // SIMPLEX_H_INCLUDED具体实现
#include "simplex.h"Elemtype *calculate_x(pcalcu_node calcu_node){Elemtype *x = (Elemtype*)malloc(n * sizeof(Elemtype));int j;for(j = 0; j < n; j++){if(calcu_node->B1[j] == 0)x[j] = 0;else{int i = 0;for(i; i < m; i++){if(calcu_node->A[i][j] == 1)x[j] = calcu_node->B[i];}}}return x;}presult simplex(Elemtype **input_A,Elemtype *input_B,Elemtype *input_C){pcalcu_node calcu_node = (pcalcu_node)malloc(sizeof(calcu_node));calcu_node->A = (Elemtype**)malloc(m * (sizeof(Elemtype)));calcu_node->B = (Elemtype*)malloc(m * sizeof(Elemtype));int i = 0,j = 0;for(; i < m; i++){calcu_node->B[i] = input_B[i];calcu_node->A[i] = (Elemtype*)malloc((n + 1) * sizeof(Elemtype));for(j = 0; j < n; j++)calcu_node->A[i][j] = input_A[i][j];}calcu_node->C = (Elemtype*)malloc((n+1) * sizeof(Elemtype));calcu_node->B1 = (int*)malloc((n+1) * sizeof(int));for(i = 0; i < n; i++){calcu_node->C[i] = input_C[i];}calcu_node->z = 0;init_simplex(calcu_node);presult result = (presult)malloc(sizeof(result));Elemtype min_value = 0,cur_value;int min_record = -1;while(1){min_value = MAX_VALUE;for(i = 0; i < n; i++){if(calcu_node->C[i] < 0)break;}if(i >= n){result->x = calculate_x(calcu_node);result->z = calcu_node->z;return result;}else{for(j = 0; j < m; j++){if(calcu_node->A[j][i] > 0){cur_value = calcu_node->B[j] / calcu_node->A[j][i];if(min_value > cur_value){min_record = j;min_value = cur_value;}}}if(min_record == -1){printf("unbounded \n");exit(-1);}else{pivot(calcu_node,min_record,i);}}}}void print_node(pcalcu_node calcu_node){/*打印调试*/if(calcu_node == NULL){printf("error node is NULL\n");exit(-1);}int i = 0;for(; i < n; i++)printf("%.0lf ",calcu_node->C[i]);printf("\n");int j = 0;for(i = 0; i < m; i++){printf("%.0lf ",calcu_node->B[i]);for(j = 0; j < n; j++){printf("%.0lf ",calcu_node->A[i][j]);}printf("\n");}for(i = 0; i < n; i++)printf("%.0lf ",calcu_node->B1[i]);printf("\n");}pcalcu_node init_simplex(pcalcu_node calcu_node){int min_record = 0;int i,j = 0;calcu_node->B1[n – 1] = 1;for(i = 1; i < m; i++ ){calcu_node->B1[n – i – 1] = 1;if(calcu_node->B[i] < calcu_node->B[min_record])min_record = i;}for(i; i < n; i++)calcu_node->B1[n – i – 1] = 0;if(calcu_node->B[min_record] >= 0){return calcu_node;}n++;for(i = 0; i < m; i++) //{calcu_node->A[i][n – 1] = -1;}Elemtype *rec_C = calcu_node->C;calcu_node->C = (Elemtype*)malloc(n * sizeof(Elemtype));for(i = 0; i < n – 1; i++){calcu_node->C[i] = 0;}calcu_node->C[n – 1] = 1;calcu_node->B1[n – 1] = 0;Elemtype min_value = -1;Elemtype cur_value = 0;pivot(calcu_node,min_record,0);min_record = -1;while(1){for(i = 0; i < n; i++){if(calcu_node->C[i] < 0)break;}if(i >= n){break;}else{for(j = 0; j < m; j++){if(calcu_node->A[j][i] > 0){cur_value = calcu_node->B[j] / calcu_node->A[j][i];if(min_value < cur_value)min_record = j;}}if(min_record == -1){printf("error it is unbounded\n");exit(-1);}else{pivot(calcu_node,i,j);}}}if(calcu_node->z == 0){n–;calcu_node->C = rec_C;for(i = 0; i < n; i++){if(calcu_node->B1[i] == 1){Elemtype temp = calcu_node->C[i];int k = 0;for(; k < m; k++)if(calcu_node->A[k][i] == 1)break;calcu_node->z -= temp * calcu_node->B[k];for(j = 0; j < n; j++)calcu_node->C[j] -= temp * calcu_node->A[k][j];}}}else{printf("error no answer\n");exit(-1);}}void pivot(pcalcu_node calcu_node,int l,int e){int j,i = -1;Elemtype temp = 0;temp = calcu_node->A[l][e];calcu_node->B[l] /= temp;for(j = 0; j < n; j++){if(calcu_node->B1[j] == 1 && calcu_node->A[l][j] == 1)i = j;calcu_node->A[l][j] /= temp;}calcu_node->B1[i] = 0;calcu_node->B1[e] = 1;for(i = 0; i < m; i++){if(i == l)continue;calcu_node->B[i] -= calcu_node->B[l] * calcu_node->A[i][e];temp = calcu_node->A[i][e];for(j = 0; j < n; j++){calcu_node->A[i][j] -= temp * calcu_node->A[l][j];}}temp = calcu_node->C[e];calcu_node->z -= temp * calcu_node->B[l];for(j = 0; j < n; j++){calcu_node->C[j] -= temp * calcu_node->A[l][j];}}测试
如果心胸不似海，又怎能有海一样的事业。
