How to calculate an optimal combination of metals based on price

Question

My dad asked me to write a program that calculates the optimal way to create a specific alloy by mixing other alloys based on price.

An example:

We have three elements in a certain alloy. An example of mixtures could be

80% iron, 19% carbon, 1% zinc : price 200 70% iron, 25% carbon, 5% zinc : price 300 90% iron, 8% carbon, 2% zinc : price 250 Lets say there are 50 more combinations available for different prices

My goal is to melt everything to an alloy. The alloy i want is 85% iron, 13% carbon, 2% zinc

How could I find the most optimal combinations(cheapest total price) of alloys to melt them into the alloy I want.

In the real world case there will be around 8 different elements with a maximum and minimum amount allowed in the final alloy. So there is a margin.

What would he the best way to calculate this?

Answer 1

Let $x_i,$ denote the type of alloy for all $i=1,2,\ldots,8$. For example, $x_1=iron, x_2=carbon $ etc. $UB_i$ denotes the upper bound possible for production of material $i$ (in percentage), $LB_i$ the lower bound. $c_i$ is the cost of producing one percent of type $i$. So the optimization model you will write will be a very simple LP:

$\min \sum_i c_ix_i$

$s.t \ \ LB_i\leq x_i \leq UB_i \quad \forall i\in\{1,2,\ldots,8\}$ (constraint of maximum-minimum production)

$\ \ \ \ \ \ \ \sum_i x_i \geq 1$ (constraint that satisfies 100% is produced)

Example YALMIP code in Matlab can be:

x = sdpvar(8,1)
c = [] %enter manually
LB = [] %enter manually
UB = [] %enter manually
Objective = [c.'*x]
Constraints = [ LB<=x<=UB]
Constraints = [Constraints, sum(x)>=1]
optimize(Constraints,Objective)

Answer 2

Calling $$ p=\left[\begin{array}{ccc} 0.8 & 0.19 & 0.1\\ 0.7 & 0.25 & 0.5\\ 0.9 & 0.8 & 0.2 \end{array}\right] $$

the basic elements $\left\{ x_{1},x_{2},x_{3}\right\} =${iron,carbon,zinc} proportions for each alloy $\left\{ y_{1},y_{2},y_{3}\right\} $we have

$$ x_{i}=\sum_{j=1}^{3}p_{j,i}y_{j} $$

now we need a target alloy such that

$$ \begin{array}{rcl} x_{1} & \ge & 0.85y_{0}\\ x_{2} & \ge & 0.13y_{0}\\ x_{3} & \ge & 0.2y_{0} \end{array} $$

where $y_{0}$is the needed target ammount. Also the restrictions dictate

$$ y_{i}\ge0 $$

The objective is the minimization of

$$ f=c_{1}y_{1}+c_{2}y_{2}+c_{3}y_{3} $$

with

$$ c=\left\{ 200,300,250\right\} $$

As an example, defining $y_{0}=100$ we have the result

$$ \left\{ y_{1}=0,y_{2}=3.22,y_{3}=92\right\} $$

with a total cost of $f\approx23000$