3.3.1 Scalar Form

(3.1a)

subject to the constraints

(3.2a)

(3.3a)

where c _j , b _j , and a _ij (i = 1, 2, …, m; j = 1, 2, …, n) are known constants, and x _j are the decision variables.

3.3.2 Matrix Form

(3.1b)

subject to the constraints

(3.2b)

(3.3b)

where

The characteristics of a linear programming problem, stated in standard form, are

1. The objective function is of the minimization type.
2. All the constraints are of the equality type.
3. All the decision variables are nonnegative.

It is now shown that any linear programming problem can be expressed in standard form by using the following transformations.

1. The maximization of a function f (x ₁, x ₂, …, x _n ) is equivalent to the minimization of the negative of the same function. For example, the objective function
   

   is equivalent to

   

   Consequently, the objective function can be stated in the minimization form in any linear programming problem.

2. In most engineering optimization problems, the decision variables represent some physical dimensions, and hence the variables x _j will be nonnegative. However, a variable may be unrestricted in sign in some problems. In such cases, an unrestricted variable (which can take a positive, negative, or zero value) can be written as the difference of two nonnegative variables. Thus, if x _j is unrestricted in sign, it can be written as , where
   

   It can be seen that x _j will be negative, zero, or positive, depending on whether is greater than, equal to, or less than .

3. If a constraint appears in the form of a “less than or equal to” type of inequality as
   

   it can be converted into the equality form by adding a nonnegative slack variable x _n+1 as follows:

   

   Similarly, if the constraint is in the form of a “greater than or equal to” type of inequality as

   

   it can be converted into the equality form by subtracting a variable as

   

   where x _n+1 is a nonnegative variable known as a surplus variable.

It can be seen that there are m equations in n decision variables in a linear programming problem. We can assume that m < n; for if m > n, there would be m − n redundant equations that could be eliminated. The case n = m is of no interest, for then there is either a unique solution X that satisfies Eqs. (3.2b) and (3.3b) (in which case there can be no optimization) or no solution, in which case the constraints are inconsistent. The case m < n corresponds to an underdetermined set of linear equations, which, if they have one solution, have an infinite number of solutions. The problem of linear programming is to find one of these solutions that satisfies Eqs. (3.2b) and (3.3b) and yields the minimum of f.

3.5.1 Definitions

1. Point in n‐dimensional space. A point X in an n‐dimensional space is characterized by an ordered set of n values or coordinates (x ₁, x ₂, …, x _n ). The coordinates of X are also called the components of X.
2. Line segment in n dimensions (L). If the coordinates of two points A and B are given by and (j = 1, 2, …, n), the line segment (L) joining these points is the collection of points X(λ) whose coordinates are given by with 0 ≤ λ ≤ 1.

   Thus

   (3.4)

   In one dimension, for example, it is easy to see that the definition is in accordance with our experience (Figure 3.7):

   (3.5)

   whence

   (3.6)
3. Hyperplane. In n‐dimensional space, the set of points whose coordinates satisfy a linear equation
   (3.7)

   is called a hyperplane. A hyperplane, H, is represented as

   (3.8)

   A hyperplane has n − 1 dimensions in an n‐dimensional space. For example, in three‐dimensional space it is a plane, and in two‐dimensional space it is a line. The set of points whose coordinates satisfy a linear inequality like a ₁ x ₁ + ⋯ + a _n x _n  ≤ b is called a closed half‐space, closed due to the inclusion of an equality sign in the inequality above. A hyperplane partitions the n‐dimensional space (E ⁿ ) into two closed half‐spaces, so that

   (3.9)
   (3.10)

   This is illustrated in Figure 3.8 in the case of a two‐dimensional space (E ²).

4. Convex set. A convex set is a collection of points such that if X ⁽¹⁾ and X ⁽²⁾ are any two points in the collection, the line segment joining them is also in the collection. A convex set, S, can be defined mathematically as follows:
   

   where

   

   A set containing only one point is always considered to be convex. Some examples of convex sets in two dimensions are shown shaded in Figure 3.9. On the other hand, the sets depicted by the shaded region in Figure 3.10 are not convex. The L‐shaped region, for example, is not a convex set, because it is possible to find two points a and b in the set such that not all points on the line joining them belong to the set.

5. Convex polyhedron and convex polytope. A convex polyhedron is a set of points common to one or more half‐spaces. A convex polyhedron that is bounded is called a convex polytope.

   Figure 3.11a and b represents convex polytopes in two and three dimensions, and Figure 3.11c and d denotes convex polyhedra in two and three dimensions. It can be seen that a convex polygon, shown in Figure 3.11a and c, can be considered as the intersection of one or more half‐planes.

6. Vertex or extreme point. This is a point in the convex set that does not lie on a line segment joining two other points of the set. For example, every point on the circumference of a circle and each corner point of a polygon can be called a vertex or extreme point.
7. Feasible solution. In a linear programming problem, any solution that satisfies the constraints (see Eqs. (3.2b) and (3.3b)) is called a feasible solution.
8. Basic solution. A basic solution is one in which n − m variables are set equal to zero. A basic solution can be obtained by setting n − m variables to zero and solving the constraint Eq. (3.2b) simultaneously.
9. Basis. The collection of variables not set equal to zero to obtain the basic solution is called the basis.
10. Basic feasible solution. This is a basic solution that satisfies the nonnegativity conditions of Eq. (3.3b).
11. Nondegenerate basic feasible solution. This is a basic feasible solution that has got exactly m positive x _i .
12. Optimal solution. A feasible solution that optimizes the objective function is called an optimal solution.
13. Optimal basic solution. This is a basic feasible solution for which the objective function is optimal.

3.5.2 Theorems

The basic theorems of linear programming can now be stated and proved.2

The proofs of Theorems 3.4–3.6 can be found in Ref. [1].

3.9.1 Identifying an Optimal Point

3.9.2 Improving a Nonoptimal Basic Feasible Solution

From the last row of Eq. (3.21), we can write the objective function as

(3.25)

If at least one is negative, the value of f can be reduced by making the corresponding x _j  > 0. In other words, the nonbasic variable x _j , for which the cost coefficient is negative, is to be made a basic variable in order to reduce the value of the objective function. At the same time, due to the pivotal operation, one of the current basic variables will become nonbasic and hence the values of the new basic variables are to be adjusted in order to bring the value of f less than . If there are more than one the index s of the nonbasic variable x _s which is to be made basic is chosen such that

(3.26)

Although this may not lead to the greatest possible decrease in f (since it may not be possible to increase x _s very far), this is intuitively at least a good rule for choosing the variable to become basic. It is the one generally used in practice, because it is simple and it usually leads to fewer iterations than just choosing any . If there is a tie‐in applying Eq. (3.26), (i.e. if more than one has the same minimum value), we select one of them arbitrarily as .

Having decided on the variable x _s to become basic, we increase it from zero, holding all other nonbasic variables zero, and observe the effect on the current basic variables. From Eq. (3.21), we can obtain

(3.27)

(3.28)

Since Eq. (3.28) suggests that the value of x _s should be made as large as possible in order to reduce the value of f as much as possible. However, in the process of increasing the value of x _s , some of the variables x _i (i = 1, 2, …, m) in Eq. (3.27) may become negative. It can be seen that if all the coefficients i = 1, 2, …, m, then x _s can be made infinitely large without making any x _i  < 0, i = 1, 2, …, m. In such a case, the minimum value of f is minus infinity and the linear programming problem is said to have an unbounded solution.

On the other hand, if at least one is positive, the maximum value that x _s can take without making x _i negative is . If there are more than one the largest value x _s ^* that x _s can take is given by the minimum of the ratios for which . Thus

(3.29)

The choice of r in the case of a tie, assuming that all  > 0, is arbitrary. If any for which  > 0 is zero in Eq. (3.27), x _s cannot be increased by any amount. Such a solution is called a degenerate solution.

In the case of a nondegenerate basic feasible solution, a new basic feasible solution can be constructed with a lower value of the objective function as follows. By substituting the value of given by Eq. (3.29) into Eqs. (3.27) and (3.28), we obtain

(3.30)

(3.31)

which can readily be seen to be a feasible solution different from the previous one. Since in Eq. (3.29), a single pivot operation on the element in the system of Eq. (3.21) will lead to a new canonical form from which the basic feasible solution of Eq. (3.30) can easily be deduced. Also, Eq. (3.31) shows that this basic feasible solution corresponds to a lower objective function value compared to that of Eq. (3.22). This basic feasible solution can again be tested for optimality by seeing whether all in the new canonical form. If the solution is not optimal, the entire procedure of moving to another basic feasible solution from the present one has to be repeated. In the simplex algorithm, this procedure is repeated in an iterative manner until the algorithm finds either (i) a class of feasible solutions for which f → −∞ or (ii) an optimal basic feasible solution with all i = 1, 2, …, n. Since there are only a finite number of ways to choose a set of m basic variables out of n variables, the iterative process of the simplex algorithm will terminate in a finite number of cycles. The iterative process of the simplex algorithm is shown as a flowchart in Figure 3.14.

1. 1 Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton, NJ: Princeton University Press.
2. 2 Adams, W.J., Gewirtz, A., and Quintas, L.V. (1969). Elements of Linear Programming. New York: Van Nostrand Reinhold.
3. 3 Garvin, W.W. (1960). Introduction to Linear Programming. New York: McGraw‐Hill.
4. 4 Gass, S.I. (1985). Linear Programming: Methods and Applications, 5e. New York: McGraw‐Hill.
5. 5 Hadley, G. (1962). Linear Programming. Reading, MA: Addison‐Wesley.
6. 6 Vajda, S. (1960). An Introduction to Linear Programming and the Theory of Games. New York: Wiley.
7. 7 Orchard‐Hays, W. (1968). Advanced Linear Programming Computing Techniques. New York: McGraw‐Hill.
8. 8 Gass, S.I. (1970). An Illustrated Guide to Linear Programming. New York: McGraw‐Hill.
9. 9 Winston, W.L. (1991). Operations Research: Applications and Algorithms, 2e. Boston: PWS‐Kent.
10. 10 Taha, H.A. (1992). Operations Research: An Introduction, 5e. New York: Macmillan.
11. 11 Murty, K.G. (1983). Linear Programming. New York: Wiley.
12. 12 Karmarkar, N. (1984). A new polynomial‐time algorithm for linear programming. Combinatorica 4 (4): 373–395.
13. 13 Rubinstein, M.F. and Karagozian, J. (1966). Building design using linear programming. Journal of the Structural Division , Proceedings of ASCE 92 (ST6): 223–245.
14. 14 Au, T. (1969). Introduction to Systems Engineering: Deterministic Models. Reading, MA: Addison‐Wesley.
15. 15 Stoecker, W.F. (1989). Design of Thermal Systems, 3e. New York: McGraw‐Hill.
16. 16 Stark, R.M. and Nicholls, R.L. (1972). Mathematical Foundations for Design: Civil Engineering Systems. New York: McGraw‐Hill.
17. 17 Maass, A., Hufschmidt, M.A., Dorfman, R. et al. (1962). Design of Water Resources Systems. Cambridge, MA: Harvard University Press.

1. 3.1 State the following LP problem in standard form:
   

   subject to

   
2. 3.2 State the following LP problem in standard form:
   

   subject to

   
3. 3.3 Solve the following system of equations using pivot operations:
   
4. 3.4 It is proposed to build a reservoir of capacity x ₁ to better control the supply of water to an irrigation district [16,17]. The inflow to the reservoir is expected to be 4.5 × 10⁶ acre–ft during the wet (rainy) season and 1.1 × 10⁶ acre–ft during the dry (summer) season. Between the reservoir and the irrigation district, one stream (A) adds water to and another stream (B) carries water away from the main stream, as shown in Figure 3.16. Stream A adds 1.2 × 10⁶ and 0.3 × 10⁶ acre–ft of water during the wet and dry seasons, respectively. Stream B takes away 0.5 × 10⁶ and 0.2 × 10⁶ acre–ft of water during the wet and dry seasons, respectively. Of the total amount of water released to the irrigation district per year (x ₂), 30% is to be released during the wet season and 70% during the dry season. The yearly cost of diverting the required amount of water from the main stream to the irrigation district is given by 18(0.3x ₂) + 12(0.7x ₂). The cost of building and maintaining the reservoir, reduced to a yearly basis, is given by 25x ₁. Determine the values of x ₁ and x ₂ to minimize the total yearly cost.
5. 3.5 Solve the following system of equations using pivot operations:
   
6. 3.6 What elementary operations can be used to transform
   

   into

   

   Find the solution of this system by reducing into canonical form.

7. 3.7 Find the solution of the following LP problem graphically:
   

   subject to

   
8. 3.8 Find the solution of the following LP problem graphically:
   

   subject to

   
9. 3.9 Find the solution of the following LP problem graphically:
   

   subject to

   
10. 3.10 Find the solution of the following problem by the graphical method:
    

    subject to

    

    where e is the base of natural logarithms.

11. 3.11 Prove Theorem 3.6.

    For Problems 3.12–3.42, use a graphical procedure to identify (a) the feasible region, (b) the region where the slack (or surplus) variables are zero, and (c) the optimum solution.

12. 3.12
    
    subject to
    
13. 3.13 Rework Problem 12 when x and y are unrestricted in sign.
14. 3.14
    

    subject to

    
15. 3.15 Rework Problem 14 when x and y are unrestricted in sign.
16. 3.16
    
    subject to
    
17. 3.17 Rework Problem 16 by changing the objective to Minimize f = x − y.
18. 3.18
    
    subject to
    
19. 3.19 Rework Problem 18 by changing the objective to Minimize f = x − y.
20. 3.20
    
    subject to
    
21. 3.21
    
    subject to
    

    x and y are unrestricted in sign

22. 3.22 Rework Problem 20 by changing the objective to Maximize f = x + y.
23. 3.23
    
    subject to
    
24. 3.24
    
    subject to
    
25. 3.25 Rework Problem 24 by changing the objective to Maximize f = x − 8y.
26. 3.26
    
    subject to
    

    x ≥ 0, y is unrestricted in sign

27. 3.27
    
    subject to
    
28. 3.28
    
    subject to
    
29. 3.29
    
    subject to
    

    x ≥ 0, y is unrestricted in sign

30. 3.30
    
    subject to
    
31. 3.31 Rework Problem 30 by changing the objective to Maximize f = x − 4y.
32. 3.32
    
    subject to
    
33. 3.33 Rework Problem 32 by changing the objective to Maximize f = 4x + 5y.
34. 3.34 Rework Problem 32 by changing the objective to Minimize f = 6x + 2y.
35. 3.35
    
    subject to
    

    x and y are unrestricted in sign

36. 3.36
    
    subject to
    
37. 3.37 Rework Problem 36 by changing the objective to Maximize f = 5x + 2y.
38. 3.38 Rework Problem 36 when x is unrestricted in sign and y ≥ 0.
39. 3.39
    
    subject to
    
40. 3.40
    
    subject to
    
41. 3.41 Rework Problem 40 by changing the constraint x + 2y ≥ 6 to x + 2y ≤ 6.
42. 3.42
    
    subject to
    
43. 3.43
    
    subject to
    
44. 3.44 Reduce the system of equations
    

    into a canonical system with x ₁, x ₂, and x ₃ as basic variables. From this derive all other canonical forms.

45. 3.45
    
    subject to
    

    Find all the basic feasible solutions of the problem and identify the optimal solution.

46. 3.46 A progressive university has decided to keep its library open round the clock and gathered that the following number of attendants are required to reshelve the books:

    Time of day (h)	Minimum number of attendants required
    0–4	4
    4–8	7
    8–12	8
    12–16	9
    16–20	14
    20–24	3

    If each attendant works eight consecutive hours per day, formulate the problem of finding the minimum number of attendants necessary to satisfy the requirements above as a LP problem.

47. 3.47 A paper mill received an order for the supply of paper rolls of widths and lengths as indicated below:

    Number of rolls ordered	Width of roll (m)	Length (m)
    1	6	100
    1	8	300
    1	9	200

    The mill produces rolls only in two standard widths, 10 and 20 m. The mill cuts the standard rolls to size to meet the specifications of the orders. Assuming that there is no limit on the lengths of the standard rolls, find the cutting pattern that minimizes the trim losses while satisfying the order above.

48. 3.48 Solve the LP problem stated in Example 1.6 for the following data: l = 2 m, W ₁ = 3000 N, W ₂ = 2000 N, W ₃ = 1000 N, and w ₁ = w ₂ = w ₃ = 200 N.
49. 3.49 Find the solution of Problem 1.1 using the simplex method.
50. 3.50 Find the solution of Problem 1.15 using the simplex method.
51. 3.51 Find the solution of Example 3.1 using (a) the graphical method and (b) the simplex method.
52. 3.52 In the scaffolding system shown in Figure 3.17, loads x ₁ and x ₂ are applied on beams 2 and 3, respectively. Ropes A and B can carry a load of W ₁ = 300 lb. each; the middle ropes, C and D, can withstand a load of W ₂ = 200 lb. each, and ropes E and F are capable of supporting a load W ₃ = 100 lb. each. Formulate the problem of finding the loads x ₁ and x ₂ and their location parameters x ₃ and x ₄ to maximize the total load carried by the system, x ₁ + x ₂, by assuming that the beams and ropes are weightless.
53. 3.53 A manufacturer produces three machine parts, A, B, and C. The raw material costs of parts A, B, and C are $5, $10, and $15 per unit, and the corresponding prices of the finished parts are $50, $75, and $100 per unit. Part A requires turning and drilling operations, while part B needs milling and drilling operations. Part C requires turning and milling operations. The number of parts that can be produced on various machines per day and the daily costs of running the machines are given below:

    Machine part	Number of parts that can be produced on
    	Turning lathes	Drilling machines	Milling machines
    A	15	15
    B		20	30
    C	25		10
    Cost of running the machines per day	$250	$200	$300

    Formulate the problem of maximizing the profit.

    Solve Problems 3.54–3.90 by the simplex method.

54. 3.54 Problem 1.22
55. 3.55 Problem 1.23
56. 3.56 Problem 1.24
57. 3.57 Problem 1.25
58. 3.58 Problem 7
59. 3.59 Problem 12
60. 3.60 Problem 13
61. 3.61 Problem 14
62. 3.62 Problem 15
63. 3.63 Problem 16
64. 3.64 Problem 17
65. 3.65 Problem 18
66. 3.66 Problem 19
67. 3.67 Problem 20
68. 3.68 Problem 21
69. 3.69 Problem 22
70. 3.70 Problem 23
71. 3.71 Problem 24
72. 3.72 Problem 25
73. 3.73 Problem 26
74. 3.74 Problem 27
75. 3.75 Problem 28
76. 3.76 Problem 29
77. 3.77 Problem 30
78. 3.78 Problem 31
79. 3.79 Problem 32
80. 3.80 Problem 33
81. 3.81 Problem 34
82. 3.82 Problem 35
83. 3.83 Problem 36
84. 3.84 Problem 37
85. 3.85 Problem 38
86. 3.86 Problem 39
87. 3.87 Problem 40
88. 3.88 Problem 41
89. 3.89 Problem 42
90. 3.90 Problem 43
91. 3.91 (a) (b) The temperatures measured at various points inside a heated wall are given below:

    Distance from the heated surface as a percentage of wall thickness, x i	0	20	40	60	80	100
    Temperature, t i (°C)	400	350	250	175	100	50

    It is decided to use a linear model to approximate the measured values as

    (3.41)3.41

    where t is the temperature, x the percentage of wall thickness, and a and b the coefficients that are to be estimated. Obtain the best estimates of a and b using linear programming with the following objectives.

    1. (a) Minimize the sum of absolute deviations between the measured values and those given by Eq. (3.41): ∑ _i |a + bx _i  − t _i |.
    2. (b) Minimize the maximum absolute deviation between the measured values and those given by Eq. (3.41):

       

92. 3.92 A snack food manufacturer markets two kinds of mixed nuts, labeled A and B. Mixed nuts A contain 20% almonds, 10% cashew nuts, 15% walnuts, and 55% peanuts. Mixed nuts B contain 10% almonds, 20% cashew nuts, 25% walnuts, and 45% peanuts. A customer wants to use mixed nuts A and B to prepare a new mix that contains at least 4 lb. of almonds, 5 lb. of cashew nuts, and 6 lb. of walnuts, for a party. If mixed nuts A and B cost $2.50 and $3.00 per pound, respectively, determine the amounts of mixed nuts A and B to be used to prepare the new mix at a minimum cost.
93. 3.93 A company produces three types of bearings, B ₁, B ₂, and B ₃, on two machines, A ₁ and A ₂. The processing times of the bearings on the two machines are indicated in the following table:

    Machine	Processing time (min) for bearing:
    	B 1	B 2	B 3
    A 1	10	6	12
    A 2	8	4	4

    The times available on machines A ₁ and A ₂ per day are 1200 and 1000 minutes, respectively. The profits per unit of B ₁, B ₂, and B ₃ are $4, $2, and $3, respectively. The maximum number of units the company can sell are 500, 400, and 600 for B ₁, B ₂, and B ₃, respectively. Formulate and solve the problem for maximizing the profit.

94. 3.94 Two types of printed circuit boards A and B are produced in a computer manufacturing company. The component placement time, soldering time, and inspection time required in producing each unit of A and B are given below:

    Circuit board	Time required per unit (min) for:
    	Component placement	Soldering	Inspection
    A	16	10	4
    B	10	12	8

    If the amounts of time available per day for component placement, soldering, and inspection are 1500, 1000, and 500 person–minutes, respectively, determine the number of units of A and B to be produced for maximizing the production. If each unit of A and B contributes a profit of $10 and $15, respectively, determine the number of units of A and B to be produced for maximizing the profit.

95. 3.95 A paper mill produces paper rolls in two standard widths; one with width 20 in. and the other with width 50 in. It is desired to produce new rolls with different widths as indicated below:

    Width (in.)	Number of rolls required
    40	150
    30	200
    15	50
    6	100

    The new rolls are to be produced by cutting the rolls of standard widths to minimize the trim loss. Formulate the problem as an LP problem.

96. 3.96 A manufacturer produces two types of machine parts, P ₁ and P ₂, using lathes and milling machines. The machining times required by each part on the lathe and the milling machine and the profit per unit of each part are given below:

    Machine part	Machine time (h) required by each unit on:			Cost per unit
    	Lathe	Milling machine
    P 1	5	2	$200
    P 2	4	4	$300

    If the total machining times available in a week are 500 hours on lathes and 400 hours on milling machines, determine the number of units of P ₁ and P ₂ to be produced per week to maximize the profit.

97. 3.97 A bank offers four different types of certificates of deposits (CDs) as indicated below:

    CD type	Duration (yr)	Total interest at maturity (%)
    1	0.5	5
    2	1.0	7
    3	2.0	10
    4	4.0	15

    If a customer wants to invest $50 000 in various types of CDs, determine the plan that yields the maximum return at the end of the fourth year.

98. 98 The production of two machine parts A and B requires operations on a lathe (L), a shaper (S), a drilling machine (D), a milling machine (M), and a grinding machine (G). The machining times required by A and B on various machines are given below.

    Machine part	Machine time required (hours per unit) on:
    	L	S	D	M	G
    A	0.6	0.4	0.1	0.5	0.2
    B	0.9	0.1	0.2	0.3	0.3

    The number of machines of different types available is given by L : 10, S : 3, D : 4, M : 6, and G : 5. Each machine can be used for eight hours a day for 30 days in a month.

    1. Determine the production plan for maximizing the output in a month
    2. If the number of units of A is to be equal to the number of units of B, find the optimum production plan.
99. 3.99 A salesman sells two types of vacuum cleaners, A and B. He receives a commission of 20% on all sales, provided that at least 10 units each of A and B are sold per month. The salesman needs to make telephone calls to make appointments with customers and demonstrate the products in order to sell the products. The selling price of the products, the average money to be spent on telephone calls, the time to be spent on demonstrations, and the probability of a potential customer buying the product are given below:

    Vacuum cleaner	Selling price per unit	Money to be spent on telephone calls to find a potential customer	Time to be spent in demonstrations to a potential customer (h)	Probability of a potential customer buying the product
    A	$250	$3	3	0.4
    B	$100	$1	1	0.8

    In a particular month, the salesman expects to sell at most 25 units of A and 45 units of B. If he plans to spend a maximum of 200 hours in the month, formulate the problem of determining the number of units of A and B to be sold to maximize his income.

100. 3.100 An electric utility company operates two thermal power plants, A and B, using three different grades of coal, C ₁, C ₂, and C ₃. The minimum power to be generated at plants A and B is 30 and 80 MWh, respectively. The quantities of various grades of coal required to generate 1 MWh of power at each power plant, the pollution caused by the various grades of coal at each power plant, and the costs of coal are given in the following table:

     Coal type	Quantity of coal required to generate 1 MWh at the power plant (tons)			Pollution caused at power plant					Cost of coal at power plant
     	A	B	A	B	A	B
     C 1	2.5	1.5	1.0	1.5	20	18
     C 2	1.0	2.0	1.5	2.0	25	28
     C 3	3.0	2.5	2.0	2.5	18	12

     Formulate the problem of determining the amounts of different grades of coal to be used at each power plant to minimize (a) the total pollution level, and (b) the total cost of operation.

101. 3.101 A grocery store wants to buy five different types of vegetables from four farms in a month. The prices of the vegetables at different farms, the capacities of the farms, and the minimum requirements of the grocery store are indicated in the following table:

     Price ($/ton) of vegetable type
     Farm	1 (Potato)	2 (Tomato)	3 (Okra)	4 (Eggplant)	5 (Spinach)	Maximum (of all types combined) they can supply
     	1	200	600	1600	800		1200	180
     2	300	550	1400	850	1100	200
     3	250	650	1500	700	1000	100
     4	150	500	1700	900	1300	120
     Minimum amount required (tons)	100	60	20	80	40

     Formulate the problem of determining the buying scheme that corresponds to a minimum cost.

102. 3.102 A steel plant produces steel using four different types of processes. The iron ore, coal, and labor required, the amounts of steel and side products produced, the cost information, and the physical limitations on the system are given below:

     Process type	Iron ore required (tons/day)	Coal required (tons/day)	Labor required (person‐days)	Steel produced (tons/day)	Side products produced (tons/day)
     1	5	3	6	4	1
     2	8	5	12	6	2
     3	3	2	5	2	1
     4	10	7	12	6	4
     Cost	$50/ton	$10/ton	$150/ person‐day	$350/ton	$100/ton
     Limitations	600 tons available per month	250 tons available per month	No limitations on availability of labor	All steel produced can be sold	Only 200 tons can be sold per month

     Assuming that a particular process can be employed for any number of days in a 30‐day month, determine the operating schedule of the plant for maximizing the profit.

103. 3.103 Solve 3.7 using MATLAB (simplex method).
104. 3.104 Solve Problem 12 using MATLAB (simplex method).
105. 3.105 Solve Problem 24 using MATLAB (simplex method).
106. 3.106 Find the optimal solution of the LP problem stated in Problem 45 using MATLAB (simplex method).
107. 3.107 Find the optimal solution of the LP problem described in Problem 101 using MATLAB.