單純形法求解線性規劃問題（C++實現代碼）

單純形法求解線性規劃問題（C++實現代碼）

1 單純形法

（1） 單純形法是解線性規劃問題的一個重要方法。
其原理的基本框架為：
第一步：將LP線性規劃變標准型，確定一個初始可行解（頂點）。
第二步：對初始基可行解最優性判別，若最優，停止；否則轉下一步。
第三步：從初始基可行解向相鄰的基可行解（頂點）轉換，且使目標值有所改善—目標函數值增加，重復第二和第三步直到找到最優解。
（2） 用程序進行運算前，要將目標函數及約束方程變成標准形式。

於非標准形式須作如下變換：
a) 目標函數為極小值min z=CX時，轉換為max z=-CX形式；
b) 在約束方程中有 “≤”時，在加上一個松弛變量；
c) 在約束方程中有 “≥”時，采用減去一個松弛變量，再加上一個人工變量；
d) 在約束方程中有 “=”時，加上一個人工變量；
e) 所有的人工變量，松弛變量的目標函數系數置為0。
（3） 對於標准形式的線性規劃問題。用單純形法計算步驟的框圖。

2 程序測試及結果：

線性規劃問題如下:
max z=2*x1-3*x2+3x3;
x1+ x2 -x3<=7;
x1- x2 +x3<=-7;
x1-2*x2 +2*x3<=4;
x1,x2,x3>=0;

3 C++實現代碼

// Simplex.cpp : 定義控制台應用程序的入口點。
//
//
/********************************* 
----------------------------------- 
單純形法求解線性規劃問題（C++實現代碼）
----------------------------------- 
Author:牧之丶  Date：2014年
Email:[email protected] 
**********************************/  
#include stdafx.h
#include 
#include 
using namespace std;
#define M 10000        //全局變量大M
 float juzhen[11][31];//核心矩陣表 
 int m=0,n=0,t=0;//m:結構向量的個數 //n:約束不等式個數  //t:目標函數類型：－1代表求求最小值，1代表求最大值                          
void input() //輸入接口函數
{   
    int i,j; 
    cout<<－－－－－－－－－－單純形法的參 數 輸 入－－－－－－－－－－－<>m; 
    cout<>n; 
    for (i=0;i<=n+1;i++) 
    for (j=0;j<=m+n+n;j++)  
         juzhen [i][j]=0;      //初始化矩陣，所有元素均為0
   //讀入約束條件 
   cout<=）:<>juzhen [i][j]; 
    } 
   for (i=1;i<=n;i++) 
     {  
       juzhen [i][0]=juzhen [i][m+2]; 
       juzhen [i][m+2]=0; 
     } 
  //讀入目標條件 
        cout<>juzhen [0][i]; 
     cin>>t; 
  //矩陣調整 
  if(t==-1)  
      for(i=1;i<=m;i++)  
          juzhen [0][i]=(-1)*juzhen [0][i]; 
  for(i=1;i<=n;i++) 
  {  
      juzhen [i][m+i]=juzhen [i][m+1]; 
         if(i!=1) 
             juzhen [i][m+1]=0; 
  } 
} 
//算法函數 
void comput() 
{ 
    int i,j,flag,temp1,temp2,h,k=0,temp3[10]; 
    float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c; 
    //初始化 
  for(i=1;i<=n;i++)  
     temp3[i]=0; 
   for(i=0;i<11;i++) 
   {    temp4[i]=0; 
        temp5[i]=0; 
   } 
    for(i=1;i<=n;i++) 
  { 
     if(juzhen [i][m+i]==-1) 
      { 
       juzhen [i][m+n+i]=1; 
       juzhen [0][m+n+i]=M; 
       temp3[i]=m+n+i; 
      } 
     else  
         temp3[i]=m+i; 
  } 
     for(i=1;i<=n;i++) 
           temp4[i]=juzhen [0][temp3[i]]; 
     //循環求解 
do{    
    for(i=1;i<=m+n+n;i++) 
     {   
        a=0; 
        for(j=1;j<=n;j++) 
          a+=juzhen [j][i]*temp4[j]; 
          juzhen [n+1][i]=juzhen [0][i]-a; 
        } 
    for(i=1;i<=m+n+n;i++) 
         { 
            if(juzhen [n+1][i]>=0) flag=1; 
            else  
            {   
                flag=-1; 
                 break; 
             } 
          } 
    if(flag==1) 
    {     for(i=1;i<=n;i++) 
             {  
                  if(temp3[i]<=m+n) temp1=1; 
                           else 
                              {  
                                  temp1=-1; 
                                  break; 
                               } 
              } 
    //輸出結果 
    cout<