﻿ Stat 525代写 Linear Optimization代写 - 统计作业, 考试助攻

# Stat 525代写 Linear Optimization代写

2021-06-24 17:18 星期四 所属： 统计作业 浏览：60 ## 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.

• 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.
• 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( + 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 cx δ is satisfied by every vector in P if and only if the optimal cost of the LP problem

maximize

cx

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. 