Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Problem:

Given 11 numbers

{N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}

where

  • N1:amount of profit from product A

    N2:amount of profit from Product B

    N3:amount of time in hours required to make A in factory1(F1)

    N4:amount of time in hours required to make B in factory1(F1)

    N5:maximum number of hours available in a week to make products in F1

    N6:amount of time in hours required to make A in factory2(F2)

    N7:amount of time in hours required to make B in factory2(F2)

    N8:maximum number of hours available in a week to make products in F2

    N9:amount time in hours required to make A in factory3(F3)

    N10:amount time in hours required to make B in factory3(F3)

    N11:maximum number of hours available in a week to make products in F3

Output:

3 numbers {R1,R2,R3} or "-1"

where:

R1:total number of A's to manufacture in a week

R2:total number of B's to manufacture in a week

R3:total profit which is **maximum possible profit** with the right mix of A and B

**result = `-1` if R1 and/or R2 is non integer(contains fraction)**

consider the Input {10.5,13,3,7,5,6,5,11,16,11,21.6}

                    PRODUCT A               PRODUCT B        total hours/Week

Profit/Piece             10.5                  13

Hours required in F1     3                     7                   5

Hours required in F2     6                     5                   11

Hours required in F3     16                    11                  21.6 

Any Idea/Algorithm?

Thanks in Advance

share|improve this question
    
Ex: Input:[10.5 13 3 7 5 6 5 11 16 11 21.6] output:NULL Input:[300 500 1.5 3.2 4.5 0 2 12 3 2 18] output:3 0 900 –  user6709 Feb 6 '13 at 15:59
2  
Downvoters, would you care to give some constructive criticism? –  Yuval Filmus Feb 6 '13 at 16:50
    
my idea is as follows: for each factory find the number of A and B products such that it's maximizes profit. But i am not getting how the output of {10.5,13,3,7,5,6,5,11,16,11, 21.6} is NULL –  user6709 Feb 6 '13 at 16:59
    
From my interpretation, you need to maximize all three factories at the same time; otherwise, this is (a) not a dynamic programming question, (b) only requires the first five numbers because the algorithm for maximizing for one factory is generalizable, and (c) even in your second example, why would the answer be 3A's if the factories were seperate? Yet, even given that, wouldn't the other example be 1A and not NULL? –  Merbs Feb 6 '13 at 17:41
    
If we consider the case of moving from one factory to another. for example If A requires 3hrs and total number of hrs/week in F1 is 5 then make(5/3) A's in F1 and try to make(1/3)A's in some other factory –  user6709 Feb 6 '13 at 17:51
show 3 more comments

1 Answer 1

This is a basic constrained optimization problem. This will require linear programming because you have inequality constraints.

Alternatively since this is entirely linear and each factory is independent of each other, work out which option A/B offers the highest return per factory. Call this the chosen product. Work out how many units of the chosen product can be produced given the constraint. Look at the factory downtime, if this is bigger than required to build more unit of the non-chosen item then this must also be produced.

Then compare hour blocks to produce the object A,B (i.e. F1 is 3 or 7) to calculate how many multiples of the not-chosen product are foregone in producing the last unit of the chosen product, you must also add on any factory downtime at this stage. i.e. let the value for the chosen product be 7 and 3 for the non-chosen, then we have 2 units foregone. But if we have 2 hours downtime, then it should be (7+2) / 3 to yield 3 units foregone.

Compare if the units foregone for the last output of the chosen product at a given factory exceed in value the last unit produced (this is the remainder problem).

If true, then the factory produces this mixed output. If false, proceed with the prior output strategy for said factory.

Select highest and then move on to the next factory. Rest should be obvious.

This is my C++ code to solve the problem using my alternative method. I hope this clears up all questions.

// Cybernex's example program in c++

include iostream

using namespace std;

// prototypes and n11 variables setting

void announcer(int);

void calculatefactory (float, float, float, float, float);

void closingannounce();

float price1 = 10.5;

float price2 = 13;

float hourf1a = 3;

float hourf1b = 7;

float hourf2a = 6;

float hourf2b = 5;

float hourf3a = 16;

float hourf3b = 11;

float totalf1 = 5;

float totalf2 = 11;

float totalf3 = 21.6;

// total output of good a

float r1 = 0;

// total output of good b

float r2 = 0;

// total value of output

float r3 = 0;

int main(){

// factory 1

announcer(1); calculatefactory (price1, price2, hourf1a, hourf1b, totalf1);

// factory 2 announcer(2); calculatefactory (price1, price2, hourf2a, hourf2b, totalf2);

// factory 3 announcer(3); calculatefactory(price1, price2, hourf3a, hourf3b, totalf3);

// closing outputs closingannounce();

return 0; };

// for clarity in outputs

void announcer (int a){ cout << endl << "We are calculating for factory: " << a << endl << endl; };

// gives final results

void closingannounce (){ cout << endl << endl << endl << endl; cout << "Total quantity of A produced by all factories " << r1 << endl; cout << "Total quantity of B produced by all factories " << r2 << endl; r3 = (r1 * price1); r3 = r3 + (r2 * price2); cout << "Total value of output is " << r3 << endl; }

// main alg

void calculatefactory (float pricea, float priceb, float hoursa, float hoursb, float totaltime){

// CHECK AT LEAST 1 UNIT CAN BE PRODUCED FOR EACH GOOD

bool canamake = false; bool canbmake = false; if (hoursa <= totaltime){ canamake = true; }; if (hoursb <= totaltime){ canbmake = true; };

// No output possible

if (canamake == false && canbmake == false){ cout << endl << "No output possible at this factory" << endl; };

// A is possible, B is not

if (canamake == true && canbmake == false){

// first step work out how many of A can be made

int internaloutput = totaltime / hoursa;

// We cannot use the remaining hours so this is total output for this factory

r1 = r1 + internaloutput;

cout << endl << "The factory produces " << internaloutput << " of good A" << endl; cout << "The factory produces 0 of good B" << endl;

};

// B is possible, A is not

if (canamake == false && canbmake == true){

// first step work out how many of B can be made

float internaloutput = totaltime / hoursb;

// We cannot use the remaining hours so this is total output for this factory

r2 = r2 + internaloutput;

cout << endl << "The factory produces " << internaloutput << " of good B" << endl; cout << "The factory produces 0 of good A" << endl;

};

// A and B are feasible

if (canamake == true && canbmake == true){

// SELECT CHOSEN OUTPUT

float internal1 = pricea / hoursa; float internal2 = priceb / hoursb;

// Chosen output is A OR if they are even we will make A anyway

if (internal1 >= internal2){

// Work out how much of A we can make

int internaloutputa = totaltime/hoursa; int internaloutputb;

// can we make any of B with the remainer?

float internal3 = totaltime; internal3 = internal3 - (internaloutputa * hoursa);

if (internal3 >= hoursb){ internaloutputb = internal3 /hoursb; };

// We now have our first set of solutions, which we must test for the unit foregone problem // first remove the marginal output from good a

int altinternaloutputa = internaloutputa - 1; int altinternaloutputb;

// now we look at how many more of b we can make

float internal4 = totaltime; internal4 = internal4 - (altinternaloutputa * hoursa); if (internal4 >= hoursb){ altinternaloutputb = internal4 / hoursb; };

// Now we compare the values to work out which solution we prefer

float value1 = internaloutputa*price1 + internaloutputb * price2; float value2 = altinternaloutputa * price1 + altinternaloutputb * price2;

// former output is more profitable

if (value1 >= value2){ r1 = r1 + internaloutputa; r2 = r2+ internaloutputb; cout << endl << "The factory produces " << internaloutputa << " of good A" << endl; cout << "The factory produces " << internaloutputb << " of good B" << endl; } if (value1 < value2){ r1 = r1 + altinternaloutputa; r2 = r2 + altinternaloutputb; cout << endl << "The factory produces " << altinternaloutputa << " of good A" << endl; cout << "The factory produces " << altinternaloutputb << " of good B" << endl; } };

// Chosen output is B

if (internal1 < internal2){

// Work out how much of B we can make

int internaloutputb = totaltime/hoursb; int internaloutputa;

// can we make any of B with the remainer?

float internal3 = totaltime; internal3 = internal3 - (internaloutputb * hoursb);

if (internal3 >= hoursa){ internaloutputa = internal3 /hoursa; };

// We now have our first set of solutions, which we must test for the unit foregone problem // first remove the marginal output from good a

int altinternaloutputb = internaloutputa - 1; int altinternaloutputa;

// now we look at how many more of b we can make

float internal4 = totaltime; internal4 = internal4 - (altinternaloutputb * hoursb);

if (internal4 >= hoursa){ altinternaloutputa = internal4 /hoursa; };

// Now we compare the values to work out which solution we prefer

float value1 = internaloutputa*price1 + internaloutputb * price2; float value2 = altinternaloutputa * price1 + altinternaloutputb * price2;

// former output is more profitable

if (value1 >= value2){ r1 = r1 + internaloutputa; r2 = r2 + internaloutputb; cout << endl << "The factory produces " << internaloutputa << " of good A" << endl; cout << "The factory produces " << internaloutputb << " of good B" << endl; }

if (value1 < value2){ r1 = r1 + altinternaloutputa; r2 = r2 + altinternaloutputb; cout << endl << "The factory produces " << altinternaloutputa << " of good A" << endl; cout << "The factory produces " << altinternaloutputb << " of good B" << endl; } }; }; };

share|improve this answer
    
my understanding is as follows.In the above example for factory1 "chosen product" is A. so we can produce (5/3)=1 A.We have 1 unit foregone.(coz in factory 1 we can't produce B). But i am not getting-"Compare if the units foregone for the last output of the chosen product at a given factory exceed in value the last unit produced (this is the remainder problem)." can you explian this with example given above? –  user6709 Feb 6 '13 at 18:40
    
You have zero units foregone because 7(b) is larger than 3(a). Units foregone is entirely for the last unit of the chosen product so can only apply if x(b) < y(a) when (a) is the chosen product. An example could be let (a) be the chosen product. (a) requires 10 hours per unit. Let (b) require 3 hour per unit. I have 25 hours on my factory. I have a remainder of 2 hours - factory downtime (2a + 1b). Although 1 (a) produces more profit then 4 (b), 5 (b) produce more profit than 1(a). So it is better to make 1(a) and 5(b) in this situation. This is why we do the units foregone comparison –  anon Feb 6 '13 at 19:02
    
I understand your constraint solution, but how would you explain the examples given? –  Merbs Feb 6 '13 at 19:07
    
So, for above example 1)chosen product is A 2) downtime for factory1 is 2 3)if we get 5 more hours we can choose B so we are foregone by 0? am i right? –  user6709 Feb 6 '13 at 19:14
1  
@Cybernex You should avoid giving the whole code ... boil it down to a pseudocode. And in either case, use proper formatting. –  Paresh Feb 10 '13 at 14:29
show 4 more comments

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.