Linear optimization: Mathematical formulations of complex problems (How to) 1: Unterschied zwischen den Versionen

Version vom 28. Juni 2013, 15:24 Uhr

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

First of all the problem should be regarded properly and the information should be structured. This helps not to lose the overview caused of the huge amount of information.

In the next step it could be useful to transform the text-based information into a graph if it is possible. So you can easily comprehend the processes and go through the problem step by step.

After that you should define the variables. Clear assignments like input and output factors can be set directly as well as all other arrows of the graph can be equipped with variables. Some of these variables could lead to equations in the formulation and could be cleared while setting up the restrictions. So you don't have to worry about having to much variables.

Now you can formulate the restrictions. You have to use the information in the graph in combination with further information given in the text or additional tables. Beware of traps like information that is implied by the text and not written out or information not needed to solve the problem.

As a last step you have to set up the objective function. Though it could be 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.

Then 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 formulations of the example

After reading the case in the example you can draw the production and selling process in a graph. Don't care about variables now, simply start drawing what you read. 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.

Now there is a proper graph for the processes you can go through the text again and start to define the variables. Go through the text again and mark the arrows with the variables you have found. Here it could be:

${\displaystyle x_{1}=}$ lemonade concentrate

${\displaystyle x_{2}=}$ coke concentrate

${\displaystyle x_{3}=}$ whisky

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

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

${\displaystyle x_{6}=}$ lemonade in liters

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

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

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

${\displaystyle x_{10}=}$ water in liters

${\displaystyle x_{11}=}$ CO2 in liters

${\displaystyle x_{12}=}$ can of lemonade

${\displaystyle x_{13}=}$ can of coke

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

After defining the variables you can start setting up the restrictions. 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) ${\displaystyle 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 ${\displaystyle x_{4}}$ in 1 liter, ${\displaystyle 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.

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

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

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

10) ${\displaystyle 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. 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) ${\displaystyle x_{3}=0,4x_{9}}$

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

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

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

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

16) ${\displaystyle 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 ${\displaystyle x_{9}}$ because it could be replaced by ${\displaystyle {\frac {1}{0,6}}x_{9}}$. Now we have proper restrictions and can go on setting up the objective function.

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

- selling price per can: ${\displaystyle 1,50\$}$

- material costs per can: ${\displaystyle 0,05\$}$

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

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

- price of CO2: ${\displaystyle 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}}})