0206. Linear Programming Dual

Input file name:	dual.in
Output file name:	dual.out
Time limit:	2 s
Memory limit:	64 megabytes

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 x_i be a variable. Some x_i may be required to be non-negative or non-positive. The goal is to minimize or maximize the sum c₁x₁+c₂x₂+…+c_nx_n under a set of restrictions.

Let A = (a_ij) be an m *n matrix. Denote the product a_i,1x₁+a_i,2x₂+…+a_i,nx_n as A_ix. Each restriction has the form A_ix ≥ b_i, A_ix ≤ b_i or A_ix = b_i.

Dual to this linear program is defined as the linear program with variables y_i 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₁y₁+b₂y₂+…+b_my_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_ix ≤ b_i restrictions must be non-negative and variables associated with A_ix ≥ b_i restrictions must be non-positive. In case the primal problem was a minimization one, the variables, associated with A_ix ≥ b_i restrictions must be non-negative and variables associated with A_ix ≤ b_i restrictions must be non-positive. Variables associated with A_ix = 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^T_iy_i ≤ c_i, A^T_iy_i ≥ c_i, or A^T_iy_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 file

The first line of the input file contains n and m (1 ≤ n, m ≤ 100).

The second line of the input file 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 "\texttt{xi}", multiplication sign is omitted, minus sign may replace the plus sign when needed to state that c_i is negative. Terms with c_i = 0 are omitted. If all c_i are zero, "0" is given as the objective function. Terms with c_i = ±1 are given without `1' character.

The third line contains the word "with".

Next n lines contain non-negativity and non-positivity 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 integer, 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 are given without `1' character.

Input file contains no extra spaces.

Output file

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 coefficient where needed, keeping only the sign. You must not print `+' if the following term has the negative coefficient.

Examples:

dual.in	dual.out
3 4 min 2x1-x3 with x1>=0 x2 arbitary x3<=0 under x1+x2+x3>=0 3x2=3 -x1-x2+100x3<=-4 0=0	4 3 max 3y2-4y3 with y1>=0 y2 arbitary y3<=0 y4 arbitary under y1-y3<=2 y1+3y2-y3=0 y1+100y3>=-1

Source: Petrozavodsk Winter 2004. Andrew Stankevich Contest 4, Friday, January 30
Author: Andrew Stankevich

Discuss       Submit a solution



Printable version