Páll Jensson & Pétur K. Maack

Engineering Faculty

University of Iceland

The Practical Use of Duality

in Product Mix Optimization

Abstract

Linear Programming is a well-known method for optimizing product mix when planning production, at least in the literature. In real life, however, applications are in most cases limited to big companies. In small and medium-sized firms the product mix decisions are usually taken by simple comparison of net profit contribution of the various products, or by some ad hoc methods.

This paper presents new ideas of graphical decision aid for simple product mix decisions based on the duality theory of Linear Programming. The usefulness of these ideas is demonstrated for the case of daily production planning in fish processing. A prototype system for decision support is described and the application possibilities in fish processing are discussed.

Key-words

Linear Programming, Product Mix, Duality, Graphical Decision Aid.

Acknowledgements

The authors would like to thank Mr. Grétar Mar Steinarsson for programming the system presented in this paper

Introduction

The duality theory of Linear Programming (LP) describes the mathematical property that to every LP model there is a corresponding dual model such that:

Primal:max z = cx;Axb;x  0.

Dual: min w = b'y;A'yc';y 0.

Here x are decision variables and y are dual variables (shadow prices or Lagrange multipliers), c and b are data vectors, A is a data matrix and ' means transposed.

Duality is an interesting property and the beauty of mathematics is at its best here. However, beside the interpretation and use of the shadow prices, it seems that this theory has not gained a widespread use in real life. Textbooks give an economic interpretation of the dual model, like [1] page 204 or [2] page 275. It is the experience, however, that this interpretation is not widely understood or used in industry, at least not in small firms.

Duality is, however, not at all useless in real life. In this paper a graphical decision aid based on the dual model of Linear Programming, for use in product mix problems, will be proposed. The objective is that the decision aid is applicable in small companies even though there is no knowledge of the theory of Linear Programming in the company. As an example of fields of application the biggest industry of Iceland, fish processing, is chosen. This industry is characterized by a great number of small firms with practically no knowledge of optimization models, having to deal with product mix decisions almost daily.

Product mix decisions in fish processing

As other kind of food production, fish processing has to solve the problems connected with the fact that either the raw materials or the finished products, or in some cases even both, are perishable and difficult to store because of limited shelf life. Also, the quantity and quality of raw materials are subject to frequent and often great fluctuations and therefore offer new problem situations to the production managers, even every day.

In [3] an LP model of daily production planning in fish processing plants was proposed. The model covers many aspects of day to day decision making. The LP model discussed in this paper is a special case of the model in [3]. Here, the product mix aspect will be studied for one fish species and under the following assumptions:

1. The product mix is to be decided for one planning period, say a day or a week, without any inventory considerations or other coupling between periods.

2. The limiting resources, i.e. potential bottlenecks are only two, in our case raw material and manpower.

These assumptions might seem rather restricting, in particular the latter. However, let us keep in mind that one is dealing with small firms where it is very likely that the production bottlenecks that really matter are few. In fish processing the quantity of raw material varies a lot from day to day so typically the bottleneck is the raw material one day but the manpower the next day.

The decision variables in our model are x, the quantity to be produced in the planning period, x(j) for product no. j. Contrary to other manufacturing industries where raw material is bought as needed, many fish processing plants in Iceland cannot control the supply of fish. One must process whatever the fishing fleet brings to land. Therefore, raw material quantity is a constraint rather than a decision variable.

The data for the model is as follows:

c is the net profit contribution of the products, c(j) for product no. j ($/unit)

m is manpower requirements, m(j) for product no. j (hours/unit)

r is raw material requirements, r(j) for product no. j (kg/unit)

M is available manpower (hours)

R is available raw material (kg)

In [4] it is pointed out how important it is to calculate the net profit contribution coefficients c(j) correctly. The standard definition of unit contribution is unit sales price minus all variable unit costs, including in particular labor and raw materials, resulting in contribution to cover fixed costs and profit. However, one should be careful not to subtract sunk cost but only cost that will be affected by the decision making for which the calculation of contribution was intended.

As we have observed in the fish processing industry, it is a common error to subtract labor and raw material costs as these are usually considered variable costs. In our case however, when planning production for say a day in fish processing, this is wrong as people will be paid for the whole day regardless of the product mix decisions made, and the raw material is already bought and the price paid is therefore sunk cost. So c(j) is mainly the sales price ($/unit) minus some small amount of variable cost like packing material and possibly an estimated inventory cost depending on how long time we anticipate until the product will be sold and paid for.

The LP model and its dual are:

Primal:max z =  c(j) x(j)(maximizing total contribution)

Manpower: m(j) x(j)  M(shadow price of M is yM $/hour)

Raw material: r(j) x(j)  R(shadow price of R is yR $/kg)

x 0

Dual:min w = M yM + R yR

Product no. j:m(j) yM + r(j) yR c(j)

yM, yR 0

Notice that because the primal has only two constraints the model will never propose more than two products in the production plan. This is actually a fortunate property in our case as many reasons outside the scope of our model suggest that few products should be in the product mix at the same time.

Table 1
Lab / 600 / 0 / Buy R / 100 / 0 / Sell R / 35
RawMat / 65 / 0 / Overt / 2500 / 0 / Sell W / 200
Prod / Yield / Prod. / Price / RM / Labor / Emb / Contr
1/0 / kg/kg / kg/h / $/kg / $/kg / $/kg / $/kg / $/kg / $/hour / $/Rkg
1 / k1 / 41% / 14,2 / 299 / 159 / 42 / 10,2 / 88 / 4246 / 123
1 / k2 / 41% / 15,0 / 294 / 159 / 40 / 8,1 / 87 / 4410 / 121
0 / k3 / 41% / 14,3 / 400 / 159 / 42 / 9,4 / 190 / 5720 / 164
1 / k4 / 41% / 18,7 / 255 / 159 / 32 / 5,3 / 59 / 4769 / 105
1 / k5 / 41% / 20,3 / 248 / 159 / 30 / 5,0 / 55 / 5034 / 102
1 / k6 / 45% / 28,4 / 227 / 144 / 21 / 7,9 / 54 / 6447 / 102
1 / k7 / 43% / 22,8 / 240 / 151 / 26 / 7,9 / 55 / 5472 / 103
1 / k8 / 43% / 21,2 / 236 / 151 / 28 / 8,5 / 48 / 5003 / 101
1 / k9 / 41% / 15,0 / 312 / 159 / 40 / 7,2 / 106 / 4680 / 128
Raw Mat / 4000 / kg
Manpower / 200 / hours
Prod. / Yield / Price
kg/h / % / $/kg
k6 / 28,4 / 0,45 / 227
k9 / 15 / 0,41 / 312

Fig. 1

Graphical representation of the dual

A graphical representation of the dual is possible as the dual variables are only two. Fig. 1 is based on real data from a fish processing plant in Iceland, see Table 1. The axes are the shadow prices yR and yM. As the figure shows each product is represented by a dual constraint in the dual model. The possible optima, depending on the slope of the dual objective function, the ratio R/M, are shown in Fig. 1 by letters A, B and C. On Fig. 2 the primal problem is shown, where all products except the two indicated as the best candidates by the dual are excluded.

The optimal strategy is clear in principle: When R/M is very small one looks for the highest point on the yR axis in Fig. 1, and vice versa (high R/M means that one looks for a high value on the yM axis), i.e. choose the product that results in the highest value per unit of bottleneck ($/kg raw material or $/hour of manpower) whenever it is clear which resource is the bottleneck. There are however intermediate values of R/M where the best decision is not as obvious. Therefore the decision maker, usually the plant foreman, needs a decision aid like the one proposed in this paper.

The results above are in accordance with the principles in "Optimized Production Technology", see for example [5] page 761, where the emphasis is on "Bottleneck Scheduling", i.e. finding the bottlenecks in the production process and then planning production around these bottlenecks. However, the calculation of net profit contribution per unit of a bottleneck resource and using this to aid in product mix decision situations is not found in common textbooks on business administration.

Fig. 2

Use of Net Profit Contribution for Product Mix Decisions

It is noteworthy that for a period of more than 20 years, similar principles as discussed above have been in use in the fishing industry in Iceland. Even in the very small companies, computers have been used to calculate and print out for the production managers, for every single product:

cR(j) = c(j)/r(j), net profit contribution per kg raw material ($/kg)

cM(j) = c(j)/m(j), net profit contribution per hour manpower ($/hour)

These numbers can be seen on Fig. 1, where the dual constraints meet the axes. To take an example of their use, the production manager might select a product with low m(j), a "fast" product, giving the highest cM(j), on days when manpower is a bottleneck. Vice versa, on days when there is little raw material available, he would choose the product with highest cR(j).

The problem is what to do when it is not clear what is the bottleneck. Here we propose that Fig.1, the dual model graph, could be used as a decision aid for the production managers.

Graphical Decision Support for Product Mix

By using Fig. 1, the production manager is able to see graphically on the axes the coefficients cR(j) and cM(j) for the various products, which he is used to read from the computer printouts. The slope of the objective function for the dual model is determined by the ratio R/M. He can see which two products are the candidates for the optimal product mix, like point B on Fig. 1, which for a certain range of the ratio R/M results in an optimal combination of net profit contribution per unit of each of the two bottlenecks. Because of this, and because a concept like duality is not very well known in the industry, Fig.1 is called the "Contribution Graph".

A prototype of a graphical system as is described here was developed by the authors using Excel 5.0 and Visual Basic. The system begins by presenting a table for editing the basic assumptions, see Table 1, and after that Fig. 1 appears. When the user selects with the mouse a point on Fig. 1, for example A, B or C, the system calculates the corresponding product mix (or simply the quantity to produce in case of a single product solution) and the total net profit contribution.

If the user wishes, he can bring up Fig. 2, i.e. the graph of the primal model for the two products in the solution, showing the two bottleneck resources as constraints. Therefore, we have called Fig. 2 the "Bottleneck Graph". Also the objective function is shown on the graph.

Fig. 3

Furthermore, the user can order a so-called "Buyer’s Graph", see Fig. 3, which is a shadow price graph showing the shadow price yR, that is the maximum attractive price to pay for additional units of the raw material, as a function of increasing R. This could become an important decision aid when buying fish on the daily fish markets, possibly in the future on a lap top computer. A similar graph for the shadow price of manpower, which increases as yR decreases, could be added as an aid for decisions regarding overtime work.

All these graphs, and the assumption table, are stored in the Excel 5.0 system in one workbook, making it very easy to jump between sheets. The system has been demonstrated for several production managers in Icelandic fish processing plants and the responses have been very encouraging, although further dialog and requirements analysis is necessary. Also, more programming effort is needed to integrate the system into the software environment in freezing plants and potentially also into software on-board of factory trawlers.

Conclusions

In this paper, new ideas of graphical decision aid for simple product mix decisions based on the duality theory of Linear Programming have been presented. The usefulness of these ideas was demonstrated for the case of daily production planning in fish processing. A prototype system for decision support was described and the application possibilities in fish processing were discussed.

The idea presented in this paper can be extended and enriched in several ways. The possibilities to buy more raw material and man-hours (overtime work), or reversely to sell some of the resources, can easily be added to the models and to Fig. 1. These decision variables in the primal model will appear as vertical and horizontal constraints in the dual model graph, see Fig. 4, which we can call an “Extended Contribution Graph”.

Fig. 4

One might also want to add simple upper bounds on the primal variables, i.e. market constraints on the products, which however would add to the complexity and therefore the usefulness of the dual model graph in Fig. 1. This we leave to the interested reader to try and assess.

In some real world cases, more can be bought of resources as needed on the market, even on a daily basis as discussed in the case of fish processing. This is true for raw materials for fish processing in more and more places as fish markets are gaining on. Even some of the labor is available on a day to day basis. With these cases in mind, it is of interest to study further how to develop decision aids for "Optimal System Design" as presented in [6], based on the ideas in this paper.

References

1.Hillier, F. S. & Lieberman, G. J.: "Introduction to Operations Research". McGraw-Hill 6. edition 1995.

2.Winston, W. L.:”Operations Research. Applications and Algorithms”. Duxbury Press 3. edition 1994.

3.Jensson, P.: "Daily Production Planning in Fish Processing Firms". European Journal of Operations Research, Vol. 36, No. 3, 1988.

4.Jensson, P. & Maack P.K.: "Cost Concepts for selection of processing activities" (in Icelandic). Technical Report, Engineering Institute, Univ. of Iceland 1985.

5.Nahmias, S. : "Production and Operations Analysis", 2. ed. Irwin 1993.

6.Hessel, M. & Zeleny, M.: "Optimal System Design: Towards new Interpretation of Shadow Prices in Linear Programming". Comput. Opns. Res. Vol.14, No. 4 1987.

1