sketch the nonzeros Recall the formulation for a twostage st

sketch the nonzeros

Recall the formulation for a two-stage stochastic linear program: max cx + sigma^K_k = 1 pkq^k y^k subject to Ax = b, T^kx + W^ky^k = h_k. 1 lessthanorequalto k lessthanorequalto K, x greaterthanorequalto 0, y^k greaterthanorequalto 0, 1 lessthanorequalto k lessthanorequalto K. There are n_1 first-stage variables x. and n_2 second-stage variables y^k for every scenario 1 lessthanorequalto k lessthanorequalto K. Similarly, there are m_1 first-stage constraints Ax = b and for every scenario 1 lessthanorequalto k lessthanorequalto K, there are m_2 second-stage constraints T^kx + W^ky^k = h_k, 1 lessthanorequalto k lessthanorequalto K. Recall that the matrix A is m_1 times n_1, the matrices T^k are m_2 times n_1, and the matrices W^k are m_2 times n_2. The vector b epsilon R^m1 and the vectors h_k epsilon R^m12. A two-stage stochastic program has \"simple recourse\" if the only possible recourse actions are to pay shortage or surplus penalties: for every scenario, the matrix W = [I, -I] and the second-stage objective is strictly positive. In this case. n_2 = 2m_2. Consider a two-stage stochastic linear program that has the following characteristics: There are no constraints on the first-stage decision, x (i.e., m_1 = 0). For every scenario 1 lessthanorequalto k lessthanorequalto K, the matrix T^k is the same matrix T. This matrix T is totally unimodular. The stochastic program has simple recourse, that is, W = [I, -I]. For every scenario, the right-hand vector h_k is integral. \"Sketch\" the nonzeros in the constraint matrix in terms of the submatrices T and W = [I. -I]. The following is an (incorrect) example of what we\'re looking for: (T W T W T W W), but your sketch should hold for an arbitrary K. Prove that under the five conditions above, if the two-stage stochastic linear program has a feasible solution and is bounded, then there exists an optimal solution to the two-stage stochastic linear program that has integral x and integral y^k for every 1 lessthanorequalto k lessthanorequalto K.

Solution

(a)here k is constant,and obtaining the non zero values

w=( t w t t w) this is the correct order for the matrix.

(b)here x and y is in tthe intrvals 0,1 because it is the linear system.

and the values of k is 1 and K.