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 cj's indicate the coefficients of the objective function, the bi's the constants (resource restrictions), and aij 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) b1 and b2

(5 pts)

 

 

 

 

 

(d) c2 and c4

(5 pts)

 

 

 

 

 

(e) a11 and a21

(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 = (c1,c2,c3) (x1,x2,x3)

subject to:

 

x1 > 0, x2 > 0, x3 > 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 b1 is changed to b1'. 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 b1' 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 0th 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 1st come 1st 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 1st person waiting, 10 minutes for the 2nd person waiting, and 5 minutes for the 3rd 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 P0 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 4th machine is shut down. As soon as one of the three is fixed, the 4th 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)