Linear optimization: Mathematical formulations of problems presented in the course 5: Unterschied zwischen den Versionen

Version vom 26. Juni 2013, 19:04 Uhr

LP: 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.

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${\displaystyle _{j}}$ : amount of product j (j=1,2,.., n)

c${\displaystyle _{j}}$ : 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${\displaystyle _{i}}$${\displaystyle _{j}}$* x${\displaystyle _{j}}$ ≤ b${\displaystyle _{i}}$  ; j = 1 for i = 1,2,...,m

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

x${\displaystyle _{j}}$ ≥ 0 for j = 1,2,...,n

a${\displaystyle _{i}}$${\displaystyle _{j}}$ : needed capacity to produce one unit of the product

b${\displaystyle _{i}}$ : capacity limit

LP: 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

aijxj ≤ bi (upper bound) aijxj ≥ bi (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.

LP: 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 15kg, 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 15kg of the first sort available -> x<=15

and the mixture consists of at least 6kg second sort -> y>=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 12kg of the second sort in stock

Y<=12

3) The profit has to be maximized:

Zmax=(x+y)*p1+(15-x)*p2+(12-y)*p3

Zmax=(x+y)*40+(15-x)*48+(12-y)*36

4) x ≥ 0

y ≥ 0

LP: 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.

need of resource per product

Solution Example 2:

Steps:

1) Some variables are already given in the discription.

xI : amount of product I

xII: 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:

12xI+ 9xII ≤ 240

4xI+ 2xII ≤ 128

8xI+ 16xII ≤ 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.

(56-48)xI + (40-34)xII -> max !

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

xI ≥ 0

xII ≥ 0

LP: Sources

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

http://www.wikipedia.de