A furniture dealer deals in only two items-tables and chairs. He has to invest and has storage space of at most 60 pieces. A table costs and a chair . He estimates that from the sale of one table, he can make a profit of and that from the sale of one chair a profit of . He wants to know how many tables and chairs he should buy from the available money so as to maximize his total profit, assuming that he can sell all the items which he buys.

1 Write the linear programming model

2 Solve the model using graphical method

3 Answer the following questions based on simplex method. (1) Write the augmented form of the LP model (2) Identify non-basic variables and basic variables, and give the starting basic solution (3) From this starting point, what is the entering variable of the Simplex method? (4) What is the leaving variable? (5) Write the tabular form of the LP model. (6) Solve the basic feasible solution of the first Iteration and tell if it is the optimal solution

Sol241:

Linear Programming Model: Let x be the number of tables and y be the number of chairs the dealer should buy. Maximize Profit = 250x + 75y Subject to: 2500x + 500y =>=>

Graphical Method: The feasible region is a triangle bounded by the lines 2500x + 500y = 50000, x + y = 60, and the axes x = 0, y = 0. The corner points of the feasible region are (0, 0), (0, 60), and (20, 40). At point (0, 0), the profit is 0. At point (0, 60), the profit is 7560 = 4500. At point (20, 40), the profit is 25020 + 75*40 = 7250. Therefore, the dealer should buy 20 tables and 40 chairs to maximize his profit.

Simplex Method: Augmented form of the LP model: -2500x - 500y =>= 0 Profit = -250x - 75y=>

Non-basic variables: x, y Basic variables: slack variables s1, s2 Starting basic solution: x = 0, y = 0, s1 = 60, s2 = 0

Entering variable: x Leaving variable: s2

Tabular form: x y s1 s2 b

z -250.0 -75.0 0.0 0.0 0.0 s1 1.0 1.0 1.0 0.0 60.0 s2 -1.0 0.0 0.0 1.0 0.0

z 0.0 75.0 0.0 -250.0 -15000.0

Basic feasible solution of the first iteration: x = 0, y = 0, s1 = 60, s2 = 0 This is not the optimal solution since the coefficient of y in the objective function is negative. We need to perform another iteration.