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;}elsetemp3[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;
}