Monday, May 5, 2008

Simple(x) Problem

Imagine you have following a problem. There are some people which needs access to some resources (lets make it students and beer problem). There are some dorms where students are located and shops which stores specific amount of this golden drink. As students are very lazy mammal they can access only this shops that are not very distanced.
We must provide each student with a bear. How to organize delivery?

How to deal with such a problem ?

Is there an optimal solution ?

This is typical resources allocation problem with constrains.
All students must be served. We can translate this problem and treat our students as resources. Let Xi be a number of bears per i'th dorm, Yj number of bears in j'th shop. Let also xij be number of bears for i'th dorm from j'th shop.
Then we can describe our problem as maximization problem of following function

SUM(xij) - where we take into consideration only such a xij where j'th shop can be reached from i'th dorm.
The constrains are following:
For each j: SUMi(xij) <= Yj
which means that we cannot give more bears than we have in j shop.

For each i: SUMj(xij) = Xi
which means that all students from i'th dorm must be served.

The only problem is that for some reason this cannot be solved using OpenOffice solver on my laptop (probably not ideal openSuse configuration ;) ). So please use something more comercial :D
Sometimes working at the university also means solving quite daily life problems ;)

No comments: