Optimizing a Gourmet Canned Foods Production

Table of contents:

1. Introduction

2. Standard form

3. The problem

4. Solution of the Problem
4.1 Primal
4.2 Answer Report
4.3 Sensitivity Report
4.4 Limits Report
4.5 Dual
4.6 Answer Report
4.7 Sensitivity Report
4.8 Limits Report

5. Primal Dual theorem
5.1 Primal
5.2 Dual
5.3 Economic Interpretation

6. References

1. Introduction:

In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

Linear programming is an important field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. (wikipedia.com)

Linear programming (LP) is one of the most widely applied O.R. techniques and owes its popularity principally to George Danzig's simplex method (Danzig 1963) and the revolution in computing. It is a very powerful technique for solving allocation problems and has become a standard tool for many businesses and organisations. Although Danzig's simplex method allows solutions to be generated by hand, the iterative nature of producing solutions is so tedious that had the computer never been invented then linear programming would have remained an interesting academic idea, relegated to the mathematics classroom. Fortunately, computers were invented and as they have become so powerful for so little cost, linear programming has become possibly one of the most widespread uses for a personal PC. (wikipedia.de)

There are of course numerous software packages which are dedicated to solving linear programs (and other types of mathematical program), of which possibly LINDO, GAMS and XPRESS-MP are the most popular. All these packages tend to be DOS based and are intended for a specialist market which requires tools dedicated to solving LPs. In recent years, however, several standard business packages, such as spreadsheets, have started to include an LP solving option, and Microsoft Excel is no exception. The inclusion of an LP solving capability into applications such as Excel is attractive for at least two reasons. Firstly, Excel is perhaps the most popular spreadsheet used both in business and in universities and as such is very accessible. Second to this, the spreadsheet offers very convenient data entry and editing features which allows the student to gain a greater understanding of how to construct linear programs.

(http://www.economicsnetwork.ac.uk/cheer.htm)

A mathematical programming model is linear programming as long as each function is expressed in linear form. It is possible to limit the decision so much that there is no possible way to satisfy all the limits (infeasibility).

2. Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

- A linear function to be maximized

illustration not visible in this excerpt

- Problem constraints of the following form

illustration not visible in this excerpt

- Non-negative variables

illustration not visible in this excerpt

3. The problem:

This small canning company is specialized in gourmet canned foods. Their five products are listed below. Marketing’s estimated maximum daily demands are given in terms of cans (each of which contains 16 ounces by weight). Marketing has also made commitments in the form of signed contracts to deliver. The maximum demands include these signed contract commitments.

illustration not visible in this excerpt

The production department obtains input materials and fills 16 ounce cans. All quantities are in ounces, all costs and sales prices/can are in $. There is a maximum production limit of 24,000 cans/day. Canning costs are constant. Requirements by can type are given below. It costs the company five cents to process each can. Current sales price is given in the last column.

illustration not visible in this excerpt

The company has a contract with a ham supplier for daily delivery of up to 30,000 ounces of ham at $0.40 per ounce. They also have a contract with a lima bean supplier for up to 100,000 ounces of lima beans per day at $0.05 per ounce. They do not have to pay for materials they do not use. They grow their own jalapenos, which cost $0.10 per ounce to pick (shown above). There is more jalapeno supply than can be used. There is also an unlimited supply of tangy bayou water.

illustration not visible in this excerpt

Profit = 0.21 H&B + 0.20 JHB + 0.10 LB + 0.15 JLB + 0.10 JP

Lower Constraints:

illustration not visible in this excerpt

Upper constraints:

illustration not visible in this excerpt

[...]