C : 线性规划例题求解

Submit Page   TestData   Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 93     Solved: 49    

Description

求解下述线性规划模型的最优值min �1�1+�2�2+�3�3�.�. �11�1+�12�2+�13�3≤�1>0�21�1+�22�2+�23�3≤�2>0�31�1+�32�2+�33�3≤�3>0�1,�2,�3≥0

Input

依次输入�1�2�3�11�12�13�1�21�22�23�2�31�32�33�3

Output

目标函数最优值，保留小数点后两位有效数字。若无最优解，输出“No solution”。

Sample

#0

Input

Copy

1 -2 0
1 -1 0 1
-2 1 0 4
1 1 1 10

Output

Copy

-14.00

Hint

#include <iostream>
#include <cmath>
#include "stdio.h"
using namespace std;
#define M 10000
double kernel[110][310];
int m = 0, n = 0, t = 0;
void input()
{
	// cin >> n;
	// cin >> m;
	m = 3;
	n = 3;
	int i, j;
	// 初始化核心向量
	for (i = 0; i <= m + 1; i++)
		for (j = 0; j <= n + m + m; j++)
			kernel[i][j] = 0;
	for (i = 1; i <= n; i++)
		cin >> kernel[0][i];
	for (i = 1; i <= m; i++)
	{
		// cout<<"    不等式"<<i<<"  ";
		for (j = 1; j <= n + 2; j++)
		{
			if (j == n + 1)
			{
				kernel[i][j] = 1;
			}
			else
			{
				cin >> kernel[i][j];
			}
		}
	}

	for (i = 1; i <= m; i++)
	{
		kernel[i][0] = kernel[i][n + 2];
		kernel[i][n + 2] = 0;
	}

	t = 1;
	if (t == -1)
		for (i = 1; i <= n; i++)
			kernel[0][i] = (-1) * kernel[0][i];
	for (i = 1; i <= m; i++)
	{
		kernel[i][n + i] = kernel[i][n + 1];
		if (i != 1)
			kernel[i][n + 1] = 0;
	}
}

// 算法函数
void comput()
{
	int i, j, flag, temp1, temp2, h, k = 0, temp3[100];
	double a, b[110], temp, temp4[110], temp5[110], f = 0, aa, d, c;
	for (i = 1; i <= m; i++)
		temp3[i] = 0.0000;
	for (i = 0; i < 11; i++)
	{
		temp4[i] = 0.000;
		temp5[i] = 0.0000;
	}
	for (i = 1; i <= m; i++)
	{
		if (kernel[i][n + i] == -1)
		{
			kernel[i][n + m + i] = 1;
			kernel[0][n + m + i] = M;
			temp3[i] = n + m + i;
		}
		else
			temp3[i] = n + i;
	}
	for (i = 1; i <= m; i++)
		temp4[i] = kernel[0][temp3[i]];

	do
	{
		for (i = 1; i <= n + m + m; i++)
		{
			a = 0;
			for (j = 1; j <= m; j++)
				a += kernel[j][i] * temp4[j];
			kernel[m + 1][i] = kernel[0][i] - a;
		}
		for (i = 1; i <= n + m + m; i++)
		{
			if (kernel[m + 1][i] >= 0)
				flag = 1;
			else
			{
				flag = -1;
				break;
			}
		}
		if (flag == 1)
		{
			for (i = 1; i <= m; i++)
			{
				if (temp3[i] <= n + m)
					temp1 = 1;
				else
				{
					temp1 = -1;
					break;
				}
			}
			if (temp1 == 1)
			{
				// cout << " 此线性规划的最优解存在!" << endl << endl << "  最优解为：" << endl << endl << "     ";
				for (i = 1; i <= m; i++)
					temp5[temp3[i]] = kernel[i][0];
				for (i = 1; i <= n; i++)
					f += t * kernel[0][i] * temp5[i];

				for (i = 1; i <= n; i++)
				{
					// cout << "x" << i << " = " << temp5[i];
					// if (i != n)
					// cout << "， ";
				}
				// cout << " ;" << endl << endl << "     最优目标函数值f= " << f << endl << endl;
				printf("%.2f\n", f);
				return;
			}
			else
			{
				// cout << " 此线性规划无解" << endl << endl;
				cout<<"No solution"<<endl;
				return;
			}
		}
		if (flag == -1)
		{
			temp = 100000;
			for (i = 1; i <= n + m + m; i++)
				if (kernel[m + 1][i] < temp)
				{
					temp = kernel[m + 1][i];
					h = i;
				}

			for (i = 1; i <= m; i++)
			{
				if (kernel[i][h] <= 0)
					temp2 = 1;
				else
				{
					temp2 = -1;
					break;
				}
			}
		}
		if (temp2 == 1)
		{
				cout<<"No solution"<<endl;
			// cout << "此线性规划无约束";
			return;
		}
		if (temp2 == -1)
		{
			c = 100000;
			for (i = 1; i <= m; i++)
			{
				if (kernel[i][h] != 0)
					b[i] = kernel[i][0] / kernel[i][h];
				if (kernel[i][h] == 0)
					b[i] = 100000;
				if (b[i] < 0)
					b[i] = 100000;
				if (b[i] < c)
				{
					c = b[i];
					k = i;
				}
			}
			temp3[k] = h;
			temp4[k] = kernel[0][h];
			d = kernel[k][h];
			for (i = 0; i <= n + m + m; i++)
				kernel[k][i] = kernel[k][i] / d;
			for (i = 1; i <= m; i++)
			{
				if (i == k)
					continue;
				aa = kernel[i][h];
				for (j = 0; j <= n + m + m; j++)
					kernel[i][j] = kernel[i][j] - aa * kernel[k][j];
			}
		}

	} while (1);
	return;
}

int main()
{
	input();
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < m + 2; j++)
		{
			// cout<<kernel[i][j]<<" ";
		}
		// cout<<endl;
	}
	comput();
	// int a = 0;
	// scanf("%d", &a);
	// cout<<f<<endl;
	return 0;
}