Operations
Research
Que. 1 Minimize Z=4x1 + x2
S.t. 3x1+x2=3
4x1+3x2 ³ 6
x1+2x2 £ 4
x1, x2 ³0
Ans.
First Method :
Graph
Z=
4x1 + x2
3x1 + x2 = 3
4x1 + 3x2 = 6
x1 + 2x2 = 4
TOP
3x1 + x2 = 3 --------------------------------(1)
x1 + 2x2= 4 --------------------------------(2)
Multiplying equation (1) by
(2) and taking the –ve
signs in equation we get
6x1 + 2x2 = 6
-x2 – 2x2 = -4
5x1 = 2
\x1 = 2/5 -----------------------(3)
Now substituting the value
of x1 in equation (2) we get:
x1 + 2x2 = 4
2/5 + 2x2 =4
\ 2x2 = 4 – 2/5
\ 2x2 = 18/5
\ x2 = 18/5 * ½
\ x2 = 9/5 ------------------------(4)
Z = 4x1 + x2
= 4*2/5 + 9/5
= 8/5 + 9/5 = 17/5
= 3.4
Second Method
Minimize Z=4x1 + x2
S.t. 3x1+x2=3
4x1+3x2 ³ 6
x1+2x2 £ 4
x1, x2 ³0
Maximize –4x1 –
x2
S.t. 3x1+x2=3
4x1 + 3x2 – x3 = 6
x1 + 2x2 + x4 = 4
Phase I :-
In this problem we consider
the following programming problem
Maximize -x5 – x6
S.t. 3x1 + x2 + x5 = 3
4x1 + 3x2 – x3 + x6 =
6
x1 + 2x2 + x4 = 4
x1, x2, x3, x4, x5, x6 ³
0
An initial basic feasible solution
of the problem is given by
x5=3, x4 =4, x6=6
TOP
Table : 1
| |
|
Cj |
0 |
0 |
0 |
0 |
-1 |
-1 |
|
CB |
Basic
Variable |
XB |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
M/R |
-1 |
X5 |
3 |
3 |
1 |
0 |
0 |
1 |
0 |
1 |
-1 |
X6 |
6 |
4 |
3 |
-1 |
0 |
0 |
1 |
3/2 |
0 |
X4 |
4 |
1 |
2 |
0 |
1 |
0 |
0 |
4 |
| |
|
|
-7 |
-4 |
1 |
0 |
-1 |
-1 |
|
| |
|
|
-7 |
-4 |
1 |
0 |
0 |
0 |
|
X1 becomes
a basic variables and x5 becomes
a non-basic variables in the next
alteration it is no longer considerations
for re-entry.
Table : 2
| |
|
Cj |
0 |
0 |
0 |
0 |
-1 |
|
CB |
Basic
Variable |
XB
Sol. |
X1 |
X2 |
X3 |
X4 |
X6 |
M/R |
0 |
X1 |
1 |
1 |
1/3 |
0 |
0 |
0 |
3 |
-1 |
X6 |
2 |
0 |
5/3 |
-1 |
0 |
1 |
6/5 |
0 |
X4 |
3 |
0 |
5/3 |
0 |
1 |
0 |
9/5 |
| |
Zj |
Zj |
0 |
-5/3 |
1 |
0 |
-1 |
|
| |
Zj - Cj |
Zj - Cj |
0 |
-5/3 |
1 |
0 |
0 |
|
x2
becomes basic variable and x6
becomes non-basic variable in
the next alteration. It is no
longer considered for re-entry.
Table
: 3
| |
|
Cj |
0 |
0 |
0 |
0 |
|
CB |
Basic
Variable |
XB
Sol. |
X1 |
X2 |
X3 |
X4 |
M/R |
0 |
X1 |
3/5 |
1 |
0 |
1/5 |
0 |
|
0 |
X2 |
6/5 |
0 |
1 |
-3/5 |
0 |
|
0 |
X4 |
1 |
0 |
0 |
1 |
1 |
|
| |
|
Zj |
0 |
0 |
0 |
0 |
|
| |
|
Zj - Cj |
0 |
0 |
0 |
0 |
|
The
phase-I computation is completed
at this stage. Both artificial
variables have been removed
from the basic. We have also
found a basic feasible solutions
of the problem namely x1 = 3/5,
x2= 6/5, x4 = 1.
Phase II :-
In this phase we use the actual
objective functions of problem.
Table
1:-
| |
|
Cj |
-4 |
-1 |
0 |
0 |
|
CB |
Basic
Variable |
XB |
X1 |
X2 |
X3 |
X4 |
M/R |
-4 |
X1 |
3/5 |
1 |
0 |
1/5 |
0 |
3 |
-1 |
X2 |
6/5 |
0 |
1 |
-3/5 |
0 |
-2 |
0 |
X4 |
1 |
0 |
0 |
1 |
1 |
1 |
| |
|
Zj |
-4 |
-1 |
-1/5 |
0 |
|
| |
|
Zj - Cj |
0 |
0 |
-1/5 |
0 |
|
X1
becomes a basic variable and
x5 become a non-basic variable
in the next alteration. It is
no longer consideration for
re-entry.
Table 2:-
| |
|
Cj |
-4 |
-1 |
0 |
0 |
|
CB |
BasicVariable |
XB |
X1 |
X2 |
X3 |
X4 |
M/R |
-4 |
X1 |
2/5 |
1 |
0 |
0 |
-1/5 |
|
-1 |
X2 |
9/5 |
0 |
1 |
0 |
-3/5 |
|
0 |
X3 |
1 |
0 |
1 |
1 |
1 |
|
| |
Zj |
Zj |
-4 |
-1 |
0 |
1/5 |
|
| |
Zj - Cj |
Zj - Cj |
0 |
0 |
0 |
1/5 |
|
As
all the Zj - Cj ³ 0 the current
solutions maximize the reused
objective functions. Hence the
solution of the problem is given
bellow:
X1 = 2/5 = 0.4
X2 = 9/5 = 1.8
X3 = 1
X4 = 0
The
minimize value of the objective
function is
Z
= 4x1 + x2
= 4 * 2/5 + 9/5
=
17/5
Z = 3.4
From above both methods we find that the value of objective
function Z is 3.4 |
