Reference no: EM131014069

Lesson 7: More Integer Linear Programming

Solve the following problems by first determining the model  (on paper; written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution.  Be sure to write/type a short summary explaining what your solution means.

1) The great treasures of King Tut are on display in the Giza Museum in Cairo.  The layout of the museum is shown in the figure below.  The figure shows different rooms joined by open doors.  A guard standing at a door can watch two adjoining rooms.  The museum's security policy requires guard presence in every room.  Formulate the problem as an ILP to determine the smallest number of guards.

2) UWP's School of Engineering is preparing a 5-year plan for building construction and expansion to accommodate new offices, laboratories, and classrooms.  The Electrical Engineering faculty has proposed project for all 3 available parcels of land:  a digital circuits lab on the northwest parcel at $48 million, a faculty office annex on the southeast parcel at $20.8 million, and a computer vision lab on the northeast parcel at $32 million.  The Mechanical Engineering faculty has 3 alternative proposals all for the same northwest parcel: a large lecture room building at $28 million, a heat transfer lab at $44 million, and a computer-aided design expansion at $17.2 million.  The Industrial Engineering faculty has only 2 proposals:  a manufacturing research center on the southeast parcel at $36.8 million, and a tunnel from their current building to the new center for an additional $1.2 million.  The Dean of Engineering scores the impact of these projects as 9, 2, and 10 for the EE proposals, 2, 5, and 8 for the ME alternatives, 10 and 1 for the IE ideas.  He wishes to allocate his available $100 million to maximize the total impact, selecting projects on an all-or-nothing basis with at one per land parcel.

a. Describe in written form the budget limits, mutual exclusiveness constraints, and project dependency requirements of this capital budgeting problem.

b. Formulate a capital budgeting integer linear program to select an optimal combination of proposals.

c. Use Excel's Solver to solve the ILP model from part (b).

3) Develop the B&B tree for each of the following problems by hand using the method described in the Brand and Bound section (pp. 336-341). You may verify your answer using the Solver, but credit will be given for the manual solution.

a. Maximize    z = 5x₁ + 4x₂
subject to

5x₁ + 3x₂ ≤ 28
4x₁ + 9x₂ ≤ 23
x₁, x₂ ≥ 0 and integer

b.    Minimize     z = 2x₁ + 3x₂
subject to

3x₁ + 2x₂ ≥ 13
2x₁ + 5x₂ ≥ 18
x₁, x₂ ≥ 0 and integer

Lesson 8: Non-Linear Programming

1. Using Calculus, find and classify all mins and maxs of the function f(x,y) = 6 + x³ - 3xy + y³ on the region given by -3 ≤ x ≤ 3 and -3 ≤ y ≤ 3. Remember to check the boundaries.
2. Using the Solver, find all of the mins and maxs of the function f(x,y) = 6 + x³ - 3xy + y³ on the region given by -3 ≤ x ≤ 3 and -3 ≤ y ≤ 3.
3. Using Calculus, find and classify all critical points of the function f(x,y) = x² - 4xy² + 2x²y + 4 on the region given by -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2. Remember to check the boundaries.
4. Using the Solver, find all of the mins and maxs of the function f(x,y) = x² - 4xy² + 2x²y + 4 on the region given by -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2.

Note:  For each of the minima and maxima points found, please list the ordered pair, the function value at that point, and whether that point is a locally or globally-optimal point.

Lesson 10: Gradient Method

1) Consider the unconstrained NLP max x₁x₂ - 5(x₁ - 2)⁴ - 3(x₂ - 5)⁴. Start at the point x₍₀₎ = (3,1) and compute 3 iterations of the gradient search to find points x₍₁₎, x₍₂₎, and x₍₃₎. Next, solve for the actual solution to this problem using Excel. Then make a plot of the 4 solutions (x₍₀₎ through x₍₃₎) and show how these points are making progress toward the solution you found using the Solver.

2) Repeat all of the steps of problem 1 using the new starting point of x₍₀₎ = (7,3).

a. Does the solution change or does the algorithm seem to find the same optimal point?

b. Does the solution arrive at/near the optimal point more quickly?

Lesson 11: Sensitivity Analysis

1) For this assignment you will be performing a parametric analysis using the spreadsheet Commentary11.xlsx.  First, try to replicate the parametric analysis shown in the Lesson 11 commentary.  Particularly, try changing the right-hand side value for the first constraint from 12 to the values shown in the commentary.  Are you able to find the same objective function values that are shown in the graph on the commentary?  You don't need to turn this in but this will check that you are on the right track.  If so, then continue by solving/completing the following instructions:

a. Modify the 2^nd constraint (page 36) so that the 40% value changes from 20% to 80% in 10% increments (i.e. 20%, 30%, 40%, ..., 80%).  Plot the objective function value against the percentage.  Note:  The 1^st constraint will go back to the original value of $12 when you modify the 2^nd constraint.

b. Modify the 3^rd constraint (page 36) so that the value of 50% changes again from 20% to 80% in 10% increments.  Again, plot the objective function value against the percentages.

c. Modify the 4^th constraint so that the bad debt value changes from 0% to 10%.  Plot the objective function value against the percentages.  Remember the 2^nd and 3^rd constraints are reset to their original values as you modify the 4^th constraint.

Note: There is a sensitivity analysis tool that is part of the Microsoft Excel Solver tool.  While you may look at this to see if you can figure out what it is telling you, you will not be using this tool as you prepare the answers for this assignment.  You will instead be running the Solver several times (once for each new value of the constraint) and then recording the results.

Lesson 12: Heuristic Programming

1. Consider the following function:

f(x) = 0.01127 x⁶ - 0.3585 x⁵ + 3.0244 x⁴ + 15.6906 x³ + 29.57625 x² - 19.1625 x

The function has multiple maxima and minima in the range x = 1, 2, 3, ..., 10.  Apply 6 TS iterations to estimate the maximum and minimum.  Use x₀=5, tabu tenure period of τ=2 iterations, and q = 3 (see example on page 358 for the meaning of q).

You will want to create a table in Excel tracking the values that you use and solve for during the calculations you perform in each iteration. 

For the random number generator, use the =rand() function in Excel.  This will create a random number between 0 and 1.  Multiply this number by the number of values in the neighborhood, and round up the result.  The result of this function will tell you which value in your neighborhood to choose.  For example, if you have 5 values in your neighborhood, you could use the following function:   =ROUNDUP(5*RAND(),0)  This function will provide random integers between 1 and 5.  Then click F9 on your keyboard each time you want a new random number.

Summarize what you learned about the minima, maxima, and the variable values that produce these function values.

2. Solve problem 1 again applying 6 TS iterations but this time using x_0=5, tabu tenure period of τ=3 iterations, and q = 3 .

3. Solve problem 1 again applying 6 TS iterations but this time using x_0=5, tabu tenure period of τ=2 iterations, and q = 2 .

4. Solve problem 1 again applying 6 TS iterations but this time using x_0=5, tabu tenure period of τ=3 iterations, and q = 2 .

5. In a few paragraphs, summarize what you've learned from problems 1,2,3, and 4 changing the tabu tenure period and the integer constant q that affects the size of the neigborhood.  How did your results change?  Which settings worked better for finding the maxima and minima?

Lesson 13: Genetic Algorithms

First, before you start this assignment, please note that the binary values for the feasible values are reversed from what you might normally see; that is, the binary digits have a reversed order (LSB comes first).  For example, the number sequence 0, 1, 2, 3, ... looks like this:  000, 100, 010, 110, ...  rather than 000, 001, 010, 011, ...  I have looked into why this is done this way, but I haven't found a good reason yet.  Anyways, please be sure to follow the convention used by the book.

1) Suppose that GA is used to find the maximum of F(x), x = 0, 1, ..., 255.  Let x = 200 and x = 134 represent parents P1 and P2.

a. Represent P1 and P2 as binary codes.

b. Use uniform crossover to create C1 and C2.

c. Create C1 and C2 using a 1-point crossover.

d. Create C1 and C2 using a 2-point crossover.

2) Analyze the genetic algorithm at the website https://gencar.co/ or https://boxcar2d.com/. Discuss how the algorithm's goals, how it works, and how this compares to the genetic algorithm taught in our textbook.  I expect to see a significant level of detail in your answer.

Lesson 14: Deterministic Dynamic Programming

1. Solve Example 12.1-1 on page 429 of your textbook but assume the following routes are used:

d(1, 2) = 7, d(1, 3) = 4, d(1, 4) = 12,

d(2, 5) = 13, d(2, 6) = 9,

d(3, 5) = 5, d(3, 6) = 3,

d(4, 5) = 11, d(4, 6) = 10,

d(5, 7) = 5,

d(6, 7) = 8,

Note: Your solution will be graded on how well you are able to show calculations similar to those on pages 430 and 431.  That is, clearly show what happens at each stage.

2. Complete problem 1 using the Backward Recursion method described in section 12.2 on page 433 of your textbook.

3. From what you learned completing problems 1 and 2, which method did you prefer doing by hand?  There is no right or wrong answer here but I would like to see a few well-written sentences describing your preference.

4. Based on what you read in the textbook, which method (Forward Recursion or Backward Recursion) is more commonly used and why?  Please note that there is a correct answer for this one and it should be supported from your reading assignment for this unit.

5. A student must select 12 elective courses from four different departments, with at least one course from each department.  The 12 courses are allocated to the four departments in a manner that maximizes 'knowledge'.  The student measures knowledge on a 100-point scale and comes up with the following chart (note: the more courses taken in a particular department, the greater the gain in knowledge, however notice that no improvement is gained by taking the 6^th course from Dept I since the knowledge is already at 100%, and therefore your model probably won't recommend taking the 6th course from this department.):

	Number of Courses
Dept	1	2	3	4	5	6	≥7
I	30	55	70	85	100	100	100
II	15	50	75	90	95	100	100
III	10	20	30	40	50	60	70
IV	30	40	50	75	90	100	100

How should the student select the courses?

Note:  For problems 5 and 6, you should write the model that you will be solving in a Word document (or pdf file).  Then solve this problem using Excel.  You should use the regular Solver tool rather than the Excel Knapsack Tool available from the textbook's author.  I would like you get experience solving these problems manually with tools that you will have available every day, such as MS Excel.

6. A gardener wishes to plant a new garden measuring 10 x 30 feet.  The gardener wishes to plant four types of vegetables: tomatoes, green beans, Brussel sprouts, and corn.  The garden is organized in 10-foot rows.  The corn and bean rows are 1 foot wide, the tomato rows are 2 feet wide, the Brussel sprout rows are 3 feet wide.  The gardener wishes to plant at least one row of each vegetable, however it should be noted that the gardener likes the tomatoes the best and the corn the least.  In fact, using a 1 to 10 scale she can assign a score of 10 for tomatoes, 8 for Brussel sprouts, 5 for green beans, and 3 for corn.  She would like to maximize the 'score' for her garden while also limiting the garden to having not more than half tomatoes, and no more than 2 rows of Brussel sprouts.  Note:  you are allocate the space in the garden looking at the 30 foot long side of the garden and deciding how many rows (each 10 feet long) on the 30 foot long side of the garden.

7. As a group, come up with an engineering problem that would use the DP methods learned in this lesson and write a new problem similar to problems 5 and 6.  Note, you do not need to solve this problem.

Lesson 16: Blending and Refining Models

Solve the following problems by first determining the model (on paper; written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution.  Be sure to write/type a short summary explaining what your solution means.

1) An electrical components shop packages resistors, capacitors, transistors, and diodes.  Resistors come in 100-lb boxes and cost $200 each, capacitors come in 50-lb boxes and cost $75 each, transistors come in 30-lb boxes and cost $120 each, and diodes come in 70-lb boxes and cost $210 each.  The handy-man package weighs at least 1-lb and must include by weight at least 30% resistors and 20% capacitors but at most 5% transistors and 10% diodes.  To balance the package, the number of capacitors cannot exceed the number of resistors.  Resistors and capacitors have equal weight and each weighs 3 times as much a transistor and 2 times as much as a diode.  Develop an LP model to determine the optimal mix of this package, and find the solution using Excel's Solver tool.

2) Friendly Fuel Company makes three fuel blends, A, B, and C, for its customers.  These blends are created using four ingredients: Q, R, S, and T.  The daily availabilities of the ingredients are 500 barrels, 300 barrels, 100 barrels, and 100 barrels, respectively.  The corresponding costs per barrel are $50, $70, $100, and $200.  Fuel blend A is a 50:8:3 mix of ingredients Q, R, and T.  Fuel blend B is a 60:2:6 mix of ingredients Q, S, and T.  Fuel blend C is a 40:2:3:2 mix of ingredients Q, R, S, and T.  The blends are produced by the barrel and Friendly Fuel sells blends A, B, and C for $200, $250, and $300 per barrel.  The minimum daily demand for blends A, B, and C is 100, 120, and 100 barrels, respectively.  Develop an LP model to determine the optimal production mix of the fuels and the associated amounts of the ingredients.  Find the solution using Excel's Solver tool.

3) Barbados Sugar Company produces brown sugar, processed (white) sugar, powdered sugar, and molasses from sugar cane syrup.  The company purchases 4800 tons of syrup weekly and is contracted to deliver at least 30 tons weekly of each type of sugar.  The production process starts by manufacturing brown sugar and molasses from the syrup.  A ton of syrup can be converted into either 0.35 ton of brown sugar or 0.15 ton of molasses.  White sugar is produced by processing brown sugar.  It takes 1 ton of brown sugar to produce 0.7 tons of white sugar.   Powdered sugar is produced from white sugar through a special grinding process that has a 90% conversion efficiency (1 ton of white sugar produces 0.90 ton of powdered sugar).  The profits per ton for brown sugar, white sugar, powdered sugar, and molasses are $120, $180, $235, and $50, respectively.  Formulate the problem as a linear program (LP) and determine the weekly production schedule using Excel's Solver tool.

Lesson 17: Transportation Models

Solve the following problems by first determining the model (on paper; written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution.  Be sure to write/type a short summary explaining what your solution means.

1) In transportation models, you learned that it was important that the model be balanced.  That is, the total demand equals the total supply.  This may not be realistic to everyday problems since we often have backlogged orders or storage of extra product; however we need to include this in our model using dummy sources and dummy nodes.  For each of these problems, identify whether a dummy source or dummy node is needed in the model.  Support your answers with calculations:

a. Supply:      

Demand:    

b. Supply:      

Demand:    

c. Supply:      

Demand:    

d. Supply:      

Demand:    

Note: for part d, you will notice that one supply value is left as a variable.  Write the conditions leading to us needing a dummy source or a dummy node (or neither).

2) Cars are shipped from three distribution centers to five dealers.  The shipping cost is based on the mileage between the sources and the destinations and is independent of whether the truck makes the trip with partial or full loads.  The following table summarizes the mileage between the distribution centers and the dealers together with the monthly supply and demand figures given in number of cars.  A full truckload includes 16 cars.  The transportation cost per truck mile is $20.

Mileage Chart and Supply and Demand for Problem 2
		Dealer
		1	2	3	4	5	Supply
	1	120	150	170	150	80	150
Center	2	80	100	100	200	160	250
	3	30	10	80	250	300	375
Demand		125	200	50	175	225

3) The demand for a special small engine over the next five quarters is 300, 250, 200, 250, and 400 units, respectively.  The manufacturer supplying the engine has different production capacities estimated at 280, 310, 400, 200, and 300 for the five quarters.  Back-ordering is not allowed, but the manufacturer may use overtime to fill the immediate demand, if necessary.  The overtime capacity for each period is half the regular capacity.  The production costs per unit for the five periods are $100, $96, $116, $102, and $106, respectively.  The overtime production cost per engine is 50% higher than the regular production cost.  If an engine is produce now for use in a later period, an additional storage cost of $4 per engine per period is incurred.  Formulate the problem as a transportation model.  Determine the optimum number of engines to be produced during regular time and overtime of each period.

The demand for a special small engine over the next five quarters is 300, 250, 200, 250, and 400 units, respectively.  The manufacturer supplying the engine has different production capacities estimated at 280, 310, 400, 200, and 300 for the five quarters.  Back-ordering is not allowed, but the manufacturer may use overtime to fill the immediate demand, if necessary.  The overtime capacity for each period is half the regular capacity.  The production costs per unit for the five periods are $100, $96, $116, $102, and $106, respectively.  The overtime production cost per engine is 50% higher than the regular production cost.  If an engine is produce now for use in a later period, an additional storage cost of $4 per engine per period is incurred.  Formulate the problem as a transportation model.  Determine the optimum number of engines to be produced during regular time and overtime of each period.

Lesson 18: Assignment Models

1) Solve the following assignment models to determine the minimum production costs.  Each table shows 5 production plants and the cost (in millions of dollars) to build 5 different engines. Each plant can only build one engine.  Use the Hungarian method to solve these two assignment methods.  Show all steps, explain what you did at each step, and clearly state the final solution.

	Engine							Engine
	1	2	3	4	5			1	2	3	4	5
Plant 1	4	7	3	2	7		Plant 1	6	6	4	2	7
Plant 2	5	3	5	2	8		Plant 2	9	5	2	6	6
Plant 3	8	7	5	2	6		Plant 3	3	4	7	10	3
Plant 4	4	7	5	2	6		Plant 4	2	9	5	2	1
Plant 5	8	10	7	6	3		Plant 5	9	1	2	4	6

                 Table 1    - Scenario 1                                                 Table 2 - Scenario 2

2) Solve the two assignment models from problem 1 by first writing the model on paper (written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution.  Be sure to write/type a short summary explaining what your solution means.

3) Did you find the same solutions using the two methods?  Why or why not?

4) Solve problem 6 on page 205 of your textbook, however rather than using the data in Table 5.41 on page 206, solve the problem using the data on the following table.  First write the model on paper (written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution.  Be sure to write/type a short summary explaining what your solution means.

		New Center
		I	II	III	IV
Existing Center	1	0	6	9	13
	2	6	5	4	6
	3	3	0	6	7
	4	10	8	12	1

Lesson 19: Network Models

1) Draw the network defined by:

N = {1, 2, 3, 4, 5, 6, 7}

A = {(1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7)}

2) In Example 6.1-1 on page 211 of your textbook, you learned that a round-trip is not possible given the current number of bridges.  Specify the smallest number and location of additional bridges needed to construct a round-trip. Draw a diagram/picture of the new town, its bridges (including the new ones, clearly labeled), and the complete round-trip.

3) Solve Example 6.2-1 on page 213 of your textbook, however start at node 3 instead of node 1, and show that the algorithm produces the same solution.  Be sure to clearly show your solution using diagrams of each iteration as the author did on page 214.

4) In intermodal transportation, loaded truck trailers are shipped between railroad terminals on special flatbed carts.  The figure below shows the location of the main railroad terminals in the United States and the existing railroad tracks.  The objective is to decide which tracks should be 'revitalized' to handle the intermodal traffic.  In particular, the Los Angeles (LA) terminal must be linked directly to Washington DC (DC) to accommodate expected heavy traffic.  Other than that, all remaining terminals can be linked, directly or indirectly, such that the total length (in miles) of selected tracks is minimized.  Determine the segments of the railroad tracks that must be included in the revitalization program.

Solve this problem manually (without the help of the Solver) and show the iterations similar to how Example 6.2-1 was solved in the textbook.

5) The figure (see below) shows the ACME Communication Network between two stations, 1 and 9.  The probability that a link in the network will operate without failure is shown on each arc.  Messages are sent from station 1 to station 9, and the objective is to determine the route that maximizes the probability of a successful transmission.  Formulate the situation as a shortest-route model, and determine the optimum solution.  Solve this problem manually but you may also include a Solver solution verifying your solution.

6) Describe why it was beneficial to use logarithms for problem 5 when you were solving for the optimum solution.  Be sure to clear mathematical language (such as naming certain properties/rules that are used) and show mathematical examples if necessary.

7) Your company performs maintenance and makes upgrades to communication lines.  Through a new technology, you can make a communication line 99.999% efficient.  To make things easier, let's assume that this is 100% efficient and there is no chance of a communication failure.  ACME Communication company hires you to upgrade one of its lines increasing the chance of a successful communication to 100% or 1.0.  Which line would you upgrade and why?  How much of an improvement would this give ACME Communications?  That is, compare your answer from problem 7 to that from problem 5.  Solve this problem manually but you may also include a Solver solution verifying your solution.

8) The following table lists activities required of a political advance team in arranging a campaign rally (simplified, of course). 

k	Activity	Duration (days)	Predecessor Activities
1	Contact local party	2	---
2	Find location	1 ½	1
3	Arrange date and time	1	1,2
4	Notify news media	1	3
5	Arrange sound system	3	3
6	Coordinate police security	1	3
7	Install speaking platform	1 ½	3,5
8	Decorate platform and site	1	7

a) Construct the corresponding CPM project network.

b) Determine the critical path.

c) What is the minimum project duration?

d) What is the latest start time that the news media must be notified?

e) There was a delay in coordinating the police security.  This activity will require 2 days instead of 1.  Suppose that you are preparing for a conference call with the national party executives.  Clearly explain how this could affect the planning of the rally.

Lesson 20: Traveling Salesperson Problems

1) FedEx and UPS have several round-trip delivery routes each day.  How might FedEx and  UPS use the Traveling Salesperson Model to help minimize costs?  Describe the data elements (cities and distances) needed to model this problem as a TSP.  The answer to this problem should be written in a way that clearly explains this method to an executive at your company while also using the terminology/language from this section of the textbook.

2) Consider problem 3 on page 403.

a. Find a lower bound.  Show your work/calculations or describe the steps you've used.

b. Use the Solver to find the actual solution.

c. Compare these two values.

3) Consider problem 3 on page 403.

a. Find a lower bound.  Show your work/calculations or describe the steps you've used.

b. Use the Solver to find the actual solution.

c. Compare these two values.

Lesson 22: Life Cycle Stages and the LCA Framework

For a product of your choice, determine a suitable scope. Also, identify the functional unit. Pick a product of interest to you, as the group project for this unit is to perform a complete LCA on a product.

Questions you may have:

Q:  How does this differ from the Unit 4 Group Project?  A:  The Lesson 22 Assignment is a chance to practice creating LCA scopes.  You can test whether you have a good idea and whether your functional unit is correct for the comparison of products.  If you find that you have a good idea for your Lesson 22 assignment, you may want to discuss this with your Unit 4 Project Group as a potential for your group project.  But again, the group project and lesson 22 assignments are different.

Q:  Do I pick one product or two?  A:  When I say "for a product of your choice", I'm referring to a general product, such as silverware or coins.  Then you would choose types of that product to compare for your LCA, such as plastic and stainless steel silverware or copper vs. zinc coins.

Q:  How do I complete this assignment as a group?  Isn't this an individual assignment?  A:  Each student will choose their own LCA idea.  Usually the results are about 3 to 5 paragraphs per individual (no more than 1 page per person).  The group would then submit all individual results in one file that will be submitted into the Lesson 22 Assignment Dropbox.  The group should review all of the individual submissions and offer suggestions to each other to ensure that everybody is on the right track for this assignment.   If there is significant disagreement or if there are questions, the group may contact the professor for support.  Again, this assignment is not the same as the Unit 4 group project.  The goal of this assignment is to get you to start brainstorming about possible projects to use for the Unit 4 group project.