Linear optimization: Mathematical formulations of complex problems (How to) 1

Authors: M.Caliskan, M.Voltz

Theory

In contradiction to simple optimization problems, complex problems are not to solve graphically in 2D because of containing more than 2 variables. The complexity rises with incerasing number of variables and interdependance between them.

How to formulate complex problems mathematically

Reading and structuring

First of all the problem should be regarded and the text be read properly. After that the information should be structured, e.g. with annotations to the text, short summaries next to complex information or writing out numbers from text based information. This helps not to lose the overview caused of the huge amount of information.

Graphical representation

In the next step it could be useful to transform the text-based information into a graph if it is possible. Simply go through your structured text and try to draw a plot of the information from the text. Start with obvious nodes (if you can define them) and connect them with arrows to show the coherences. So you easily can comprehend the processes and go through the problem step by step.

Definition of variables

After that you should define the variables. Assigning a variable to each of the edges in the graph is a good way to start. Don't worry about interdependences between them yet, simply assign them. Some of these variables can lead to equations in the formulation and could be cleared while setting up the constraints. Keep in mind that it's better to have some more variables that are cleared later on than having a too small number of variables and so beeing not able to solve the problem.

Formulating constraints

Now you can formulate the constraints. You have to use the information in the graph in combination with further information given in the text or additional tables. You have to pay attention to the fact, that you have to mention the input side in many cases due to limitational interdependences between the factors.

Beware of traps like information that is implied by the text and not written out or information not needed to solve the problem.

Non-negativity-conditions

A thing often neglected are the non-negativity-conditions. If some of the variables mustn't be negative these conditions compulsory have to be set up. So do not forget them, they belong to the linear program as well.

Objective function

When you have to set up the mathematical formulation for a simple linear problem the objective function mostly is the thing you start with. The facts are clearly visible and you easily can set it up.

While dealing with a more complex problem, another approach might be better. When you set up the objective function after formulating the constraints, you might be much more focused on the problem already.

Though there are different types of objective functions like minimizing cost or maximizing profit or contribution margin you have to look carefully what is asked of you. For the case of maximizing the contribution margin you have to set up the cost and earnings for each output factor step by step and later sum them up for the final objective function.

After that, you should have a well formulated mathematical model for a complex problem.

Example: Beverage Factory

The "story"

In a beverage factory are delivered concentrate for the production of coke and orangelemonade soft drinks every day. The storage capacity is limited to 3500 l each. Furthermore, 1000 l of whisky are delivered and can be stored each day.

The concentrates are transferred into barrels with a capacity of 100 l for further transportation. The Whisky is transferred into 50 l barrels. Beneath the use in production the "coke-concentrate" is also sold to a fast-food restaurant for 1500€ per barrel. The factory can sell up to 6 barrels to the fast-food restaurant every day. Only full barrels are sold.

In the soft drink plant the concentrate, water and CO2 are mixed to coke and lemonade. The CO2 bottles have a capacity of 20 l each. Water is available to infinity. The capacity of the production is limited to 20000 l of soft drinks each day. The mixture of 1 l of lemonade consists of 0,3 l orange lemonade concentrate, 0,68 l water and 0,0002 l CO2. The mixture of 1 l of coke consists of 0,35 l coke concentrate, 0,63 l water and 0,0002 l CO2.

A part of the produced coke soft drink is transferred to the long drink plant where it is mixed with whisky. Each liter of whisky-coke consists of 40% of whisky and 60% of coke

After the production the drinks are filled into cans with a capacity of 0,3 l. The material cost for each can are 0,05€.

20000 cans of orange lemonade have to be sold to a supermarket due to a delivery contract.

The purchase prices for the other ressources are: - orange concentrate: 12 €/l - coke concentrate: 10 €/l - water: 0,2 €/l - CO2: 70 €/bottle - whisky: 20 €/l

The cans are sold for: - lemonade: 1,50€ - coke: 1,7€ - whisky-coke: 4,50€

Every can produced is sold.

How many cans of each product have to be produced and sold to maximize the contribution margin?

Mathematical formulation of the example

Reading and structuring

After reading the text you could structure it for yourself if you want to. This example already is quite well structured, so there is no need for more activity.

Graphical representation

Now you can draw the production and selling process in a graph. In the example you can detect four nodes (storage, longdrink plant, soft drink plant and filling plant), many connections between them in form of arrows (because the edges have to be directed here) as well as three input factors and four output factors. Then assign variables to the edges, don't worry about their meaning yet.

It might look like this after that:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Definition of variables

Now there is a proper graph for the processes you can go through the text again and start to define the variables we just assigned to the arrows.

In this case they are:

$x_{1}=$ lemonade concentrate

$x_{2}=$ coke concentrate

$x_{3}=$ whisky

$x_{4}=$ coke concentrate used in production

$x_{5}=$ coke concentrate sold to fast food restaurant

$x_{6}=$ lemonade in liters

$x_{7}=$ coke for whisky in liters

$x_{8}=$ coke for sale in liters

$x_{9}=$ whisky-coke in liters

$x_{10}=$ water in liters

$x_{11}=$ CO2 in liters

$x_{12}=$ can of lemonade

$x_{13}=$ can of coke

$x_{14}=$ can of whisky-coke

Formulating constraints

After defining the variables you can start setting up the constraints. Start with the easy ones like the input factors and then carefully go through the whole graph and set up the relationships between the different variables.

1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1\leq3500

2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2\leq3500

3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_3\leq1000

These three restricions express the limited input factors caused by the storage capacity.

4) $x_{2}=x_{4}+100x_{5}$

This restriction expresses the transfer of the coke concentrate into barrels containing 100 liters. Here is the first trap because in production we have to work in 1 liter steps, the 100 liter barrel is only considered for selling to the fast food restaurant. So we have got $x_{4}$ in 1 liter, $x_{5}$ in 100 liters. There is also the unnecessary information that whisky is transferred into barrels.

5) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_5\leq6

6) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_5\in\N

This is the limited sale capacity to the restaurant and the constraint that only full barrels are sold, so $x_{5}$ has to be integer.

7) $x_{1}=0,3x_{6}$

8) $x_{4}=0,35(x_{7}+x_{8})$

9) $x_{10}=0,68x_{6}+0,63(x_{7}+x_{8})$

10) $x_{11}=0,0002(x_{6}+x_{7}+x_{8})$

Those are the mixtures of lemonade and coke. You have to pay attention to the fact that you have to look from the input side, not from the output side because it's a limitational production function. So it's not "Coke consists of 0,63 liters water..." but "The amount of water needed is 0,63 times the amount of coke plus 0,68 times the amount of lemonade." Otherwise you could create output even if the amount of one of the needed ingredients is 0.

11) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_6+x_7+x_8\leq20000

This is the capacity limit of the soft drink plant in liters.

12) $x_{3}=0,4x_{9}$

13) $x_{7}=0,6x_{9}$

This is the mixture of whisky-coke. You can see again that the input side is considered.

14) $x_{6}=0,3x_{12}$

15) $x_{8}=0,3x_{13}$

16) $x_{9}=0,3x_{14}$

These restricions describe the transfer of the mixed drinks into the cans in the filling plant. Watch the input side!

17) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{12}\geq20000

Finally this is the satisfaction constraint for the delivery of lemonade to the supermarket.

You may have recognized that there is no compulsive need for the variable $x_{9}$ because it could be replaced by ${\frac {1}{0,6}}x_{9}$. Now we have proper restrictions and can go on setting up the objective function.

Non-negativity-conditions

All of our used variables have to be greater or equal zero, so we can say that:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_i\geq0

,  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall x
   with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \in [1,...,14]

Objective function

Now calculate the contribution margins for each product by itself an then sum them up to the objective function.

The contribution margin for the cans of lemonade $x_{12}$ consists of the following elements:

- selling price per can: $1,50\$$

- material costs per can: $0,05\$$

- price of lemonade concentrate: $12{\frac {\$}{\text{l}}}$

- price of water: $0,20{\frac {\$}{\text{l}}}$

- price of CO2: $70{\frac {\$}{\text{bottle}}}$ (Attention, it's a trap!)

So we can set up the formula:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): CM_{Lemonade}=1,50\$-0,05\$-0,3(0,3\text{l}\cdot12\frac{\$}{\text{l}}+0,68\text{l}\cdot0,20\frac{\$}{\text{l}}+0,0002\text{l}\cdot\frac{70\frac{\$}{\text{bottle}}}{20\frac{\text{l}}{\text{bottle}}})

You have to mention that most of the given information for the mixtures are in liters but for the contribution margin you need the amounts per can. So you have to multiply the data concerning the liters by 0,3 to consider the volume of the cans.

The last part of the equation displays the cost of CO2 per liter which has to be calculated from the price per bottle and its capacity.

For the other products you can set up the equation for the contribution margin equally. By summing them up you receive the objective function.