There are two files in which one is written homework and the other one requires Matlab. Please do the questions the way before. Thank you!Math 171A: Linear Programming

Instructor: Philip E. Gill © 2021 (Not to be Reposted)

Winter Quarter 2021

Matlab Assignment #4

Due Wednesday February 24, 2021

Starred exercises require the use of Matlab.

2

Mathematics 171A

Exercise 4.1.∗ A completed m-file maxstep.m has been placed on the class web-site for

your use.

(a) Download the m-file maxstep.m and place it in your Matlab working folder. Make

sure that you understand how it works—later you will be required to use it in an m-file

of your own that solves a linear program.

(b) The diet problem of Assignment 1 has inequality constraints Ax ≥ b, where

28

15

6

30

20

510

34

1

A=

0

0

0

0

0

0

0

0

24

15

10

20

20

370

35

0

1

0

0

0

0

0

0

0

25

6

2

25

20

500

42

0

0

1

0

0

0

0

0

0

14

2

0

15

10

370

38

0

0

0

1

0

0

0

0

0

31

8

15

15

8

400

42

0

0

0

0

1

0

0

0

0

3

0

15

0

2

220

26

0

0

0

0

0

1

0

0

0

15

4

0

20

15

345

27

0

0

0

0

0

0

1

0

0

9

10

4

30

0

110

12

0

0

0

0

0

0

0

1

0

55

1

100

2

100

120

100

2

100

2

2000

80

350

20

0

, and b = 0 .

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

Load the diet problem and compute the point x̄ at which the constraints corresponding

to rows 2, 3, 5, 7, 9, 11, 12, 14, and 16 of A above are active. Use the m-file maxstep.m

to find the maximum feasible step from x̄ along the direction

−1

1

−1

1

p=

1 .

−1

1

1

1

Matlab #4

3

Exercise 4.2.∗

(a) Consider the matrix of active constraints

0

0

5

2

7

−4

2

0

4 −2

.

Aa =

−6

0 −3

3

5

−1 −8

4 −7 −3

Use mysolve.m to construct a direction p along which the residual of the third constraint increases, but all the other residuals remain the same. If the rows of Aa are

labeled 1 through 4, what are the indices of the active set after a positive step along

this direction?

(b) Repeat part (a) for the vertex

0

9

0

Aa =

−3

3

−8

−1

3

6 −5 −4

1

6 −4

5

1

6 −5 −4

−4 −5

3

2

.

5 −6

3

2

−3

0

7 −1

0

0

0

0

Comment on your results. Is the vertex degenerate or nondegenerate?

4

Mathematics 171A

Exercise 4.3.∗ Consider the linear program

minimize

x1 ,x2 ,x3

subject to

3×1 − x2 + 2×3

− 2×1 + 4×2 + 4×3

x1 + 4×2 + x3

− 2×1 + x2 + 2×3

2×1 − 2×2

− 3×2 + x3

x1

x2

x3

≥ 6

≥ 5

≥ 1

≥ 0

≥ −2

≥ 0

≥ 0

≥ 0,

and the point x̄ = (1, 1, 1)T . Find the active set at x̄ and determine if the point x̄ is

optimal. If x̄ is not optimal, find a direction p such that

cTp < 0 and Aa p ≥ 0.
Matlab #4
5
Exercise 4.4.∗ Consider the linear program
minimize
cTx subject to Ax ≥ b.
n
x∈R
Consider a particular problem with objective vector c =
feasible point x̄, the active constraint matrix is given by
−6
5
1
0 −1
7 −6 −2
3
Aa = −2
−4 −2
7
2 −4
(−10, 3, 8, 2, −5, 6, 2)T . At a
3
0
3
1
0 .
1
(a) Is x̄ a vertex? If x̄ is a vertex, is it degenerate or nondegenerate? Justify your answer.
(b) Determine whether or not x̄ is optimal.
6
Mathematics 171A
Exercise 4.5.∗ Load the diet problem of Assignment 1 and compute the point x̄ at which
the constraints corresponding to rows 2, 3, 5, 7, 9, 11, 12, 14, and 16 of A are active. Using
x̄ as initial point, solve the diet problem using the simplex method. Show your work.
Math 171A: Linear Programming
Instructor: Philip E. Gill © 2021 (Not to be Reposted)
Winter Quarter 2021
Homework Assignment #4
Due Wednesday February 24, 2021
2
Mathematics 171A
Exercise 4.1. Consider the feasible region F of points in Rn satisfying the constraints
Ax ≥ b, where A is a nonzero m × n matrix. Assume that F contains at least one point.
Show that, if a nonzero vector p exists such that Ap ≥ 0, then F is unbounded.
Homework #4
3
Exercise 4.2. Show that the feasible region for the equality constraints Ax = b is either
empty or convex.
4
Mathematics 171A
Exercise 4.3. Let Aa be a nonzero m × n matrix, and let CN denote the dual cone
CN = {w : w = ATa λ,
λ ≥ 0}.
(a) Show that CN is a convex set.
(b) Is CN a subspace of Rn ? Explain why or why not.
Homework #4
5
Exercise 4.4. Suppose that the objective vector of a linear program is c = (2, 1)T , and
that the matrix of active constraints at a feasible point x̄ is
1
1
1 −2
Aa =
1 −3 .
1
2
(a) Is x̄ a vertex? If so, is it degenerate or nondegenerate? Explain your answer.
(b) Graph the dual cone. Use your graph to either verify that x̄ is optimal or find a
direction p such that cTp < 0 and Aa p ≥ 0.
6
Mathematics 171A
Exercise 4.5. Consider the following five constraints
x1 + 2x2 ≤ 3, x1 − x2 ≥ 0, 2x1 + x2 ≤ 3, x1 + 5x2 ≤ 6, x1 − 2x2 ≥ −1.
(a) Sketch the feasible region and find the degenerate vertex x0 .
(b) How many possible working sets are there at x0 ?
(c) Suppose that we wish to minimize x1 + x2 subject to these constraints, starting at x0
and using the simplex method. Find a working set A0 for which the Lagrange multiplier
vector λ (the solution of AT0 λ = c) contains at least one negative component λs , but
the simplex search direction satisfying A0 p = es is not a feasible descent direction.
Draw a picture showing p emanating from x0 . What are the blocking constraints?
(d) Under the same conditions as in part (c), find a working set Ā0 for which the Lagrange
multiplier vector contains at least one negative component, but the associated search
direction p̄ is a feasible descent direction. Draw a picture showing p̄ emanating from
x0 .
(e) Can you find a feasible descent direction at x0 if we wish instead to minimize −x1 −x2 ?
Explain your answer.
Purchase answer to see full
attachment

#### Why Choose Us

- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee

#### How it Works

- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "
**PAPER DETAILS**" section. - Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “
**CREATE ACCOUNT & SIGN IN**” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page. - From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.