Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 38 ยท Projects and Practice

Practice Problem Set

Eight practice problems on integer programming, transportation, max flow, assignment, scheduling, queues, blending and project planning, with runnable solutions and answers to check against.

Reading about optimization is not the same as doing it. This lesson gives you eight problems that cover the second half of the course: integer programming, network flows, scheduling and queueing, and applications. Try each one on paper or in your own code first. Then run the solution blocks to check your answers.

A good workflow for every problem:

  1. Identify the type (knapsack? transportation? flow? queue?).
  2. Write the decision variables, the objective and the constraints in words, then in symbols.
  3. Estimate the answer (a bound or a rough value) before computing.
  4. Solve, then verify (constraints satisfied? sensible magnitude? matches a simple method?).

The problems

Problem 1: Project selection. A firm has five projects with values 12, 9, 14, 7, 11 (in thousands) and costs 20, 15, 25, 10, 18. The budget is 50. Projects 1 and 3 cannot both be chosen (they need the same team). Which projects maximize total value? Also compute the LP relaxation value and explain the gap. (Hint: Binary Variables and Logic.)

Problem 2: Unbalanced shipping. Two warehouses hold 40 and 60 units. Three stores need 30, 25 and 35 units. Unit shipping costs are [4, 6, 9] from warehouse 1 and [5, 3, 7] from warehouse 2. Find the cheapest plan and say how many units stay in stock. (Hint: The Transportation Problem.)

Problem 3: Maximum flow. A network has nodes 0 to 5, source 0 and sink 5, with arcs (capacity): 0-1 (7), 0-2 (9), 1-3 (5), 1-2 (3), 2-4 (8), 3-5 (6), 4-3 (2), 4-5 (7). What is the maximum flow, and what is a minimum cut? (Hint: Max Flow and Min Cut.)

Problem 4: Assignment. Four engineers can be assigned to four tasks. The score matrix (higher is better) has rows [9,4,7,8], [6,8,3,5], [7,7,9,2], [5,6,4,9]. Maximize the total score. (Hint: The Assignment Problem.)

Problem 5: Sequencing. Five jobs with processing times 6, 2, 8, 3, 5 must run on one machine. Which order minimizes the mean completion time, and what is that mean? (Hint: Scheduling Basics and Dispatch Rules.)

Problem 6: A single-server queue. Customers arrive at 6 per hour and one clerk serves 8 per hour (both exponential). Find utilization, the average number in the system, the average number waiting, and the average time in the system and in the queue in minutes. (Hint: Queueing Fundamentals and the M/M/1 Queue.)

Problem 7: Blending crude oil. Crude A costs 30 per barrel, yields 30% gasoline and has 4% sulfur. Crude B costs 45 per barrel, yields 60% gasoline and has 1% sulfur. Buy 100 barrels in total so that at least 40 barrels of gasoline can be made and the total sulfur is at most 3 barrels, at least cost. (Hint: Blending and Feed Mix.)

Problem 8: Project duration. Activities (duration, predecessors): A (4, none), B (3, A), C (5, A), D (2, B), E (4, B and C), F (3, D and E). What is the project duration and the critical path? (Hint: Critical Path Method.)

Solutions: problems 1 to 4

Python Solutions to problems 1 to 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Answers.

  1. Choose projects 1, 4 and 5 for a value of 30 at a cost of 48. The LP relaxation gives 31.2, because it can take fractions of a project; the gap of 1.2 is the price of integrality.
  2. The cheapest plan costs 440: warehouse 1 sends 30 to store 1 and keeps 10, and warehouse 2 sends 25 to store 2 and 35 to store 3. The surplus of 10 units stays at warehouse 1 (the dummy column).
  3. The maximum flow is 13. A minimum cut has capacity 13 as well (the max-flow min-cut theorem); you can find it by listing the nodes reachable from the source in the residual graph.
  4. The total score is 35, achieved by the diagonal assignment: engineer 1 to task 1, 2 to 2, 3 to 3, 4 to 4 (9 + 8 + 9 + 9). Checking a few alternatives by hand is easy.

Solutions: problems 5 to 8

Python Solutions to problems 5 to 8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Answers.

  1. SPT order is job 2, 4, 5, 1, 3 (times 2, 3, 5, 6, 8), with completion times 2, 5, 10, 16, 24. The sum is 57, so the mean is 11.4.
  2. Utilization 0.75; L = 3, Lq = 2.25; W = 30 minutes in the system and Wq = 22.5 minutes in the queue. Little's law check: L = 6 * 0.5 hours = 3.
  3. Buy 66.67 barrels of crude A and 33.33 of crude B for a cost of 3,500. Both requirements are binding: gasoline is exactly 40 barrels and sulfur exactly 3 barrels, so there is no cheaper mix.
  4. The project takes 16 days along A, C, E, F (4 + 5 + 4 + 3). Activity D has 4 days of slack: it can start as late as day 11 instead of day 7, because F cannot begin before E ends on day 13. Activity B has 2 days of slack, since E waits for C until day 9.

Going further

If you solved all eight, try these extensions without looking at a solution:

  • Problem 1 with the extra rule "if project 4 is chosen, project 5 must be chosen" and with a minimum of two projects.
  • Problem 2 with a penalty of 10 per unit of unmet demand instead of a surplus.
  • Problem 3 with a node capacity of 5 on node 2.
  • Problem 5 with due dates; minimize the maximum lateness and compare with the number of tardy jobs.
  • Problem 6 with two clerks (M/M/2): how much does the average wait fall? (Multi-Server Queues and Simulation)
  • Problem 7 with a third crude oil and with a whole-barrel purchase requirement (MILP).

Keep a personal "pattern sheet": for each model type (knapsack, fixed charge, flow, assignment, queue) write the variables and constraints in two lines. Most real problems are one of those patterns in disguise.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Problem 1 the LP relaxation (31.2) exceeds the integer optimum (30). What does this show?

    For a maximization problem the relaxation bounds the integer optimum from above.
  2. 2. Why is a dummy column added in Problem 2?

    Total supply is 100 and demand 90; a zero-cost dummy destination takes the leftover.
  3. 3. What is the first thing to do when faced with a new optimization problem?

    A clear model, and an estimate of the answer, come before any computation.
  4. 4. In Problem 8 which activity has slack?

    The critical path is A, C, E, F; activity D (after B) is not on it and has 4 days of slack.

Summary

  • Practice means modeling first, solving second and verifying third.
  • The eight problems covered integer programming, transportation, flows, assignment, scheduling, queueing, blending and project planning.
  • Always compare the integer answer with the relaxation, the transportation plan with supply and demand totals, and queue formulas with Little's law.
  • Extending a solved problem with one extra rule is the fastest way to learn the modeling patterns.
  • You now have the tools to model, solve and analyze a wide range of operations research problems.

Next: Back to the Linear Programming track