Master key concepts in Transportation, Assignment, Linear Programming, and Project Management
Your overall progress
This study guide covers fundamental concepts and methods in Operations Research, focusing on four key areas: Transportation Problems, Assignment Problems (Hungarian Method), Linear Programming, and Project Management (PERT/CPM). The objective is to understand how these techniques are used to optimize resource allocation, minimize costs, maximize profits, and manage project schedules.
The Transportation Problem aims to find the most cost-effective way to distribute goods from multiple sources (e.g., factories, service centers) to multiple destinations (e.g., warehouses, customers).
This iterative method seeks an initial feasible solution by prioritizing the lowest shipping costs.
Hint: Look for the smallest number in the cost matrix. This will be your starting point for allocation.
Hint: Compare the supply at the source and the demand at the destination. Allocate the smaller of the two values.
Hint: Update the supply and demand values. If either reaches zero, that row or column is eliminated from further consideration.
Hint: Continue the process, always selecting the cell with the minimum cost from the remaining options.
Hint: Multiply each allocation by its corresponding cost and sum all these products to get the total shipping cost.
The Fraser Silver Mine Company has two mines (sources) and three warehouses (destinations). The shipping costs, supplies, and demands are as follows:
| Source | W1 | W2 | W3 | Supply |
|---|---|---|---|---|
| Mine 1 | $10 | $2 | $20 | 15 |
| Mine 2 | $7 | $9 | $4 | 25 |
| Demand | 10 | 15 | 15 | 40 |
The minimum cost in the matrix is $2, which is in the cell (Mine 1, W2).
Hint: Scan the entire cost matrix to find the smallest value. In this case, it's $2 at the intersection of Mine 1 and W2.
At cell (Mine 1, W2), we allocate the minimum of supply (15) and demand (15), which is 15 units.
Hint: Compare the supply at Mine 1 (15) and the demand at W2 (15). Since they're equal, we allocate the full 15 units.
After allocation:
Hint: When a source's supply is exhausted or a destination's demand is met, that row or column is no longer available for allocation.
The remaining cells are:
Hint: With Mine 1 and W2 eliminated, we only have Mine 2 with W1 and W3 to consider. The minimum cost is $4.
At cell (Mine 2, W3), we allocate the minimum of supply (25) and demand (15), which is 15 units.
Hint: Mine 2 has 25 units available, and W3 needs 15 units. We allocate the smaller value, which is 15 units.
After allocation:
Hint: W3's demand is fully met, so we don't need to allocate any more units to this destination.
The only remaining cell is (Mine 2, W1). We allocate the remaining supply of 10 units to meet W1's demand of 10 units.
Hint: With only one cell left, we allocate all remaining supply to meet the remaining demand.
Total Shipping Cost (TSC) = (15 × $2) + (15 × $4) + (10 × $7) = $30 + $60 + $70 = $160
| Source | W1 | W2 | W3 | Supply |
|---|---|---|---|---|
| Mine 1 | - | 15 ($2) | - | 15 |
| Mine 2 | 10 ($7) | - | 15 ($4) | 25 |
| Demand | 10 | 15 | 15 | 40 |
Hint: Multiply each allocation by its cost and sum the results: (15 units × $2) + (15 units × $4) + (10 units × $7) = $30 + $60 + $70 = $160.
The Assignment Problem is a special type of transportation problem where resources (e.g., trucks, workers) are assigned to tasks (e.g., routes, jobs) on a one-to-one basis, with the objective of minimizing the total cost or maximizing total profit. The Hungarian Method is a widely used algorithm for solving this problem.
Hint: This creates at least one zero in each row, which helps in identifying potential assignments.
Hint: This creates at least one zero in each column, further simplifying the matrix for optimal assignment identification.
Hint: Draw the minimum number of horizontal and/or vertical lines required to cover all zeros in the matrix.
Hint: This indicates that we can make a complete assignment where each row and column has exactly one assignment.
Hint: Find the smallest uncovered element, subtract it from all uncovered elements, and add it to elements at the intersection of two lines.
Hint: Prioritize zeros with minimum original cost if multiple options exist.
Hint: Look up the original cost matrix values for the positions where you made assignments and sum them.
A company needs to assign 5 trucks to 5 routes with the following cost matrix:
| Truck/Route | R1 | R2 | R3 | R4 | R5 |
|---|---|---|---|---|---|
| T1 | 10 | 5 | 13 | 15 | 16 |
| T2 | 3 | 9 | 18 | 13 | 6 |
| T3 | 10 | 7 | 2 | 2 | 2 |
| T4 | 7 | 11 | 9 | 7 | 12 |
| T5 | 7 | 9 | 10 | 4 | 12 |
Subtract the minimum element of each row from all elements in that row:
| Truck/Route | R1 | R2 | R3 | R4 | R5 | Row Min |
|---|---|---|---|---|---|---|
| T1 | 5 | 0 | 8 | 10 | 11 | 5 |
| T2 | 0 | 6 | 15 | 10 | 3 | 3 |
| T3 | 8 | 5 | 0 | 0 | 0 | 2 |
| T4 | 0 | 4 | 2 | 0 | 5 | 7 |
| T5 | 3 | 5 | 6 | 0 | 8 | 4 |
Hint: For each row, find the minimum value and subtract it from every element in that row. This ensures each row has at least one zero.
Subtract the minimum element of each column from all elements in that column:
| Truck/Route | R1 | R2 | R3 | R4 | R5 |
|---|---|---|---|---|---|
| T1 | 5 | 0 | 8 | 10 | 11 |
| T2 | 0 | 6 | 15 | 10 | 3 |
| T3 | 8 | 5 | 0 | 0 | 0 |
| T4 | 0 | 4 | 2 | 0 | 5 |
| T5 | 3 | 5 | 6 | 0 | 8 |
| Col Min | 0 | 0 | 0 | 0 | 0 |
Since all column minimums are zero, the matrix remains unchanged.
Hint: For each column, find the minimum value and subtract it from every element in that column. In this case, all columns already have a zero, so no change is needed.
We need to cover all zeros with the minimum number of lines:
| Truck/Route | R1 | R2 | R3 | R4 | R5 |
|---|---|---|---|---|---|
| T1 | 5 | 0 | 8 | 10 | 11 |
| T2 | 0 | 6 | 15 | 10 | 3 |
| T3 | 8 | 5 | 0 | 0 | 0 |
| T4 | 0 | 4 | 2 | 0 | 5 |
| T5 | 3 | 5 | 6 | 0 | 8 |
We can cover all zeros with 4 lines (rows T1, T3, T5 and column R1).
Hint: Try to cover all zeros with as few lines as possible. Draw lines through rows or columns that contain zeros. The minimum number of lines needed is 4.
The number of lines (4) is less than the number of rows/columns (5), so we need to modify the matrix.
Hint: For an optimal assignment to be possible, the number of lines must equal the number of rows/columns. Since 4 < 5, we need to proceed to the next step.
Find the smallest uncovered element (which is 2). Subtract it from all uncovered elements and add it to elements at the intersection of two lines:
| Truck/Route | R1 | R2 | R3 | R4 | R5 |
|---|---|---|---|---|---|
| T1 | 5 | 0 | 6 | 8 | 9 |
| T2 | 0 | 6 | 13 | 8 | 1 |
| T3 | 8 | 5 | 0 | 0 | 0 |
| T4 | 0 | 4 | 2 | 0 | 5 |
| T5 | 3 | 5 | 6 | 0 | 8 |
Hint: The smallest uncovered element is 2. Subtract 2 from all uncovered elements and add 2 to elements at the intersection of two lines (if any).
Now, we can cover all zeros with 5 lines (equal to the number of rows/columns), so an optimal assignment is possible.
Hint: After modifying the matrix, we now need 5 lines to cover all zeros, which equals the number of rows/columns. This means we can make an optimal assignment.
Make assignments by selecting zeros such that each row and column has exactly one assigned zero:
| Truck/Route | R1 | R2 | R3 | R4 | R5 |
|---|---|---|---|---|---|
| T1 | 5 | 0 | 6 | 8 | 9 |
| T2 | 0 | 6 | 13 | 8 | 1 |
| T3 | 8 | 5 | 0 | 0 | 0 |
| T4 | 0 | 4 | 2 | 0 | 5 |
| T5 | 3 | 5 | 6 | 0 | 0 |
Hint: Select one zero in each row and column, ensuring no two assignments share the same row or column. Start with rows/columns that have only one zero.
Total Assignment Cost (TAC) = 5 + 3 + 2 + 7 + 12 = $29
Hint: Sum the original costs for the assigned positions: T1-R2 ($5) + T2-R1 ($3) + T3-R3 ($2) + T4-R4 ($7) + T5-R5 ($12) = $29.
Linear Programming (LP) is a mathematical technique used to optimize a linear objective function, subject to linear equality and inequality constraints. It is widely used for resource allocation, production planning, and mix problems.
The graphical method is suitable for problems with two decision variables.
Hint: Define decision variables, state the objective function, and write down all constraints as linear inequalities.
Hint: Treat each inequality as an equality and plot the corresponding lines on a graph.
Hint: The feasible region is the area that satisfies all constraints simultaneously, including non-negativity constraints.
Hint: Identify the coordinates of all vertices of the feasible region. These points represent the intersection of constraint lines.
Hint: Substitute the coordinates of each corner point into the objective function.
Hint: For maximization problems, the corner point yielding the highest objective function value is optimal. For minimization, it's the lowest value.
A jewelry store wants to maximize profit from necklaces (X) and bracelets (Y). Each necklace requires 2 grams of gold and 3 grams of platinum, and each bracelet requires 3 grams of gold and 1 gram of platinum. The store has 120 grams of gold and 90 grams of platinum available. Additionally, due to market demand, the store can produce at most 30 bracelets. The profit per necklace is $40 and per bracelet is $30.
Decision Variables:
Hint: Define variables for what you're trying to decide (number of necklaces and bracelets). The objective is to maximize profit, so create an equation for total profit. Constraints represent resource limitations and market restrictions.
Convert each inequality to an equation and plot the corresponding lines:
Hint: To plot a line, find two points that satisfy the equation. For 2X + 3Y = 120, when X=0, Y=40; when Y=0, X=60. Connect these points to draw the line.
The feasible region is the area that satisfies all constraints simultaneously. It is a polygon bounded by the lines and the axes, in the first quadrant (since X ≥ 0, Y ≥ 0).
Hint: The feasible region is where all constraints overlap. For each constraint, shade the region that satisfies the inequality. The feasible region is where all shaded areas intersect.
The corner points of the feasible region are:
Hint: Corner points are where constraint lines intersect or where constraints meet the axes. Solve systems of equations to find intersection points.
Substitute each corner point into the objective function Z = 40X + 30Y:
Hint: For each corner point (X,Y), plug the values into the objective function Z = 40X + 30Y to calculate the profit at that point.
The maximum profit is $1,500, achieved at two points:
Hint: For maximization, select the corner point(s) with the highest objective function value. If multiple points yield the same maximum value, there are multiple optimal solutions.
Project Management techniques like PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method) are used to plan, schedule, and control complex projects. They help in identifying the critical activities that determine the project's duration and assessing project completion probabilities.
Hint: Create a table of all activities, their predecessors, and time estimates (to, tm, tp).
Hint: For each activity, use the PERT formulas: $te = (to + 4tm + tp) / 6$ and $\sigma^2 = ((tp - to) / 6)^2$.
Hint: Use Activity-on-Node (AON) or Activity-on-Arrow (AOA) notation to represent activities and their dependencies.
Hint: Calculate ES and EF for all activities, moving from the start to the end of the project. The EF of the last activity is the project completion time.
Hint: Calculate LS and LF for all activities, moving from the end to the start of the project.
Hint: Slack = LS - ES or LF - EF. Activities with zero slack are on the critical path.
Hint: The critical path is the longest path through the network diagram, consisting of activities with zero slack.
Hint: Sum the variances of all activities on the critical path.
Hint: Use the Z-score formula: $Z = (D - T_E) / \sqrt{V}$, where D is the desired completion time and $T_E$ is the critical path's expected time. Look up the Z-score in a standard normal distribution table.
A project has the following activities with their time estimates (in weeks) and predecessors:
| Activity | Predecessor | to | tm | tp |
|---|---|---|---|---|
| A | - | 3 | 6 | 9 |
| B | A | 2 | 5 | 8 |
| C | A | 4 | 7 | 10 |
| D | B | 1 | 4 | 7 |
| E | C | 3 | 6 | 9 |
| F | D, E | 2 | 5 | 8 |
| G | F | 1 | 4 | 7 |
Using the formulas $te = (to + 4tm + tp) / 6$ and $\sigma^2 = ((tp - to) / 6)^2$:
| Activity | te | σ² |
|---|---|---|
| A | (3 + 4×6 + 9)/6 = 36/6 = 6 | ((9-3)/6)² = 1 |
| B | (2 + 4×5 + 8)/6 = 30/6 = 5 | ((8-2)/6)² = 1 |
| C | (4 + 4×7 + 10)/6 = 42/6 = 7 | ((10-4)/6)² = 1 |
| D | (1 + 4×4 + 7)/6 = 24/6 = 4 | ((7-1)/6)² = 1 |
| E | (3 + 4×6 + 9)/6 = 36/6 = 6 | ((9-3)/6)² = 1 |
| F | (2 + 4×5 + 8)/6 = 30/6 = 5 | ((8-2)/6)² = 1 |
| G | (1 + 4×4 + 7)/6 = 24/6 = 4 | ((7-1)/6)² = 1 |
Hint: For each activity, calculate the expected time using the weighted average formula. The variance measures the uncertainty in the time estimate.
The project network diagram (AON notation) would look like this:
Activities D and E both must be completed before F can start.
Hint: In AON notation, each activity is represented by a node, and arrows show dependencies. Activity A has no predecessor, so it starts at the beginning. Activity F has two predecessors (D and E).
Calculate ES and EF for all activities:
| Activity | ES | te | EF |
|---|---|---|---|
| A | 0 | 6 | 6 |
| B | 6 | 5 | 11 |
| C | 6 | 7 | 13 |
| D | 11 | 4 | 15 |
| E | 13 | 6 | 19 |
| F | 19 (max of EF of D and E) | 5 | 24 |
| G | 24 | 4 | 28 |
Hint: For activities with multiple predecessors, ES is the maximum of the EF values of all predecessors. For example, F can only start after both D (EF=15) and E (EF=19) are completed, so ES for F is 19.
Calculate LS and LF for all activities (starting from the end with LF = EF of the last activity):
| Activity | LF | te | LS |
|---|---|---|---|
| G | 28 | 4 | 24 |
| F | 24 | 5 | 19 |
| E | 19 | 6 | 13 |
| D | 19 | 4 | 15 |
| C | 13 | 7 | 6 |
| B | 15 | 5 | 10 |
| A | 6 (min of LS of B and C) | 6 | 0 |
Hint: For activities with multiple successors, LF is the minimum of the LS values of all successors. For example, A has two successors (B and C), so LF for A is the minimum of LS for B (10) and LS for C (6), which is 6.
Calculate Slack = LS - ES for each activity:
| Activity | ES | LS | Slack |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 6 | 10 | 4 |
| C | 6 | 6 | 0 |
| D | 11 | 15 | 4 |
| E | 13 | 13 | 0 |
| F | 19 | 19 | 0 |
| G | 24 | 24 | 0 |
Hint: Slack represents the flexibility in scheduling an activity. Activities with zero slack are on the critical path and cannot be delayed without delaying the entire project.
The critical path consists of activities with zero slack: A → C → E → F → G
Hint: The critical path is the longest path through the network. In this case, it's A-C-E-F-G with a total duration of 28 weeks.
Project Variance (V) = Sum of variances of activities on the critical path:
Hint: The project variance is the sum of the variances of all activities on the critical path. It measures the overall uncertainty in the project completion time.
Calculate the probability of completing the project within 26 weeks:
Therefore, there is an 18.6% chance of completing the project within 26 weeks.
Hint: The Z-score measures how many standard deviations the desired completion time is from the expected completion time. A negative Z-score means the desired time is less than the expected time.
What is the primary objective of a Transportation Problem, and what condition must be met for a balanced problem?
Activity: A specific task or work element that is part of a project.
Assignment Problem: A special type of transportation problem where resources are assigned to tasks on a one-to-one basis to minimize cost or maximize profit.
Backward Pass: A calculation process in PERT/CPM used to determine the latest possible start and finish times for activities without delaying the project.
Critical Path (CP): The longest sequence of activities in a project network diagram, determining the minimum project completion time. Activities on the critical path have zero slack.
Critical Path Method (CPM): A project modeling technique used to analyze tasks, determine task dependencies, and identify the critical path.
Column Reduction: A step in the Hungarian Method where the minimum element of each column is subtracted from all elements in that column, creating at least one zero in each column.
Constraints: Linear inequalities or equalities in a linear programming model that limit the possible values of decision variables, representing resource availability or other restrictions.
Decision Variables: Unknown quantities in a mathematical model (e.g., linear programming) whose values are to be determined to achieve the optimal solution.
Demand: The quantity of goods required at a particular destination in a transportation problem.
Destination: A point where goods are received or required in a transportation problem (e.g., warehouses, customers).
Early Finish (EF): The earliest time an activity can be completed, calculated by adding the activity's expected time to its Early Start time.
Early Start (ES): The earliest time an activity can begin, considering the completion of all its predecessor activities.
Expected Time ($t_e$): A weighted average of optimistic, most likely, and pessimistic time estimates for an activity in PERT, calculated as $(to + 4tm + tp) / 6$.
Feasible Region: The set of all points on a graph that satisfy all the constraints of a linear programming problem.
Forward Pass: A calculation process in PERT/CPM used to determine the earliest possible start and finish times for activities, moving from the project's beginning to its end.
Hungarian Method: An algorithm used to solve assignment problems efficiently by transforming the cost matrix to simplify finding an optimal assignment.
Late Finish (LF): The latest time an activity can be completed without delaying the entire project.
Late Start (LS): The latest time an activity can begin without delaying the entire project.
Least Cost Method (Short-Cut Method): An iterative method for finding an initial feasible solution to a transportation problem by prioritizing allocations to cells with the lowest shipping costs.
Linear Programming (LP): A mathematical technique used to optimize a linear objective function subject to a set of linear equality and inequality constraints.
Non-negativity Constraints: A common set of constraints in linear programming stating that decision variables cannot take negative values.
Objective Function: A linear equation in an LP model that represents the quantity to be maximized (e.g., profit) or minimized (e.g., cost).
Optimistic Time ($t_o$): The shortest possible time an activity can be completed under ideal conditions in PERT.
Pessimistic Time ($t_p$): The longest possible time an activity might take under the worst possible conditions in PERT.
Predecessor Activity: An activity that must be completed before another activity can start.
Program Evaluation and Review Technique (PERT): A project management tool used to analyze and represent the tasks involved in completing a given project, especially useful for projects with uncertain activity times.
Project Variance (V): The sum of the variances of all activities on the critical path, used to assess the uncertainty in the project completion time.
Row Reduction: A step in the Hungarian Method where the minimum element of each row is subtracted from all elements in that row, creating at least one zero in each row.
Shipping Cost/Unit: The cost associated with transporting one unit of a product from a specific source to a specific destination.
Slack (S): The amount of time an activity can be delayed without delaying the project completion time (LS - ES or LF - EF).
Source: A point from which goods are shipped in a transportation problem (e.g., factories, mines).
Successor Activity: An activity that cannot start until a preceding activity is completed.
Supply: The quantity of goods available at a particular source in a transportation problem.
Total Assignment Cost (TAC): The sum of the original costs for the chosen assignments in an assignment problem.
Total Shipping Cost (TSC): The sum of the products of allocated quantities and their respective shipping costs in a transportation problem.
Transportation Problem: A type of linear programming problem that deals with determining the most efficient way to transport goods from multiple sources to multiple destinations to minimize total shipping costs.
Variance ($\sigma^2$): A measure of the dispersion or uncertainty in an activity's completion time, calculated as $((tp - to) / 6)^2$.
Z-score: A statistical measure indicating how many standard deviations an element is from the mean, used in PERT to calculate the probability of project completion by a desired date.