I'm trying to formulate a linear program for this problem:

There is a blacksmith who can produce $n$ different alloys, where alloy $i$ sells for $p_i$ dollars per unit. One unit of alloy $i$ takes $g_i$ grams of gold and $s_i$ grams of silver to produce. The blacksmith has a total of $G$ grams of gold and $S$ grams of silver to work with, and can produce as many units of each type of alloy as they want within the material constraints. The blacksmith is allowed to produce and sell a non-integer number of units of each alloy.

I think I came up with a solution, but it seems way too simple, and I think I'm missing something in my understanding of linear programming. This is my thought process:

Each alloy $a_i$ sells for $p_i$ dollars, so we can represent our profit as $P = \sum_{i=1}^{n} p_i a_i$.

Each $a_i$ costs $g_i$ and $s_i$ to make, so for each $a_i$, we have $C(a_i) = g_i + s_i$, where $C(a_i)$ is the cost of $i$th alloy.

This is the part I'm iffy on: We're given that we have $G$ and $S$ amounts of gold and silver. I'm not quite sure what the proper way of representing the constraints is.

What I was thinking is that the sum of all $C(a_i)$ must be less than or equal to $G + S$, i.e. $\sum_{i=1}^{n} (g_i + s_i) \le G + S$. But I am not sure how to connect this back to the profit and cost functions we have above.

Am I on the right track? What is the smart way to represent constraint functions for linear programs?

  • $\begingroup$ It is true that each each $a_i$ requires a certain amount $g_i$ of gold and a certain amount $s_i$ of silver, but we don't really need to consider their sum to form the constraints. We are interested in making sure that the total amount of gold does not exceed $G$ and the total amount of silver does not exceed $S$. Why not say $\sum_{1}^{n} g_i \leq G$? $\endgroup$ – user155242 Oct 20 '18 at 4:04
  • $\begingroup$ You have two constraints $\sum\limits_{i=1}^n a_i\cdot g_i\leq G$ and $\sum\limits_{i=1}^n a_i\cdot s_i\leq S$ They are both connected to the profit by the variable $a_i$ Don´t forget to mark your questions as answered. Otherwise users are less willing to anwer your questions. $\endgroup$ – callculus Oct 20 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.