
ZOJ Problem Set  2590
In this problem you have to find the dual to the linear programming problem given in general form. Linear programming problem is set in the following way. For i = 1, 2, ... , n let xi be a variable. Some x_{i} may be required to be nonnegative or nonpositive. The goal is to minimize or maximize the sum c_{1}x_{1} + c_{2}x_{2} + ... + c_{n}x_{n} under a set of restrictions. Let A = (a_{ij}) be an m*n matrix. Denote the product a_{i,1}x_{1} + a_{i,2}x_{2} + ... + a_{i,n}x_{n} as A_{i}x. Each restriction has the form A_{i}x >= b_{i}, A_{i}x <= b_{i} or A_{i}x = b_{i}. Dual to this linear program is defined as the linear program with variables yi for i = 1, 2, ... ,m (the number of dual variables is equal to the number of restrictions in the primal problem). If the primal problem was a minimization problem, the dual is a maximization one and vice versa. The objective function of the dual problem is b_{1}y_{1} + b_{2}y_{2} + ... + b_{m}y_{m}. Each dual variable is associated with the restriction of the primal problem. If the primal problem was a maximization one, variables, associated with A_{i}x <= b_{i} restrictions must be nonnegative and variables associated with A_{i}x >= b_{i} restrictions must be nonpositive. In case the primal problem was a minimization one, the variables, associated with A_{i}x >= b_{i} restrictions must be nonnegative and variables associated with A_{i}x <= b_{i} restrictions must be nonpositive. Variables associated with A_{i}x = b_{i} restriction may be arbitary in either case. The restrictions in the dual problem use matrix A^{T} (A transposed) instead of A. Restricitions have one of the form A_{i}^{T} y_{i} <= c_{i}, A_{i}^{T} y_{i} >= c_{i}, or A_{i}^{T} y_{i} = c_{i}. You must determine the type of the restriction using the idea that the dual to the dual problem is the primal problem again. Given primal linear programming problem, output its dual. Input The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 40) which is the number of test cases. T test cases follow, each preceded by a single blank line. The first line of each test case contains n and m (1 <= n,m <= 100). The second line of each test contains the objective function of the given problem. The first word of the line is either "min" or "max", the objective function follows. All c_{i} are integer, x_{i} is given as "x_{i}", multiplication sign is omitted, minus sign may replace the plus sign when needed to state that ci is negative. Terms with c_{i} = 0 are omitted. If all ci are zero, "0" is given as the objective function. Terms with c_{i} = 1 or c_{i} = 1 are given without '1' character. The third line contains the word "with". Next n lines contain nonnegativity and nonpositivity conditions for the variables. If the variable may be arbitary, the word "arbitary" is used. The next line contains the word "under". Following m lines contain restrictions, all a_{ij} and b_{i} are integers, multiplication sign is omitted, terms with a_{ij} = 0 are omitted, if for some i all a_{ij} are zero, "0" is used as the left side of the equation. Terms with a_{ij} = 1 or a_{ij} = 1 are given without '1' character. Input file contains no extra spaces. Output For each test case, output the dual to the problem given in the input file, in the same format. Remember, that the first line must contain the number of variables and restrictions in the dual problem, so that the output file produced is the valid input file for the problem with the exception that it has 'y' instead of 'x'. You must list variables in all statements in increasing order of their numbers and must omit terms equal to zero. You must omit +1 or 1 coefficient where needed, keeping only the sign. You must not print '+' if the following term has the negative coefficient. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case. Sample Input 2 3 4 min 2x1x3 with x1>=0 x2 arbitary x3<=0 under x1+x2+x3>=0 3x2=3 x1x2+100x3<=4 0=0 1 1 min x1 with x1>=0 under x1>=1 Sample Output 4 3 max 3y24y3 with y1>=0 y2 arbitary y3<=0 y4 arbitary under y1y3<=2 y1+3y2y3=0 y1+100y3>=1 1 1 max y1 with y1>=0 under y1<=1 Author: Andrew Stankevich Source: Andrew Stankevich's Contest #5 