在加拿大代写中，数学是最常见的一个科目。本文是Linear Optimzation代写中较为常见的和Theory of Calculus 以及 Real analysis相关的数学代写案例，CoursePear数学代写 From 2009。
McGill University
Department of
Mathematics and Statistics
Courtney Paquette
MATH 417/517 – Linear Optimzation
Homework Set No. 2
Due Date: Friday, September 30 by 11:59 pm (local Montreal)
Submission Method: CrowdMark, submit each problem separately
3.1 (LP standard form) Bring the linear program
max x1 + 2x2 + 3x3 s.t. x1 + x3 ≥ 0,
x1 − x3 ≤ 0,
x1 + x2 = 1,
x1, x2 ≥ 0.
to standard form
min cT x s.t. Ax = b, x ≥ 0,
with A ∈ Rm×n, b ∈ Rm and c ∈ Rn and write down A, b, c and n, m ∈ N explicitly. (3 P.)
3.2 (LP modelling) A hauling company has trucks (of the same size) a the locations A and B, namely 18 at location A and 12 at location B. These are to be sent to the terminals R,S and T where there are 11, 10 and 9 trucks needed, respectively. The distances (in km) from the locations to the terminals are given in the following table:
Terminal R Terminal S Terminal T
Location A 9
| 5 | 4 |
Location B 7 8 10
The trucks are to be routed such that the kilometers driven are minimal and such that the needs at every terminal are met.
a) Formulate this problem as a linear program.
b) Use linear algebra to reduce it to a two-dimensional problem in order to solve it graphically.
(3+8 P.)
3.3 (The full rank assumption on A) Let P = P(A, b) be a nonempty polyhedron
in standard form with
A =
− aT1 −
...
− aTm −
∈ Rm×n
such that rank A = k < m and ai1, . . . , aikare linearly independent. Show that for (the polyhedron in standard form)
n
Q :=
we have Q = P.
(4 P.)
x ∈ Rn
aTijx = bij(j = 1, . . . , k), x ≥ 0o
3.4 (Finitely many basic feasible points) Let b ∈ Rm, A ∈ Rm×n with rank A = m and let P = P(A, b) be the polyhedron in standard form defined by (A, b). Show that P has at most finitely many basic feasible points.
(4 P.)
4.1 For v ∈ Rncompute inf vT x | x ≥ 0 . (2 P.)
4.2 (Dual of the dual is the primal problem) For (A, b, c) ∈ Rm×n × Rm × Rn consider the primal linear program
min cT x s.t. Ax = b, x ≥ 0 (P)
and its dual
max bTy s.t. ATy ≤ c. (D)
Show that the dual of the dual program is (equivalent to) the primal. (4 P.)
4.3 Consider the primal linear program (P) and its dual (D) and show: a) If (P) is unbounded then (D) is infeasible.
b) If (D) is unbounded then (P) is infeasible.
Afterwards fill in the table below.
| inf(P) = −∞ | inf(P) ∈ R | inf(P) = +∞ | |
| sup(D) = −∞ | |||
| sup(D) ∈ R | |||
| sup(D) = +∞ |
Use the symbol ’X’ if the case for the tuple (inf(P),sup(D)) can occur, and ’×’ if this case cannot occur. Verify the positive case by an example, and cite a result from the lecture that explains the negative case.
(2+9 P.)
*4.4 (Equivalence of Farkas Lemma and strong duality) Show that the Farkas Lemma (Proposition 2.4.5) follows from the strong duality theorem (Theorem 2.5.6).
(4 P.)
| Remarks • The problems marked with ’*’ are only compulsory for the honours students (MATH 517). It goes without saying that everybody else is also encouraged to tackle them. • You may (and are encouraged to) work with other students in the class on the assignments, and you can submit in groups of maximally 2 students. You must also cite any materials you have used to complete your work. Since both the midterm and the final exam will, in part, be heavily based on the homework assignments, it is strongly recommended to take the homework seriously. |
CoursePear™是一家服务全球留学生的专业代写。
—-我们专注提供高质靠谱的美国、加拿大、英国、澳洲、新西兰代写服务。
—-我们专注提供Essay、统计、金融、CS、经济、数学等覆盖100+专业的作业代写服务。
CoursePear™提供各类学术服务，Essay代写，Assignment代写，Exam / Quiz助攻，Dissertation / Thesis代写，Problem Set代做等。