Assignment No 3- CS 538, S2023
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.
2023-03-14