Linear Programming Questions and Answers:
Questions:
Q:1
Define and discuss the linear programming technique, including assumptions of linear programming and accounting data used therein. See answer.
Q:2
What is meant by the unit cost in linear programming problems? See answer.
Q:3
Hale Company manufactures products A and B, each of which requires two processes, grinding and polishing. The contribution margin is $3 for A and $4 for B. A graph showing the maximum number of units of each product that can be processed in the two departments identifies the following corner points: A = 0, B = 20; A = 20, B = 10; A = 30, B = 0. What is the combination of A and B that maximizes the total contribution margin? See answer.
Q:4
What is the simplex method? See answer.
Q:5
The Golden Hawk Company wants to maximize the profits on the products A, B, C. The contribution margin for each product follows:
| Product |
Contribution Margin |
| A |
$2 |
| B |
$5 |
| C |
$4 |
The production requirements and departmental capacities, by departments, are as follows:
| Department |
Production Requirement By Product (Hours) |
Departmental Capacity (Total Hours) |
|
A |
B |
C |
30,000 |
| Assembling |
2 |
3 |
2 |
38,000 |
| Painting |
1 |
2 |
2 |
28,000 |
| Finishing |
2 |
3 |
1 |
|
Formulate the objective function and the constraints. See answer.
Q:6
Formulate the objective function and the constraints for a situation in which a company seeks to minimize the total cost of materials A and B. The per pound cost of A is $25 and B, $10. The two materials are combined to form a product that must weigh 50 pounds. At least 20 pounds of A and no more than 40 pounds of B can be used. See answer.
Q:7
Discuss the components of a simplex tableau. See answer.
Q:8
What is the purpose of a slack variable? See answer.
Q:9
A partial linear programming maximization simplex tableau for products x and y and slack variables s1 and s2 appears below:
|
Mix |
0 |
6 |
7 |
0 |
0 |
| Quantity |
x |
y |
s1 |
s2 |
| 7 |
y |
4 |
2 / 3 |
1 |
1 / 3 |
0 |
| 0 |
s2 |
4 |
4 / 3 |
0 |
-1 / 3 |
1 |
(a) Compute the index row.
(b) Has an optimum solution been reached? Explain.
(c) Suppose that one unit of s1 were placed in the solution. What effect would this have on product y? See answer.
Q:10
What is the purpose of an artificial variable? See answer.
Q:11
What is a shadow price? Explain its significance. See answer.
Q:12
An optimal linear programming simplex tableau appears below for products x and y and slack variables s1 and s2. Both constraints are of the ≤ type.
|
Mix |
0 |
12 |
14 |
0 |
0 |
| Quantity |
x |
y |
s1 |
s2 |
| 12 |
x |
3 |
1 |
0 |
-1 / 4 |
3 / 4 |
| 14 |
y |
2 |
0 |
1 |
1 / 2 |
-1 / 2 |
|
|
64 |
0 |
0 |
4 |
2 |
(a) What is the value of an additional unit of a constraint corresponding to s1, i.e., what is the shadow price for s1?
(b) Compute the maximum decrease over which the shadow price for s2 is valid. See answer.
Q:13
Define dynamic programming. See answer.
Q:14
Select the answer which best completes the statement: See answer.
|
(a)
|
The simplex method of the linear programming is:
- A general procedure that will solve only two variables simultaneously.
- A means of determining the objective function in the problem.
- A means of determining the constraints in the problem.
- A general procedure for solving all linear programming problems.
|
| (b) |
A decision model designed to help its user find the best alternative or decision rule according to some criteria is said to be:
- Random
- Probabilistic
- Optimizing
- Satisfying
|
| (c) |
The use that is not an application of linear programming is:
- Scheduling flight crews to various flights to minimize costs.
- Routing production to minimize costs
- Determining the optimum trade-off between time and costs to maximize profits
- Deciding which warehouses will service which customers to minimize total shipping costs.
|
| (d) |
A Company manufactures two products, q and p, in a small building with limited capacity. The sales price, cost data, and production time are given below:
|
Product q |
Product P |
| Sales price per unit |
$20 |
$17 |
| Variable cost of producing and selling a unit |
$12 |
$13 |
| Hours to produce a unit |
$3 |
$1 |
Based on this information, the contribution margin maximization objective function for a linear programming solution may be stated as:
- 20q + 17p
- 12q + 13p
- 3q + 1p
- 8q + 4p
|
| (e) |
Globe Manufacturing has several plants in different cities and servers customer in various other cities. Globe wants to know the best way to schedule shipments from various plants to various customers and has been advised that the problem can be solved using linear programming. In transporting cost minimization problem, the usual coefficients of the objective function would be:
- Usage rates for transportation facilities
- Restrictions on transportation facilities
- Shipping costs
- Time estimates for the critical path
|
| (f) |
Fite company plans to expand its sales force by opening as many as 10 new branch offices and has set $5,200,000 as the capital available for this purpose. Fite will open only two types of branches: 10-person branches (type a), initial outlay of $650,000 each; and 5 person branches (type b), initial outlay of $335,000 each. Expected annual after tax cash inflow for types a and b is $46,000 and $18,000, respectively. No more than 100 employees will be hired for the new branch offices. In a system of inequalities for a linear programming model, the one not representing a constraint is:
- a + b ≤ 10
- 10a + 5b ≤ 100
- $46,000a + $18,000b ≤ $64,000
- $6,50,000a + $335,000b ≤ $5,200,00
|
| (g) |
In a system of inequalities for a linear programming model, to equalize an inequality such as 3x + 2y 15:
- Invert the inequality
- Add a slack variable
- Add an artificial variable
- Multiply each variable by -1 See answer.
|
Answers:
A:1
Linear programming is a quantitative technique for selecting an optimum plan. It is an efficient search procedure for finding the best solution to a problem containing many interactive variables. The desired objective is to maximize some function e.g., contribution margin, or to minimize some function, e.g., costs. Determination of the optimum objective is usually subject to various constraints or restrictions on possible alternatives. These constraints describe availabilities, limitations, and relationships of resources to alternatives.
The key assumption is linearity, which prevails in two respects. First, the contribution margin or cost associated with with one unit of product or activity is assumed to be the same for all identical units. Second, resource inputs per unit of activity are assumed to be the same for all units. Another assumption inherent in linear programming is that all factors and relationships are deterministic.
Accounting data such as the contribution margin or cost factors would be used in determining the objective – to maximize the contribution margin or to minimize cost. Accounting data would also be used to establish the constraints. Such constraints might include one or more of the following: machine capacity, labor force, quantity of output demanded, time, or capital.
Once the data are available, the linear programming model (equations) might be solved graphically, if no more than two variables are involved, or by the simplex method. When the model contains many variables and constraints, the solution may require the use of a computer.
A2:
In linear programming problems, the unit cost refers to the directly traceable variable cost rather than the total cost.
A3:
(a = 0, b = 20); $3(0) + $4(20) = $80 CM
(a = 20, b = 10); $3(20) + $4(10) = $100 CM – Maximum CM
(a = 30, b = 0); $3(30) + $4(0) = $90 CM
A4:
The Simplex method is an iterative process which approaches an optimum solution in such a way that an objective function of maximization or minimization is fully reached. Each iteration in this process shortens the distance (mathematically and graphically) from the objective function.
A5:
CM = 2a + 5b + 4c
Assembling: 2a + 3b + 2c ≤ 30,000
Painting: 1a + 2b + 2c ≤ 38,000
Finishing: 2a + 3b + 1c ≤ 28,000
A6:
C = 25a + 10b
Subject to: a +b = 50; a ≥ 20; b ≤ 40
A7:
Components of a simplex tableau:
- The objective row contains the coefficients of the objective function.
- The variable row contains the variables of the problem, including slack variables.
- The problem row contains the coefficient of the variables in the constraints with one row for each constraint. Variable not included in a constraint are assigned zero coefficients. New problem rows are computed with each iteration.
- The objective column represents the contribution margin per unit of the variables in the solution, and receives different entries at each iteration.
- The variable column contains the variables used to find the solution. In the first tableau, only slack and artificial variables are entered in this column, since a no-production situation is the starting point of the iteration process.
- The quantity column shows the constant values of the constraints in the first tableau, it shows the solution mix.
- The index row contains values which indicate whether an optimum solution has been reached; if there are any negative numbers in it, an optimum solution has not yet been reached. The value in the objective column represents the total contribution margin.
A8:
The slack variable is a fictitious variable that takes up the slack in the inequalities. Mathematically speaking, slack variables are treated like other variables and their fictitious character disappears in the solution process. Slack variables enter the objective function but receive a coefficient of zero and do not influence the final result.
A9:
(a) The index row is computed as follows:
| Step 1 and 2:4(7) + 4(0) = 28
2 /3(7) + 4/3(0) = 14/3
1(7) + 0(0) = 7
1/3(7) + [-1/3(0)] = 7/3
0(7) + 1(0) = 0 |
Step 3:28 – 0 = 28
14/3 – 6 = -4/3
7 -7 = 0
7/3 – 0 = 7/3
0 -0 = 0 |
(b) An optimum solution has not been reached because a negative figure, -4/3, still remains in the index row. Hence, the contribution margin can be increased by introducing x into solution
(c) Product y would be reduced by 1/3 of a unit.
A10:
The artificial variable is a computational device allowing two types of restrictions to be treated: the equality type (=) and the greater-than-or-equal-to type (≥).
A11:
A shadow price is the result of relaxing a constraint in a contribution margin maximization problem or cost minimization problem. The optimum mix of a firm assumes a given set of constraints. If a constraint is relaxed, a shadow price results and simply shows the change in the contribution margin per unit or in costs thereby results. The shadow price thus gives a maximum unit variable cost increase that could be incurred to acquire one more unit of a constraining factor. Shadow prices are only valid over a relevant range. Shadow prices also indicate the opportunity cost of using a resource for some other purpose.
A12:
| (a) |
$14 |
(1/2) |
= |
$7 |
|
$12 |
(-1/4) |
= |
-3 |
|
|
|
|
—— |
|
|
|
|
$4 |
|
|
|
|
==== |
| (b) |
|
(1) |
(2) |
|
|
Product |
Units |
S2 |
S2 |
|
x |
3 |
3 / 4 |
4* |
|
y |
2 |
-1 / 2 |
-4 |
|
*Maximum decrease over which shadow price of S2 is valid |
A13:
Dynamic programming involves breaking a problem into a set of smaller problems and then reassembling the results. It is best suited for decisions that must be made in sequence and that influence future decisions in the sequence.
A14:
| (a) 4 |
(b) 3 |
(c) 3 |
| (d) 4 |
(e) 3 |
(f) 3 |
| (g) 2 |
|
|
|
