Assignment -
This assignment is composed of three questions.
Question 1 - At the beginning of the fall semester, the director of the computer facility of a certain university is confronted with the problem of assigning different working hours to her operators. Because all the operators are currently enrolled in the university, they are available to work only a limited number of hours each day.
There are six operators (four men and two women). They all have different wage rates because of differences in their experience with computers and in their programming ability. The following table shows their wage rates, along with the maximum number of hours that each can work each day.
|
Operator
|
Wage rate ($/Hour)
|
Maximum Hours of Availability
|
|
Mon.
|
Tue.
|
Wed.
|
Thurs.
|
Fri.
|
|
K.C.
|
10.00
|
6
|
0
|
6
|
0
|
6
|
|
D.H.
|
10.10
|
0
|
6
|
0
|
6
|
0
|
|
H.B.
|
9.90
|
4
|
8
|
4
|
0
|
4
|
|
S.C.
|
9.80
|
5
|
5
|
5
|
0
|
5
|
|
K.S.
|
10.80
|
3
|
0
|
3
|
8
|
0
|
|
N.K.
|
11.30
|
0
|
0
|
0
|
6
|
2
|
Each operator is guaranteed a certain minimum number of hours per week that will maintain an adequate knowledge of the operation. This level is set arbitrarily at 8 hours per week for the male operators and 7 hours per week for the female operators (K.S. and N.K.)
The computer facility is to be open from 8 A.M. to 10 P.M. Monday through Friday with exactly one operator on duty during these hours. On Saturdays and Sundays, the computer is to be operated by other staff.
Because of a tight budget, the director has to minimize cost. She wishes to determine the number of hours she should assign to each operator on each day. Formulate a linear programming model for this problem (DO NOT SOLVE IT).
Question 2 - Suppose that the following canonical tableau is associated with a maximization problem
|
BV
|
z
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
rhs
|
|
z
|
1
|
0
|
0
|
0
|
c1
|
3
|
c2
|
c3
|
200
|
|
x1
|
0
|
0
|
1
|
0
|
a1
|
1
|
0
|
7
|
β
|
|
x2
|
0
|
0
|
0
|
1
|
-2
|
2
|
a2
|
-1
|
7
|
|
x3
|
0
|
1
|
0
|
0
|
0
|
-1
|
3
|
1
|
10
|
The entries c1, c2, c3, a1, a2 and β in the above tableau are parameters. The question below are independent and they all refer to the above tableau. State the most general conditions on the parameters c1, c2, c3, a1, a2 and β that make the statements of each question below true. If you do not state any condition with respect to a specific parameter, I will assume that the parameter can take on any value from - ∞ to ∞.
(a) The current basic solution is optimal and degenerate. (Observation: A basic solution is called degenerate if the value of one of its basic variables is equal to zero.)
(b) The current basic solution is feasible but the LP is unbounded.
(c) The current basic solution is feasible, x6 is a candidate to enter the basis and x3 leaves the basis when x6 enters the basis.
(d) The current basic solution is feasible, x7 is a candidate to enter the basis, but when x7 enters the basis, both the solution and the objective value remain unchanged.
(e) The current basic solution is feasible, x7 is a candidate to enter the basis, and when x7 enters the basis, x1 remains basic and the value of x1 at the new BFS (after the pivot) is equal to 7. What will be the values of x3 and x7 in the new BFS?
Question 3 - Consider the following LP problem:
maximize 2x1 + 2x2
s.t. x1 + x2 ≤ 2,
4x1 + x2 ≥ 4,
x1 ≥ 0, x2 ≥ 0.
(a) Use graphical method to find all extreme points and all optimal solutions of LP (??).
(b) Convert LP (??) into an equivalent one in standard form. Find all basic feasible solutions (BFS) of the standard form LP. (Remark: You do not have to solve the standard form LP.) Describe the correspondence between these BFS's and the extreme points obtained in part (a).
Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston.