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 |
|
|
|
