5.6: Chapter 5 Exercises

P5.1 (8 pts)

Suppose I am managing a system of n cell phone sites. A site consists of ‘antennas and electronic communications equipment placed on a radio mast or tower to create a cell in a cellular network.’ I have records of the age of the electronic equipment (\(a_i\) where \(a\) is the current age of the site \(i\)) and a physical condition assessment rating (\(r_i\) where \(r\) is the condition rating index for a site \(i\) on a scale of 1 to 5 with 1 being excellent) of the physical systems each year. I also have a measure of the importance of each site, \(t_i\) where \(t\) is the amount of cellular traffic at a particular site \(i\). In each year, routine maintenance is performed at each site. I can also choose to rehabilitate the physical site (antenna towers, etc.) (which would move the site to condition 2, replace the electronic components (which would also move the site to condition 2), or do both physical rehabilitation and electronic component replacement (which would move the site to condition 1). Each of these actions has an associated cost, denoted \(c_{ij}\) where \(i\) indicates a particular site \(i\) and \(j\) is one of the management strategies.

Formulate a linear programming decision model that would select the best management action for each site in the coming year. ‘Formulate’ means to write out the problem equations. Define appropriate decision and other variables. Your objective is to minimize the sum over all sites of site condition multiplied by importance of each site. Your constraints are an allowable budget and a requirement that the electronics must be replaced if the age is greater than 6 years old.

P5.2 (4 pts)

Suppose you wish to minimize the cost of delivering ethanol from a set of production facilities with a maximum production supply \(S_i\) where \(i\) goes from 1 to \(n\), to a set of metropolitan petroleum mixing facilities (as ethanol is mixed with gasoline) with required amounts \(P_j\) where \(j\) goes from 1 to \(m\). Assume the cost of transportation from a production facility to a mixing facility is \(C_{ij}\).

a. Formulate a linear program problem to serve the required demand with the least cost.

b. What might cause your linear program to be infeasible for the solution?

P5.3 (8 pts)

Let us try an application of a roadway management system optimization model. Suppose I have a small roadway network with 10 links as shown below. In this example, we will just number links (rather than naming them by beginning and endpoints) and consider three action possibilities with forecast pavement conditions post-action as shown. Pavement condition varies from 1 to 7, with 7 excellent. This problem is sufficiently small that in can be solved with the add-in solver program in EXCEL.

Link	Length	Average Daily Traffic	PCI Do-Nothing	PCI with Main	Maintenance Cost	Rehabilitation Cost	PCI with Rehab.
1	5	10	4	5	5	16	7
2	4	13	3	4	4	15	7
3	3	12	3	4	3	10	7
4	6	11	2	3	6	20	7
5	7	25	5	6	7	22	7
6	5	50	4	5	5	20	7
7	4	40	3	4	4	15	7
8	3	20	3	4	3	10	7
97	8	15	2	3	8	28	7
10	2	10	1	2	2	6	7

a. Your objective function will have 30 terms, corresponding to the 10 links multiplied by three possible action decision variables: do-nothing, maintenance or rehabilitation. Each term is the product of length, average daily traffic, forecast pavement condition index (PCI) and a decision variable and divided by the sum of the product of length times average daily traffic. Write out your complete problem formulation, including definitions of variables, the various terms in your objective function, and your various constraints (including non-negativity and integral restrictions).

b. Find optimal solutions for budgets of 40 and 100. What do you conclude about the maintenance and rehabilitation strategies from your results?
c. Do either of your optimal solutions have a fractional decision variable value? What could you do about this in practice knowing that costs and pavement conditions are all uncertain?
d. Do you think this problem formulation and data are reasonable? Why or why not?

P5.4 (4 pts)

Let us couple a linear programming problem with a Markov deterioration model. Suppose you have components with three possible States: 1 – good, 2 – ok, 3 – poor. You have one possible action: moves to state 1 with probability 1 at cost ci for component i. State transition probabilities with no action are: p11 = .8, p12=.2, p22 = .8, p23 = .2, p33 = 1. others zero. You have a budget B for the year and current conditions are described by a vector \(si\). Formulate problem to minimize the average condition of all components at end of the year.

P5.5 (8 pts)

The facility manager of a plant is attempting to devise a shift pattern for his workforce. Each day of every working week is divided into three eight-hour shift periods (00:01-08:00, 08:01-16:00, 16:01-24:00) denoted by night, day and late respectively. The plant must be manned at all times and the minimum number of workers required for each of these shifts over any working week is as below:

• Mon Tues Wed Thur Fri Sat Sun
  • Night 5 3 2 4 3 2 2
  • Day 7 8 9 5 7 2 5
  • Late 9 10 10 7 11 2 2
• The union agreement governing acceptable shifts for workers is as follows:
  • Each worker is assigned to work either a night shift or a day shift or a late shift and once a worker has been assigned to a shift they must remain on the same shift every day that they work.
  • Each worker works four consecutive days during any seven day period.
  • In total there are currently 60 workers.
• Formulate an optimization problem to minimize the number of workers in the labor pool.