|
LINEAR PROGRAMMING
- Introduction
- Concepts and Methods
- Concepts and Geometric Interpretation
- General Statement of the Linear Programming Problem
- Slack and Surplus Variables
- Feasible and Basic Feasible Solutions of the Constraint Equations
- Optimization with the Simplex Method
- Simplex Tableau
- Mathematics of Linear Programming
- Degeneracy
- Artificial Variables
- Formulating and Solving Problems
- Sensitivity Analysis
- Changes in the Right Hand Side of the Constraint Equation
- Changes in the Coefficients of the Objective Function
- Changes in the Coefficients of the Constraint Equations
- Addition of New Variables
- Addition of More Constraint Equations
- Closure
- Selected List of Texts on Linear Programming and Extensions
- References
- Problems
| Problems | top |
4-1. Solve the following problem by the Simplex Method.
Maximize: 6x1 + x2 = p
Subject to: 3x1 + 5x2 < 13
6x1 + x2 < 12
x1 + 5x2 < 10
Determine the range on x1 and x2 for which the optimal solution remains optimal. Explain. (Note: It is not necessary to use sensitivity analysis.)
4-2. Solve the following problem by the Simplex Method.
Maximize: x1 + 2x2 + 3x3 - x4 = p
Subject to: x1 + 2x2 + 3x3 + x5 = 15
2x1 + x2 + 5x3 + x6 = 20
x1 + 2x2 + x3 + x4 = 10
Start with x4, x5, and x6 in the basis.
4-3 a. Solve the following problem by the Simplex Method.
Maximize: 2x1 + x2 = p
Subject to: x1 + x2 < 6
x1 - x2 < 2
x1 + 2x2 < 10
x1 - 2x2 < 1
b.Compute the inverse of the optimal basis, and the largest changes in bi's for the optimal solution remain optimal.
4-4. Solve the following problem by the Simplex Method.
Maximize: 3x1 + 2x2 = p
Subject to: x1 + x2 < 8
2x1 + x2 < 10
Solution
4-5 a. Solve the following problem by the Simplex Method.
Maximize: x1 + 2x2 = p
Subject to: x1 + 3x2 < 105
-x1 + x2 < 15
2x1 + 3x2 < 135
-3x1 + 2x2 < 15
b. Solve this problem by the classical theory using Lagrange Multipliers, and explain why Lagrange Multipliers are sometimes called "shadow" or "implicit" prices.
4-6a. Solve the following problem by the Simplex Method using slack and artificial variables:
Maximize: x1 + 10x2 = p
Subject to: -x1 + x2 > 5
3x1 + x2 < 15
b.Calculate the inverse of the optimal basis and the Lagrange Multipliers.
c.Calculate the largest changes in the right-hand side of the constraint equations (bj's) for the optimal solution in part (a) to remain optimal.
4-7. Solve the following problem by the Simplex Method using the minimum number of slack, surplus, and artificial variables needed for an initially feasible basis.
Minimize: 2x1 + 4x2 + x3 = c
Subject to: x1 + 2x2 - x3 < 5
2x1 - x2 + 2x3 = 2
-x1 + 2x2 + 2x3 > 1
4-8a. Solve the following problem using the Simplex Method using an artificial variable x6 in the second constraint equation and adding the term -106x6 to the objective function.
Maximize: 2x1 + x2 + x3 = p
Subject to: x1 + x2 + x3 < 10
x1 + 5x2 + x3 > 20
b.Compute the effect of changing cost coefficient c1 from 2 to 3, i.e., Dc1 = 1, and c3 from 1 to 4, i.e., Dc3 = 3, using the results of example 4-6.
c.Without resolving the problem, find the new optimal solution if the first constraint equation is changed to the following by using the results of example 4-6.
x1 + x2 + x3 < 5
Also, compute the new optimal values of x1 and x2 and value of the objective function.
4-9.Consider the following linear programming problem
Maximize: 2x1 + x2 = p
Subject to: x1 + 2x2 < 10
2x1 + 3x2 < 12
3x1 + x2 < 15
x1 + x2 < 4
a.Solve the problem by the Simplex Method using slack variables in the first three equations and an artificial variable in the fourth constraint equation as the initially feasible basis.
b.The following matrix is the inverse of the optimal basis, A-1. Multiply this matrix by the matrix A to obtain the unit matrix I.
c.Compute the Lagrange Multipliers for the problem.
d.Compute the changes in the right-hand side of the constraint equations that will cause all of the values of the variables in the basis to become zero.
4-10.(3) Consider the following problem based on a blending analysis.
Minimize: 50x1 + 25x2 = c
Subject to: x1 + 3x2 > 8
3x1 + 4x2 > 19
3x1 + x2 > 7
a.Solve this problem by the Simplex Method.
b.Compute the inverse of the optimal basis and the Lagrange Multipliers.
c.Determine the effect on the optimal solution (variables and cost) if the right-hand side of the second constraint equations is changed from 19 to 21 and the right-hand side of the third constraint equations is changed from 7 to 8.
d.Show that the following must hold for the optimal solution to remain optimal considering changes in the cost coefficients.
3/4 < c1/c2 < 3
4-11.Consider the following linear programming problem.
Maximize: x1 + 9x2 + x3 = p
subject to: x1 + 2x2 + 3x3 < 9
3x1 + 2x2 + 2x3 < 15
a.Solve this problem by the Simplex Method.
b.Compute the inverse of the optimal basis and the Lagrange Multipliers.
c.Determine the largest changes in the right-hand side and in the cost coefficients of the variables in the basis for the optimal solution to remain optimal.
4-12.Solve the following problem by the Simplex Method. To demonstrate your understanding of the use of slack and artificial variables, use the slack variable in the first two constraint equations and an artificial variable in the third constraint equation as the initially feasible basis.
Maximize: x1 + 2x2 = p
Subject to: -x1 + x2 < 2
x1 + x2 < 6
x1 + x2 > 1
4-13
a.Derive equation (4-31) from equation (4-30). Explain the significance of the terms in equation (4-31), and discuss the application of this equation in sensitivity analysis associated with coefficients of the variables in the objective function.
b.Starting with equation (4-25) show that the change in b which gives the limit on Db for x*i,new = 0 is equal to -b.
4-14. In a power plant which is part of a chemical plant or refinery, both electricity and process steam (high and low pressure) can be produced. A typical power plant has constraints associated with turbine capacity, steam pressure and amounts, and electrical demand. In Stoecker(14) the following economic and process model is developed for a simple power plant producing electricity, high pressure steam x1, and low pressure steam x2.
Maximize: 0.l6x1 + 0.14x2 = p
Subject to: x1 + x2 < 20
x1 + 4x2 < 60
4x1 + 3x2 < 72
Determine the optimal values of x1 and x2 and the maximum profit using the Simplex Method.
4-15. A company makes two levels of purity of a product which is sold in gallon containers. Product A is of higher purity than product B with profits of $0.40 per gallon made on A and $0.30 per gallon made on B. Product A requires twice the processing time of B, and if all B is product, the com[any could make 1,000 gallons per day. However, the raw material supply is sufficient for only 800 gallons per day of both A and B combined. Product A requires a container of which only 400 one gallon containers per day are available while there are 700 one gallon containers per day available for B. Assuming all of the product can be sold of both A and B, what volumes of each should be produced to maximize the profit? Solve the problem graphically and by the Simplex Method.
4-16. A wax concentrating plant, as shown below, receives feedstock with a low concentration of wax and refines it into a product with a high concentration of wax. In Stoecker(14) the selling prices of the products are x1, $8 per hundred pounds, and x2, $6 per hundred pounds; the raw material costs are x3, $1.5 per hundred pounds, and x4, $3 per hundred pounds.
The plant operates under the following constraints:
a. The same amount of wax leaves the plant as enters it.
b. The receiving facilities of the plant are limited to no more than a total of 800 lb/hr.
c. The packaging facilities can accommodate a maximum of 600 lb/hr of x2 and 500 lb/hr of x1.
If the operating cost of the plant is constant, use the Simplex Algorithm to determine the purchase and production plan that results in the maximum profit.
4-17. A company produces a product and a by-product, and production is limited by two constraints. One is on the availability raw material, and the other is on the capacity of the processing equipment. The product requires 3.0 units of raw material and 2.0 units of processing capacity. The byproduct requires 4.0 units of raw materials and 5.0 units of processing capacity. There is a total of 1700 units of raw material available and a total of 1600 units of processing capacity. The profit is $2.00 per unit for the product and $4.00 per unit for the by-product.
The economic model and constraints are:
Maximize: 2x1 + 4x2
Subject to: 3x1 + 4x2 < 1700 raw material constraint
2x1 + 5x2 < 1600 processing capacity constraint
a. Determine the maximum profit and the production of the product x1 and by-product x2 using the Simplex Method.
b. Calculate the inverse of the optimal basis and the Lagrange Multipliers.
c. i. If the total raw material available is increased from 1700 to 1701, determine the new product, byproduct, and profit.
ii. If an additional 10 units of processing capacity can be obtained at a cost of $7, i.e., 1600 is increased to 1610, is this additional capacity worth obtaining?
d. A second by-product can be produced that requires 4.0 units of raw material and 3 1/3 units of processing capacity. Determine the profit that would have to be made on this by-product to consider its production.
4-18.(14) A chemical plant whose flow diagram is shown in Figure 4-9 manufactures ammonia, hydrochloric acid, urea, ammonium carbonate, and ammonia chloride from carbon dioxide, nitrogen, hydrogen, and chlorine. The x values in Figure 4-9 indicate flow rates in moles per hour.
The costs of the feed stocks are c1, c2, c3, and c4, and the values of the products are p5, p6, p7, and p8 in dollars per mole, where the subscript corresponds to that of the x value. In reactor 3 the ratios of molal flow rates are m = 3x7 and x1 = 2x7 and, in other reactors, straightforward material balances apply. The capacity of reactor 1 is equal to or less than 2,000 mol/hr of NH3 and the capacity of reactor 2 is equal to or less than 1,500 mol/hr of HCl as given by Stoecker (14).
a.Develop the expression for the profit.
b.Write the constraint equations for this plant.
4-19.(8)The flow diagram of a simple petroleum refinery is shown in Figure 4-10. The prices and quality specifications of the products and their minimum production rates are given below:
The current cost of crude is $32.00/barrel
Operating cost for separation in the crude still is $0.25 per barrel for each product produced. The operating cost for the catalytic cracking unit is $0.10 for the straight-run distillate and $0.15 for the straight-run fuel oil.
The following table gives the specifications for each blending component:
The capacity of the catalytic cracking unit must not exceed 50,000 barrels/day, and the crude still is limited at 100,000 barreals/day. The crude is separated into three volume fractions in the crude still, 0.2 straight-run gasoline, 0.5 straight-run distillate, and 0.3 straight-run fuel oil. In the catalytic cracking unit a product distribution of 0.7 barrels of cat. naphtha, 0.4 light cat. cycle oil, and 0.2 barrel of heavy cat. cycle oil is obtained per barrel of straight-run distillate. The straight run fuel oil product distribution is 0.1 barrel of cat. naphtha, 0.3 barrel of light cat. cycle oil, and 0.7 barrel of heavy cat. cycle oil.
Present a matrix representation of this simple refinery, similar to the one shown in Figure 4-8. Be sure to include the objective function and material balance, unit, and blending constraints.
4-20.For the results of the MPS optimization of the simple refinery consider the following:
a.In Table 4-12(b) on p. 4-60, it shows that the variable SRNPG is not in the basis. Compute the largest change in the cost coefficient of SRNPG for the optimal solution to remain optimal. Confirm that this is the correct answer by the sensitivity analysis results tabulated in the chapter.
b.In Table 4-12(b) the fuel oil (FO) flow rate is at the optimal value of 10,000 barrels/day. Compute the change in the profit if the fuel oil flow rate is increased to 11,000 barrels/day using Lagrange Multipliers. Would this change cause the problem to be resolved according to the MPS results, why?
c.The marketing department of the company requires a minimum of 5,000 barrels/day of residual fuel, a new product. Residual fuel (RF) is straight-run fuel oil (SRFO) directly from the atmospheric distillation column. The price is $10.00 /barrel, and it is sold "as is." Give the modifications required to the matrix in Figure 4-8 to determine the optimum way to operate the refinery with this new product.
4-21.Prepare a matrix of the objective function and constraint equations
from the process flow diagram for the contact process for sulfuric acid
like the one given in Figure 4-8
for the simple refinery. The process flow diagram for the contact process
is given in Figure 7-21. Use
the following data, and assume that the units not included below have
a fixed operating cost that do not effect the optimization.
4-22.(17)In linear programming there is a dual problem that is obtained from the original or primal problem. Many times the dual problem can be solved with less difficulty than the primal one. The primal problem and corresponding dual problem are stated below in a general form.
Primal Problem Dual Problem
Maximize: cTx Minimize: bTv
Subject to: A x < b Subject to: AT v > c
x > 0 v > 0
The relationships between the primal and dual problems are summarized as follows. First, the dual of the dual is the primal problem. An m x n primal gives an n x m dual. For each primal constraint there is a dual variable and vice versa. For each primal variable there is a dual constraint and vice versa. The numerical value of the maximum of the primal is equal to the numerical value of the minimum of the dual. The solution of the dual problem is the Lagrange Multipliers of the primal problem.
a. Give the primal problem of the following dual problem.
Minimize: 10v1 + 15v2
Subject to: v1 + 5v2 > 8
v1 + v2 > 4
b. Solve the dual problem by the Simplex Method.
c. Using the solution of the dual problem, determine the optimal values for the variables in the primal problem.
4-23.The dual problem of linear programming can be obtained from the primal problem using Lagrange Multipliers. Using the form of the equations given in problem 4-22 for the primal problem and, considering the slack variables have been added to the constraints, show that the Lagrangian function can be written as:
L(x, l) = cT x + lT(A x - b)
Rearrange this equation to give the following form.
L(x, l) = -bTl + xT(AT + c)
Justify that the following constrained optimization problem can be obtained from the Lagrangian function:
Minimize: bTl
Subject to: ATl > c
This is the dual problem given in problem 4-22. Note that the independent variables of the dual problem are the Lagrange Multipliers or "shadow prices" of the primal problem.
4-24.A primal programming can be converted into a dual problem as described in problems 4-22 and 4-23. This approach is used when the dual problem is easier to solve than the primal problem. The general form of the primal problem and its dual was given in problem 4-22.
a. Solve the dual problem of the primal problem and its dual given below.
Primal problem
Minimize: 10x1 + 6x2 + 8x3
Subject to: x1 + x2 + 2x3 > 2
5x1 + 3x2 + 2x3 > 1
Dual problem:
Maximize: 2v1 + v2
Subject to: v1 + 5v2 < 10
v1 + 3v2 < 6
2v1 + 2v2 < 8
b. In this procedure the solution of the primal problem is the negative of the coefficients of the slack variables in the objective function of the final iteration of the Simplex Method of the dual problem, and the solution of the dual problem is the negative of the Lagrange Multipliers for the primal problem. Give the solution of the primal problem and the Lagrange Multipliers for the primal problem, and show that the minimum of the objective function of the primal problem is equal to the maximum of the objective function of the dual problem.
c. In the primal problem give the matrix to be inverted to compute the inverse of the optimal basis.
d. Compute the Lagrange multipliers using equation (4-22), and show that they agree with the solution from the dual problem.
e. A new variable x6 is added to the problem, as shown below.
Minimize: 10x1 + 6x2 + 8x3 + 2x6 = p
Subject to: x1 + x2 + 2x3 + x4 + 5x6 = 2
5x1 + 3x2 + 2x3 + x5 + 3x6 = 1
Will the optimal solution remain optimal or will the problem have to be resolved? Explain.