$[10$ points$]$ We can easily see that $x_1=x_2=x_3=1$ is a feasible point for the following linear

program:

Maximize $u=4x_1+2x_2+3x_3$

Subject to:

$2x_1+3x_2+x_{3}12$

$x_1+4x_2+2x_{3}10$

$3x_1+x_2+x_{3}10$

$x_1,x_2,x_{3}0$

a$)$ Write this LP with slack variables. What are the values of the slack variables at the point

$x_1=x_2=x_3=1?$ What is the value of the objective function at this point?

b$)$ Without solving the problem, identify which variables are basic and which are non$-$basic

at this point.

c$)$ What is the dual of this LP$?$ Write it in minimum form with all surplus variables.

d$)$ Note that each constraint in the LP has a unique variable, and that there is a dual

variable that corresponds to that constraint. These are called complimentary variables.

List all the pairs of complimentary variables in your primal and dual LP$.$

e$)$ Find any feasible point for the dual. What are the values of all the dual variables

$($including slack variables$)$ at this point? What is the value of the dual objective function

at this point?

f$)$ Multiply together the values of all the pairs of complimentary variables $($giving $6$

products$)$ then add them together. What do you get? Compare this to the difference

between the value of the dual objective function you calculated in $($e$)$ and the value of

the primal objective function from $($a$).$ What do you notice?

g$)$ Solve both the primal and the dual LPs $($you can use a solver$).$ What are the values of all

the variables at the optimum? What do you notice about the product of each of the

pairs of complimentary variables? This is a property of primal$/$dual linear programs

called Tucker Duality.