Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment No 3- CS 538, S2023

Date Due: March 10th, 2023

1. In the Simplex approach, show the following:  (here recall that j  = cj  −对i∈B ci dij ).

(a) Let y be a solution to the constraints Ay = b, not necessarily a basic feasible solution.  Let (B) be the relative cost vector defined w.r.t. a basis B . Show that T y = g − f where f is the cost of the current solution associated with B and g is the cos of y .

(b) Suppose the Simplex is at basis B and selects a basis B\ by choosing a column j s.t. j  < 0. Is the cost of the solution guaranteed to decrease? Under which condition would it not.

2. Investigate the following and report your findings:

(a) How does the Simplex method find the first Basic Feasible solution

(b) Can the Simplex Method cycle, i.e. repeat a basis? under what conditions.

(c) What is the complexity of the Simplex method.

3. In the system Ax = b,x ≥ 0 solved via Simplex, can two different basis in A result in the same vertex. If so, give an example. If not prove your statement.

4.  Can a column vector in A that has just left the basis B when Simplex moves to B\  return to the basis at the very next step?

5.  A network problem is formulated for a directed graph G = (V,E) using the node-arc incidence matrix which represent the matrix A in the Simplex method.  Show that a set of |V | − 1 columns is linearly independent if and only if the corresponding arcs, considered as undirected edges in the undirected version of G, is a tree. Interpret the pivot step of the simplex method in the light of this fact.