Math 160代做、data代写、MATLAB程序设计调试、代写MATLAB语言

日期：2020-05-27 11:02

Math 160 (Spring Quarter 2020) Homework Project 4 (Combinatorial Optimization Models)

Due date: 06/04/2020, 11:59pm

INSTRUCTIONS

? All homework projects need to be done individually. No teams can be formed.

? All homework projects will have many problems, both theoretical and practical.

? Submit your homework project to Canvas as one single pdf file. In this project, you don’t

need to submit your codes.

? Note that since MAT-167 is a prerequisite, concepts/terminology/results related to MAT-167

are presumed.

? Knowledge on using MATLAB is presumed.

? Write legibly preferably using word processing if your hand-writing is unclear.

? Be organized and use the notation appropriately. Show your work on every problem. Correct

answers without support work will not receive full credit.

1. Math models for UC Davis Advising: The optimal order of enrolling in courses!

A directed graph G = (V, A) can be used to represent the order of actions to be take in any

project (task a needs to be done before b, if there is an arc from a to b). A topological ordering

of the vertices is an assignment of the value yi to each vertex such that for every arc ij then

yi ≥ yj + 1. The assignment says the best order to do a project.

(a) Show that a directed graph has a topological ordering, then there is no directed cycle.

Write a simple discrete model to detect whether a directed graph has a cycle.

(b) A UC Davis student in major X (say applied math major, economic major, etc.) has

to take certain required courses that have pre-requisites. Create a directed graph whose

nodes are all possible Math courses in each of the majors and there is an arc from course

a to course b if course a is a pre-requisite to b, thus a has to be taken before b! How big is

this graph? Let us call this the Math-major-course graph, MMC Make some comments

about the structure of the MMC graph (number of nodes? number of arcs?). How does

the graph differs from a stats major’s graph?

(c) Write a math model that, given one of the 3 majors of the UC Davis mathematics

department, tells the students at least one good order, one that does not skip prerequisites,

in which to take their math courses and graduate in minimum amount of

time. Assume that there is a limit of two math courses to take each quarter. Can you

find at least two good orders in each of the majors?

2. Finding the best path: Here are some some challenges about optimal paths:

(a) Let G be a directed graph with distances or costs on its arcs and two special vertices

s, t. We are interested on the “longest” paths using two possible definitions: (a) If we

call the length of a path the sum of the lengths on the path. Write a model to compute

the longest path on a network. (b) If we instead call the length of a path the largest

length among all the arcs in the path, write another model to compute the longest path

on a network under this definition.

(b) Let G be a graph with two distinguished vertices s, t. An even st-path is a path from

s to t with an even number of edges. Describe a computer algorithm to find a shortest

even st-path (one with as few edges as possible).

HINT: Not easy to use the st-path formulation in class. Instead you can reformulate

as a minimum cost perfect matching problem! Construct an auxiliary graph H from G,

make a copy of the graph G, and remove vertices s, t. Call that new graph G0

. Construct

H starting with the union of G, G0 and joining every vertex v ∈ G different from s, t

with its copy in G0

. Use H.

(c) Consider again, the TSP for n cities and cost of travel cij .

(a) Write a new model for the TSP, different from the ones we saw in class. This time

use the binary variables xi,j,k, where it equals 1 if the k-th leg of the trip, the salesman

goes from city i to city j. Your formulation must have a cubic number of constraints.

What are they?

(b) Given a graph G = (V, E) representing say the cities of California connected by

highways, we wish to find out whether there is a tour of the vertices of G (a cycle

visiting each vertex exactly once) which only uses the existing edges in E. Suppose you

have a powerful software that solves the Traveling salesman problem. How would you

use that algorithm for the TSP to answer that question? What costs should you pick

on arcs?