Buy Linear Programming Assignment
In each of the following instances, describe the data elements (cities and distances) needed to model the problem as a TSP.
(a) Seers Service Center schedules its daily repair visits to customers. The jobs are categorized and grouped and each group assigned to a repairperson. At the end of the assignment, the repairperson reports back to the service center.
(b) A baseball fan wishes to visit eight major league parks in (1) Seattle, (2) San Francisco, (3) Los Angeles, (4) Phoenix, (5) Denver, (6) Dallas, (7) Chicago, and (8) Tampa before returning home in Seattle. Each visit lasts about one week. The goal is to spend the least money on airfare.
(c) A tourist in New York City wants to visit 8 tourist sites using local transportation. The tour starts and ends at a centrally located hotel. The tourist wants to spend the least money on transportation.
(d) A manager has m employees working on n projects. An employee may work on more than one project, which results in overlap of the assignments. Currently, the manager * Problems 459 meets with each employee individually once a week. To reduce the total meeting time for all employees, the manager wants to hold group meetings involving shared projects. The objective is to reduce the traffic (number of employees) in and out of the meeting room.
(e) Meals-on-Wheels is a charity service that prepares meals in its central kitchen for delivery to people who qualify for the service. Ideally, all meals should be delivered within 20 minutes from the time they leave the kitchen. This means that the return time from the last location to the kitchen is not a factor in determining the sequence of deliveries.
(f) DNA sequencing. In genetic engineering, a collection of DNA strings, each of a specified length, is concatenated to form one universal string. The genes of individual DNA strings may overlap. The amount of overlaps between two successive strings is measurable in length units. The length of the universal string is the sum of the lengths of the individual strings less the overlaps. The goal is to concatenate the individual strings in a manner that minimizes the length of the universal string
11-3 Propose a tour using the Excel TSP Tool provided. Provide a business justification for the route/routes selected.
Seers Service Center schedules its daily repair visits to customers. The matrix ‘Tij ‘ below gives the travel time (in minutes) between the service center (row 1 and column 1) and seven jobs. The jobs are assigned to one of the repairpersons during an 8-hr shift. At the end of the day, the repairperson returns to the service center to complete paperwork
(a) Compare the lower bounds on the optimum tour length using both the assignment model and linear programming. Is the assignment model solution optimum for the TSP?
(b) Given that journeying between jobs is nonproductive and assuming a 1-hr lunch break, determine the maximum productivity of the repairperson during the day
®
‘Tij ‘ = (0 20 15 19 24 14 21 11
20 0 18 22 23 22 9 10
15 18 0 11 21 14 32 12
19 22 11 0 20 27 18 15
24 23 21 20 0 14 25 20
14 22 14 27 14 0 26 17
21 9 32 18 25 26 0 20
11 10 12 15 20 17 20 0 )
11-2.1 Attempt to improve the AMPL Code provided to provide a closed tour. In addition to submitting the final code you came to provide discussion about concerns and approaches used.
A book salesperson who lives in Basin must call once a month on four customers located in Wald, Bon, Mena, and Kiln before returning home to Basin. The following table gives the distances in miles among the different cities.
Miles between cities
Basin Wald Bon Mena Kiln
Basin 0 125 225 155 215
Wald 125 0 85 115 135
Bon 225 85 0 165 190
Mena 155 115 165 0 195
Kiln 215 135 190 195 0
The objective is to minimize the total distance traveled by the salesperson.
(a) Write down the LP for computing a lower-bound estimate on the optimum tour length.
9-41 Solve using Excel or AMPL
Jobco Shop has 10 outstanding jobs to be processed on a single machine. The following table provides processing times and due dates. All times are in days, and due time is measured from time 0:
Job Processing time (day) Due time (day)
1 10 20
2 3 98
3 13 100
4 15 34
5 9 50
6 22 44
7 17 32
8 30 60
9 12 80
10 16 150
If job 4 precedes job 3, then job 9 must precede job 7. The objective is to process all 10 jobs in the shortest possible time. Formulate the model as an ILP, and determine the optimum solution by modifying the AMPL file amplEx9.1-4.txt.
