上 機 實 驗 報 告

班級：自動化班

專業/方向：自動化

姓名：

實 驗 成 績

(10分制)

學號：

上機實驗名稱：使用C語言實現單純形法求解線性規劃問題

上機時間：2015年5月20日

上機地點：信自234

一、實驗目的和要求

1、目的：

掌握單純形算法的計算步驟，并能熟練使用該方法求解線性規劃問題。

了解算法?程序實現的過程和方法。

2、要求：

使用熟悉的編程語言編制單純形算法的程序。

獨立編程，完成實驗，撰寫實驗報告并總結。

二、實驗內容和結果

1、單純形算法的步驟及程序流程圖。

(1)、算法步驟

(1)將線性規劃化為標準形。

(2)用最快的方法確定一個初始基本可行解X(0)。當s·t均為“≤”形式時，以松馳變量做初始基本變量最快。

(3)求X(0)中非基本變量xj的檢驗數σj。若，則停止運算，X(0)=X*(表示最優解)，否則轉下一步。

(4)①由確定xk進基；

②由確定xl出基，其中alk稱為主元素；

③利用初等變換將alk化為1，并利用alk將同列中其它元素化為0，得新解X(1)。

(5)返回(3)，直至求得最優解為止。

(2)、程序圖

找出初始基可行解列出初始單純形表

找出初始基可行解列出初始單純形表

計算校驗數

所有δj<=0?

對于某個δj>0，是否存在Pj<=0

確定為入基變量

確定出基變量

計算新的單純形表

已得最優解，結束

無最優解，結束

2、單純形算法程序的規格說明

各段代碼功能描述：

(1)、定義程序中使用的變量

#include

#include

#define m 3 /*定義約束條件方程組的個數*/

#define n 5 /*定義未知量的個數*/

float M=1000000.0;

float A[m][n]; /*用于記錄方程組的數目和系數;*/

float C[n]; /*用于存儲目標函數中各個變量的系數*/

float b[m]; /*用于存儲常約束條件中的常數*/

float CB[m]; /*用于存儲基變量的系數*/

float seta[m]; /*存放出基與入基的變化情況*/

float delta[n]; /*存儲檢驗數矩陣*/

float x[n]; /*存儲決策變量*/

int num[m]; /*用于存放出基與進基變量的情況*/

float ZB=0; /*記錄目標函數值*/

(2)、定義程序中使用的函數

void input();

void print();

int danchunxing1();

int danchunxing2(int a);

void danchunxing3(int a,int b);

(3)、確定入基變量，對于所有校驗數均小于等于0，則當前解為最優解。

int danchunxing1()

{

int i,k=0;

int flag=0;

float max=0;

for(i=0;i

if(delta[i]<=0)

flag=1;

else {flag=0;break;}

if(flag==1)

return -1;

for(i=0;i

if(max

{ max =delta[i];k=i;}

}

return k;

}

(4)、確定出基變量，如果某個大于0的校驗數，對應的列向量中所有元素小于等于0，則線性規劃問題無解。

int danchunxing2(int a)

{

int i,k,j;

int flag=0;

float min;

k=a;

for(i=0;i

if(A[i][k]<=0)

flag=1;

else {flag=0;break;}

if(flag==1)

{printf("\n該線性規劃無最優解!\n"); return -1;}

for(i=0;i

{

if(A[i][k]>0)

seta[i]=b[i]/A[i][k];

else seta[i]=M;

}

min=M;

for(i=0;i

{

if(min>=seta[i])

{min=seta[i];j=i;}

}

num[j]=k+1;

CB[j]=C[k];

return j;

}

(5)、迭代運算，計算新的單純形表。

void danchunxing3(int p,int q)

{

int i,j,c,l;

float temp1,temp2,temp3;

c=p;/*行號*/

l=q;/*列號*/

temp1=A[c][l];

b[c]=b[c]/te

總結

以上是生活随笔為你收集整理的c语言编程线性规划,使用C语言实现单纯形法求解线性规划问题.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。