opt_13.cpp

我这个程序用C++实现了最优化方法里面的单纯性算法

/*****************************************************************************
* Copyright (C) by tangxin. All rights reserved.                             *
* FileName: danchunxing.cpp                                                  *
* Author:  唐鑫    Date:26/04/08  Number: B05060128                          *
* Description: 单纯形算法                                                    *
* Function List:    // 主要函数及其功能                                      *
* 1.void input(type A[][N],type C[N],type CB[N],int B[N],int &m,int &n)      *
*    用于输入需要运算的数据并把它们存放在应该存放的地方为下面的运算作准备    *
* 2.void danchunxing(type A[][N],type C[N],type CB[N],int B[N],int m,int n)  *
*   实现单纯形算法                                                           *
* 3.void output_A(type A[][N],int m,int n)                                   *
*   用于在每一步迭代后输出结果，实现数据输出                                 *
******************************************************************************/

#include<iostream>
#include<exception>
int const N(100);/*用于控制数组开辟的内存空间*/
int const MAX(1000);/*这里象征一个足够大的值，为后面选出最小的thita服务*/
typedef double type;
void input(type A[][N],type C[N],type CB[N],int B[N],int &m,int &n);
void danchunxing(type A[][N],type C[N],type CB[N],int B[N],int m,int n);
void output_A(type A[][N],int m,int n);
int main(){
	try{
		type A[N][N]={};
		type C[N]={},CB[N]={};
		int B[N]={};
		int m(0),n(0);
		input(A,C,CB,B,m,n);
		danchunxing(A,C,CB,B,m,n);
	}
	catch(...){
		std::cerr<<"***An exception was thrown.***\n";
	}
}
void output_A(type A[][N],int m,int n){
	std::cout<<"Matrix A is: \n";
	for(int i(0);i<m;++i){
		for(int j(0);j<=n;++j){
			std::cout<<A[i][j]<<" ";
		}
		std::cout<<'\n';
	}
}
void input(type A[][N],type C[N],type CB[N],int B[N],int &m,int &n){
	std::cout<<"Type in the Row & Col of the broad sense Matrix A along with B: \n";
	std::cin>>m>>n;
	for(int i(0);i<m;++i){
		for(int j(0);j<n;++j){
			std::cout<<"Now please type in the element of A["<<i<<"]["<<j<<"]: ";
			std::cin>>A[i][j];
			if(! std::cin)throw std::exception();
		}
	}
	for(int p(0);p<m;++p){
		std::cout<<"Please type in the element of b["<<p<<"]: ";
		std::cin>>A[p][n];
		if(! std::cin)throw std::exception();
	}
	for(int j(0);j<n;++j){
		std::cout<<"Type in the element of Matrix C["<<j<<"]: ";
		std::cin>>C[j];
		if(not std::cin)throw std::exception();
	}
	for(int i(0);i<m;++i){
		std::cout<<"Type in the element of Matrix CB["<<i<<"]: ";
		std::cin>>CB[i];
		if(not std::cin)throw std::exception();
	}
	for(int i(0);i<m;++i){
		std::cout<<"Type in the identifier of CB: \n";/*提示输入基矩阵CB相应的下标，存储在B中*/
		std::cin>>B[i];
		if(not std::cin)throw std::exception();
	}
}
void danchunxing(type A[][N],type C[N],type CB[N],int B[N],int m,int n){
	type thita[N];
	type delta[N];
	type min(MAX);
	do{
		for(int i(0);i<n;++i){
			delta[i]=C[i];
			for(int j(0);j<m;++j){
				delta[i]-=CB[j]*A[j][i];/*求delta的值*/
			}
			std::cout<<"delta: "<<delta[i]<<'\n';
		}
		int detect_j(0);
		for(int j(0);j<n;++j){
			if(delta[j]<min){
				min=delta[j];
				detect_j=j;/*选择最小的一个delta作为入基变量，将其下标赋给detect_j*/
			}
		}
		for(int i(0);i<m;++i){
			if(A[i][detect_j]>0)thita[i]=A[i][n]/A[i][detect_j];/*计算thita的值，如果相应的A矩阵中的值小于等于0，就赋给thita一个足够大的值，方便后面比较*/
			else thita[i]=MAX;
			std::cout<<"thita: "<<thita[i]<<'\n';
		}
		min=MAX;
		int detect_i(0);
		for(int x(0);x<m;++x){
			if(thita[x]<min){
				min=thita[x];
				detect_i=x;/*detect_i的值是对应的最小的thita值的下标*/
			}
		}
		/////////////////////////////////////////////////////////
		/*下面对增广矩阵A实施消元*/
		CB[detect_i]=C[detect_j];
		B[detect_i]=detect_j;
		type t(0);
		for(int i(0);i<m;++i){
			t=A[i][detect_j]/A[detect_i][detect_j];
			for(int j(0);j<n+1;++j){
				if(i!=detect_i){
					A[i][j]-=t*A[detect_i][j];
				}
			}
		}
		for(int j(0);j<=n;++j){
			A[detect_i][j]=A[detect_i][j]/A[detect_i][detect_j];
		}
		std::cout<<" mid A: \n";
		output_A(A,m,n);
		int flag(0);
		for(int j(0);j<n;++j){
			if(delta[j]<0)flag++;
		}
		if(flag==0)break;
	}while(true);
		std::cout<<"The optimum solution is : \n";/*输出最优解*/
		for(int j(0);j<n;++j){
			int flag2(0);
			for(int i(0);i<m;++i){
				if(j==B[i]){std::cout<<A[i][n]<<" ";flag2++;}
			}
			if(flag2==0)std::cout<<"0 ";
		}
}