**Next message:**A.D.Bhatt: "Triangulation Algo"**Previous message:**Jody Champion: "EPSON selects YARC RIP for new 9000 printer"**Maybe in reply to:**Monica & Glenn Whiteside: "ATTN: Ray Brandes on Linear Programming"**Next in thread:**Ray Brandes: "Re: ATTN: Ray Brandes on Linear Programming"**Reply:**Ray Brandes: "Re: ATTN: Ray Brandes on Linear Programming"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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/

**Next message:**A.D.Bhatt: "Triangulation Algo"**Previous message:**Jody Champion: "EPSON selects YARC RIP for new 9000 printer"**Maybe in reply to:**Monica & Glenn Whiteside: "ATTN: Ray Brandes on Linear Programming"**Next in thread:**Ray Brandes: "Re: ATTN: Ray Brandes on Linear Programming"**Reply:**Ray Brandes: "Re: ATTN: Ray Brandes on Linear Programming"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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