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

Introduction

The aim of linear programming (LP) is to optimize a linear function dependent on a set of linear inequations.

It is often used to solve production problems. You can optimize the production planning with the LP.

Mathematical Formulation

The objective function is defined like this:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1},x_{n})= c_{1}x{_{1}}+c_{2}x_{2}+....+c_{n}x_{n} = \sum_{i=1}^{n} c_{i}x{_{i}}

x_i : amount of product j (j=1,2,.., n)

c_i : related economical factor to product j (e.g.: profit, marginal return)

The objectice function can be maximized or minimized depending on cost or profit consideration.

The linear inequations manifest themselves as constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j=1}^{n} a_{ij} \cdot x_{j} \le b_{i}

 ; j = 1 for i = 1,2,...,m

The optimal Programm cannot allow negative amounts of items to guarantee an admissible solution:

x_j ≥ 0 for j = 1,2,...,n

a_ij : needed capacity to produce one unit of the product

b_i : capacity limit

Approach

The approach of formulating the mathematical model of a LP-Problem has four steps.

1) First you identify the variables and allocate them specific symbols.

2) In the next steps you look for the constraints and write them as a linear equation/ inequation. These constraints limit the solution volume.

The constraints can look like this

a_ijx_j ≤ b_i (upper bound) a_ijx_j ≥ b_i (lower bound)

3) Then declare the objective function as a linear function. Depending on the situation the objective function has to be maximized or minimized.

4) Finally the non-negativity restrictions have to be added. These restrictions exclude the negative values of the variables.

Example 1

A tea merchant wants to establish a two-sorts mixture of tea, which he would like to sell at a price of € 40 per kilogram.

The first kind is available to 15 kg, which can be sold at a price of € 48 per kilogram.

At least 6 kg of this species is determined for the mixture. Of the second kind he has 12kg in stock and a maximum of 60% should be included in the mix.

This variety can be sold for the kilogram price of 36 €.

How to mix, so that the sale of the mixture and the remaining quantities of the two varieties, is earning the largest possible profit?

Solution Example 1:

1) The tea merchant wants to produce two sorts of tea:

X amount of the sort 1 Y amount of the sort 2 P1 selling price for mixture between sort 1 and 2 P2 selling price for sort1 P3 selling price for sort2

2) There are 15 kg of the first sort available -> Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \le 15

and the mixture consists of at least 6kg second sort -> Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y \ge 6

The mixture is at maximum of 60% a product of sort 2.

$y<0,6(x+y)$

<=> $y<0,6x+0,6y$

<=> $0,4y<0,6x$

<=> $y<3/2x$

There are 12 kg of the second sort in stock

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

3) The profit has to be maximized:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z_{max}=(x+y)\cdot p_{1}+(15-x)\cdot p_{2}+(12-y)\cdot p_{3}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z_{max}=(x+y)\cdot 40+(15-x)\cdot 48+(12-y)\cdot 36

4)

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

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

Example 2

An Enterprise has three resources(1,2,3) to choose and can produce two products(I, II) threw different processes.

The required amount of resources, the capacity of the resources, variable unit costs and the unit returns are illustrated in the following table.

product	resource 1	resource 2	resource 3	variable unit costs	unit returns
I	12	4	8	48	56
II	9	2	16	34	40
capacity	240	128	336

Solution Example 2:

Steps:

1) Some variables are already given in the discription.

x_I : amount of product I

x_II: amount of product II

capacity limits and needed capacity for product I or product II are given in the table.

variable unit costs and unit return are also known from the table.

2) Constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 12x_{I}+ 9x_{II} \le 240

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4x_{I}+ 2x_{II} \le 128

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 8x_{I}+ 16x_{II} \le 336

3) In this case the marginal return has to be maximized. Therefor you have to subtract the unit costs from the unit return to get the marginal return.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (56-48)x_{I} +(40-34)x_{II} -> max!

4) As the company is producing the amount of products cannot be negative.

x_I ≥ 0

x_II ≥ 0

Sources

http://www.techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/WS0304/IntAlg/Ausarbeitungen/lp.pdf

http://www.wikipedia.de

Authors: Niklas Hack, Endric Müller und Kevin Brümmel