CHAPTER

Linear Programming

3.1 INTRODUCTION Linear programming (LP) is a quantitative method for solving problems concerning resource allocation. This study is about managing the resources how the management should allocate the resources efficiently so that maximum benefits can be obtained from the limited resources available. Examples of resources are raw materials, employees, labor hours, machine hours, financial budgets, etc. Since the resources are limited, the management must utilize and allocate them efficiently so that the firm could obtain maximum profit. 3.2 REQUIREMENTS OF A LINEAR PROGRAMMING PROBLEM The linear programming problems have four important properties in common. 1. All Linear Programming problems in practice seek to maximize or to minimize certain quantity, usually profit or cost. We refer to this property as the objective function of a Linear Programming problem. 2. All problems have certain restrictions, or constraints that limit the degree to which we can achieve our objective. Therefore, we want to maximize or minimize the objective function, subject to some limited resources available (constraints). 3. There must be some alternative courses of action to choose from in the solution. If there is no alternative solution to choose from, then we would not need LP. 4. The objective and constraints in Linear Programming problems must be expressed in terms of linear equations or inequalities. The linear mathematical relationship requires all terms used in the objective functions and the constraints involved to be of the first degree. 54

3.3 FORMULATING LINEAR PROGRAMMING PROBLEMS Three components of Linear Programming are the variables, objective and constraints. The variables are continuous, controllable, and non-negative. X1 represents the first variable, X2 represents the second variable, and so on; X1, X 2, X n > 0. The objective of the Linear Programming problem is a mathematical representation of the goals in terms of a measurable objective such as the amount of profit, cost, revenue, or quantity. It must be in a linear function and is represented by one of these two forms: i) Maximize or ii) Minimize C1X1 + C 2X 2 +.. + C nX n, C 1X 1 + C 2X 2 +.. + C nX n.

The constraints are a set of mathematical expressions representing the restrictions imposed on the controllable variables and thereby limiting the possible values of those variables. The mathematical expressions of the constraints can be given either as linear equations (=) or as linear inequalities (<, >, >, <). A linear programming model will be structured to find the values of controllable variables that maximize or minimize a defined linear objective function, subject to a set of defined linear constraints and subject to the non-negativity restrictions. Example 3.1 The owner of a small company that manufactures clocks must decide how many clocks of each type to produce daily in order to maximize profit. The company manufactures two types of clocks, that is regular clocks and alarm clocks. The resources required to produce the clocks are labor and processing machine. The limited resources available every day are as follows: Labor hours Machine hours = 1,600 hours = 1,800 hours

The requirement for resources for each type of clocks is as follows:

55

To produce one unit of regular clock requires 2 hours of labor, and 6 hours of machine time. While to produce one unit of alarm clock requires 4 hours of labor, and 2 hours of machine time. The profit for each unit of regular clock sold is RM 3.00, while the profit for each unit of alarm clock sold is RM 8.00. Determine how many units of each type of clock should be manufactured every day so that the profit is maximum? Solution: First of all we need to define the decision variables involved: Let Let X1 = number of regular clocks to manufacture per day, X2 = number of alarm clocks to manufacture per day.

Now we should construct a table to present the total resources available, the required resources for each clock, and the profit obtained if each unit of the respective clocks is sold. Refer to Table 3.1. The manager must now determine the values of X1 and X2. Table 3.1: The resources, the requirements, and the profits Resources X1 X2 Total resources required (regular clock) (alarm clock) available Labor hours Machine hours Profit per unit 2 6 3 4 2 8 1600 1800

The objective function is to maximize the profit: Maximize profit 3X1 + 8X2 Subject to the constraints: Labor hours constraint : 2X1 + 4X2 < 1600 Machine hours constraint non-negativity conditions : 6X1 + 2X2 < 1800 : X1 > 0, X2 > 0.

This is a two-variable Linear Programming problem. The managers job is to determine how many regular clocks (X1) and how many alarm clocks (X2) to produce in order to maximize the profit. We can solve this problem using a graphical method.

56

Example 3.2 A manufacturer produces two types of cotton cloth: Denim and Corduroy. Corduroy is a heavier grade cotton cloth and, as such, requires 3.5kg of raw cotton per meter whereas Denim requires 2.5kg of raw cotton per meter. A meter of Corduroy requires 3.2 hours of processing time, and a meter of Denim requires 3 hours. Although the demand for Denim is practically unlimited, the maximum demand for Corduroy is 510 meters per month. The manufacturer has 3250kg of cotton and 3000 hours of processing time available each month. The manufacturer makes a profit of RM4.50 per meter from Denim and RM6 per meter from Corduroy. The manufacturer wants to know how many meters of each type of cloth to produce to maximize profit. (a) Formulate a linear programming model for the above problem. Solution: Let X1 be the quantity of denim cloth type to be produced Let X2 be the quantity of corduroy cloth type to be produced Resources required X1 (Denim) 2.5 3.0 4.5 Maximize Profit = 4.50X1 + 6.00X2 Subject to constraints: 2.5X1 + 3.5X2 < 3250 (cotton cloth constraint) 3.0X1 + 3.2X2 < 3000 (processing time constraint) X1 > 0 0 < X2 < 510 (the production of courdroy should not exceed the maximum demand of 510 meters) X2 (Corduroy) 3.5 3.2 6.0 Total resources available 3250 3000

Cotton cloth Processing time Profit

57

Example 3.3 A non-profit organization is raising fund for AIDS victims. They plan to sell two types of soft drinks namely cherry fizz and lemon pop. They decided to set up a soft drink stall in Kuala Lumpur. The resources required to produce the drinks are ingredient A and B. To produce one batch of cherry fizz requires 5 liters of ingredient A and 5 liters of ingredient B, while to make one batch of lemon pop requires 3 liters of ingredient A and 11 liters of ingredient B. There are 30 liters of ingredient A and 55 liters of ingredient B available for use. Due to some marketing strategy, the organization has decided not to produce more than 4 batches of lemon pop at any one time. Profit is made at RM 3 for each batch of cherry fizz and RM 4 for each batch of lemon pop. How many batches of each type should be produced every time so that the profit is maximum? Solution: Define the decision variables: Let X1 = number of batches of cherry fizz to produce, and X2 = number of batches of lemon pop to produce. Resources required Ingredient A Ingredient B Profit Cherry fizz (X1) 5 5 3 Lemon pop (X2) 3 11 4 Resources Available 30 55

From the table we can write the mathematical inequalities as follows: Constraints: 5X1 + 3X2 < 30; 5X1 + 11X1 < 55; X1 > 0, X2 < 4 (not more than 4 batches of lemon pop to be produced)

58

Objective function: The total profit made is 3X1 + 4X2, and this is to be maximized Thus, the linear programming model may be written as: Maximize 3X1 + 4X2 subject to: 5X1 + 3X2 < 30; 5X1+ 11X2 < 55; X2 < 4; X1 > 0.

3.4 GRAPHICAL SOLUTION TO A LINEAR PROGRAMMING PROBLEM If a linear programming problem involves only two decision variables (X1 and X2), the solution may be found using the graphical technique. In practice, this technique is not commonly employed since most LP problems involve more than two variables. However, the technique is illustrated using the problem in Examples 3.1. In the graphical solution method, what you need to do is: a) b) c) d) Obtain the linear equation for each constraint in the problem Plot the linear equations of the constraints on the graph Determine the feasible region based on the inequalities in (a) Obtain the feasible solution points based on the feasible region in (c) e) Obtain an optimal solution for the problem by applying each feasible solution point into the objective function.

59

3.4.1 THE FEASIBLE REGION AND CORNER POINTS METHOD Example 3.4 Consider the problem in Example 3.1. Find the optimal solution to the problem by using the graphical method. The objective is to maximize the profit: Maximize 3x1 + 8x2. Subject to: The Constraints: labor hours machine hours non-negativity conditions Solution: Firstly, plot all linear equations of the constraints on the graph. Secondly, shade the area covered by the respective inequality ( , etc) of the constraints. Thirdly, determine the feasible region, that is the common region which belongs to the inequalities. The feasible region is the common area or the area that overlapps all constraints. Find all coordinates (X1 and X2) that fall in the feasible region. The coordinates that fall in the feasible region are the feasible solutions for the problem at hand. Solve all intersections between constraints and also determine their coordinates. Finally, input each coordinate of the feasible solution into the objective function and determine its value. For the maximization objective function, the optimal solution occurs at the feasible solution that yields the maximum value. And for the minimization objective function, the optimal solution occurs at the feasible solution that yields the minimum value. : 2x1 + 4x2 < 1600 -----(1) : 6x1 + 2x2 < 1800 -----(2) : x1, x2 > 0.

60

Applying to Example 3.4. The first thing to do is to draw both equations (Equation 1 and Equation 2) on the same graph. In order to draw any equation, we need to obtain at least two coordinates from the respective equation. Constraint Equation (1) 2X1 + 4X2 = 1600 Let X2 = 0, then we have 2X1 + 4(0) = 1600 2X1 = 1600 or X1 = 800 Then (800, 0) will be the first coordinate on the graph. Let X1 = 0, then we have 2(0) + 4X2 = 1600 4X2 = 1600 or X2 = 400 Then (0, 400) will be the second coordinate on the graph. Now, you can draw the linear equation 2X1 + 4X2 = 1600 by connecting the two coordinates. Constraint Equation (2) 6X1 + 2X2 = 1800 Let X2 = 0, then we have 6X1 + 2(0) = 1800 6X1 = 1800 or X1 = 300 Then (300, 0) will be the first coordinate on the graph. Let X1 = 0, then we have 6(0) + 2X2 = 1800 hence 2X2 = 1800 or X2 = 900 Then (0, 900) will be the second coordinate on the graph. Now, you can draw the linear equation 6X1 + 2X2 = 1800 by connecting the two coordinates.

X2
(0,900) 900

(0,400) 400

(300,0)

(800,0)

X1

61

Once we have plotted the two constraints, we will find the two equations intercept with one another. In this case, we have to solve the two equations simultaneously to determine the coordinate where the two equations intercept. How to estimate the coordinate of interceptions between the two equations: The equation of constraints: Machine Hours Labor Hours Non negativity conditions : 6X1 + 2X2 = 1800 : 2X1 + 4X2 = 1600 : X1 > 0, X2 > 0

Divide the second equation (labor hours) by 2, we have: 1/2 [2X1 + 4X2 = 1600] Machine Hours Labor Hours X1 + 2X2 = 800

: 6X1 + 2X2 = 1800 ----(1) : X1 + 2X2 = 800 ----(2)

Subtract the two equations (1) (2), we obtain: 6X1 + 2X2 = 1800 ----(1) (-) X1 + 2X2 = 800 ----(2) 5X1 Therefore X1 = 200 Then, substitute X1 = 200 into equation (2): 200 + 2X2 2X2 2X2 Therefore = 800 = 800 200 = 600 = 1000

X2 = 300

So the interception point beween the two equations occurs at (200, 300)

62

Figure 3.1: Feasible Region as defined by all constraints for Example 3.4 X2
(0,900) 900

(0,400) 400 (200,300)

(0,0) 0

(300,0) 300

(800,0)

X1
800

From Figure 3.1, the feasible solutions are (0, 400), (200, 300), and (300, 0). For your information, the feasible solution only occurs at the coordinates in the feasible region. The feasible region is the region covered by all constraints requirement in the problem (in this case there are two constraints). Applying the objective function Maximize 3X1 + 8X2 on the feasible solution, we have: At (0, 400) the profit is 3(0) + 8(400) = RM3,200 * = RM900

At (200, 300) the profit is 3(200) + 8(300) = RM3,000 At (300, 0) the profit is 3(300) + 8(0) The objective of the above linear programming problem is to maximize the profit. The maximum profit RM3,200 occurs at (0, 400). Hence, the company should decide to produce X1 = 0 (regular clock) and X2 = 400 (alarm clock) in order to maximize the profit based on the current constraints.

63

3.4.2 SOLVING THE MINIMIZATION PROBLEMS Sometimes the problem is stated in terms of the cost of materials used in production instead of the profit contribution for each product. In this case the objective function should be changed to minimizing the cost. Example 3.5 A firm produces 2 types of chemicals namely AA and BB. Chemical AA costs RM2 per liter and chemical BB costs RM3 per liter to manufacture. Over the week, at least 6 liter of AA and 2 liter of BB must be produced. One of the raw materials needed to make each chemical is in short supply and only 30gm are available. Each liter of AA requires 3gm of this material while each liter of BB requires 5gm. How many liters of AA and BB should the firm produce in order to minimize the total cost? Solution: Define decision variables: Let x1 = number of liters of chemical AA to be produced Let x2 = number of liters of chemical BB to be produced Define the objective function; Minimize total cost = 2x1+ 3x2 Define the constraints; x1 > 6 (at least 6 litres of AA should be produced) x2 > 2 (at least 2 litres of BB should be produced) 3x1+ 5x2 < 30; Thus, the problem becomes: Minimize total cost = 2x1 + 3x2 Subject to constraints: x1 > 6 (at least 6 liters of x1 to be produced)

x2 > 2 (at least 2 liters of x2 to be produced)

x1, x2 > 0 (the non-negativity constraints)

64

Again, we should plot the equation of constraints, obtain the feasible region, the feasible solution points, and finally apply the objective function on the feasible solution points to determine the optimal solution.

Figure 3.2: Feasible Region for Example 3.5

From the graph (Figure 3.3), the feasible solution points occur at (6, 12/5), (6, 2), and (20/3, 2) Applying the objective function 2X1 + 3X2, we have: At (6, 12/5) : 2(6) + 3(12/5) At (6, 2) : 2(6) + 3(2) At (20/3, 2) : 2(20/3) + 3(2) = RM19.2 = RM18.0 (minimum cost) = RM19.3

Hence the optimal solution occurs at X1 = 6, X2 = 2

x1 = number of liters of chemical X to be produced x2 = number of liters of chemical Y to be produced

65

Example 3.6 AGM Super-Bike Company (ASC) has the latest product on the upscale toy market; boys, girls and toddlers bike in bright fashion colors, a strong padded frame, chromeplated chairs, brackets and valves, and a non-slip handle bar. Due to the best sellers market for high quality toys, ASC is confident that it can sell all the bicycles produced, at the following prices; boys bike at RM 420, girls bike at RM 350 and toddlers bike at RM 150. The companys accountant has determined that direct labor costs will be 45% of the price ASC receives from the boys model, 40% of the price ASC receives from the girls model and 30% from the toddlers model. Production costs other than labor, but excluding painting and packaging are RM 45 per boys bike, RM 35 per girls bike and RM 20 per toddlers bike. Painting and packaging cost is RM 25 per bike regardless of the model. ASC plants overall production capacity is 400 bicycles per day. However realizing that the demand for boys bikes are more than girls bikes, the marketing manager insists that ASC must produce not more than 200 units of girls bikes, and not more than 100 units of toddlers. Each boys bikes requires 3 labor hours, each girls bike requires 2.4 hours and each toddlers bike requires 2 hours to complete. ASC currently employs 120 workers, who work 8-hours per day. Assume the company does not retrench workers since the company believes its stable work force is one of its biggest assets. (a) Formulate the above Linear Programming problem. Solution: First of all, we need to define the decision variables as follows: Let: X1 be the number of boys bikes produced per day. X2 be the number of girls bikes produced per day. X3 be the number of toddlers bikes produced per day.

66

Variables
Selling price (RM) Labor Cost Production Cost Painting Cost Net Profit

X1 420 -189 -45 -25 161

X2 350 -140 -35 -25 150

X3 150 -45 -20 -25 60

Requirements X1 X2 X3 X2 X3 Labor Objective function is: X1 3.0

Variables X2 X2 2.4 X3 X3 2.0

Resources 400 200 100 960 hours

Maximize profit: 161X1 + 150X2 + 60X3 Subject to (constraints) : X1 + X2 + X3 < 400 (capacity constraints) X2 < 200 (production constraint for X2 girls bike) X3 < 100 (production constraint for X3 toddlers) 3 X1 + 2.4 X2 + 2 X3 < 960 (labor hours constraint) X1, X2, X3 > 0 (non-negativity constraints)

67

Example 3.7 Toy Race Car Company manufactures three different race cars called Racer_1, Racer_2, and Racer_3. The resources required to make the products are technical services, labor and administration. Table below provides the requirements for the production. The profits for each unit sold for Racer_1, Racer_2, and Racer_3 are RM10, RM6, and RM4 respectively. Product Racer 1 Racer 2 Racer 3 Technical Services (hour) 1 2 3 Labor (hour) 10 4 5 Administration (hour) 2 2 6 Unit profit (RM) 10 6 4

The resources available for each week are 100 hours of technical services, 600 hours of labor, and 300 hours of administration. (a) Formulate the problem as a linear programming problem. Solution: Let X1 be the number of Racer_1 to be produced. X2 be the number of Racer_2 to be produced. X3 be the number of Racer_3 to be produced. The limited resources available are technical services (100 hours), labor (600 hours), and administration (300 hours). The above informations are summarized in the following table: Resources Technical Labor Administration Profit X1 1 10 2 10 X2 2 4 2 6 X3 3 5 6 4 Total Resources 100 600 300

The objective function: Maximize profit 10X1 + 6X2 + 4X3 Subject to (constraints): 1X1 + 2X2 + 3X3 < 100 (Technical services constraints) 68

10X1 + 4X2 + 5X3 < 600 (Labor constraints) 2X1 + 2X2 + 6X3 <300 (Administration constraints) X1, X2, X3 > 0 (Non-negativity constraints)

3.4.3 SPECIAL CASES IN LINEAR PROGRAMMING

Case 1: Infeasibility A condition that arises when there is no solutions to a linear programming that satisfies all of the constraints; graphically, no feasible region exists. Case 2: Unboundedness A linear programming problem will not have a finite solution; graphically, the feasible region is open-ended. Case 3: Redundancy The presence of redundant constraints; simply one that does not affect the feasible solution region. Case 4: Alternate Optimal Solutions Two or more feasible solutions that give the same optimal value; graphically, when the slope of the objective function is parallel to one of the constraints (infinitely many solutions).

3.5 THE SIMPLEX METHOD In the previous section, we saw how a linear programming problem with only two variables (X1 and X2) was solved by using the graphical method. However, if the linear 69

programming problem has more than two variables (X1, X2, .,Xn), the graphical method is impossible to apply since normal graphs only possess two dimensions. In this section, an algebraic method is developed to solve Linear Programming (LP) problems with more than two variables. The technique, called the simplex method, is an iterative process that begins with the initial solution and, by means of computational routines, moves to an improved solution until the optimal or final solution is reached. In particular, for a two-variable problem, we have seen that it is only necessary to examine the feasible solution points obtained in the feasible region, and this is precisely what the simplex method does. Essentially the method repeatedly searches for a better solution point until the objective function cannot be improved further even if we move to another feasible solution point. In this section, we will not discuss the process in details since its complexity requires a longer medium of instruction. In addition only Mathematicians and Statisticians have the capacity and patience to discuss such process. For us non-Mathematicians and nonStatisticians, it is relevant for us to be more interested in how to set-up the actual problem into the initial simplex table, and the interpretation of the results in a final table in term of management problem; assuming the process would be carried out by a computer package called QM for Windows (manual computation is very tedious). The computer package is available in the market and is being used by managers to analyze their data. The manager only needs to know how to intepret the results in the final table for their decision making.

3.5.1 HOW TO SET UP THE INITIAL SIMPLEX SOLUTION Before setting up the initial simplex table, it is essential to write the problems in their standard form:

70

a) b) c) e)

All decision variables (X1, X2, .,Xn) must be non-negative (> 0). The objective function is either to maximize (for profit) or to minimize (for cost) The Right-Hand-Side of each constraint is a non-negative (quantity of resources). d) All constraints must be in the form of mathematical equations. We need to introduce the slack variables to represent the unused resources. * Slack variables will become an Identity Matrix in the initial solution.

Example 3.8 (APR 2001) Obtain the initial simplex table for Example 3.7 Objective function: Maximize profit 10X1 + 6X2 + 4X3 Subject to (constraints): 1X1 + 2X2 + 3X3 < 100 (Technical services constraints) 10X1 + 4X2 + 5X3 < 600 (Labor constraints) 2X1 + 2X2 + 6X3 < 300 (Administration constraints) X1, X2, X3 > 0 (Non-negativity constraints) Solution: Since we have 3 resources in each of the equations, we need to introduce three slack variables namely S1, S2, and S3 to represent the unused resources 1 (technical services hours), resources 2 (labor hours), and resources 3 (administration hours) respectively. Now, we write the above equation using the standard form of simplex method. Maximize profit 10X1 + 6X2 + 4X3 + 0S1 + 0S2 + 0S3 1X1 + 2X2 + 3X3 + 1S1 + 0S2 + 0S3 10X1 + 4X2 + 5X3 + 0S1 + 1S2 + 0S3 2X1 + 2X2 + 6X3 + 0S1 + 0S2 + 1S3 = 100 = 600 = 300

Profit contribution for each variable (X1, X2, X3, S1, S2, S3) 10 6 4 0 0 0 X1 X2 X3 S1 S2 S3 1 2 3 1 0 0 10 4 5 0 1 0

Quantity 100 600 71

300

The initial simplex table for Example 3.8 Cj

Solution Mix S1 S2 S3 Zj Cj - Z j

10 x1
1 10 2 0 10

6 x2
2 4 2 0 6

x3
3 5 6 0 4

0 S1 1 0 0 0 0

0 S2 0 1 0 0 0

0 S3 0 0 1 0 0

Resources Quantity 100 600 300

0 0 0

Example 3.9 Solve the following problem using the simplex method. Maximize (profit): Subject to 3x1 + 8x2 2x1 + 4x2 < 1600 (labor hours constraint) 6x1 + 2x2 < 1800 (machine hours constraint)

x2 < 350 (materials constraint) x1, x2 > 0;

Where S1, S2, S3 are called Slack Variables (representing unused resources) The above equations are now expressed in Table 3.2. Table 3.2: Initial Simplex Table for Example 3.9 Cj
profit

Solution Mix S1 S2 S3 Zj

3 x1
2 6 0 0

8 x2
4 2 1 0

0 S1 1 0 0 0

0 S2 0 1 0 0

0 S3 0 0 1 0

Resources Quantity 1600 1800 350 0 72

0 0 0

Cj - Z j

Always remember that the optimal solution occurs at the identity matrix. From the above table, we can intepret the initial solution as follows: S1 = 1600, S2 = 1800, S3 = 350 All resources remain in original quantity (unused) since the production has not started The solution for decision variables x1 = 0, x2 = 0 The total profit = 0. The Value of Zj and Cj - Zj row: The Zj value in each column in the table is the sum of each number in the C j column multiplied by the corresponding number in the decision variable column. For example: The Zj value under variable x1 is the summation of 0(2) + 0(6) + 0(0) = 0 The Zj value under variable x2 is the summation of 0(4) + 0(2) + 0(1) = 0 The Zj value for the quantity column provides the profit obtained in the current solution. In this case the profit is 0(1600) + 0(1800) + 0(350) = 0 Meanwhile, the Cj - Zj value in each column represents the net profit for each variable. To compute these Cj - Zj values, simply deduct the Zj value obtained for each decision variable from the Cj value at the top of every variable. For example, the Cj - Zj under x1 is 3 0 = 3. The the Cj - Zj under x2 is 8 0 = 8. The same steps are used to compute the values for S1, S2, and S3 respectively. 3.5.2 SIMPLEX SOLUTION PROCEDURES The Simplex Algorithm 1. For the maximization problem, if there are variables that have positive signs in row Cj- Zj, select the highest number and the variable which corresponds to this is called

73

the entering variable. (If all numbers in the row Cj - Zj are either 0 or negative values, an optimal solution has been reached). 2. Find the ratios of the resources quantity to the numbers in the column of the entering variable. Select the smallest ratio. The variable which corresponds to this smallest ratio, will be the variable to be omitted from the solution mix. This variable is called the leaving variable. 3. The pivot number is the number at the intersection of the column of the entering variable and the row of the leaving variable. Divide every number in the pivot row by the pivot number and this row (R) is then written in the next table in the same row position as it was in the previous table. 4. To obtain the remaining rows in the new table, it should be firstly noted that the column of a variable in the current solution mix are all zeros except for a 1 in the row corresponding to this variable. This condition must now be obtained for the variable that is entered in (1). This is obtained by adding and subtracting suitable multiples of row R from the rows of the previous table. When this is done, return to (1). For the problem at hand, this algorithm should be applied twice to obtain a final (third) simplex table. The final simplex table (using simplex algorithm) is shown in Table 3.3

Table 3.3 Final Simplex Table for Example 3.9 Cj 3 0 8 Solution Mix

3 x1
1 0 0 3 0

8 x2
0 0 1 8 0

x1
S2

x2
Zj Cj - Z j

0 S1 0.5 -3 0 1.5 -1.5

0 S2 0 1 0 0 0

0 S3 -2 10 1 2 -2

Resources Quantity 100 500 350 3100

74

3.5.3 INTERPRETATION OF SIMPLEX SOLUTION From the final table (Table 3.3), the optimal solution for this production is as follows: X1 = 100, X2 = 350, S1 = 0, S2 = 500, S3 = 0, with total profit = $ 3100. i.e. To maximize the total profit, the company should produce 100 units of X1 and 350 units of X2. S1 = 0 and S3 = 0, mean the labor hours and assemblies hours are all used (balance = 0). S2 = 500 means 500 hours of processing time left unused at the end of production process. (i.e. only 1800-500 = 1300 hours of processing are used). For the next production, the management should allocate only 1300 hours of processing time. This optimal solution (as expected) agrees with those found by graphical method. It is clear that with the number of arithmetic calculations involved in the simplex method, an arithmetic error would occur when solving an LP problem manually. For this reason, we will be solving the LP problems with the aid of a computer package. Nevertheless, it is important to understand how the simplex algorithm works, since this knowledge is very useful when performing a sensitivity analysis on the solution. 3.5.4 SPECIAL CASES IN LINEAR PROGRAMMING FIVE special cases may arise when solving an LP problem using the simplex method. Case 1 : No feasible solution (infeasibility) If there are no values of the decision variables that satisfy all of the constraints, then the problem is said to have no feasible solution. This case can be recognized in the simplex method when one or more artificial variables appear with a positive value in the final table. Case 2 : Alternative optimal solution For some LP problems, there may be more than one set of values for the decision variables that gives the optimal value of the objective function. In the simplex method, this can be recognized when there is a zero value.

75

In row Cj - Zj of the final table under a variable that is not in the final solution mix, such LP problems are said to have an alternative optimal solution. An alternative optimal solution may be found by entering the said variable into a solution mix and performing a further iteration on the table. Case 3 : Unbounded solution In some LP problems, the value of the objective function may be made as large (maximization) or as small (minimization) as we please. Such problems are said to have an unbounded solution. They can be recognized in the simplex method when, at any iteration for a maximization (minimization) problem there is a positive (negative) number in row Cj - Zj and zero and/or negative number in the column underneath. Case 4 : Unbounded feasible region but bounded optimal solution Although the feasible region is unbounded, the optimal solution is bounded; i.e. the objective function has a finite optimal value. An unbounded feasible region can be recognized in LP problem when in any column (excluding row Cj - Zj) of any table, there are zero and/or negative numbers. The solution will be unbounded only if in addition to this condition, there is a positive (negative) in row Cj - Zj in that column for a maximization (minimization) problem. Case 5 : Degenerate solution In Step (2) of the simplex algorithm, it was stated that if there was a tie for minimum ratio to decide the variable leaving the solution mix then the tie should be broken arbitrarily. At the next iteration, however, the values of those variables in the tie that did not leave the solution mix will be zero. A solution in which one or more of the variables in the solution mix has a value of zero is said to be degenerate. This degeneracy in LP problem may cause a situation, in which the simplex iteration enter a loop and repeat the same sequence of iterations without reaching the optimal solution, fortunately this does not happen very often in practice.

3.6 THE DUAL IN LINEAR PROGRAMMING 76

Every linear programming problem has a twin problem associated with it. One problem is called primal while the other is called dual. In an easier term, the dual is simply looking at the same problem but from the opposite perspective. For example, the primal is looking at maximizing profit but the dual is looking at minimizing resources. Looking at the dual perspective is useful for two reasons: 1) There is less computation required to solve the dual problem compared to solving the primal problem 2) The solution of the dual problem has a meaningful economic interpretation. For example, in the dual solution, we can have the actual prices that should be paid for each unit of extra resources if the company wants to continue with the production (shadow price).

3.6.1 THE RELATIONSHIP BETWEEN THE PRIMAL AND DUAL PROBLEMS 1. The primal problem is maximization, while the dual problem is minimization. 2. The maximization of primal problem has < (less or equal) constraints while the minimization of dual problem has > (greater or equal constraints). 3. Each constraint of the primal would become a variable in the dual problem. 4. The quantity of resources of the constraints in primal problem would become the coefficient of the objective function in the dual problem. 5. The coefficient of objective function in the primal would become the quantity of the constraint in the dual 6. From a symmetry, the dual of the dual problem would be the primal problem.

Example 3.10 Primal problem Maximize 3X1 + 4X2

77

subject to 5X1 + 3X2 < 30 : Y1 5X1 + 11X2 < 55 : Y2 X2 < 4 X1, X2 > 0. : Y3

Dual problem

Minimize 30Y1 + 55Y2 + 4Y3 subject to 5Y1 + 5Y2 >3 3Y1 + 11Y2 + Y3 > 4 Y1, Y2, Y3 > 0

Example 3.11 Maximize subject to 3X1 + 2X2 + 4X3 2X1 + X2 + 5X3 < 40 : Y1 X1, X2, X3 > 0. The corresponding dual problem is Minimize subject to 40Y1 + 10Y2 2Y1 + 3Y2 > 3 Y1 4Y2 > 2 5Y1 + Y2 > 4 Y1, Y2 > 0. * If the maximization of primal problem has < constraints, then the minimization of dual problem will have > constraints. * The optimal values of the primal and dual objective functions are equal.

3X1 - 4X2 + X3 < 10 : Y2

3.6.2 THE OPTIMAL SOLUTION FOR DUAL VARIABLES

78

The optimal solution for the dual variables (Y1, Y2, ..Yn) can be obtained from the final simplex table of primal problem under the resources columns (S1, S2, ..,Sn). Since the objective function of dual is to minimize resources, the optimal solutions for Y1, Y2, ..Yn can be found under S1, S2, ..,Sn respectively in the row Cj - Zj (ignore the negative sign) of the final simplex table (primal). Example 3.12 Using Example 3.9: Maximize (profit): 3X1 + 8X 2 + 0S1 + 0S2 + 0S3

Subject to 2X1 + 4X2 + 1S1 + 0S2 + 0S3 = 1600 : Y1 6X1 + 2X2 + 0S1 + 1S2 + 0S3 = 1800 : Y2 0X1 + 1X2 + 0S1 + 0S2 + 1S3 = 350 : Y3 X1, X2, S1, S2, S3 > 0.

Table 3.4: Initial Simplex Table for Example 3.9 (problem in the primal form) Cj Solution 0 0 0 Resources 3 8 X1 X2 S1 S2 S3 Mix Quantity 0 0 0 S1 S2 S3 Zj Cj - Z j 2 6 0 0 3 4 2 1 0 8 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1600 1800 350 0

The dual variable Y1 corresponds to the first primal constraint that contains the slack variable S1 (unused resources 1). The dual variable Y2 corresponds to the second primal constraint that contains the slack variable S2 (unused resources 2). The dual variable Y3 corresponds to the third primal constraint that contains the slack variable S3 (unused resources 3). Hence, the optimal value of Y1 can be obtained under column S1 in row Cj - Zj.

79

That is, Y1 = 0, Y2 = 0, Y3 = 0 in the initial simplex table (Table 3.4).

Table 3.5: Final Simplex Table for Example 3.9 (problem in the primal form) Cj 3 0 8 Solution Mix X1 S2 X2 Zj Cj - Z j X1 (3) 1 0 0 3 0 X2 (8) 0 0 1 8 0 S1 (0) 0.5 -3 0 1.5 -1.5
(Y1)

S2 (0) 0 1 0 0 0
(Y2)

S3 (0) -2 10 1 2 -2
(Y3)

Resources Quantity 100 500 350 3100

* Y1, Y2, Y3 are the shadow prices for resources 1, 2, and 3 respectively

From the final simplex table of the primal, we can intepret the solution as follows: X1 = 100 units, X2 = 350 units S1 = 0 (all resource 1 is used) S2 = 500 (500 units of resource 2 is unused) S3 = 0 (all resource 3 is being used) Maximum profit = 3 (100) + 8 (350) = RM 3,100.00 (Maximum) 3.6.3 INTERPRETATION OF THE DUAL VARIABLES The corresponding dual problem for Example 3.12 is: Minimize (resources): 1600Y1 + 1800Y2 + 350Y3 Subject to 2Y1 + 6Y2 Y1, Y2, Y3 > 0 The optimal values for dual variables Y1, Y2, Y3 are located in row Cj - Zj under S1, S2, S3 columns respectively in the final simplex table (Table 3.5). From Table 3.5, we get Y1= 1.5, Y2 = 0 and Y3 = 2. >3

4Y1 + 2Y2 + Y3 > 8

80

If we input the values of Y1= 1.5, Y2 = 0 and Y3 = 2 into the objective function: Minimize (resources): 1600Y1 + 1800Y 2 + 350Y3 , we will get : The total resources used = 1600 (1.5) + 1800 (0) + 350 (2) = RM 3100 (Minimum). This value (RM3100) is equivalent to the maximum profit under the primal form. The optimal value of a dual variable which is associated with a primal constraint gives an indication of how much the objective function (profit) increases for every unit increase in the resources provided that the current solution remains feasible and optimal. That is, if the resources of a primal constraint is increased by one unit, the value of the objective function is increased by Yi unit as long as the current solution mix is feasible. In other words, the optimal values of the dual variable (Y 1, Y2, Y3) are called shadow prices for resources 1, 2, and 3 respectively. These values indicate the actual worth of each resources if the management wants to obtain additional resources to continue production. The dual variable Yi may be interpreted as the per-unit contribution of the ith resource (Si) to the value of the objective function. In Example 3.12, the optimal values of the dual variables are Y1 = 1.5, Y2 = 0 and Y3 = 2. Remember, the solution must always be greater than zero (Y1, Y2, Y3 > 0), hence all negative values are changed to positive values. The interpretation of Y1, Y2, Y3: Each additional unit of the first resource (labor hours) would contribute RM1.50 to the profit in the primal objective function. Hence, if the management wants to obtain additional labor (overtime hours), the cost should not be higher than RM1.50 per hour. In other words, RM1.50 is the shadow price for labor hours. Each additional unit of the second resource (processing hours) contributes RM0.

So, at the moment any increase in processing hour does not have any monetary value or does not contribute anything to the profit. This is because of the current production which

81

has resulted in the unused resource 2 (S2 = 500). Any increase of this resources is unnecessary. Each additional unit of the third resource (alarm assemblies) would contribute RM2.00. In other words, this additional resource should not cost more than RM2.00 per unit since RM2.00 is the shadow price for resource 3.

EXERCISES

(APR 2001) The Toy Race Car Company manufactures three different race-cars called Racer 1, Racer 2, and Racer 3. The resources required to make the products are technical services, labour and administration. The table below gives the requirements for the production. Product Racer 1 Racer 2 Racer 3 Technical Services (hour) 1 2 3 Labor (hour) 10 4 5 Administration (hour) 2 2 6 Unit profit (RM) 10 6 4

The resources available for each week are 100 hours of technical services, 600 hours of labor, and 300 hours of administration. (a) Formulate the problem as a linear programming problem. 82

(b)

The optimal simplex table for the above problem is given below. The S1, S2, S3 are the slack variables for technical services, labor, and administration hours respectively. Cj 6 10 0 Solution Mix X2 X1 S3 Zj Cj - Zj 10 X1 0 1 0 10 0 6 X2 1 0 0 6 0 4 X3 5/6 1/6 4 20/3 -8/3 0 S1 5/3 -2/3 -2 10/3 -10/3 0 S2 -1/6 1/6 0 2/3 -2/3 0 S3 0 0 1 0 0 Resources Quantity 66.67 33.33 100.00 733.32

(i) Specify the optimal daily production levels for the company for the three products. What is the total profit? (ii)Which resource is not fully utilized? If so, how much is the spare capacity? (iii) Write down the dual of the problem. (iv) Based on the table, obtain the solution of the dual problem.

(SEPT 2002) a) Summit Events Management plans to rent out sales booths during the Ramadan Food and Fashion Fair. The booths are to be set up at a popular shopping mall. There should be a maximum of 100 booths, comprising three different types: Type 1, Type 2, and Type 3. The rental will be at a flat rate of RM500 each. However, the cost of setting up the booth varies depending on the type of booth. The cost per unit and the number of hours to set up each booth are as follows: Cost per unit No. of man-hours Type 1 RM 400 1 Type 2 RM 200 2 Type 3 RM 300 1

83

Summit has a RM32,000 budget to cover the cost. There are 4 workers available to set up the booths. Each of them works 8 hours per day for 5 days. Formulate a linear programming problem to determine the number of each type of booth to maximize profit: Let: X1 = Quantity of Type 1 booth X2 = Quantity of Type 2 booth X3 = Quantity of Type 3 booth S1=slack variable for the number of booths S2=slack variable for the budget S3=slack variable for man-hour

b) The following is the final simplex table for the above problem. Cj 200 0 300 Solution Mix X3 S2 X2 Zj Cj-Zj i. ii. iii. iv. v. (c) 100 X1 1 10 0 200 -200 300 X2 0 0 1 300 0 200 X3 1 0 0 200 0 0 S1 2 -40 -1 100 -100 0 S2 0 1 0 0 0 0 S3 -1 10 1 100 -100 Resources 40 8000 60

State the optimal solution and interpret the values of all variables. Determine the maximum profit. How much of the budget will be used to reach the optimal solution? Formulate the dual and determine the optimal solution. What would be the effect on the profit if 5 more man-hour is made available? Puncak Distribution packages distributes industrial supplies. A standard

shipment can be packaged in a class A container, a class B container, or a class C container. One unit of class A container yields a profit of RM9, one unit of class B container yields a profit of RM7, and one unit of class C container yields a profit of RM8. Each shipment requires a certain amount of packing materials, material I and material II ( in meters), and packing time (in hour). The final simplex table of the problem is given below: Cj 9 Solution Mix X1 RM9 X1 1 RM7 X2 0 RM8 X3 0.8 RM0 S1 0.6 RM0 S2 -0.4 RM0 S3 0 Resources 32

84

7 0

X2 S3 Zj Cj - Z j

0 0 9 0

1 0 7 0

0.8 -0.6 12.8 -4.8

-0.4 -0.2 2.6 -2.6

-0.6 -0.2 0.6 -0.6

0 1 0 0

12 6 372

X1, X2 and X3 represent the number of class A, class B, and class C containers respectively. S1, S2 and S3 are the slack variables representing the unused amount of packing materials (I and II) and packing time respectively. (i) (ii) What is the optimal number of each class of containers and the total profits? Puncak is considering getting an extra packing material I at a cost of RM2.00 per meter. Should the firm do so? (iii) What is the optimal solution of the dual problem? Interpret.

(MAR 2004) Muarlite Company produces three types of desk lamps: Lamp A, Lamp B and Lamp C. The lamps require three limited resources: fiberglass, plastic and wood. The resource requirements for each lamp are as follows: Lamp A requires 1 unit of fiberglass, 3 units of plastic and 2 units of wood. Lamp B requires 2 units of fiberglass and 8 units of wood. Lamp C requires 1 unit of fiberglass and 2 units of plastic. There are 500 units of fiberglass, 460 units of plastic and 840 units of wood available each week. Profits from the sales of Lamp A, Lamp B and Lamp C are RM30, RM10 and RM40, respectively. (a) Formulate a linear programming model for this problem with the objective of maximizing the weekly profit.

(b)

The optimal solution to the above problem is given by the following simplex table.

Cj 0

Solution Mix S1

30 X1 -1

10 X2 0

40 X3 0

0 S1 1

0 S2 -0.5

0 S3 -0.25

Resources 60 85

40 10

X3 X2 Zj Cj - Z j

1.5 0.25 62.5 -32.5

0 1 10 0

1 0 40 0

0 0 0 0

0.5 0 20 -20

0 0.125 1.25 -1.25

230 105

X1, X2 and X3 are the respective productions of Lamp A, Lamp B and Lamp C. S1, S2 and S3 are the respective amounts of slacks of fiberglass, plastic and wood. (i) Obtain the quantity of each type of desk lamps to produce per week and determine the total weekly profit. (ii) (iii) (iv) State the resource(s) that is or are not fully utilized in the optimal production. Formulate the dual of the problem. Obtain the optimal solution of the dual and briefly explain the values.

(OCT 2004) The objective of a linear programming problem is to maximize profit. The optimal solution to the problem is given by the following simplex table. Cj 40 0 50 Solution Mix X2 S2 X1 Zj Cj - Zj 50 X1 0 0 1 50 0 40 X2 1 0 0 40 0 0 S1 0.32 -0.32 -0.2 2.8 -2.8 0 S2 0 1 0 0 0 0 S3 -0.12 0.12 0.2 5.2 -5.2 Quantity 12 8 30

Where S1, S2 and S3 are the slacks for Resources 1, 2 and 3 respectively. i) ii) iii) Write down the objective function for the above problem. Explain why this solution is already optimal. Obtain the optimal solution and determine the total profit. iv) Are there any changes in the total profit when additional units of Resource 2 are obtained? Explain your answer. v) Is it worthwhile to obtain Resource 3 at RM5.00 per unit? Explain your answer.

86

(SEPT 2001) A manufacturer produces two types of cotton cloth: Denim and Corduroy. Corduroy is a heavier grade cotton cloth and, as such, requires 3.5kg of raw cotton per meter whereas Denim requires 2.5kg of raw cotton per meter. A meter of Corduroy requires 3.2 hours of processing time, and a meter of Denim requires 3 hours. Although the demand of Denim is practically unlimited, the maximum demand for Corduroy is 510 meters per month. The manufacturer has 3250kg of cotton and 3000 hours of processing time available each month. The manufacturer makes a profit of RM4.50 per meter from Denim and RM6 per meter from Corduroy. The manufacturer wants to know how many meters of each type of cloth to produce to maximize profit. (a) Formulate a linear programming model for the above problem. (b) The final simplex table of the LP problem is shown below:

Cj 0 4.5 6

Solution Mix S1 X1 X2 Zj Cj Zj

4.5 X1 0 1 0 4.5 0

6 X2 0 0 1 6 0

0 S1 1 0 0 0 0

0 S2 -0.83 0.33 0 1.5 -1.5

0 S3 -0.83 -1.07 1 1.2 -1.2

Quantity 325 456 510

X1 = number of meters of corduroy produced, X2 = number of meters of denim produced, S1, S2 and S3 are the slack variables for cotton usage, processing time and demand for corduroy respectively. (i) Determine the optimal production level and calculate the maximum profit obtained. (ii) How many cotton (S1) and processing time (S2) are left over the optimal solution? (iii) What is the maximum amount the manufacturer is willing to spend for an additional processing time? 87

(iv) What will be the effect on the optimal solution if the manufacturer could only obtain 3000 kg of cotton per month? Justify your answer.

(MAR 2005) a. A marketing company is doing research in order to maximize its profit of selling products X, Y, and Z. These products will be sold from door to door. X is sold at RM7 per unit. It takes a sales person 10 minutes to sell one unit of X and it costs RM1 to deliver the goods to the customer. Y is sold at RM5 each, and it takes a sales person 15 minutes to sell one unit. The goods are left with the customer at the time of sale. Z is sold at RM12 each unit. It takes a sales person 12 minutes to sell one unit of Z, and it costs RM0.80 to deliver it to the customer. During the week, a sales person is only allowed delivery expenses of not more than RM75 and selling time is expected not to exceed 30 working hours. If the unit costs of product X, Y, and Z are respectively RM2.20, RM1.80, and RM4.25, how many units of X, Y, and Z must be sold to maximize the total sales? Formulate the problem as a linear programming model and develop an initial simplex table for the problem (Do not solve the problem) b. Indah Pottery Sdn Bhd, a manufacturer of products made from clay, is in the process of introducing new design of vase namely Design 1, Design 2, and Design 3. The products will be sold to the local market and to be exported to neighboring countries. The production manager of the formulated the equation given below. X1 = Quantity of Design 1 vase X2 = Quantity of Design 2 vase X3 = Quantity of Design 3 vase Maximize Z = 12X1 + 18X2 + 10X3 Subject to: 2X1 + 3X2 + 4X3 < 50 X1 + X2 + X3 < 0 X2 + 1.5X3 < 0 88

All X1, X2, and X3 > 0 State the dual for this problem ii) The following is the final simplex table of the primal problem. Complete the table by finding all values in the Zj and Cj Zj rows. Cj 12 18 0 Solution Mix X1 X2 S3 Zj Cj - Zj 12 X1 1 0 0 18 X2 0 1 0 10 X3 0.2 1.2 2.7 0 S1 0.2 0.2 0.2 0 S2 -0.6 0.4 0.4 0 S3 0 0 1 Quantity 10 10 10

iii) Give the optimal solution of the primal and briefly interpret it. 7 (NOV 2005) A company supplies three components to automotive manufacturers. The components are processed on 2 phases: Moulding and Polishing. The duration in minutes required on each machine are as follows: Phase Component A B C Moulding 16 5 8 Polishing 12 6 8

The moulding machine is available for 120 hours and the polishing machine is available for 110 hours. No more than 200 units of component C can be sold, but up to 1000 units of component B can be sold. In fact, the company already has orders for 500 units of component A that must be delivered. The profit per unit for component A, B and C are RM8.00, RM6.00 and RM9.00 respectively. Formulate the above Linear Programming problem. 8 (APR 2006) a) C-Bizz Mart is a retail catalog store specializing in cosmetics. Phone orders are taken each day by a pool of computer operators, some of them are permanent while some are temporary staff. A permanent operator can process an average of 75 orders per day, while 89

a temporary operator can process an average of 52 orders per day. The company receives an average of at least 600 orders per day. A permanent operator will process about 1.3 orders with errors each day, while a temporary operator averages 4.2 orders per day with errors. The store wants to limit errors to 24 per day. A permanent operator is paid RM60 per day including benefits and a temporary operator is paid RM40 per day. The company wants to know the number of permanent and temporary operators to hire in order to minimize costs. Formulate a linear programming model for the above problem.

b) Consider the following linear programming problem: Minimize Z = 2000X1 + 700X2 + 1600X3 Subject to: 5X1 + 2X2 + 2X3 > 20 4X1 + X2 + 2X3 > 30 X1, X2, X3 > 0 i) Write the dual for the above linear programming problem. The following is an incomplete final simplex table for the dual. Cj 30 0 0 Solution Mix Y2 S2 S3 Zj Cj - Zj ii) Complete the above simplex table iii) State the optimal solution (including the minimum cost) for the dual. iv) State the optimal solution (including the maximum profit) for the primal. 9 (OCT 2006) 20 Y1 1.25 0.75 -0.5 30 Y2 1 0 0 0 S1 0.25 -0.25 -0.5 0 S2 0 1 0 0 S3 0 0 1 Quantity 500 200 600

90

a) Xlent Electronics manufactures several products including 25-inch GE25 and 29inch GE29 televisions. It makes a profit of RM50 on each GE25 and RM75 on each GE29. During each shift, Xlent allocates up to 300 man-hours in its production area and 240 man-hours in its assembly area to manufacture the televisions. Each GE25 requires 2 man-hours in the production area and 1 man-hour in the assembly area while each GE29 requires 2 man-hours in the production area and 3 man-hours in the assembly area. Determine the production levels for GE25 and GE29 that would optimize the profit per shift. Formulate the above linear programming problem Solve the problem by using the graphical method Complete the following initial simplex table: Cj Solution Mix S1 S2 A1 Zj Cj-Zj X1 (3) 6 5 1 X2 (5) 3 7 1 S1 (0) 1 0 0 S2 (0) 0 1 0 A1 (-M) 0 0 1 Quantity Bi 300 200 50

10. (APR 2007) a) ACE Sdn Bhd manufactures three products X1, X2, and X3. The products must go through two production processes: Machining and Assembly. The capacity in each production process is limited by the number of labor hours available as shown in the following table. Labor hour for each product X2 0.5 0.5 Available X3 1.0 2.0 hours 700 600

Process Machining Assembly

X1 0.5 0.5

Profits for the products X1, X2, and X3 are RM150, RM130, and RM250 respectively. i) Formulate the above problem as a linear programming model

91

ii) iii)

Write the dual of the problem Set-up an initial simplex table for the problem

b)

Given the following simplex table of a manufacturing firm: Cj 0 150 250 0 130 Solution mix S3 X1 X3 S4 X2 Zj Cj - Zj 150 X1 0 1 0 0 0 150 0 130 X2 0 0 0 0 1 130 0 250 X3 0 0 1 0 0 250 0 0 S1 0.25 0 -0.25 -0.25 1 67.5 -67.5 0 S2 0.25 1 -0.25 -0.25 0 87.5 -87.5 0 S3 1 0 0 0 0 0 0 0 S4 0 0 0 1 0 0 0 0 S5 -0.5 0 0.5 -0.5 0 125 -125 Quantity 56.25 250.00 143.75 243.75 375.00

i) What is the quantity of each product (X1, X2, and X3) that should be produced? Determine the total profit. Intepret the shadow price for Resource 5 State the resources that are not fully utilized. Obtain the solution for the dual problem. Calculate the minimum resources used.

i)

ii)

v)

v)

11. (OCT 2007) Write down the standard form and construct the initial simplex table for the following linear programming problem: Maximize Z = 3X1 + 2X2 + X3 Subject to X1 + 2X2 + 2X3 < 30 2X1 + 3X2 + X3 < 50

92

X1 2X2 > 0 X1, X2, X3 > 0 12. (OCT 2007) a) Solve the following linear programming problem graphically, using the corner point method. Minimize Cost = X1 + 2X2 Subject to 1X1 + 3X2 > 900 8X1 + 2X2 > 1600 3X1 + 2X2 > 1200 X2 < 700 X1 X2 > 0

b) The following is the incomplete final simplex table for the dual, where S1, S2 and

S3 are the slack variables for the dual Cj 10 24 50 Solution mix Y1 Y2 Y3 Zj Cj - Zj

10 Y1 1 0 0

24 Y2 0 1 0

50 Y3 0 0 1

0 S1 4 0 0

0 S2 -2 2 0

0 S3 -1 -1 1

Quantity 4 3 2

Complete the above simplex table

ii. Explain why this table gives the optimal solution

iii. What is the optimal solution for the primal? Interpret. What is the total cost?

93

13. (APR 2008) a) The optimal simplex table for the linear programming problem is given in the following table: Cj Solution Mix S1 X2 X1 ZJ CJ-ZJ 12 X1 0 0 1 15 X2 0 1 0 14 X3 -1 1 0 0 S1 1 0 0 0 S2 2 1 -1 0 S3 -3 -0.5 1 Quantity 12 16 4

Where, X1= number of units of Product 1 produced per week X2= number of units of Product 2 produced per week X3= number of units of Product 3 produced per week S1= Slack variable for labor hours in Department A S2= Slack variable for labor hours in Department B S3= Slack variable for labor hours in Department C i) Complete the optimal simplex table ii) Determine the optimal production level and the maximum profit obtained. iii) The firm is considering hiring an extra labor on a part time basis at a rate of RM3.50 per hour in Department C. What would be the daily profit obtained by the firm? (Assume the firm operates 8 hours daily) 14. (OCT 2008) a) A housing developer has purchased 20,000 m2 of land on which he is planning to build two types of houses, detached and semi-detached within an overall budget of RM3 million. A detached house costs RM60,000 to build and requires 650 m2 of land and a semi-detached house costs RM40,000 to build and requires 300 m2 of land. From past experience, the developer estimates the profits of a detached house and a semi-detached house to be about RM9,000 and RM6,000 respectively. i) Formulate a linear programming (LP) model for this problem. ii) Write down the dual for this LP primal problem.

94

b) The following is the optimal simplex table for the linear programming problem of a company manufacturing two products X1 and X2. S1 , S2 and S3 are the slack variables of the three resources A, B and C respectively involved in the manufacturing process. Solution Cj Mix X2 S2 X1 Zj Cj- Zj i) Complete the above simplex table ii) State the optimal solution, including the total profit. iii) Is it worthwhile to purchase additional units of resource A at a cost of RM35.00 per unit? Why? 40 X1 0 0 1 30 X2 1 0 0 0 S1 3.33 -0.67 -1.67 0 S2 0 1 0 0 S3 -2.22 0.44 2.78

Quantity 20 1 25

95