0
$\begingroup$

A factory has $A$ and $B$ products. $A$ is made with $4X + 2Y$ raw materials. $B$ is made $2X + 4Y$ raw materials.

We want to maximize total profit.

Input

  • amount of profit $A$ per item, amount of profit $B$ per item and
  • number of $X$ and number of $Y$ raw materials.

Output

  • Number of A which will be produced,
  • number of B which will be produced,
  • total profit.

Example

Input:
profitA = $8, profitB = $6,
numberOfX = 600, numberOfY = 480,
Output:
numberOfA = 120,
numberOfB = 60,
totalprofit = $1320.

My solution is brute force algorithm. I find maximum number of $A$ will can produce and I decrease it one by one then compare result and get maximum profit. But this is not efficient. Is there a algorithm that solve this problem?

Formula = mA*pA + mB*pB => maximum
pA: profit A, pB: profit B,
mA: number of product A, mB: number of product B,
Producing mA number A are required 4*mA number X and 2*mB number Y,
producing mB number B are required 2*mB number X and 4*mB number Y.
$\endgroup$
1
$\begingroup$

Express the objective function for profit: "maximize $P_o = n_A p_A + n_B p_B$" in terms of $n_A$ (or $n_B$). If we produce $n_A$ items then from the constraints we have: $$n_B = \min (\frac{n_X - 4 n_A}{2}, \frac{n_Y - 2 n_A}{4}).$$ Thus we have a max-min problem. I believe this can be solved using auxiliary constraint technique like-so: https://stackoverflow.com/questions/10792139/using-min-max-within-an-integer-linear-program

$\endgroup$
5
  • $\begingroup$ Sorry my late comment, firstly thank you for your time, but your formula is not always true because there may be a situation that item A may not product since it has a few profit. For example: input profitA = $$1, profitB = $10, numberofX=600, numberofY=480,in this situation output is: mA=0, mB=120, totalprofit=$1200. $\endgroup$ – Halil İbrahim Oymacı Apr 22 '16 at 18:20
  • 1
    $\begingroup$ I see the flaw in my logic. Based on what you say, I am not sure enhancing the objective function as max $(P_o, P_A, P_B)$ with $P_A = ($max $n_A) p_A$ and $P_B = ($max $n_B) p_B$ will work either. If I come up with something, will post. $\endgroup$ – NameRakes Apr 22 '16 at 19:08
  • $\begingroup$ Edited my answer to show max-min problem structure $\endgroup$ – NameRakes Apr 22 '16 at 23:31
  • $\begingroup$ Thank you again, My searching solution is similar your offer algorithm. I don't understand your shared link but I will research auxiliary constraint technique, is there more different techniques to solve this problem? $\endgroup$ – Halil İbrahim Oymacı Apr 23 '16 at 6:20
  • $\begingroup$ My understanding is that the auxiliary term added to the objective function moves the objective function up or down away from the surface containing the saddle point. I haven't researched into other techniques. $\endgroup$ – NameRakes Apr 23 '16 at 11:18

Your Answer

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

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