xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

线性代数代写-171A

时间：2021-01-15

Math 171A: Linear Programming

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

Winter Quarter 2021

Homework Assignment #1

Due Friday January 15, 2021

I know that you are all aware of the importance of doing the homework assignments. This

is the best way to keep up with the class and do well in the midterm and final examinations.

Unfortunately, the graders will not have the time to grade every exercise. Instead, they will

grade two or three exercises (including at least one Matlab exercise) and give a fixed score

for every other exercise attempted.

The starred exercises require the use of Matlab. Remember that it is necessary to do all

the Matlab assignments to obtain credit for the class.

Exercise 1.1. In the JuiceCo mixture problem considered in class, x represents gallons of

cranapple, y gallons of appleberry.

(a) How many gallons of each juice mixture are represented by each corner point? Evaluate

the profit formula 3x+ 4y at each corner point of the feasible region.

(b) Which corner point represents the maximum profit for each of the following profit

formulas:

(i) profit = 3x+ 4y (the definition used in class);

(ii) profit = 2x+ 5y;

(iii) profit = 5x+ 3y.

Exercise 1.2. Convert the JuiceCo problem into “all-inequality form” min cTx, subject to

Ax ≥ b and define the quantities A, b, and c.

Exercise 1.3. Consider the following constraints in two variables: (1) x1 − 2x2 ≤ −1; (2)

x1 − x2 ≥ −3; (3) 12 ≤ x2 ≤ 4; (4) 2x1 − 2x2 ≤ 6; (5) x1 + x2 ≤ 6; (6) x1 ≥ 0; and (7)

x2 ≥ 0.

(a) Define the matrix A and vector b that express these constraints in the form Ax ≥ b.

(b) Draw the feasible region defined by the 8 constraints. Outline the feasible region on

your graph and label each of the corner points.

(c) Draw the level curve along which the linear function −2x1 − x2 is equal to −8.

(d) Draw the level curve along which the linear function −x1 − x2 is equal to −6.

Exercise 1.4. Suppose that your diet consists of a selection of the following items from a

well-known fast food restaurant (we give each food a nickname to assist in referring to it):

QP: Quarter Pounder FR: Fries, small

MD: McLean Deluxe SM: Sausage McMuffin

BM: Big Mac 1M: 1% Lowfat Milk

FF: Filet-O-Fish OJ: Orange Juice

MC: McGrilled Chicken

2 Mathematics 171A

You are interested in providing your diet with appropriate amounts of the following seven

“nutrients”:

Prot: Protein Iron: Iron

VitA: Vitamin A Cals: Calories

VitC: Vitamin C Carb: Carbohydrates

Calc: Calcium

Using the internet you have found how much of each nutrient is in one serving of each food,

and the total of each nutrient that you require. You also found the price per serving of each

food. The relevant costs, requirements, and nutritional values are:

QP MD BM FF MC FR SM 1M OJ Req’d

Cost 1.84 2.19 1.84 1.44 2.29 0.77 1.29 0.60 0.72

Prot 28 24 25 14 31 3 15 9 1 55

VitA 15 15 6 2 8 0 4 10 2 100

VitC 6 10 2 0 15 15 0 4 120 100

Calc 30 20 25 15 15 0 20 30 2 100

Iron 20 20 20 10 8 2 15 0 2 100

Cals 510 370 500 370 400 220 345 110 80 2000

Carb 34 35 42 38 42 26 27 12 20 350

Formulate a linear program with a solution that defines the least expensive combination of

the foods providing a day’s nutritional requirements. Write the problem in the form min

cTx, subject to Ax ≥ b.

Exercise 1.5.∗ You have formulated the diet problem above as a linear program of the

form min cTx subject to Ax ≥ b.

(a) In class we defined a “corner point” as a feasible point that lies at the intersection of n

hyperplanes. Give an upper limit on the number of corner points for the diet problem.

(Don’t just guess a number, give an estimate based on the row and column dimensions

of the constraint matrix.)

(b) Find three corner points and compute the value of the objective function at each one.

Exercise 1.6. Consider the inequality constraint aTx ≤ b where a 6= 0. Show that the

constraint normal points “into” the infeasible half-space.

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

Winter Quarter 2021

Homework Assignment #1

Due Friday January 15, 2021

I know that you are all aware of the importance of doing the homework assignments. This

is the best way to keep up with the class and do well in the midterm and final examinations.

Unfortunately, the graders will not have the time to grade every exercise. Instead, they will

grade two or three exercises (including at least one Matlab exercise) and give a fixed score

for every other exercise attempted.

The starred exercises require the use of Matlab. Remember that it is necessary to do all

the Matlab assignments to obtain credit for the class.

Exercise 1.1. In the JuiceCo mixture problem considered in class, x represents gallons of

cranapple, y gallons of appleberry.

(a) How many gallons of each juice mixture are represented by each corner point? Evaluate

the profit formula 3x+ 4y at each corner point of the feasible region.

(b) Which corner point represents the maximum profit for each of the following profit

formulas:

(i) profit = 3x+ 4y (the definition used in class);

(ii) profit = 2x+ 5y;

(iii) profit = 5x+ 3y.

Exercise 1.2. Convert the JuiceCo problem into “all-inequality form” min cTx, subject to

Ax ≥ b and define the quantities A, b, and c.

Exercise 1.3. Consider the following constraints in two variables: (1) x1 − 2x2 ≤ −1; (2)

x1 − x2 ≥ −3; (3) 12 ≤ x2 ≤ 4; (4) 2x1 − 2x2 ≤ 6; (5) x1 + x2 ≤ 6; (6) x1 ≥ 0; and (7)

x2 ≥ 0.

(a) Define the matrix A and vector b that express these constraints in the form Ax ≥ b.

(b) Draw the feasible region defined by the 8 constraints. Outline the feasible region on

your graph and label each of the corner points.

(c) Draw the level curve along which the linear function −2x1 − x2 is equal to −8.

(d) Draw the level curve along which the linear function −x1 − x2 is equal to −6.

Exercise 1.4. Suppose that your diet consists of a selection of the following items from a

well-known fast food restaurant (we give each food a nickname to assist in referring to it):

QP: Quarter Pounder FR: Fries, small

MD: McLean Deluxe SM: Sausage McMuffin

BM: Big Mac 1M: 1% Lowfat Milk

FF: Filet-O-Fish OJ: Orange Juice

MC: McGrilled Chicken

2 Mathematics 171A

You are interested in providing your diet with appropriate amounts of the following seven

“nutrients”:

Prot: Protein Iron: Iron

VitA: Vitamin A Cals: Calories

VitC: Vitamin C Carb: Carbohydrates

Calc: Calcium

Using the internet you have found how much of each nutrient is in one serving of each food,

and the total of each nutrient that you require. You also found the price per serving of each

food. The relevant costs, requirements, and nutritional values are:

QP MD BM FF MC FR SM 1M OJ Req’d

Cost 1.84 2.19 1.84 1.44 2.29 0.77 1.29 0.60 0.72

Prot 28 24 25 14 31 3 15 9 1 55

VitA 15 15 6 2 8 0 4 10 2 100

VitC 6 10 2 0 15 15 0 4 120 100

Calc 30 20 25 15 15 0 20 30 2 100

Iron 20 20 20 10 8 2 15 0 2 100

Cals 510 370 500 370 400 220 345 110 80 2000

Carb 34 35 42 38 42 26 27 12 20 350

Formulate a linear program with a solution that defines the least expensive combination of

the foods providing a day’s nutritional requirements. Write the problem in the form min

cTx, subject to Ax ≥ b.

Exercise 1.5.∗ You have formulated the diet problem above as a linear program of the

form min cTx subject to Ax ≥ b.

(a) In class we defined a “corner point” as a feasible point that lies at the intersection of n

hyperplanes. Give an upper limit on the number of corner points for the diet problem.

(Don’t just guess a number, give an estimate based on the row and column dimensions

of the constraint matrix.)

(b) Find three corner points and compute the value of the objective function at each one.

Exercise 1.6. Consider the inequality constraint aTx ≤ b where a 6= 0. Show that the

constraint normal points “into” the infeasible half-space.