- 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
4-1. Solve the following problem by the Simplex Method.
4-2. Solve the following problem by the Simplex Method.
Start with x 4-3 a. Solve the following problem by the Simplex Method.
4-4. Solve the following problem by the Simplex Method.
Solution
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:
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 (b 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.
2x
-x 4-8a. Solve the following problem
using the Simplex Method using an artificial variable x
4-9.Consider the following linear programming problem
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.
4-11.Consider the following linear programming problem.
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.
4-13
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 x
Determine the optimal values of
x 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 x The plant operates under the following constraints:
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:
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
c
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:
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.
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.
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:
Rearrange this equation to give the following form.
Justify that the following constrained optimization problem can be obtained from the Lagrangian function:
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.
Will the optimal solution remain optimal or will the problem have to be resolved? Explain. |