dcxf.cpp

单纯型法

/*p248习题2
	单纯形法*/


#include "iostream.h"
#define m 4	
#define  n 6

void main()
{
	int i,j,k;
//	float a[m+1][n]={{1,1,1,0,0,0},{1,2,0,1,0,0},{1,0,0,0,1,0},{1,0,0,0,0,1},{-2,-3,0,0,0,0}};
	float b[m+1]={6,8,5,3,0};
	float a[m+1][n+1]={{1,1,1,0,0,0,6},{1,2,0,1,0,0,8},{1,0,0,0,1,0,5},{0,1,0,0,0,1,3},{-2,-3,0,0,0,0,0}};
	float x[n]={0};			//结果置于x[n]中
	int num[m]={2,3,4,5};	//记录基底向量
//	float a[m+1][n+1];
//	a=a;
	/*
	min1=-2x1-3x2
	x1+x2<=6;
	x1+2x2<=8
	x1<=5
	x2<=3
	x1>=0
	x2>=0

    x1+x2+ x3       = 6
	x1+2*x2+  x4    = 8
	x1+         x5  = 5
	   x2+        x6= 3

	1 1 | 1 0 0 0 | 6			初始形式
	1 2 | 0 1 0 0 | 8
	1 0 | 0 0 1 0 | 5
	1 0 | 0 0 0 1 | 3
-----------------------
	-2 -3|0 0 0 0 | 0
	*/
	//确定k,l------------------------------
l1:	float d=1000;
	int l=-1;
	for (j=0;j<n;j++)
	{
		if(a[m][j]<d)
		{
			d=a[m][j];
			l=j;
		}
	}
	if(a[m][l]<0)
	{
		d=1000;
		k=-1;
		for(i=0;i<m;i++)
		{
			if(a[i][l]>0)
			{
				if(a[i][n]/a[i][l]<d)
				{
					d=a[i][n]/a[i][l];
					k=i;
				}
			}
		}

		num[k]=l;
		if(k==-1)
		{
		cout<<"该线形规划有无界解"<<endl;	//无界
		goto l3;	//结束
		}
		else		//消元,用高斯消去法
		{
			float s;
			int p,k1;
			
				if(a[k][l]<0)
				{
					for (k1=0;k1<=n;k1++)
						a[k][k1]=-a[k][k1];
				}

				for (k1=0;(k1<=n)&&(k1!=l);k1++)
					a[k][k1]=a[k][k1]/a[k][l];

					a[k][l]=1;

				for (p=0;p<=m;p++)
				{
				
					if(p==k) continue;
					s=-a[p][l];
					for (k1=0;k1<n+1;k1++)
						a[p][k1]=a[p][k1]+a[k][k1]*s;
				}
			goto l1;
		}
	}
	else
	{
		for (i=0;i<m;i++)
			x[num[i]]=a[i][n];
		for (i=0;i<n;i++)
			cout<<"x"<<i+1<<"="<<x[i]<<endl;//打印结果//结束
	
	}

l3:;
}

	
/*-------------------------------------------------------

x1=4
x2=2
x3=0
x4=0
x5=1
x6=1

---------------------------------------------------------*/