1869: 线性规划

线性规划的问题由如下形式构成：

最小化 x1 + x2 + x3

满足约束 2x1 + 7.5x2 + 3x3 >= 10000

         20x1 + 5x2 + 10x3 >=30000

         x1, x2, x3        >=0

上面问题的解为2250，其中x1=1250，x2=1000，x3=0。

你要做的，就是找出问题的最优解=。=（此线性规划的输入可参考样例No.1）

第一行为两个正整数，第一个为变量数N，第二个为不等式数量M。注意，此处略去默认的非负变量约束（即x1, x2, ..., xn>=0）。

接下来的M行，首先有N个实数，表示不等式左边从第一项到最后一项的系数。然后是式子的符号，共有“<=”“>=”“==”三种符号。最后有1个整数，表示不等式右边的约束。

最后一行，首先为单词“max”或“min”，表示要求的是最大值或最小值。接着是N个实数，表示目标函数从第一项到最后一项的系数。

输出的实数均取三位小数。

如果问题无可行解，输出一行“Infeasible.”，如果问题的解无界，输出“Unbounded”。否则按照下面的格式输出：

第一行以“Ans=”开头，后接最优解的值。

接下来的N行，以“x（数字）=”开头，后接每个变量的解。

Data No.1

3 2
2 7.5 3 >= 10000
20 5 10 >= 30000
min 1 1 1
----------------------------------------
Data No.2

2 1
1 1 == 10
max 1 -1

Data No.1

Ans=2250.000
x1=1250.000
x2=1000.000
x3=0.000
----------------------------------------
Data No.2

Ans=10.000
x1=10.000
x2=0.000