Scribd Logo
Upload

Welcome to Scribd!

  • 34 views

    Assignment Problem 1

    Uploaded by

    Tushar Jethava
    This document summarizes an assignment problem presentation by Group 4. It includes the following topics: 1. Introduction by Dhara Lalu 2. Complete enumeration method explained by Gunjan Lashkari 3. Transportation problem discussed by Jay Ladva 4. Simplex method defined by Chintan Khetiya 5. Hungarian assignment method outlined by Riddhi and Kinjal 6. Special cases mentioned by Tushar and Hiren 7. Conclusion provided by Kuldeep An example of the complete enumeration method is shown to find the optimal assignment from a 3x3 cost matrix. The Hungarian assignment method is also demonstrated on a 5x5 example problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Assignment Problem 1

    Uploaded by

    Tushar Jethava
    34 views24 pages
    This document summarizes an assignment problem presentation by Group 4. It includes the following topics: 1. Introduction by Dhara Lalu 2. Complete enumeration method explained by Gunjan Lashkari 3. Transportation problem discussed by Jay Ladva 4. Simplex method defined by Chintan Khetiya 5. Hungarian assignment method outlined by Riddhi and Kinjal 6. Special cases mentioned by Tushar and Hiren 7. Conclusion provided by Kuldeep An example of the complete enumeration method is shown to find the optimal assignment from a 3x3 cost matrix. The Hungarian assignment method is also demonstrated on a 5x5 example problem.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes an assignment problem presentation by Group 4. It includes the following topics: 1. Introduction by Dhara Lalu 2. Complete enumeration method explained by Gunjan Lashkari 3. Transportation problem discussed by Jay Ladva 4. Simplex method defined by Chintan Khetiya 5. Hungarian assignment method outlined by Riddhi and Kinjal 6. Special cases mentioned by Tushar and Hiren 7. Conclusion provided by Kuldeep An example of the complete enumeration method is shown to find the optimal assignment from a 3x3 cost matrix. The Hungarian assignment method is also demonstrated on a 5x5 example problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    34 views24 pages

    Assignment Problem 1

    Uploaded by

    Tushar Jethava
    This document summarizes an assignment problem presentation by Group 4. It includes the following topics: 1. Introduction by Dhara Lalu 2. Complete enumeration method explained by Gunjan Lashkari 3. Transportation problem discussed by Jay Ladva 4. Simplex method defined by Chintan Khetiya 5. Hungarian assignment method outlined by Riddhi and Kinjal 6. Special cases mentioned by Tushar and Hiren 7. Conclusion provided by Kuldeep An example of the complete enumeration method is shown to find the optimal assignment from a 3x3 cost matrix. The Hungarian assignment method is also demonstrated on a 5x5 example problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 24

    ASSIGNMENT PROBLEM

    PRESENTED BY : GROUP NO. 4


    (JIGSAW)
    ROLL NO. 31 TO 40
    SUBMITTED TO : DR. MAYUR PARMAR
    TOPICS

     Introduction :- Dhara Lalu


     Complete enumeration method :- Gunjan
    Lashkari
     Transportation problem :- Jay Ladva
     Simplex method :- Chintan Khetiya
     HAM:- Riddhi & Kinjal
     Some special cases:- Tushar & Hiren
     Conclusion :- Kuldeep
    INTRODUCTION

     An assignment problem is a particular case of


    transportation problem where the objective is
    to assign a number of resources to an equal
    number of activities so as to minimize total
    cost or maximize total profit of allocation.
    COMPLETE ENUMARATION
    METHOD
     In these method, all possible assignments are listed
    out and the assignment involving the minimum
    cost(or maximum profit if the problem is of the
    maximization type) is selected. This represents the
    optimal solution. In case there are more than one
    assignment patterns involving the same least cost,
    they all shall represent optimal solution –the problem
    has multiple optimal then.
    EXAMPLE

    A B C

    1 120 110 80

    2 80 90 110

    3 110 140 120


     Size =3*3
    n!=3!
    =3*2*1
    =6 (there are six possible assignment)

    Assignment Time (minutes)


     A1-B2-C3 120+90+120=330
     A1-B3-C2 120+140+110=370
     A2-B1-C3 80+100+120=300
     A2-B3-C1 80+140+80=300
     A3-B1-C2 110+100+110=320
     A3-B2-C1 110+90+80=280
    TRANSPORTAION PROBLEM

     The transportation is associated with such


    problems principally because in studying
    efficient transportation routes, a special
    procedure was used which has come to be known
    as the transportation method.
    SIMPLEX METHOD

    Definition: 

     The Simplex Method  is used for calculating the


    optimal solution to the linear programming problem.
    In other words, the simplex algorithm is an iterative
    procedure carried systematically to determine the
    optimal solution from the set of feasible solutions.
     The simplex method presents an organized strategy
    for evaluating a feasible region’s vertices. This help to
    figure out the optimal value of the objective function.
    WHAT IS SIMPLEX ALGORITHM
    ?
     The transportation simplex algorithm is a linear
    program, a mathematical model representing linear
    relationships, like the transportation between a
    supplier and a destination. Linear programming
    allows the user to find the optimal or best outcome.
     The simplex algorithm proceeds by performing
    successive pivot operations each of which give an
    improved basic feasible solution; the choice of pivot
    element at each step is largely determined by the
    requirement that this pivot improves the solution.
    HUNGARIAN ASSGINMENT
    METHOD
    MEANING :

    The Hungarian method is based on the principal that if a


    constant is added to every element of raw and a column of
    cost matrix, the optimum solution of the resulting
    assignment problem is the same as the original problem and
    vice versa.
    STEPS IN HAM METHOD :
     Subtracted raw minimum
     Subtracted column minimum
     Cover all zeroes with a minimum number of lines
     Create additional zeroes
    PROBLEM OF HAM MATHOD
    1 2 3 4 5

    A 10 3 3 2 8

    B 9 7 8 2 7

    C 7 5 6 2 4

    D 3 5 8 2 4

    E 9 10 9 6 10
    1 2 3 4 5 1 2 3 4 5

    A 8 1 1 0 6 A 7 0 0 0 4
    B 7 5 6 0 5 B 6 4 5 0 3
    C 5 3 4 0 2 C 4 2 3 0 0

    D 1 3 6 0 2 D 0 2 5 0 0

    E 3 4 3 0 4 E 2 3 2 0 2
    1 2 3 4 5 1 2 3 4 5

    A 7 0 0 2 6 A 7 0 0 2 6

    B 4 2 3 0 3 B 4 2 3 0 3

    C 2 0 1 0 0 C 2 0 1 0 0

    D 0 2 5 2 2 D 0 2 5 2 2

    E 0 1 0 0 2 E 0 1 0 0 2
    ANSWER
    PERSON JOB COST

    A 2 3
    B 4 2
    C 5 4
    D 1 3
    E 3 9
    TOTAL COST 21
    SOME SPECIAL CASES

    1. Unbalanced assignment problem


    2. Constrained assignment problem
    3. Unique v/s multiple assignment problem
    CONCLUSION

    The assignment problem is a combinatorial optimization problem that is


    flexible as it can be used as an approach to model any real-world
    problem.
    THANK YOU…

    You might also like