首页 > > 详细

Math 160讲解、data辅导、MATLAB程序设计调试、辅导MATLAB语言 辅导Web开发|解析C/C++编程

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?

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!