Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Imagine, I have following model.

There is a company X, which produces one unit of final output from

  1. 0.2 units of input A and
  2. 0.8 units of input B.

Inputs A and B are bought from respective markets.

Let

  • the market price of A be 40 dollars,
  • the market price of B be 20 dollars and
  • the available money of the company be 200 dollars.

Question: How can I calculate the maximum amount of final output given those constraints?

Note: Ideally, that solution should be easily expandable to a case where there are more than 2 inputs.

I tried to solve this problem in the following way:

I divided the available money in 2 parts:

  1. 40 dollars for buying input A and
  2. 160 dollars for buying input B.

For 40 dollars, you can buy 1 unit of input A. For 160 dollars, you can buy 160/20 = 8 units of input B.

It would be no problem, if there were 2 units of A and 8 units of B, but in our case the proportions don't match.

Update 1: I need this algorithm for builing a simple model of the economy of a midsized (100 000 inhabitants) town in Russia.

Purpose of the that model of the economy: To answer questions like

  1. By how much will the unemployment change during and after the construction of a hospital?
  2. By how much will the regional GDP change, if we build a road from point A to point B?

I have data about

  • how companies of different industries transform inputs into outputs (all-Russian input-output tables) and
  • the number and sizes of companies of different industries in the city in question (regional statistics).

Using those data I can create a set of synthetic companies such that the characteristics of those virtual companies are similar to real ones.

The next step is to enable the companies to exhange goods between

  • each other and
  • final customers.

I decided to create a model of markets (I was inspired by the EOS framework, but want to develop my own model, with blackjack and other subtleties, in order to fully understand how it works).

As far as I understand, in each simulation step, following things need to happen:

  1. Every company decides, how much output it wants to produce in year N. In the simplest case, target output is equal to the amount of final product sold in year N-1.
  2. Then, the company buys inputs at the markets for every input.
  3. Then, the company produces the output from the resources it has. The quantity of the produced output is max. target output from step 1 (in case it could buy enough of each input), or less (if it couldn't buy enough of some of the inputs).
share|improve this question
1  
One final unit costs $(0.2)40+(0.8)20 = 24$, so the maximum number of final units is $\frac{200}{24} = 8 \frac{1}{3}$. Are there some other constraints that I am missing? –  copper.hat Jan 1 '13 at 18:51
    
@copper.hat See my update 1. The problem is that the company doesn't know in advance, how many resources it will buy. In step 1 (last paragraph of Update 1), the company decides on the quantity of final product it intends to produce. Then, it goes to the market (together with other buyers and sellers) and buys a certain amount of each resource. The company doesn't know in step 1 how much of every input it will buy in step 2. Finally, in step 3 it has so many of each input and now needs to produce a quantity of final output, which conforms to the constraints (0.2 of input A and 0.8 of input B). –  Dmitri Pisarenko Jan 1 '13 at 19:24
    
Dmitri, I don't really understand what the question is. Given some units of $A$ and $B$, you can produce $5 \min(A,4B)$ units of the final product. Is that what you are asking? –  copper.hat Jan 1 '13 at 19:47
    
@copper.hat Yes. Sorry for a dumb question, but how did you derive this formula ($5*min(A, 4B)$) ? I want to understand it and extend to a case with more than 2 inputs. –  Dmitri Pisarenko Jan 1 '13 at 20:20
    
Sorry, the formula should be $5 \min(A, \frac{1}{4}B)$. –  copper.hat Jan 1 '13 at 20:39

2 Answers 2

up vote 1 down vote accepted

The output is limited by the item(s) you have least of, hence the $\min$. In general, if producing a unit of output requires $\lambda_i >0 $ of item $i$, then the most output you can create with quantities $x_i$ of item $i$ is $\min_i \frac{1}{\lambda_i} x_i$.

To answer the original question, if item $i$ costs $c_i>0$ and the total available capital is $C>0$, then the maximum you can produce is $\frac{C}{\sum_i c_i \lambda_i}$.

The problem is a standard linear programming problem, in this case the solution can be obtained by inspection. However, it is fairly easy to see why this is a solution:

The problem is $\max\{ \min_i \frac{1}{\lambda_i} x_i | \sum_i c_i x_i \leq C, x_i \geq 0 \}$. Since the $c_i >0$, the solution space is compact, and the objective is continuous, hence a solution exists. Life becomes a little easier if we rescale the problem with $y_i = \frac{1}{\lambda_i} x_i$, then the problem is to solve $\max\{ \min_i y_i | \sum_i c_i \lambda_i y_i \leq C, y_i \geq 0 \}$. Since $y=0$ is feasible, we can see that this is the same problem as $\max\{ \min_i y_i | \sum_i c_i \lambda_i y_i \leq C\}$. If $\sum_i c_i \lambda_i y_i < C$, then it is clear that each $y_k$ can be increased slightly to increase the objective, hence the problem is equivalent to $\max\{ \min_i y_i | \sum_i c_i \lambda_i y_i = C\}$.

Suppose for some index $j_0$ we have $y_{j_0} > \min_i y_i$. Let $K = \{k| y_k = \min_i y_i\}$. Let $h$ be the vector $h_k = 1$ for $k\in K$, $h_{j_0} = -\frac{\sum_{k \in K} \lambda_k c_k}{\lambda_{j_0}c_{j_0}}$, and $h_j = 0$ otherwise. Note that $\sum_i c_i \lambda_i (y_i+t h_i) = C$, and for sufficiently small positive $t>0$, $\min_i y_i < \min_i (y_i+t h_i)$. Hence at a solution to the problem, we have $y_i = \hat{y}$ for all $i$. Then the constraint gives $\sum_i c_i \lambda_i \hat{y} = C$, from which we obtain the solution $\max\{ \min_i \frac{1}{\lambda_i} x_i | \sum_i c_i x_i \leq C, x_i \geq 0 \}= \frac{C}{\sum_i c_i \lambda_i}$.

share|improve this answer

The Answer is wrong. Assume it is correct, and maximum number of final units is 200/24. Let us find maximizing A and B. We can write expression for B of А and substitute it to constraints. It leads to A<0 which contradicts the initial statement of the problem.

Using simple linear programing, one finds the solution (A,B)=(0,10) and the maximum number is 8.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.