1. Rewrite each of the following to obtain an equivalent linear programming problem that has the origin as a feasible point, an objective function that you are to maximize, and only nonnegative variables. Then write down the first tableau for the problem.
(a) minimize: Z = 3x1  5x2
subject to: 3x1 + 4x2 > 5
2x1  3x2 < 10
4x1 + 5x2 = 8
x1 > 0, x2 > 0
(12 pts)
(b) maximize: Z = 4x1 + 3x2
subject to: 2x1  3x2 < 10
3x1 + 4x2 < 20
4x1  7x2 <  4
¥ < x1 < ¥, x2 > 0
(12 pts)
2. Consider the problem:
maximize: Z = x1 + 3x2  14x3
subject to: 2x1  x2 + 7x3 < 20
x1 + x2  5x3 < 10
x1 > 0, x2 > 0.
Its final tableau is:
0 
0 
3 
2 
5 

1 
0 
2 
1 
1 
30 
0 
1 
3 
1 
2 
40 
Perform sensitivity analysis to find the range for the coefficient c2 of x2 that leaves the optimal solution unchanged.
(16 pts)
3. This is the final tableau for a particular standard, maximization linear programming problem with two functional inequalities.
3 
0 
100 
0 
0 
2 
1 

11 
1 
14 
0 
14 
5 
3 
10 
7 
0 
11 
1 
8 
3 
2 
8 
Use this final tableau and the fundamental insight to answer the following questions. Below, the c_{j}'s indicate the coefficients of the objective function, the b_{i}'s the constants (resource restrictions), and a_{ij} is the coefficient in the ith row and jth column. Find or give:
(a) the optimal solution
(5 pts)
(b) the complementary solution
(5 pts)
(c) b_{1} and b_{2}
(5 pts)
(d) c_{2} and c_{4}
(5 pts)
(e) a_{11} and a_{21}
(5 pts)
(f) the optimal value of the objective function.
(5 pts)
4. You are solving a standard, maximization linear programming problem. It has 3 decision variables and 4 functional inequalities. The form of the inequalities is:
maximize: Z = (c_{1},c_{2},c_{3}) · (x_{1},x_{2},x_{3})
subject to:
x_{1} > 0, x_{2} > 0, x_{3} > 0
Your final tableau looks like:
0 
5 
10 
0 
0 
20 
0 

0 
* 
* 
1 
0 
* 
0 
100 
1 
* 
* 
0 
0 
* 
0 
25 
0 
* 
* 
0 
1 
* 
0 
30 
0 
* 
* 
0 
0 
* 
1 
10 
(a) What is the optimal solution?
(5 pts)
(b) What is the complementary optimal solution?
(5 pts)
(c) Give the basic variables for the complementary solution.
(5 pts)
(d) Now suppose b_{1} is changed to b_{1}'. You perform the standard check and discover that your optimal solution has become infeasible. What check did you do?
(5 pts)
(e) You decide to switch to the dual problem with this new b_{1}' and solve it. Write down the dual problem using the notation above.
(10 pts)
(f) You know the point given in (c) (call it y) is still feasible. (i) Write down the matrix (in terms of the symbols) that you need to invert in order to get to the tableau that has y as its feasible solution. (ii) Say what you need to do to get this tableau using this matrix. (iii) Give explicitly the numbers in the 0^{th} row of this tableau that has y as its feasible solution.
(10 pts)
5. You have a car cleaning operation. Each clean consists of two services: first you clean and scrub the inside and then you wash the outside. The inside clean takes an average of 40 minutes and the outside wash an average of 20 minutes. These individual service times are exponentially distributed. Cars arrive according to a Poisson process with a mean of one every 80 minutes. (a) Set up this system as a Markov chain. (b) The total service time (i.e. the sum of the individual service times) is a random variable with mean 1 variance 5/9. Use your summary statistics to determine Lq and Wq (in hours).
(25 pts)
6. You run a small bike shop. Customers come in, and you service them 1^{st} come 1^{st} serve. Customers arrive according to a Poisson process at the rate of 4/hr. Your expected service time is exponentially distributed with an average time of 10 minutes. You observe that customers waiting for service renege with an expected time of 20 minutes for the 1^{st} person waiting, 10 minutes for the 2^{nd} person waiting, and 5 minutes for the 3^{rd} person waiting. If there are 3 waiting for service  so 4 in the system  then all additional customers balk right away. The average customer served spends $100.
(a) Set up the rate diagram for this queue.
(15 pts)
(b) Find P_{0} and the rest of the state distributions.
(10 pts)
(c) Compute the expected number of customers lost /hr due to reneging and balking.
(10 pts)
(d) Compute the expected number of customers served /hr and, using (c), the revenue lost/hr due to reneging and balking.
(5 pts)
7.
Your company has 4 identical computers that service incoming calls. If any break down the remaining ones handle
the traffic (although somewhat slower).
You have one employee whose job includes servicing these computers. Each of these computers will break down
about once every 48 hours according to an exponentially distributed random
variable. This break down is a quick
fix 90% of the time and a long fix 10% of the time. A quick fix problem has a mean repair time of 2 hrs. A long fix problem has a mean repair time of
12 hrs. Whenever there are 3 machines
down, all incoming calls are routed to an expensive contractor and the 4^{th}
machine is shut down. As soon as one of
the three is fixed, the 4^{th} is turned back on and the calls are
routed back to your working machines.
(a) Set up the Markov chain rate diagram for this queue. (Be sure to define your states.) (b) Set up the balance equations for one of
the states when there are only two working machines.
(25 pts)