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
- Example Linear Programming Model
- Example Linear Programming Uses
- Our Services
- Our Experience
- D.W. Ellis & Associates Ltd.

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:

- transportation distribution problems
- production scheduling in oil & gas, manufacturing, chemical, etc industries
- financial and tax planning
- human resource planning
- facility planning
- fleet scheduling

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

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.

- Production planning in a chemical plant. This model optimized the operation of each unit and the use of storage facilities to meet demand at least cost.
- Refinery scheduling. Similar to the above but more than one location was involved and distribution to the customers was included.
- Rail fleet optimization. The model decided on the rail car leases for 3 types (heated, insulated, normal) of rail cars to minimize the cost of distributing product throughout Canada. Seasonal variations and car movement across the country were included.
- Truck fleet utilization. Given a fleet of trucks of different sizes and operating characteristics and costs, this model decided what trucks should be used for what deliveries from a distribution terminal to customers.
- Truck designs. The axle spacing on trucks are subject to complex loading rules. In some provinces, the design of these axle spacings can be modeled using linear programming to maximize load.
- Tax model. Personal and corporate taxes can be minimized using a linear programming model. It includes the best mix of dividends and salaries and the progressive personal tax rates.
- Oil and Gas production planning. This model optimized the actual production and the allocation of production to contracts to minimize costs to the producer.
- 'Take or Pay' optimization. Formerly gas contracts in Alberta included minimum volume purchases. In low demand periods, the purchaser had to decide from which contracts to pay for gas even though it was not delivered. Complicated payment schemes and recoveries were included.
- Off site storage locations were determined through case studies using an integer linear programming model. The entire product storage and delivery plan was optimized for various configurations of locations for the off site storage locations in order to select the best set of these storage locations.

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
- Model Specification Development
- Model Development
- Implementation
- Client Training
- Validation

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.

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.

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.

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.

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.

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.

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

- Government
- Oil and Gas
- Chemical
- Mining (including the oil sands/tarsands)
- Steel
- Pipeline
- School Boards
- Transit Properties
- Cement Production and Distribution
- Aluminum Production

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.

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.

- BSc in mathematics (Queen's University)
- MSc in statistical mathematics (Queen's University)
- MBA in management science (York University)
- PhD in management science (University of Toronto).

You are viewer .

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

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