In this exercise, we determine the duals to linear programs. Please explain your derivations!

$[50$ marks$]$

$($a$)$ Using the indirect method, find the dual to the following linear program: $[15$ marks$]$

minimise $2$x $+$ y$$subject to x $-$ y $-$ z $=1$

$2$y $+$ z $>=3$

x $>=0,$ y$,$ z unrestricted

$($b$)$ Using the direct method, find the dual to the following linear program: $[15$ marks$]$

maximise x $+2$y $+$ z

subject to x $-$ y $>=2$

y $+$ z $=1$

z $>=3$

x$,$ y$,$ z unrestricted

$($c$)$ Explain, in your own words, what the concepts of weak duality and strong duality state

about the linear program in part $($a$)$ as well as its dual. $[10$ marks$]$

$($d$)$ Imagine you have a linear program with $10,000,000$ decision variables and $10,000$

constraints. Unfortunately, the optimisation software that you use can cope very well$$with large numbers of constraints, but it struggles with large numbers of decision

variables. How can duality help you in this case?