Question

Consider the table below:

Products	Labours Hours	Materials	Market demand	Cost (£)
Laptop	3	4	6	8
Desk tops	5	2	8	10
Available resources	500	350	800

Required:

Formulate the LP Model                                                                           

Obtain the dual programme from the formulated LP in (i) above            

Solve the model in (ii) above using simplex method                               

Deduce the solution for primal program using the optimal Simplex tableau obtained in (iii) above                                                                                          

Define the following terms as used in linear programming

Shadow price

Unbound solution

Infeasible solution

Basic solution

Optimal solution

Answer 1

a) Formulation:

Let x1 be the number of laptops purchase
and x2 be the number of desktops purchase

Min Z = 8x1 + 10x2

Subject to constraints

3x1 + 5x2 >= 500
4x1 + 2x2 > = 350
6x1 + 8x2 >=800

Non Negative constraints
x1, x2 >=0

b) Solution:

Problem is

Max Z = 8 x1 + 10 x2

subject to

3 x1 + 5 x2 ≥ 500

4 x1 + 2 x2 ≥ 350

6 x1 + 8 x2 ≥ 800

and x1,x2≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '≥' we should subtract surplus variable S1 and add artificial variable A1

2. As the constraint-2 is of type '≥' we should subtract surplus variable S2 and add artificial variable A2

3. As the constraint-3 is of type '≥' we should subtract surplus variable S3 and add artificial variable A3

After introducing surplus,artificial variables

Max Z = 8 x1 + 10 x2 + 0 S1 + 0 S2 + 0 S3 - M A1 - M A2 - M A3

subject to

3 x1 + 5 x2 - S1 + A1 = 500

4 x1 + 2 x2 - S2 + A2 = 350

6 x1 + 8 x2 - S3 + A3 = 800

and x1,x2,S1,S2,S3,A1,A2,A3≥0

Negative minimum Zj-Cj is -15M-10 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 100 and its row index is 3. So, the leaving basis variable is A3.

∴ The pivot element is 8.

Entering =x2, Departing =A3, Key Element =8