Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Operations research ><

  1. May 10, 2010 #1
    Hi. I really need help with a problem I've been given @ university regarding optimisation. I have little idea how to solve it.

    We are given an employee class, say "Senior Manager", and the skills that need training, given as a vector:
    0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1

    or perhaps "Assistant Manager"
    1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0

    Then we are given numerous different programs that cover different skills, some that will obviously overlap with the ones we need to cover, and each program has a different cost.

    e.g "Program 1", $500.
    0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1

    Then we're given
    1) the number of days each program will run for
    2) the salary of each employee class and the number of days in a work year (250).
    i know 1 & 2 lead to the opportunity cost of undertaking a given program.

    how the heck do I go about optimally allocating program to employee class?
     
  2. jcsd
  3. May 11, 2010 #2

    Mark44

    Staff: Mentor

    No one has responded so far, so here are my thoughts, FWIW.

    One way to measure how useful a program is for a particular class of employees is to calculate the dot product of the employee vector with the program vector. The larger the value of the dot product, the more the program aligns with the skills needed by the particular employee class.

    For example, the assistant manager vector dotted with the program 1 vector gives
    <1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0> "dot"
    <0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1> = 2

    This means that program 1 provides training in 2 skills needed by assistant managers.

    The sr. manager vector dotted with the program 1 vector gives
    <0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1>
    <0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1> = 4,
    meaning that the training in program 1 is applicable to 4 skills needed by sr. managers.

    You can further quantify how beneficial the training is by calculating the time lost to training (in days) and the dollar amount of productivity (salary per day times number of days). You might apply this information as a tie-breaker if two different employee classes end up with identical dot products for the same training.
     
  4. May 11, 2010 #3
    Thanks alot for the response. I had a similar idea in the last day, and have been running this in excel. I've come up with an equation for employee class --> program to find the cost:


    [Cost(of program) + (Days of program/250 * Yearly Salary)]/DOT


    This should give the cost per skill of a program as matched to an employee class. The Smallest cost/skill for employee class --> program will be the one I pick, then I have to run the iteration again for the same employee class to find the second program that covers the remainder of the skills.

    Note: There's 250 working days in a year.
    -------------------------------------------
    This model looks so beautiful. But there's something we're not internalizing...

    Let's say program 1 matches 10 skills with Senior Manager, and program 2 matches 11 skills with Senior Manager.
    Let's consider the equation outputs a lower cost per skill for program 1. But, how do we know that the 11th skill doesn't have some huge cost in some other program --- that's not accounted for by the model?
     
    Last edited: May 11, 2010
  5. May 11, 2010 #4

    Mark44

    Staff: Mentor

    On your last question, can you be more specific?
     
  6. May 11, 2010 #5
    Yeah sure.

    What I mean is, if we figure out that the lowest Cost Per Skill is with Program 1, but if we were to pick Program 1 over Program 2, Program 2 might have an extra skill that program 1 doesn't have that is SUPER expensive in any other program, but by picking the 'optimal' program 1, we have this huge cost burden by having to go with program 3 that has the super expensive extra skill that program 1 doesn't have.

    This isn't accounted for in the model.
     
    Last edited: May 11, 2010
  7. May 11, 2010 #6
    Another way to say this:

    P1 is optimal vs. P2, based on cost per skill assessment. P1 has skills A-D, P2 has skills A-E. P1 has a cost per skill of $1, P2 has a cost per skill of $1.01.
    Senior Manager needs skills A-E. We determine that P1 is optimal, given this formula that we're using. However, skill E is only covered by P2 and P3, and P3 is extremely expensive, and purchasing P1 + P2 is stupid when we could've just purchased P2.

    Thus, this model would've told us to pick P1, but picking P2 is a superior strategy.

    We can manually sieve the database for the occurance of this problem, but that isn't very "scientific", which is what OR methodology demands.
     
    Last edited: May 11, 2010
  8. May 11, 2010 #7
    Another way of looking at it:

    P1 is optimal vs. P2, based on cost per skill assessment. P1 has skills A,B,C,X - $1 per skill, P2 has skills A,B,C,Y. - $1.01 per skill.

    However, P3 has skill Y at $5,000
    P4 has skill X at $0.10.


    We should've picked P2 in the first iteration, but the problem is our first iteration is BLIND to future iterations, and thus cannot make an optimal allocation!>!>!>!?>!?!?
     
  9. May 11, 2010 #8

    Mark44

    Staff: Mentor

    Isn't all that taken care of in your formula? Cost(of program) + ...
     
  10. May 12, 2010 #9
    ------------------------------------
    HERE'S A FORMULATION THAT MAKES SENSE.

    Let's say these are our thingys:
    Senior Manager needs..... : 1 1 1 1 1 0 1 1 1 1 1 0 1
    Program 1(($1/dot-skill))..: 1 1 1 1 1 0 0 0 0 0 0 0 0
    Program 2($1.50/dot-skill): 1 1 1 1 1 0 0 0 0 0 0 0 1
    Program 3($999/dot-skill).: 0 0 0 0 0 0 0 0 0 0 0 0 1
    Program 4($50/dotskill)....: 1 0 0 0 0 0 0 0 0 0 0 0 1


    If we follow the model, we'd pick Program 1, THEN program 2 ASWELL, when we should just be picking Program 2!!!


    How do we fix this dilemma ><
     
    Last edited: May 12, 2010
  11. May 12, 2010 #10

    Mark44

    Staff: Mentor

    I get the sense that you didn't understand what I said back in post #2 about dot products. What I wrote "dot" that meant the dot product of two vectors.

    For example, I had
    The sr. manager vector dotted with the program 1 vector gives
    <0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1> [itex]\cdot[/itex] <0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1> = 4.

    I'm assuming you knew what I meant by the dot product, but I'm not sure that you do.

    In post #3 you have
    [Cost(of program) + (Days of program/250 * Yearly Salary)]/DOT

    What do you mean by DOT?

    In post #9 you have
    Program 3($999/dot-skill).: 0 0 0 0 0 0 0 0 0 0 0 0 1
    What do you mean by dot-skill?
     
  12. May 12, 2010 #11
    Yeah I did get what you meant :)

    The reason why I said $$$/dot-skill is that I thought $$$/skill would be misleading, because that could've been interpreted as the cost per all skills the program offers, not just the skills that are matched up with what the Senior Manager needs (which I what I was intending to convey with /dot-skill).

    Let's say that for the example I provided,
    the rows 2-5 (i.e. Programs 1-4) are dot products of row 1.

    So the dot-value that I'd be inputing into my equation for Program 4 would be "2", as long as no programs before it have been assigned that cover skill 1 or skill 13.

    _______________________________________________


    My use of "/" when saying "$50/dot-skill" or whatever is NOT a divided sign, it's simply saying $50 per dot-skill.



    ------------------------------------------------------

    If we run our formula on the 4 programs provided, we get a suboptimal allocation, right?
     
    Last edited: May 12, 2010
  13. May 12, 2010 #12

    Mark44

    Staff: Mentor

    I'm glad that one of us does!
    $/skill conveys to me the amount of dollars per (one) skill, not for all skills. When someone writes km/hr they mean kilometers per each hour, not the number of kilometers for all the hours.
    Please, no more "dot-skill." That's terrible! It adds complexity and reduces understandability!
    Then you need to examine the formula you came up with. You can build the per-skill costs into the program vectors by using the cost, rather than just a 1. E.g., here is program 4 revised: Program 4($50/skill)....: 50 0 0 0 0 0 0 0 0 0 0 0 50
     
  14. May 12, 2010 #13
    How would one output a solution though?
     
    Last edited: May 12, 2010
  15. May 12, 2010 #14

    Mark44

    Staff: Mentor

    Since you are doing this in Excel, you could have some logic that chooses the optimal plan and displays the decision results in some cell.
     
  16. May 12, 2010 #15
    Thankyou so much for your help Mark.

    Perhaps there's a way, but I can't fathom a way of incorporating future iterations into the current iteration without some kind of mass simulation.

    Oh well, I guess I could try and formulate the problem in LINGO, somehow...

    What do you think of this, for Senior Manager, where x1, x3, x8, x10, x12 are the skills he needs to be covered, his salary is $250,000, 250 working days. Of course, in the constraints we can ignore the extra skills that the senior manager doesn't need.

    MINIMIZE z = x1+x3+x8+x10+x12;

    s.t.

    (500 - program cost) + (2 - number of days running)(250000 - salary)/(250) = x1 + x3 + x8
    600 + (3)(250000)/(250) = x1 + x8
    (800) + (4)(250000)/(250) = x10 + x12
    (1000) + (2)(250000)/(250) = x1 + x3 + x12
    .
    .


    I haven't got LINGO on this computer so I haven't had a chance to try it out xD

    The left side of the constraints are the total cost of the program, and the right side are the skills it covers that matches with the senior managers skills.

    Will this work?
     
    Last edited: May 13, 2010
  17. May 13, 2010 #16
    ^^^
    Nope, that model's totally wrong.
     
  18. May 18, 2010 #17
    Define Xij = 1 if employee class i is assigned to program j, 0 otherwise.
    Let Ai be the cost of program i.
    Let Bi be the salary of employee i.
    Let Di be the length of program i.
    Let Kij = 1 if employee i's jth skill must be trained.
    Let Qij = 1 if program i trains the jth skill.

    minimize [tex]\Sigma[/tex] [tex]\Sigma[/tex]Xij(Aj+DjBi/250)

    subject to

    XijQjk>= Kij for all i,k
    Xij= 0 or 1
     
    Last edited: May 18, 2010
  19. May 18, 2011 #18
    - Use the dual simplex method to solve the following LP:
    Max Z = -2X1 - X3
    s.t. X1 + X2 – X3 >= 5
    X1 - 2X2 + 4X3 >=8
    X1, X2, X3 >=0
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Operations research ><
  1. Math research (Replies: 9)

  2. Archimedes research (Replies: 3)

Loading...