Problem 1 (10 Points)
A company produces two kinds of products. Product A requires 1/4 hours of assembly labor, 1/8 hours of testing, and costs $1.20 of raw materials. Product B requires 1/3 hours of assembly, 1/3 hours of testing, and costs $0.90 of raw materials. Considering the company’s current personnel, there can be at most 90 hours of assembly labor and 80 hours of testing each day. Products A and B have market values of $9 and
$8, respectively.
1. Formulate a linear program that can be used to maximize the company’s daily profit.
2. Suppose that up to 50 hours of overtime assembly labor can be scheduled, at a cost of $7 per hour. Modify the linear program from Part 1 to incorporate this change. Clearly specify the new LP, not just any changes.
Problem 2 (10 Points)
1. Write the LP
maximize 2z1 + z2 subject to z1 ≥ z2
z1 + z2 ≤ 3
z1 ≥ 0,
with decision variables z1, z2 in the vector form
minimize cT x
subject to Ax ≥ b
x ≥ 0.
Clearly define c, x, A, and b. If you have added or replaced any decision variables, clearly indicate the relationship between the original decision variables and the new ones.
2. Show how x2 ≤ 16 can be represented in terms of linear constraints.
3. Show how |x − 1/2| ≤ 1/2 can be represented in terms of linear constraints.
4. We would now like to show that, on the contrary, it is not possible to represent x 1/2 1/2 using linear constraints. We’ll argue by contradiction.
In particular, recall that for any LP, any point on the line connecting two feasible points must also be feasible. In other words, the feasible region of any LP must be convex.
Suppose we could write x 1/2 1/2 in terms of linear constraints. Then x 1/2 1/2 could be used to describe the feasible region of an LP. Show that the feasible region of such an LP cannot be convex. Drawing a diagram of the set x ∈ R . |x − 1/2| ≥ 1/2 might help.
Problem 3: Non-collaborative, no help. (10 Points)
Consider the following linear program:
maximize y1 + 5y2 subject to y1 + 3y2 ≤ 15
y1 − 2y2 ≥ −5
y1 + y2 ≥ 4
y2 ≥ 1
1. Plot the feasible region in a two-dimensional graph.
2. Identify all basic feasible solutions.
3. What is the value of the objective function at an optimum solution?
Explain your answer. You may only use the graph you drew in Part 1 to derive your result; do not use Excel.
Hint: As mentioned in lecture, if the feasible region of a linear program is non-empty and bounded, then there exists an optimum solution that is a basic feasible solution.
Problem 4 (20 Points)
Please answer each of the following questions to review some important linear algebra concepts.
1. If A and B are matrices of appropriate dimensions, the (i, j)-entry of the product AB is given by
(AB)ij = aikbkj.
Now suppose A and B are n × n matrices with all entries equal to 1. What is (AB)ij?
2. In summation notation, the associative law (AB)C = A(BC) is given by
Σ Σ aikbkj ! cjl = Σ aik Σ bkjcjl .
With A and B as in Part 1, and assuming C is an n × n matrix with cil = 4, compute (ABC)il.
3. True or False: All 2 by 2 matrices commute. That is, if A and B are any 2 by 2 matrices, then
AB = BA. Explain your answer.
4. Let
1 0 8 2
A = 4 2 11 6 .
2 1 2 3
True or False: Suppose we remove one column of A. Regardless of which column we remove, the remaining three columns are linearly independent. Explain your answer.
5. True or False:
(a) If the columns of a matrix A are linearly independent, then Ax = b has exactly one solution for every b.
(b) The 7 columns of a 4 7 matrix cannot be linearly independent. Explain your answers.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
