Consider the following linear programming problem: maximize X$12+$ X$22+$ X$23$

subject to X$11+$ X$12+$ X$13=20$

X$21+$ X$22+$ X$23=20$

$-$X$11-$X$21-=20$

$-$ X$12-$ X$22-=10$

$-$ X$13-$ X$23-=10$

X$11+$ X$23<=15$

Xij $>=0,$ for all i$,$ j$..$We wish to solve this problem using Dantzig$-$Wolfe decomposition, where the

constraint X$11+$ X$23<=15$ is the only "coupling" constraint and the remaining

constraints define a single subproblem. $($a$)$ Consider the following two feasible solutions for the subproblem: Xl $($X$11,$ X$12,$ X$13,$ X$21,$ X$22,$ X$23)=(20,0,0,0,10,10),$ and

X $2($X$11,$X$12,$XI$3,$X$21,$X$22,$X$23)=(0,10,10,20,0,0).$ Construct a restricted master problem in which x is constrained to be

a convex combination of X$1$and x $2.$ Find the optimal solution and the

optimal simplex multipliers for the restricted master problem.

$($b$)$ Using the simplex multipliers calculated in part $($a$),$ formulate the subproblem and solve it by inspection.

$($c$)$ What is the reduced cost of the variable Ai associated with the optimal

extreme point Xi obtained from the subproblem solved in part $($b$)?$

$($d$)$ Compute an upper bound on the optimal cost