ISyE/Math/CS/Stat 525 – Linear Optimization
Stat 525代写 Question 1：(a)_____Every general linear programming problem can be transformed into an equivalent linear programming problem in standard form.
READ THIS!
- The exam starts at 9:30am and ends at 10:45am. I will give you an additional 15 minutes for the download/print/scan/upload operations. Therefore, you will need to submit the exam on Canvas before 11:00am.
- Some ways you can prepare the file to be submitted are: (i) you can directly edit the pdf of the exam with a tablet or computer, or (ii) you can print the exam, write on it, and then scan it or take pictures of it. You can also submit only your solutions without the text of the exam.
- This exam has a total of 4 problems and 30 points.
- Please write only one solution per question.
- The more clearly you write your answer, the better the chance that I can grade it accurately and give it full credit.
- Always justify your answers, unless otherwise stated.
- State properly any result that you use.
- Working in groups is not allowed: you must work on the exam alone. Improper collaboration will result in a score of zero.
- You are not allowed to share any content of this exam.
- For any question, you can find Prof. Alberto Del Pia at his offffice hours in Zoom throughout the duration of the exam.
- Good Luck!
Question 1 Stat 525代写
True or false …………………………………………………………. 10 points
No justifications needed. Mark “T” or “F”.
Points per question: 0 points if wrong; 1/2 point if no answer; 1 point if correct.
(a)_____Every general linear programming problem can be transformed into an equivalent linear programming problem in standard form.
(b)_____Every extreme point of a polyhedron P is also a basic solution of P.
(c)_____Every basic solution of a polyhedron P is also a vertex of P.
(d)_____The property of being a basic feasible solution is independent of the representation used (i.e., it depends on the polyhedron, but it is independent on the system of linear constraints used to describe the polyhedron.)
(e)_____In every linear programming problem in standard form, the set of all optimal solutions is bounded.
(f)_____If in a LP problem there are several optimal solutions, then there exist at least two vertices that are optimal.
(g)_____Let x be a point in a polyhedron P. It is possible that there exist infinitely many feasible directions at x.
(j)_____In the naive implementation of the simplex method the total computational effort per iteration is O(m³ + mn).
Question 2 Stat 525代写
Finite number of vertices ……………………………………………… 5 points
Let P = {x ∈ Rⁿ | Ax ≤ b} be a polyhedron. Prove that P has a finite number of extreme points.
Question 3
A tableau………………………………………………………………5 points
You are carrying out the full tableau implementation of the simplex method. In one iteration you obtain the following tableau:
(a) (1 point) Recover the missing labels, write the current solution and its cost.
(b) (4 points) Is the current solution optimal? If not, find an optimal solution with the full tableau implementation of the simplex method.
Question 4 Stat 525代写
Your boss and two polyhedra ………………………………………… 10 points
Assume that your boss gives you two polyhedra
P = {x ∈ Rⁿ | Ax ≤ b}, Q = {x ∈ Rⁿ | Cx ≤ d}.
In particular, the (m × n)-matrix A, the m-vector b, the (p × n)-matrix C, and the p-vector d are given to you. Your boss then asks you to understand whether P ⊆ Q, or to find a vector in P that is not in Q. Using your precious knowledge gained in the course 525, you write a computer program that can solve any LP problem where a linear function has to be maximized over a polyhedron (not only in standard form).
(a) (5 points) Prove that an inequality c′x ≤ δ is satisfied by every vector in P if and only if the optimal cost of the LP problem
maximize
c′x
s.t. Ax ≤ b
is less than or equal to δ.
(b) (5 points) Using (a), explain how you can give an answer to your boss using your computer program.
Hint: You can use your computer program several times with different inputs.
其他代写：homework代写 Exercise代写 course代写 作业代写 作业加急 essay代写 北美代写 北美作业代写 澳大利亚代写 英国代写 加拿大代写 app代写 algorithm代写 assignment代写 analysis代写 code代写 assembly代写 CS代写 Data Analysis代写 data代写
