Two phase method lpp

AnuragSrivastava11 8,257 views 7 slides Mar 09, 2019
Slide 1
Slide 1 of 7
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7

About This Presentation

operations research. an lpp problem asked in aktu exam solved using graphical method, simplex method and two-phase method


Slide Content

Two-Phase Method of solving an LPP
Solve the following problem by using Two-Phase method (2018, 7 marks)
Minimize z=x1+x2
subject to 2x1+x2≥4,
x1+7x2≥7,
and x1, x2≥0
Graphical Method
Step 1: Plotting the graph
������ �ℎ� ��� �������� ����������� �� ����������:
2�
1+�
2=4…(�)
�
1+7�
2=7…(��)
??????� ����� �� ���� �ℎ� ����� ����������� �� �ℎ��� ��� ���������,�� ���� ���
������ ���ℎ,�ℎ����ℎ �ℎ��ℎ �ℎ�� ����.
??????� �������� (�):
��� �
1=0
�ℎ��
2×0+�
2=4
�� 0+�
2=4
∴�
2=4
∴����� �����=(0,4)
����,��� �
2=0
�ℎ��
2�
1+0=4
�� 2�
1=4
�� �
1=
4
2

∴ �
1=2
∴������ �����=(2,0)
??????� �������� (��):
��� �
1=0
�ℎ��
0+7�
2=7
�� 7�
2=7
�� �
2=
7
7

∴ �
2=1
∴����� �����=(0,1)
����,��� �
2=0
�ℎ��
�
1+7×0=7
�� �
1+0=7
∴ �
1=7
∴������ �����=(7,0)
�ℎ� ����ℎ:

Step 2: Identifying the feasible area:
As per the direction of the constraints, the feasible area has been shown in the above graph
(above AED)
Step 3: Finding the optimum solution:
As per the Extreme Point Theorem, the optimum solution shall lie on one of the points A,
E or D.
����������� �� ??????=(0,4)
∴�ℎ� ����� �� �ℎ� ��������� �������� �� ??????:
�=�
1+�
2
=0+4
=4
??????� ����� �� ���� �ℎ� ����������� �� �,�� ℎ��� �� �������������� ����� �ℎ�
��������� �� �ℎ� ��� ����� (�) ��� (��):

2�
1+�
2=4…(�)
�
1+7�
2=7…(��)
����������� �������� (��) �� 2 ��� ����������� �������� (�)���� ��:
2�
1+14�
2=14
2�
1+ �
2= 4
− − −
0 +13�
2=10̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
�� 13�
2=10
�� �
2=
10
13

������������ �ℎ�� ����� �� �
2 �� �������� (��):
�
1+7×
10
13
=7
�� �
1+
70
13
=7
�� �
1=7−
70
13

=
13×7−70
13

=
91−70
13

=
21
13

∴����������� �� �=(
21
13
,
10
13
)
∴�ℎ� ����� �� �ℎ� ��������� �������� �� �:
�=�
1+�
2=
21
13
+
10
13
=
31
13
=2
5
13

����������� �� �=(7,0)
∴�ℎ� ����� �� �ℎ� ��������� �������� �� �:
�=�
1+�
2
=7+0
=7
∵�ℎ� ��������� �������� �� �� ������������ ����
∴�ℎ� ������� ����� �� �=�ℎ� ������� �������� ����� �� �=2
5
13

??????��:??????�� ������� �??????��� �� ?????? �� �
??????
��
��� ??????
� ���??????� ��
��
��
??????�� ??????
� ���??????� ��
��
��

Simplex Method
??????���������� ������� ��� ���������� ���������:
�������� �=�
1+�
2+0�
1+0�
2+�??????
1+�??????
2
������� ��:
2�
1+�
2−�
1+??????
1=4…(�)
�
1+7�
2−�
2+??????
2=7…(��)
�
1,�
2,�
1,�
2,??????
1,??????
2≥0
������ �� ���������=6

������ �� ���������=2
∴������ �� ���−����� ���������=6−2=4
∴������ �� ����� ���������=6−4=2
�ℎ� ��� ���������� ��������� ??????
1 ��� ??????
2 ���� �� ����� �� ������� ����� ���������
??????
1=4
??????
2=7
Initial Simplex Table
Cj 1 1 0 0 M M
Cb BV SV x1 x2 S1 S2 A1 A2
M A1 4 2 1 -1 0 1 0
4
1
=4
M A2 7 1 7 0 -1 0 1
7
7
=1 
Zj 11M 3M 8M -M -M M M

Cj–
Zj
1-3M
1-
8M
M M 0 0

Intermediate Simplex Table
M A1 3
13
7
0 -1
1
7
1 ×
3
13
7
=
21
13

�
1
=�
1
−�
2

1 x2 1
1
7
1 0 −
1
7
0 ×
1
1
7
=7
�
2=
�
2
7

Zj 3M+1
13�+1
7
1 -M
�−1
7
M ×

Cj–
Zj

6−13�
7
0 M
8−�
7
0 ×

∵ ??????
2 ℎ�� ���� �ℎ� �����
∴�� ���� ��� ��������� �ℎ� ������ �� ��� ������
Optimum Simplex Table
1 x1
21
13
1 0 −
7
13

1
13
× ×
�
1
=
7
13
�
1

1 x2
10
13
0 1
1
13

2
13
× ×
�
2
=�
2

1
7
�
1

Zj
31
13
1 1 −
6
13

1
13
× ×

Cj–
Zj
0 0
6
13

1
13
× ×

??????��: ??????
�=
��
��
,??????
�=
��
��
,??????=
��
��

Two-Phase Method
Here the solution of the LPP is completed in two phases. In the first phase of the method,
the sum of the artificial variables is minimised subject to the given constraints to get a basic
feasible solution. Th second phase minimises the original objective function starting with
the basic feasible solution obtained at the end of the first phase.
Steps of the Algorithm (Phase I)
1. Express the given LPP in the standard form.
2. Convert each of the constraints into equality by introducing slack, surplus or artificial
variables.
3. Solve the LPP by assigning a coefficient of ‘-1’ to each artificial variable in case of
maximisation problem and ‘+1’ in case of minimisation problem and zero to all other
variables in the objective function.
4. Apply the simplex algorithm to solve this LPP.
5. If Cj–Zj row indicates optimal solution and
a. the artificial variable appears as a basic variable, the given LPP has non-feasible
solution.
b. the artificial variable does not appear as a basic variable, the given LPP has a feasible
solution and we proceed to Phase II.
Phase II
6. Assign actual coefficients to the variables in the objective function and zero to the
artificial variables. That is, the last simplex table of phase I is used as the initial simplex
table for phase II. Now apply the usual simplex algorithm to the modified simplex table
to get the optimal solution to the original problem.
���.�=�
1+�
2
�/�
2�
1+�
2≥4
�
1+7�
2≥7
�
1,�
2≥0
??????���������� ������� ��� ���������� ��������� (??????ℎ��� ?????? �� �ℎ� ���−�ℎ���
���ℎ��)
���.�=0�
1+0�
2+0�
1+0�
2+??????
1+??????
2
�/�
2�
1+�
2−�
1+??????
1=4
�
1+7�
2−�
2+??????
2=7
�
1,�
2,�
1,�
2,??????
1,??????
2≥0
������ �� ���������=6
������ �� ���������=2
∴������ �� ���−����� ���������=6−2=4
∴������ �� ����� ���������=6−4=2
�ℎ� ��� ���������� ��������� ??????
1 ��� ??????
2 ���� �� ����� �� ������� ����� ���������
??????
1=4
??????
2=7

Initial Simplex Table (Phase I)
Cj 0 0 0 0 1 1
Cb BV SV x1 x2 S1 S2 A1 A2
1 A1 4 2 1 -1 0 1 0
4
1
=4
1 A2 7 1 7 0 -1 0 1
7
7
=1 
Zj 11 3 8 -1 -1 1 1
Cj–Zj -3 -8 1 1 0 0

Intermediate Simplex Table (Phase I)
1 A1 3
13
7
0 -1
1
7
1 ×
3
13
7
=
21
13

�
1=�
1−�
2 
0 x2 1
1
7
1 0 −
1
7
0 ×
1
1
7
=7
�
2=
�
2
7

Zj 3
13
7
0 -1
1
7
1 ×
Cj–Zj −
13
7
0 1 −
1
7
0 ×

∵ ??????
2 ℎ�� ���� �ℎ� �����
∴�� ���� ��� ��������� �ℎ� ������ �� ��� ������
Final Simplex Table (Phase I)
0 x1
21
13
1 0 −
7
13

1
13
× × �
1=
7
13
�
1
0 x2
10
13
0 1
1
13

2
13
× × �
2=�
2−
1
7
�
1
Zj 0 0 0 0 0 × ×
Cj–Zj 0 0 0 0 × ×
∵��� �
??????−�
?????? �������� ��� ���� ��� ��� ���������� ��������� ℎ��� ���� �ℎ� �����
∴�� �ℎ��� ����� ??????ℎ��� ????????????
Phase II Simplex Table (Optimum)
Cj 1 1 0 0
Cb BV SV x1 x2 S1 S2
1 x1
21
13
1 0 −
7
13

1
13

1 x2
10
13
0 1
1
13

2
13

Zj
31
13
1 1 −
6
13

1
13

Cj–Zj 0 0
6
13

1
13

??????��: ??????
�=
��
��
,??????
�=
��
��
,??????=
��
��

Solve the following using two-phase method:
Maximise: z = 30x + 40y + 35z
Subject to the constraints:
3x + 4y +2z ≤ 90
2x + y +2z ≤ 54
X + 3y + 2z ≤ 93
x, y, z ≥ 0 (2013)
Tags