Linear optimization: Mathematical formulations of problems presented in the course 3

Theory

Industrial problems include managing finite resources like the capacity of machinery or materials which have to be used in production processes. To maximize the profit or minimize the costs, those resources have to be used optimally. Finding the optimal configuration often requires formulating a mathematical model which represents the allocation problem. At first it is necessary to formulate an objective function which represents the overall goal of the program. Everything which influences this objective function directly has to be included. If the goal is i.e. to maximize the profit, then the objective function will include every variable which affects the profit like income or costs. Every production limitation which influences the goal indirectly has to be considered via restriction-functions by equations and inequations, which can be unlimited in number. Restrictions are i.e. the capacity of machines or the time workers are able to assemble products. To complete the mathematical model some non-negativity conditions are needed, because several variables are not allowed getting smaller than zero like the quantity of produced products.

Mathematical formulation

1) Objective function

The general form of a profit maximization objective function is as follows:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): maxP = \sum_{j}\left [ \left ( i_{j}-c_{j} \right )*x_{j} \right ]-C_{f}

In this case the target is to maximize the profit ($P$). Therefore it is necessary to multiply the amount of units sold for product j ($x_{j}$) by the difference of income minus costs per unit (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i_{j}-c_{j} ). Finally the profits per product have to be summed up to acquire the overall gainings. If there are fixed costs ($C_{f}$) they have to be subtracted from the sum as well.

2) Restrictions

Furthermore restrictions functions have to be formulated to include bottlenecks or other problematic matters:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j}a_{ij}*x_{j}\leq b_{i}

For example, the capacity of machine i needed by one unit of product j ($a_{ij}$) multiplied with the quantity of unit j ($x_{j}$) have to be smaller or equal than the total capacity of machine i ($b_{i}$).Another form of restrictions could be to define the quantity of produced units with lower ($l_{j}$) and upper ($u_{j}$) bounds:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): l_{j}\leq x_{j}\leq u_{j}

3) Non-negativity conditions

For useful solutions of linear problems it is important to limit some variables to positive numbers only, since non-existent products cannot be destroyed:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\geq 0

Example 1

Steve Jobless owns a juice facility which consists of the squeezer which extracts the juice and the juice refinery which filtrates unwanted waste out of the juice like seeds or plant parts. Steve only uses two kinds of fruits for his juices which are apples and grapes. By adding water, the juice to fruit ratio is 1:1, so one ton of fruit becomes one ton of juice. Steve has to maintain his machinery which costs him 3000€ per day.

Steve’s apple deposit has still 20t of apples in them, which are likely to get stale if they are not processed immediately. Furthermore Steve’s vendor can only deliver 120t of apples and 200t of grapes today because of fruit shortages.

The squeezer can squeeze 20 hours a day while the juice refinery can refine 10 hours a day.

Squeezing 1t of apples requires 6 minutes and only 5 minutes for grapes. Refining apples only takes 1 minute per ton while refining the grape juice needs 3 minutes.

Steve can sell the apple juice for 2€/t while grape juice only yields 1.5€/t.

At first the objective function should be formulated. Using the prices per ton of different juices, Steve’s profit can be described as:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max P = 2a+1,5g-3000

$P\colon$ profit

$a\colon$ quantity of apple juice

$g\colon$ quantity of grape juice

The next step includes the machinery restrictions:

Squeezer: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6a+5g\leq 1200

Refinery: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1a+3g\leq 600

Additionally the fruit shortages and the almost stale apples have to be considered:

Grapes: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g\leq 200

Apples: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 20\leq a\leq 1400

Furthermore Steve cannot destroy juice since he has none at the beginning:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a,g\geq 0

Example 2

Gerald Greed wants to celebrate his 50th birthday. Therefore he rented a big tent which costs him 5000€. To have enough places for his guests to sit he also has to rent 50 benches and 25 tables. Mr. Greed wants to reduce his costs and invited offers.

Company A can give him 20 benches ($b_{a}$) for 5€ each and 10 tables ($t_{a}$) for 6€ each.

Company B can give him only 20 benches ($b_{b}$) for 7€ each.

Company C can give him 50 benches ($b_{c}$) for 8€ each and 50 tables ($t_{c}$) for 10€ each.

- Objective function:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): min C= b_{a}*5+t_{a}*6+b_{b}*7+b_{c}*8+t_{c}*10+5000

- Restrictions:

$b_{a}+b_{b}+b_{c}=50$

$t_{a}+t_{c}=25$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{a}\leq 20

;   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{b}\leq 20
;    Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{c}\leq 50
;   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): t_{a}\leq 10
;   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): t_{c}\leq 50

- NNC:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_{a},b_{b},b_{c},t_{a},t_{c} \geq 0

Solution

The next step would be solving this problem which can be done

1) graphically or

2) via the Simplex-algorithm.