IE333/3033 OPERATIONS RESEARCH I - MIDTERM II
17/12/2015
Q1) A doll company makes two kinds of dolls; doll A, a high quality doll, and doll B, yielding profits of
$2.5 and $1.5, respectively per doll sold. Each doll of type A requires twice as much labor as a doll of
type B, and if all dolls made were type B, the company could make 500 per day. The supply of
material is sufficient for only 400 dolls per day of both A and B combined.
The best customer has ordered 300 dolls of type A for the coming season, an order which the
company would like to meet as far as possible. Also, the company has a desire to earn a profit of
$500 or more for the coming season as far as possible.
a) Formulate the problem of meeting both goals as far as possible using goal programming with
weights approach (assuming the both goals have the same importance). (10P)
b) Suppose that the profit goal is more important than the demand goal. Prepare a scheme
using the preemptive approach considering the minimization of the deviations from the
goals. (10P)
Q2) Consider the following LP model and its standard form representation:
Max z  3x1  2 x 2
S .t.
 3 x1  4 x 2  12
x1  5
4 x1  3 x 2  12
x1 , x 2  0
Max z  3 x1  2 x 2
S .t.
 3x1  4 x 2  x3  12
x1  x 4  5
4 x1  3 x 2  x5  12
x1 , x 2 , x3 , x 4 , x5  0
a) Use the initial solution XB = [x3, x5, x1] with B 1
1 3 0 
 0 4  1 and solve the problem
0 1 0 
optimally using the revised simplex method. (10P)
b) Draw the feasible region of the problem graphically and compute the solutions, X = [x1, x2, x3,
x4, x5], corresponding to at least two extreme points. (10P)
Q3) Consider the following LP model:
Min
z  6 x1  12 x 2  4 x3  x 4
2 x1  6 x 2  x3  x 4  12
x1 , x 2 , x3  0
x 4 : unrestricted in sign
a) Find the optimal objective value, z*, only investigating its dual model. (10P)
b) For which values of c1 (objective coefficient of x1) the dual model becomes infeasible (only by
the investing the dual model). (10p)
Q4) The following is the optimum tableau for a maximization LP model with three ≤ constraints and
all nonnegative variables. The variables x3, x4, and x5 are the slacks associated with the constraints.
z
X3
X2
X1
X1
0
0
0
1
X2
0
0
1
0
X3
0
1
0
0
X4
3
1
1
-1
X5
2
-1
0
1
Solution
?
2
6
2
a) Determine the associated optimal objective value. (Hint: recall the strong duality,
c1*x1*+....+cn*xn* = b1*y1*+...+bm*ym*). (If you couldn’t find the optimal objective value,just
use notation z* in the remaining questions if necessary). (10p)
b) Suppose that the objective function is z = 2x1 + c2x2 + 0x3 . Compute c2. (10p)
c) Find the optimality range of c1. (5p)
d) Find the feasibility range of b1. (5p)
e) Suppose that a new constraint, x1  4, is added to the original model. Does the new
constraint make the current optimal solution infeasible? If yes, find the new optimal solution.
(10p)
Download

Midterm 2 Solutions