Linear Programming

Consider the polyhedron, where
Here is a positive real number. Find all BFS of and indicate which is degenerate and which is nondegenerate. Hint: this polyhedron is given in standard form so you should first change it to canonical form.
You should get 5 BFS.
Q2 (10 points)
Consider the problem of maximizing subject to the constraints,
, and.
(a) Convert this problem to an equivalent problem in canonical form. Write your final answer in the form
.
(b ) If, use graphical analysis to find an optimal solution to the problem from part (a).
Q3 (10 points)
Let be a polyhedron in, a vector, and a scalar. Consider the set
.
(a) Prove that is a polyhedron.
(b )Is it always possible to choose in such a way so that? Explain your answer.
Q4 (10 points)
Consider the LPP of maximizing subject to the constraints,
, and.
(a) Graph the feasible set in.
(b) Using the canonical form of this problem, find all basic feasible solutions (BFS). Hint: based on your graph from part (a), how many BFS are there?
2019/10/15 Crowdmark
https://app.crowdmark.com/student/assessments/hw2-b45d3 2/2
(c) Let denote the vertex, the vertex, and the vertex of the feasible set.
Find all basic directions at each of these vertices/BFS. Hint: each of the vertices should have basic directions.
(d) For each of the basic directions you found in part (c), find the corresponding reduced cost.
Q5 (10 points)
Consider the problem of minimizing subject to and, where
Note that here so it is possible to visualize the feasible set as a subset of. Do so: graph the feasible set in. Make sure to label the lines and all the basic solutions.
Q6 (10 points)
Let be a polyhedron, where is a matrix (
) with linearly independent rows and are the components of the vector.
(a) For which values of is it possible that has a degenerate BFS? Explain.
(b) Suppose is a degenerate BFS. What can you say about the product of all the components of? Explain.
Q7 (10 points)
Let be an element of the polyhedron in canonical form. Prove that a
vector is a feasible direction at if and only if and for every such that.
Q8 (10 points)
Consider the problem of maximizing over the set. Let be an element of that satisfies and for all. Show that the set of feasible directions at the point is the set.