LINEAR PROGRAMMING

D.W. Ellis & Associates Ltd.

2220 142 Ave. Edmonton, Alta. T5Y 1E6 Canada - (780) 457-7491 -

A Competitive Advantage for Planning and Productivity

This information on Linear Programming is designed to be read sequentially. You can, however, go directly to any of the following sections:

INTRODUCTION TO LINEAR PROGRAMMING

Linear Programming is a method of expressing and optimizing a business problem with a mathematical model. It is one of the most powerful and widespread business optimization tools.

To a person with no background in the management sciences, it may be hard to believe but the tool, linear programming, can be used in a very large variety of business problems. They include:

LINEAR PROGRAMMING; an optimization technique capable of solving an amazingly large variety of business problems. A business objective (e.g. minimize costs of a distribution system), business restrictions (storage capabilities, transportation volume restrictions), and costs/revenue (storage costs, transportation costs) are formulated into a mathematical model. Algorithms for finding the best solutions are used. For more details on linear programming see the section below.

To properly apply linear programming, the analyst must be not only an expert in the tool but also have experience with the particular business situation. In this regard, a team on the project whose members represent expertise in linear programming and in the business expertise work very well.

Some other descriptions of linear programming available on the web are:

EXAMPLE LINEAR PROGRAMMING MODEL

An introductory text on management science or operations research will contain a section on linear programming. The following is an example problem.

A company makes 2 kinds of cement at its plant. It can also purchase these 2 kinds of cement at a different location. As well, it maintains 4 storage locations where it ships product for subsequent delivery to customers. It can also ship cement directly from its plant or point of purchase. It has many customs at various locations. How much of each kind of cement should it produce or purchase? What storages should be supplied from the plant and which from the point of purchase? What customers should be supplied from each of the 6 supply points? This is a large problem and its solution can make the difference between success and failure of the company.

To solve this problem, we need to formulate it as a linear program. Some notation is needed. Let i = 1 to 6 be the 6 points of shipment (the plant, the point of purchase and the 4 storages). Let j = 1 to n be the customers. Let k= 1 to 2 be the products.

Let xa(k) be the amount of product k made at the plant, xb(k) the amount of product k purchased, ta(i=1,2;i=3,6;k) be the amount of product k shipped from the plant and the point of purchase (i=1,2) to the 4 storage locations (i=3,6), and tb(i,j,k) be the amount of product k shipped from the 6 storage locations (i) to the n customers (j).

Let m(k) be the cost of making the product k at the plant, p(k) be the cost of purchasing the product k at the point of purchase, d(i=1,2;i=3,6) be the cost of sending product from the plant or point of purchase (i=1,2) to the 4 storage locations (i=3,6), and c(i,j) be the cost of sending product from the 6 points of shipment to each of the n customers (it is the same for each product).

Let M(k) be the maximum amount of product k that can be made at the plant, P(k) be the maximum amount of product k that can be purchased, and D(j,k) the demand by customer j for product k.

The real business issues that would be included in a full linear programming implementation of this problem include multiple time periods, delivery timing, costs that change with volume, handling situations when all customer demand cannot be met.

The formulation includes a cost objective function to be minimized:


  2              2            2   6               2                    6   n       2

  [ m(k)xa(k) +  [p(k)xb(k) + [   [d(i=1,2;i=3,6) [ta(i=1,2;i=3,6;k) + [   [c(i,j) [tb(i,j,k) 

 k=1            k=1          i=1 i=3             k=1                  i=1 j=1     k=1

The constraints on the solution require that the limits be met:

limit on the amount produced


        xa(k) <= M(k)       for k=1,2

limit on the amount purchased


        xb(k) <= P(k)       for k=1,2

meet customer demand


        6

        [tb(i,j,k)  = D(j,k)  for j=1,n and k=1,2

      i=1       

Existing software would quickly find the optimal solution.

The model should be complex enough to include all of the true details of the situation.

EXAMPLE LINEAR PROGRAMMING USES

OUR SERVICES

D.W. Ellis & Associates Ltd., with 28 years of experience, offers a complete consulting service in the Management Sciences. For our clients, this means being close to your business, knowing your business, and unmatched responsiveness and costs. We have worked with many large and small Alberta and national companies to simulate various aspects of their business.

Our services revolve around 6 main phases of model development:

Feasibility Study

This short study (1-3 weeks) allows the client to obtain a detailed look at what the model will be able to do, the costs and the timing. The client's decision to continue is required at this point.

Model Specification Development

This phase requires significant time on the client's part. The client must provide the modeler with details of his business situation. Included is the level of detail to be modeled, the extent of the process to be modeled, and the format of the input data and reports produced.

Model Development

D.W. Ellis & Associates Ltd. will be responsible for this phase. The client will be provided with intermediate results so progress can be monitored and changes can be made as they are required.

Implementation

This phase is usually very short. The model is transferred to the client's computer and tested. As only PC's are involved, there are typically few complications.

Client Training

Although the client will be involved as the model is designed and developed, additional training on the use of the model will be included in the plan. The client will have been involved with the details of the input data and the reports produced. An organized approach to case analysis and the interpretation of the data will be covered.

Validation

The client must select a typical period of historical time, and collect the data for this time period, and the model is run. Its results are compared to the known results for this period. The model and the data are adjusted to obtain a very close fit between the model results and the known results. The model is now ready for extensive case studies.

EXPERIENCE

Industries with whom D.W. Ellis and Associates Ltd. has consulted concerning facilities or operations modeling:

D.W. ELLIS & ASSOCIATES LTD.

D.W. Ellis & Associates Ltd. is a management consulting firm specializing in the management sciences. With 28 years of industry experience in management science, David Ellis has a very good mix of academic knowledge of linear programming and practical experience using LPs. He has developed over 20 significant LP models for various business situations. These include a gas production system, refinery scheduling, oil and gas plant production, steel production, manufacturing and assembly production, tax planning, human resource planning, and inventory management.

David W.H. Ellis

Dr. Ellis has experience in the oil, gas and chemical industries, manufacturing, mining and service organizations. He has 28 years experience working in the Management Sciences. He has spent a considerable amount of this time working with and developing LP models. He has developed a modeling concept that can be applied to almost any business situation. This approach allows models to be developed faster, be validated more easily, and cost less.

Dr. Ellis has been on the executive of many national associations and is currently a member of the Canadian Operational Research Society, The Institute of Management Science, the Operational Research Society of America, the Canadian Institute of Mining, and the American Society for Quality Control. He has presented papers and been a guest panelist at many meetings.

University

His formal education is:


You are viewer .

If you have questions or comments, please e-mail .

Back to D.W. Ellis & Associates Ltd.'s management science page