You are a locksmith tasked with producing keys k1,..., kn that sell for p1,..., pn respectively. Each key kitakes gi grams of gold and si grams of silver. You have a total of G gold and S silver to work with, and canproduce as many keys of any type as you want within the time and material constraints.
(a) Unfortunately, integer linear programming is an NP-complete problem. Fortunately, you have foundsomeone to instead buy the alloys at an equivalent price! Instead of selling keys, you have decided tofocus on melting the prerequisite metals together, and selling the mixture. Formulate the linear programto maximize the profit of the locksmith, and explain your decision variables, objective function,and constraints.
(b) Formulate the dual of the linear program from part (a), and explain your decision variables, objective function, and constraints. Your explanation should be more specific than constraint multipliers forgeneric linear programs.Hint: Formulate the dual first, then think about it from the perspective of the locksmith when negotiatingprices for buying G gold and S silver if they had already signed a contract for the prices forthe output alloys pi. Think about the breakeven point, from which the locksmith's operations begin tobecome profitable for at least one alloy.