Please Ans all the questions from $1$ to $4$ since its dependable to each other.

Column Generation

In this problem, we want to walk you through the column generation algorithm to solve the cutting

stock problem. Consider the following formulation

min${\displaystyle \underset{j=1}{\overset{n}{}}}{x}_i$

$s.t.{\displaystyle \underset{j=1}{\overset{N}{}}}{A}_j{x}_j=b$

$x_{j}0,$AAj$=1,$dots,$N.$

The problem has the following data. Customers need three types of smaller widths: $w_1=$

$5,w_2=12,w_3=16$ with quantities $b_1=150,b_2=100,b_3=80.$ The width of a big roll is $W=200.$

Assume the column generation algorithm starts from the following initial patterns:

$A_1=\left[\begin{array}{c}40\\ 0\\ 0\end{array}\right],A_2=\left[\begin{array}{c}0\\ 16\\ 0\end{array}\right],A_3=\left[\begin{array}{c}0\\ 0\\ 12\end{array}\right].$

Write down the restricted master problem $($RMP$)$ using these patterns. $1.$ Solve this RMP by hand. Find the optimal basis $B$ and its inverse $B^{-1}.$ Find the optimal dual solution

hat$(y{)}^{TT}=c_B^{TT}{B}^{-1}.$

$2.$ Solve RMP in Python CVX$.$ Write down the optimal solution, the optimal basis $B,$ and its

inverse $B^{-1}.$ Find the optimal dual solution hat$(y{)}^{TT}=c_B^{TT}{B}^{-1}.$ To take the inverse of $B,$ you can

use a calculator or computer program. In this iteration, you should be able to solve this LP

by hand. But we ask you to set up the code in CVX and solve it using CVX$.$ This code will

be used in later iterations.

$3.$ Write down the pricing problem, i$.$e$.$ the knapsack problem using the above data and the

optimal dual solution you found.

$4.$ Solve the pricing problem in CVX$.$ Should we terminate the column generation algorithm

at this point? Explain. If the column generation should continue, what is the new pattern

generated by the pricing problem?

Pleeases solve to get correct values of answers. Don't only give instructioons on how to do it$.$