Problem
There are n terminals on a circuit board. Each terminal is either positive or negative. A wire will be attached to each terminal. It must be the case that for every pair of terminals of opposite polarity the two wires must be long enough so that they can be made to touch. So given the locations of the terminals (and their polarities), the problem is to compute the shortest total length of wires needed to satisfy the stated requirement. (i) Formulate this problem as a linear program (LP) and clearly define your decision variables. Write your LP in canonical form. (ii) Write the dual of the LP from part (i). You do not need to use the canonical form.