Concepts: Formulating a linear programming problem

2.1 From a word problem to inequalities

A linear programming problem begins as a story. A dealer has money to invest and space to store goods, and wants the largest profit. A factory has machine hours and labour hours, and wants the smallest cost. The first task is to turn the story into algebra, and the steps are always the same.

Name the decision variables first. Let x be the number of one item and y the number of the other. Write the quantity that has to be maximised or minimised as a linear expression in x and y; that is the objective function. Then write each restriction in the story as a linear inequality. Finally add the non-negativity conditions, because negative tables and negative chairs have no meaning. The result is the standard form of the problem.

2.2 The furniture dealer

The example that opens the chapter shows how the steps work. The dealer in the opening example has 50,000 rupees of capital and room for 60 items. Each table ties up 2,500 rupees and brings 250 rupees of profit, while a chair ties up 500 rupees and brings 75. Take x tables and y chairs as the unknowns.

The investment gives one inequality: 2,500 x plus 500 y must be at most 50,000, which simplifies by dividing by 500 to 5x plus y at most 100. The storage gives another: x plus y at most 60. The profit gives the objective Z = 250x + 75y, and the non-negativity gives x and y at least zero. The problem is therefore to maximise Z subject to those four inequalities.

Before solving graphically, the formulation can be checked with extreme choices. Buying tables only allows 20 tables and gives a profit of Rs 5,000. Buying chairs only allows 100 chairs by money but only 60 by storage, and 60 chairs give Rs 4,500. A mixed purchase of 10 tables and 50 chairs gives Rs 6,250. These three points already show that a mixed purchase can beat both extremes, which is the reason the problem needs a systematic method.

2.3 The vocabulary of optimisation

The objective function is a linear function of the decision variables. The constraints are the linear inequalities that restrict them, and the conditions x at least zero, y at least zero are the non-negative restrictions. An optimisation problem asks for the maximum or minimum of such a function under such restrictions, and a linear programming problem is the special case where every relation is linear. The word programming here means planning, not computer programming.

A feasible solution is any point that satisfies all the constraints. The feasible region is the set of all feasible solutions, and a feasible solution that gives the optimum is an optimal solution. Any point outside the region is an infeasible solution. The feasible region is always convex: any two of its points can be joined by a segment that stays inside the region. That convexity is what makes the corner points sufficient for finding the optimum.

2.4 Worked formulations

Example 1. A factory makes two products, A and B. Each unit of A needs 2 hours on machine one and 1 hour on machine two; each unit of B needs 1 hour on machine one and 3 hours on machine two. Machine one is available for 40 hours and machine two for 60 hours. Profit is Rs 30 on A and Rs 40 on B. Formulate the problem. Let x and y be the numbers of units of A and B. The constraints are 2x plus y at most 40, x plus 3y at most 60, and x, y at least zero. The objective is to maximise Z = 30x + 40y.

Example 2. A diet is to contain at least 80 units of vitamin A and 100 units of vitamin C. Food one contains 3 units of A and 4 units of C per kg and costs Rs 10 per kg; food two contains 6 units of A and 3 units of C per kg and costs Rs 12 per kg. Formulate the problem. The formulation is to minimise Z = 10x plus 12y subject to 3x plus 6y at least 80, 4x plus 3y at least 100, and x, y at least zero.

Example 3. A transport company has two types of trucks. Type one carries 20 tonnes and type two carries 40 tonnes. The company must move 1,800 tonnes. Type one costs Rs 6,000 per trip and type two costs Rs 8,000 per trip. Formulate the problem if the company wants the minimum cost. Let x and y be the numbers of trips by the two types. Then 20x plus 40y is at least 1,800, x and y are at least zero, and the objective is to minimise Z = 6,000x plus 8,000y.