CSC 445/545: Fall 2014, Assignment #3

Due: Friday Nov. 14, beginning of class
Late submissions accepted with 10% penalty until Tues. Nov. 18 at 12:30pm.

Consider Problem 1.6, p. 10 with the initial problem as stated in the model solutions on page 465.
I solved this problem with my program and the final dictionary was:
```
X7 =  440 + 0 X1 + 0 X4 - 1 X8 - 1 X9 + 1 X10+ 1 X11
X6 =  210 + 1 X1 - 1 X4 - 1 X8 - 1 X9 + 1 X10+ 0 X11
X5 =  20  - 1 X1 + 1 X4 + 1 X8 + 0 X9 - 1 X10+ 0 X11
X3 =  400 + 0 X1 - 1 X4 - 1 X8 + 0 X9 + 0 X10+ 0 X11
X2 =  40  - 1 X1 + 0 X4 + 1 X8 + 1 X9 - 1 X10- 1 X11
-------------------------------------------------
z =  4550 - 1 X1 - 1 X4 - 1 X8 - 2 X9 - 7 X10- 3 X11
```
(a) [2] Explain the meaning of each variable Xj, j=1, 2, 3, ..., 6.
(b) [2] What are the units for the primal problem.
(c) [6] State the dual problem and determine the units for Yi, i=1, 2, 3, 4, 5. Then give an economic interpretation for the solution for the dual.
(d) [4] What is the new values of the objective function if constraints 1-5 change by t1, t2, t3, t4, t5 respectively? (assume the ti's are small)
(e) [4] What is the new optimal solution if constraints 1-5 change by t1, t2, t3, t4, t5 respectively? (assume the ti's are small)
(f) [2] Consider t1, t2, t3, t4, and t5 one at a time. What limit is there to the increase of each before a new basis would result?

Consider the problem represented by this initial dictionary:

X5 =   3  +   1 X1 +   3 X2 +   5 X3 +   1 X4
X6 =  -4  +   1 X1 +   2 X2 +   4 X3 -   4 X4
X7 =   2  +   1 X1 +   6 X2 +   2 X3 +   7 X4
X8 = -12  +   1 X1 -   3 X2 +   3 X3 +   3 X4
-----------------------------------------------
z  =   0  -  10 X1 +   0 X2 -  24 X3 +   0 X4

The second last dictionary is:

X5 =  23.00-   0.67 X1 +   8.00 X2 -   4.00 X4 +   1.67 X8
X6 =  12.00-   0.33 X1 +   6.00 X2 -   8.00 X4 +   1.33 X8
X7 =  10.00+   0.33 X1 +   8.00 X2 +   5.00 X4 +   0.67 X8
X3 =   4.00-   0.33 X1 +   1.00 X2 -   1.00 X4 +   0.33 X8
-----------------------------------------------
z  = -96.00-   2.00 X1 -  24.00 X2 +  24.00 X4 -   8.00 X8

The last dictionary is:

X5 =  17.00-   0.50 X1 +   5.00 X2 +   0.50 X6 +   1.00 X8
X4 =   1.50-   0.04 X1 +   0.75 X2 -   0.12 X6 +   0.17 X8
X7 =  17.50+   0.12 X1 +  11.75 X2 -   0.62 X6 +   1.50 X8
X3 =   2.50-   0.29 X1 +   0.25 X2 +   0.12 X6 +   0.17 X8
-----------------------------------------------
z  = -60.00-   3.00 X1 -   6.00 X2 -   3.00 X6 -   4.00 X8

(a) [3] What is the dual of this problem?
(b) [3] Explain how to read the optimal dual solution from the final dictionary for the primal.
(c) [3] Let u denote the basic feasible solution corresponding to the second last dictionary for the primal problem. Show how to verify that u is not optimal given that you know the optimal solution for the dual.
(d) [4] Show the calculations required to verify that u is not optimal by using only the complementary slackness conditions (the procedure is described on pp. 63-65, text).
(e) [3] Let w denote the basic feasible solution corresponding to the last dictionary for the primal problem. Show how to use the dual solution to verify that w is the optimal solution for the primal.
(f) [4] Show the calculations required to verify that w is optimal by using only the complementary slackness conditions (the procedure is described on pp. 63-65, text).

Consider the following 4 data points:

x y

1 11

4 7

7 3.7

9 1

(a) [3] What problem would you solve in order to find a linear approximation for these data points that minimizes the L₁-norm?
(b) [3] Put this problem into a standard form that your program could solve.
(c) [4] Solve this problem using your computer program to find the values for a₀ and a₁ where the approximating curve is y= a₀ + a₁ x.
For this question, use the same 4 data points as the previous question.
(a) [3] What problem would you solve in order to find a linear approximation for these data points that minimizes the L_infinity-norm?
(b) [3] Put this problem into a standard form that your program could solve.
(c) [4] Solve this problem using your computer program to find the values for a₀ and a₁ where the approximating curve is y= a₀ + a₁ x.
[5] Plot the 4 data points and the two curves from the previous two questions (indicating which one is the L₁-fit and which one is the L_infinity-fit). Which curve appears to give a better approximation of the data?
[10] For each of the 4 benzenoids, indicate a perfect matching that gives the Fries number. Color in the benzenoid hexagons that count towards the Fries number. There is a worksheet for this question: Click here to get it
[10] For each of the 4 benzenoids, indicate a perfect matching that gives the Clar number. Color in the benzenoid hexagons that count towards the Clar number. There is a worksheet for this question: Click here to get it.

x	y
1	11
4	7
7	3.7
9	1

Consider this benzenoid:

The adjacency matrix (with the degree of each vertex indicated):

 0 (2):  0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 1 (2):  1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 2 (2):  0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 3 (2):  0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
 4 (3):  0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1
 5 (2):  0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
 6 (2):  0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
 7 (3):  0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0
 8 (3):  0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0
 9 (2):  0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
10 (2):  0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
11 (2):  0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
12 (2):  0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
13 (3):  0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0
14 (2):  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
15 (2):  0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
16 (3):  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1
17 (3):  1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0

(a) [3] How many perfect matchings does this graph have? Justify you answer by showing all the perfect matchings of this benzenoid on the attached Perfect Matchings worksheet. Print as many copies as you need to show all the perfect matchings.
(b) [2] For each edge, label the edge on the attached Hadamard-Fries Algorithm worksheet with the number of perfect matchings of the graph containing the edge.
(c) [3] Describe a contrived linear programming problem that could be solved to find the inverse of the adjacency matrix for this graph. There should be one variable per vertex.
(d) [2] Solve your LP from (c) and explain how you determine A^-1 from the final dictionary.
(e) [3] This matrix B is equal to the number of perfect matchings times the inverse of the adjacency matrix:

 0:    0  5  0 -5  0  2   0 -2  0  1  0 -1   0  1  0 -1  0  3  
 1:    5  0  3  0 -3  0   3  0 -1  0  1  0  -1  0  2  0 -2  0  
 2:    0  3  0  5  0 -2   0  2  0 -1  0  1   0 -1  0  1  0 -3  
 3:   -5  0  5  0  3  0  -3  0  1  0 -1  0   1  0 -2  0  2  0  
 4:    0 -3  0  3  0  2   0 -2  0  1  0 -1   0  1  0 -1  0  3  
 5:    2  0 -2  0  2  0   6  0 -2  0  2  0  -2  0  4  0 -4  0  

 6:    0  3  0 -3  0  6   0  2  0 -1  0  1   0 -1  0  1  0 -3  
 7:   -2  0  2  0 -2  0   2  0  2  0 -2  0   2  0 -4  0  4  0  
 8:    0 -1  0  1  0 -2   0  2  0  3  0 -3   0  3  0 -3  0  1  
 9:    1  0 -1  0  1  0  -1  0  3  0  5  0  -5  0  2  0 -2  0  
10:    0  1  0 -1  0  2   0 -2  0  5  0  3   0 -3  0  3  0 -1  
11:   -1  0  1  0 -1  0   1  0 -3  0  3  0   5  0 -2  0  2  0  

12:    0 -1  0  1  0 -2   0  2  0 -5  0  5   0  3  0 -3  0  1  
13:    1  0 -1  0  1  0  -1  0  3  0 -3  0   3  0  2  0 -2  0 
14:    0  2  0 -2  0  4   0 -4  0  2  0 -2   0  2  0  6  0 -2  
15:   -1  0  1  0 -1  0   1  0 -3  0  3  0  -3  0  6  0  2  0  
16:    0 -2  0  2  0 -4   0  4  0 -2  0  2   0 -2  0  2  0  2  
17:    3  0 -3  0  3  0  -3  0  1  0 -1  0   1  0 -2  0  2  0

Use B to compute the matrix P₁ = A * A^-1 (typo correction, this originally said P₂ instead of P₁) for the CKC algorithm (that I have also denoted as the Hadamard-Fries algorithm).
(f) [2] Label the edges of the second picture of the benzenoid on the worksheet for (b) with the corresponding entry in P₁ (typo correction, this originally said P₂ instead of P₁). How do these values correlate to your answer for part (b)?