Homework 7 - Dynamic Programming & Course Selection Strategies | Môn Deterministic Models in Operations Research - Trường Đại học Quốc tế, Đại học Quốc gia Thành phố Hồ Chí Minh

OPERATION RESEARCH HOMEWORK 7
Instruction: Please finish all questions IN WRITING and scan to pdf to submit before the due
hour. This is individual work, to be submitted on Blackboard. All homework must be submitted
to the Document Cabinet in front of room LA2.614. Additionally, a digital copy must be
uploaded to Blackboard as a backup in case the hard copy is lost. Problem 1:
Consider the following network, where each number along a link represents the
actual distance between the pair of nodes connected by that link. The objective is
to find the shortest path from the origin to the destination. Use dynamic
programming to solve this problem. Problem 2:
Given a network where nodes are connected by edges with distances, find the
shortest path from a start node to an end node using dynamic programming. Problem 3:
A student from School of Industrial Engineering and Management (IEM) must
select courses from the list of 5 specified courses for their upcoming summer
semester. She is ambitious for getting the Encouragement scholarship which is
valued at $300. Eligible criteria for applying for the Encouragement scholarship are as follows:
1. Each course can only be registered once for this semester.
2. The maximum credits allowed to be registered is 9 credits.
The students getting the highest GPA will have a chance to achieve the scholarship.
Therefore, she must have a strategy for registration to maximize GPA. She decided
to register 9 credits for this summer semester. Then, her GPA will be calculated as follows:
Where n is the number of courses that she registers for this summer semester. The
estimated grade and the number of credits for each course are given in table 1: Course Course name Number of Expected Grade No. credits 1 Quality management 3 80 2 Ho Chi Minh’s thoughts 2 90 3 Scientific writing 2 87 4 Financial Accounting 4 83 5 Project Management 3 84
Table 1: Course list for summer semester registration
Use dynamic programming to help her to build a strategy for her registration to
maximum GPA. (Show solution table and your calculation steps for the benefit of registering course 4) Problem 4:
A startup company is setting up a technical workshop and has a budget of
$1,000. There are 5 types of equipment available for purchase. Each tool
contributes to the productivity of the workshop and has a fixed cost and productivity score. Tool No. Tool Name Cost ($) Productivity Score 1 3D Printer 400 90 2 CNC Milling Machine 600 130 3 Laser Cutter 300 85 Tool No. Tool Name Cost ($) Productivity Score 4 Soldering Station 200 50 5 Air Compressor 250 60
Each tool can be purchased at most once (i.e., you cannot buy multiple of the
same tools). Help the startup determine which tools to buy in order to maximize
total productivity without exceeding the $1,000 budget.