Linear optimization: Mathematical formulations of complex problems (How to) 2
Authors: F.Burkhard, S.Sayar
Inhaltsverzeichnis
Theory
Most of the student think that linear programming is simply a synonym for computer programming or geometry or even a type of “hard maths”. But the fact is, that a basic grasp of mathematics is just needed. The concept of linear optimization is simple, because it is really about finding solutions to problems which are expressed in terms of an entity which needs to be optimized with given constraints. Due to this, linear optimization is perhaps the most successful discipline of Operations Research. The following chart shows a structured linear optimization solution model paired with an easy introductory example.
Example-case:
A company makes two products using two machines. Each product produced requires 50 minutes processing time on the 1st and 30 minutes processing time on the 2nd machine. Each unit of one product that is produced requires 24 minutes processing time on the 1st machine and 33 minutes processing time on the 2nd machine.
At the start of the current week there are 30 units of the 1st product and 90 units of the 2nd product in stock. Available processing time on the 1st machine is forecast to be 40 hours and on 2nd machine is forecast to be 35 hours.
The demand for the 1st in the current week is forecast to be 75 units and for 2nd is forecast to be 95 units. Company policy is to maximize the combined sum of the units of the 1st product and the units of the 2nd in stock at the end of the week
Example
The OR-bakery converts three raw materials into different types of bread. In a large storage hall it is possible to appropriate 10 tons per week for production processes. The proportion of raw the raw materials are as follows:
Unfortunately the storing process is not that consistantly, so there is a loss of almost 10 percent of each of the raw materials.But it has to be done, because the materials need to mature in a hall first.
Because of the great demand for the OR bakery`s products, 4 factories are needed. The first three do not need to work at their full capacity level (only 70 %) so they produce variable costs of 0,5$/kg produced item. The fourth factory requires a higher capacity! Production costs are 1,5$/kg produces item while the energy usage is about 10000 kW/h. Factory 1 can either produce rye bread or special rye. Factory 2 can either produce special wheat or low wheat. Factory 3 can produce barley bread or special barley.
To create the popular products such as rye bread, OR-bread and barley bread there are some special recipes essential. Factory 4 deals with 20% of special rye, 50% of special wheat and 30% of secret mixture.
Secreat mixture consits of 20% low wheat and 80% of special barley. But this process (in Factory 4) takes a lot of time, so there is a maximum amount of 250kg that can be produced in only one week.
The final products can be sold to the following prices:
The bakery chef wants you to achieve as much money as you can in one week!
Presentation of the Problem
For this complex problem we have provided a graph to show the complexity! As we can immediately see there are some Input variables and also some Output variables. But inside the whole production process there are some important steps in-between. So there will be a lot of variables which have to be defined.
Second point that makes this problem difficult are the number of restrictions which have to be considered. The proportion process in Factory 4 and also the mixture process are combinatorial.
Some restrictions exist out of limitations (e.g Storage).
And the most important one is the objective function. First it has to be found out what of these whole lot of information needs to be used. Prices and Costs have to be distinguished.
Solution Process
The first step, collecting information is already done by this beautiful graph on top. It provides us a good survey of the whole problem.
Now then we can start defining the variables.
Three raw materials:
rye
wheat
barley
Now the matured materials
matured rye
matured wheat
matured barley
Next step are the Factory processes, where the following components result:
special rye
low wheat
special barley
special wheat
rye bread
barley bread
The two last variables needed result from Factory 4!
secret mixture
OR bread
What has to be added is, that there are three Input variables and also three Output variables !
After defining the variables, our next step is formulating the objective function! It expresses our main intend, so we have to do this carefully.
Making as much money as possible means considering the prices but also the costs:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \text{max G} = 2\cdot\frac{\$}{\text{kg}}\cdot x_{12}+6\frac{\$}{\text{kg}}\cdot x_{13}+4\frac{\$}{\text{kg}}\cdot x_{14}-0,5\frac{\$}{\text{kg}}\cdot(x_{12}+x_{7}+x_{11}+x_{10}+x_{14})-1,5\frac{\$}{\text{kg}}\cdot x_{13}
Next thing to do is formulating the restrictions!
Storage capacity:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1\leq2000\text{kg}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2\leq4000\text{kg}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_3\leq4000\text{kg}
Storage/Transportation loss:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_4 = x_1\cdot0,9
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_5 = x_2\cdot0,9
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_6 = x_3\cdot0,9
Limitation:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{13}\leq250\text{kg}
Combinatorial processes:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{10} = x_8\cdot0,2+x_9\cdot0,8
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{13} = x_7\cdot0,2+x_{11}\cdot0,5+x_{10}\cdot0,3
NNB:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_i\geq0\text{ }\forall\text{ i }\epsilon\text{ ( 1...14 )}
Sources
University of Manchester (2012): "METAL Teaching & Learning, Guide 4: Linear Programming". URL: http://www.maths.manchester.ac.uk/service/resources/METAL/pdfs/linear_programming/concept_lp.pdf
J. E. Beasley (2005): "OR-Notes". URL: http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html
