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
??????� ����� �� ���� �ℎ� ����������� �� �,�� ℎ��� �� �������������� ����� �ℎ�
��������� �� �ℎ� ��� ����� (�) ��� (��):
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
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)