Re: ATTN: Ray Brandes on Linear Programming

From: Monica & Glenn Whiteside (SiderWhite@worldnet.att.net)
Date: Sat Feb 27 1999 - 07:50:43 EET


Ray:

Here's an example of a Linear Programming model used for short-term
financial planning to give you a feel for what LP can do. The "accurate"
end results of the LP come from the use of accurate values for the decision
variables and the use of good model constraints. You can calculate (or
graphically solve for simple two variable systems) these linear equation
systems by hand but it is usually quite tedious - computers are wonderful
tools for number crunching, especially if you appreciate how tedious it is
to manually do the calculations!

Short-Term Financial Planning Linear Programming example (excerpted from
Operations Research, Applications and Algorithms, 3rd Ed., by Wayne L.
Winston, pp. 81-84):

Semicond is a small electronics compnay which manufactures tape recorders
and radios.
The per-unit labor costs, raw material costs, and selling price of each
product are given in the table below:
                            Tape Recorder Radio
Selling price $100 $90
Labor cost $ 50 $35
Raw material cost $ 30 $40

On December 1, 1998, Semicond has enough raw material to manufacture 100
tape recorders and 100 radios. On this same date, the company's balance
sheet is shown in the table below:
                                            Assets Liabilities
Cash $10,000
Accounts Receivable $ 3,000
(money owed to Semicond)
Inventory outstanding $ 7,000
(value of December 1, 1998 raw material inventory = 30*100 + 40*100 =
$7,000)
Bank loan $10,000

Semicond's asset/liability ratio (called the current ratio) is
$10,000+$3,000+$7,000/$10,000 = 2. Semicond must determine how many tape
recorders and radios should be produced during December. Demand is large
enough to ensure that all the goods produced will be sold (must be nice!).
But all sales are on credit and payment for goods produced in December will
not be received until February 1, 1999. During December, Semicond will
collect $2,000 in accounts receivable and Semicond must pay off $1,000 of
the outstanding loan and a monthly rent of $1,000. On January 1, 1999
Semicond will receive a shipment of raw material worth $2,000, which will be
paid for on February 1, 1999. Semicond's management has decided that the
cash balance on January 1, 1999 must be at least $4,000. Also, Semicond's
bank requires that the current ratio at the beginning of January must be at
least 2. To maximize profits from December production, (revenues to be
received) - (variable production costs), what should Semicond produce during
December?

The following decision variables are defined as:
        x1 = number of tape recorders produced during December
        x2 = number of radios produced during December

To express the objective function (what we want to solve for):
    Contribution to profit (tape recorder) = $100 - $50 - $30 = $20
    Contribution to profit (radio) = $90 - $35 - $40 = $15

This leads to the objective function:
                    max z = 20x1 + 15x2

Semicond also has the following constraints:

Constraint 1: Because of limited availability of raw material, at most 100
tape recorders can be produced during December (x1 <= 100).

Constraint 2: Because of limited availability of raw material, at most 100
radios can be produced during December (x2 <= 100).

Constraint 3: Cash on hand on January 1, 1999 must be at least $4,000 per
management's financial goal. January 1 cash on hand = December cash on hand
+ accounts receivable collected during December - portion of laon repaid
during December - December rent - December labor costs
= 10,000 + 2,000 - 1,000 - 1,000 - 50x1 - 35x2
= 10,000 - 50x1 - 35x2
Therefore Constraint 3 can be written as 10,000 - 50x1 - 35x2 >= 4,000
The "preferred or standard form" is used where all the variables are on the
left-hand side and the constant is on the right-hand side (LP computer
programs require the problem to be set up this way). Constraint 3 is then
rewritten as:
50x1 + 35x2 <= 6,000

Constraint 4: (January 1 assets/January 1 liabilities) >= 2 per bank
requirements.
Constraint 4 determines Semicond's January 1 cash position, accounts
receivable, inventory position, and liabilities in terms of x1 and x2.
Through some algebriac manipulation (too lengthy to be shown here) this
constraint is finally reduced to the following standard form:
20x1 + 15x2 >= 2,000

Combining all these elements together into what is called an LP "model"
yields the following problem:

max z = 20x1 + 15x2 (objective function)
subject to (s.t.) the following constraints:
                x1 <= 100 (tape recorder constraint)
                x2 <= 100 (radio constraint)
  50x1 + 35x2 <= 6,000 (cash position constraint)
  20x1 + 15x2 >= 2,000 (current ratio constraint)
           x1, x2 >= 0 (sign restrictions, so that the decision
variables can only assume
                                         nonnegative values)

When solved graphically or by computer program, the following optimal
solution is obtained:

z = $2,500, x1 = 50, x2 = 100

where Semicond can maximize profits by manufacturing 50 tape recorders and
100 radios in December which will contribute 20(50) + 15(100) = $2,500 to
profits.

It would be an interesting experiment to try a modified version of the above
LP model out on a small service bureau operation to see how well this works.

The above LP problem example is a relatively simple one, needless to say
they can get extremely complex when many more variables are involved. LP
has been successfully used for many different applications such as for
work-scheduling, financial and investment planning and strategy (in fact
some universities now offer degrees in "financial" engineering where they
extensively use LP models for optimization problems), refinery crude oil
blending, production process models, multiperiod or dynamic inventory
models, and many others.

Hope this answers your questions,

Glenn Whiteside

>Thanks for the reply. Now I think I understand what LP is. My next question
is
>this:
>Don't you need accurate results from each choice in order for the program
to
>determine the outcome? If you do have accurate results, why do you need the
>program?
>Perhaps a small (simple) example of the inputs would help clairify my
puzlement.
>
>Regards, Ray
>
>Monica & Glenn Whiteside wrote:
>
>> Ray:
>>
>> Linear Programming or just "LP" is a powerful tool using systems of
linear
>> equations (matrices and vectors) and various algorithms such as the
simplex
>> algorithm for solving optimization problems. There is an objective
function
>> consisting of various decision variables which are subject to certain
>> constraints which is solved for to determine a maximum (usually revenue
or
>> profit) or minimum (usually costs) or a combination or balance of both.
It
>
>

For more information about the rp-ml, see http://ltk.hut.fi/rp-ml/



This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:51:05 EEST