Question 1: Integer Programming (50 Points)
A workshop has 5 jobs to perform today. Each job must be done by exactly one machine, but a machine can do more than one job. For each machine, there is a setup cost for the regular workday. Once this cost is paid, you can use the machine for up to 8 hours; if you do not pay the setup cost, you cannot use the machine today. If you set up a machine for the regular workday, you may also elect to set up the machine for overtime, in which case there is an additional cost and you may use the machine for up to 2 more hours. On the other hand, if you do not set up a machine for the regular workday, it cannot be used for overtime. The costs are as follows:
Overtime Setup Cost
Machine 1 $ 600 $ 190
Machine 2 $ 700 $ 200
Machine 3 $ 550 $ 275
Machine 4 $ 675 $ 150
Machine 5 $ 585 $ 195
Thus, if you pay $600, you can use machine 1 for up to 8 hours, and if you pay $600 + $190 = $790, you may use machine 1 for up to 8 + 2 = 10 hours. The number of hours each job takes on each machine is as follows:
Job 1 Job 2 Job 3 Job 4 Job 5
Machine 1 3.0 4.0 5.5 2.5 3.1
Machine 2 3.8 4.9 6.4 2.9 2.7
Machine 3 3.6 4.8 5.5 3.8 2.8
Machine 4 2.9 5.3 5.6 2.9 1.9
Machine 5 3.1 6.0 5.1 2.6 2.5
Define the decision variables. (4 Points)
Develop the objective function. (4 Points)
Write the constraints. (9 Points)
Solve the problem in Excel. (18 Points: Decision variables section: 3 point,
O.F. Section: 3 points, Constraints section: 8 points, Solver: 4 points )
Question 2: Integer Programming (50 Points)
The Texas Consolidated Electronics Company is contemplating a research and development program encompassing eight research projects. The company is constrained from embarking on all projects by the number of available management scientists (40) and the budget available for R&D projects ($300,000). Further, if project 2 is selected, project 5 must also be selected (but not vice versa). Following are the resource requirements and the estimated profit for each project:
Define the decision variables. (6 Points)
Develop the objective function. (6 Points)
Write the constraints. (15 Points)
Solve the problem in Excel. (23 Points: Decision variables section: 4
points, O.F. Section: 4 points, Constraints section: 10 points, Solver: 5 points)
Project #99034 – Advanced data structure
Posted By View Student Profile
Due By (Pacific Time)
Which of the sorts that we’ve discussed in class are stable (or can easily be written to be stable)? Which are not?
How efficient is MSD Radix sort compared to Quicksort for sorting ints in Java if 8 bit bytes are used as the characters (that is, an int is comprised of four 8 bit bytes.) How does this work out in practice?
Show the search trie that results from inserting the strings (and data) “ant” (0), “anteater” (1), “antelope” (2), “aardvark” (3), “bat” (4), and “zebra” (5), into an initially empty trie. Do the same for a ternary search trie.
Give the DFA array for the Knuth-Morris-Pratt substring match algorithm for the pattern “ABCABCAB”.
Give an NFA for recognizing the regular expression “a* | ( a* b a* b a* )*”.