April 13, 2005
[Exams] Final Exam Format
Its a two part exam. The first part has 15 fill-in-the-bubble questions. The second part has 5 short essay answer type questions. There are no point values listed on the exam. The first 15 questions are worth 2 points each. The second set of 5 questions are worth 12 points each. So that's 30 points on the fill-in-the-bubble and 60 points on the essay type questions.
If I were studying for the exam, I would be sure I knew...
- How to solve recurrence relations
- How to do linear programming and what slack form looks like
- How to design algorithms and what the tradeoffs are between the different classes of algorithms we studied.
- How the graph-based algorithms we studied work.
- The stuff on the study lists for the other exams.
Posted by jones at 02:51 PM | Comments (0)
[Exams] Important typo on the final exam
On the final exam, the question that asks you to put a linear programming problem into "basic form" should read "slack form" (Its problem 18)
Posted by jones at 02:47 PM | Comments (0)
April 04, 2005
[Projects] Linear programming problem (due 4/13)
Here is the problem to solve with your linear programming project. The project is due the last day of classes. There will be no late days. The project is to turn this problem into a linear programming problem and then solve it with your simplex solver. You are free to use any input format you like and you are free to just hard-code the input right into your program if you like. This is the only problem your program will be tested on (but we will look at your source code to make sure your program isn't just "wait 2 seconds then return the solution").You are the operations director for a processing plant at a large mine. Your job is to devise a program, or plan, for the plant that maximizes profits while staying within the resource budget. The plant produces four major resources: copper, gold, silver and platinum.
In a given week, the mine produces 2,000 tons of ore that must be processed into some combination of the four major resources. A ton of ore contains 10 ounces of copper, 2 ounces of gold, 3 ounces of silver and 1 ounce of platinum. You many only extract one resource from each unit of ore processed.
Processing the ore requires power, water, labor and use of one of the three processing lines. Producing each of the resources requires different amounts of processing resources. One ounce of copper requires 30 kW hours, 1,000 gallons of water, 50 hours of labor and 4 hours of processing time on a processing line. One ounce of gold requires 15 kW hours, 6,000 gallons of water, 20 hours of labor and 6 hours of processing time on a processing line. One ounce of silver requires 19 kW hours, 4,100 gallons of water, 21 hours of labor and 19 hours of processing time on a processing line. One ounce of platinum requires 12 kW hours, 9,100 gallons of water, 10 hours of labor and 30 hours of processing time on a processing line.
There is only a limited amount of power, water, labor and processsing line time available. In a given week, you may use 1,000 kW hours of power, 1,000,000 gallons of water, 640 hours of laber and you can run the processing lines 24 hours a day for 7 days a week for a total of 504 hours.
Finally, each ounce of finished resource has an associated profit. An ounce of copper is worth $10.20, an ounce of gold is worth $422.30 dollars, an ounce of silver is worth $6.91 and an ounce of platinum is worth $853.00.
Posted by jones at 10:29 AM | Comments (2)
[Projects] TSP is due today, Monday 4/4
Just a reminder that the due date for the TSP project was moved to today. Be sure to turn something in (not neccesarily today) even if it is incomplete.
Posted by jones at 08:41 AM | Comments (0)
[Lectures] Notes on linear programming (updated 4/4)
The notes were updated to include implementation notes on page 10 on 4/4.
We have developed a set of notes on linear programming. The notes are complete, although I wouldn't be surprised if they were expanded as we cover them in class. The latest version will always be available here.
We will cover this material in class a little on Wednesday, all day Friday and Monday. The last project is to code up simplex and solve a little optimization problem.
Posted by jones at 05:23 AM | Comments (0)
April 01, 2005
[Lectures] More resources for learning linear programming
[a LP flash tutorial, notes on linear programming] The flash tutorial is quite nice, copmlete and slow. The notes are from Sean Warnick. They are also quite good.
Posted by jones at 03:22 PM | Comments (0)