代写AMPL code、data留学生代写、代做c/c++，Python，Java编程语言

日期：2020-03-23 10:15

First Homework Set

Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.

Solutions are due by midnight of Sunday, March 22, 2020 (SHARP!)

Feel free to use an AMPL code when it is helpful!

Problem 1: Let a ∈ R

n

+ and b ∈ R+ be given parameters. Let us call a subset

S ? E = {1, 2, ..., n} independent if a(S) = P

j∈S

aj ≤ b.

? Show that this defines an independence system F ? 2

E.

? Consider n = 6, a = (1, 1, 1, 4, 4, 5), b = 8, E = {1, 2, 3, 4, 5, 6}, and

S = {1, 2, 3, 4, 5}. What are the values of r(S) and ρ(S)? How much is

q(E, F) for this example?

? For an arbitrary n find a ∈ Rn+ and b ∈ R+ such that q(E, F) ≤1n?1.

Problem 2: Consider the problem of processing a set E of n jobs on a single

machine. Each job j ∈ E needs one unit of (uninterrupted) time for processing,

has a due date dj , and brings a profit of pj , if it is finished before its due date.

Let us call a subset S ? E of the jobs independent, if all the jobs in S can be

processed, in some order, such that all of them are finished on time (before their

respective due dates). Let F be the collection of all independent job subsets.

? Consider n = 7, and the following list of (dj , pj ) pairs: (3, 2), (2, 3), (4, 4),(1, 3), (4, 3), (4, 6), (6, 7). What is the ”Best-in-Greedy” solution?

? Prove that (E, F) is a matroid.

Problem 3: Let G be a graph on 5 vertices, V (G) = {1, 2, 3, 4, 5}, defined by

the set of edges E(G) = {(1, 2),(2, 3),(2, 5),(3, 4),(4, 5),(5, 1)}. Let F ? 2V (G)

be the family of independent (stable) sets of G, that is vertex subsets that do

not contain an edge inside.

? Is (V (G), F) a matroid? Why?

? Recall that the associated independence polytope is defined as

Write down the defining inequalities for PV (G),F in this case, and eliminate

the redundant ones.

? How much is the maximum of 5x2 + 3x5 over PV (G),F ?

Problem 4: Consider the graph G on n = 7 vertices V = {1, 2, 3, 4, 5, 6, 7} with

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

and with edge weights (in the previous order of edges) w1,2 = 9, w1,4 = 7,

w2,3 = 9, w2,5 = 10, w2,7 = 7, w3,4 = 8, w3,5 = 9, w4,5 = 9, w4,6 = 8, w4,7 = 8,

w5,6 = 7, w6,7 = 7.

1

? What is the weight of the maximum-weight spanning tree?

? Compute the sequence of edges chosen by Kruskal’s algorithm.

Problem 5: Let us consider a bipartite graph G = (A ∪ B, E) where set A

has 15 vertices of degree 3, 18 vertices of degree 5, and 12 vertices of degree 15

(that is |A| = 45 = 15 + 18 + 12.) Every vertex in set B is connected to exactly

1 vertex of degree 3, 2 vertices of degree 5, and 4 vertices of degree 15.

? How large is B?

? How large is a maximum cardinality matching in this graph? Why?

Problem 6: Consider the following cutting stock problem, with input length

L = 21. These 21-foot pieces are to be cut into smaller ones to fulfill the

following orders:

What is the optimal solution?

Problem 7: A company has 100M to invest in several possible projects. They

can either fund a project fully, or do not fund it at all. For each of the 12

possible projects we list in the table below the cost of the project and the net

profit the project is expected to generate (in millions of dollars.) Which projects

to fund so that the company maximizes its net profit?

P rojects

A B C D E F G H I J K L

P rof it 30 25 5 9 11 7 14 19 40 29 30 34

Cost 16 15 2 4 4 3 9 12 29 20 18 25

Solve the problem by the dynamic programming algorithm or by using an AMPL

model. Submit the optimal solution, and the corresponding AMPL .mod and

.dat files, if you worked with AMPL.

Problem 8: Consider a graph G = (V, E) (not necessarily bipartite), nonnegative

weights c : E → R+ on the edges, and the problem of finding a maximum

weight matching. How good (bad) is the greedy algorithm on this problem type?

Figure 1:

[Hint: What is the corresponding independence system F? How small q(E, F)

can be?]

Problem 9: Consider the instance of the Chinese Postman problem shown in

Figure 1. The edge traversing times are shown along the edges in minutes.

? Assume that the post office is in vertex 1. What is the optimal, time

minimizing tour of the postman? How much time does he need to deliver

all letters and get back to the post office?

? Assume that he starts at the post office and wants to finish in his house

in vertex 8. How much time does he need then to deliver all letters and

arrive home? What is his optimal tour in this case?

Problem 10: You are the manager of a consulting firm that has 5 co-workers

(A, B, C, D, and E) and 5 projects (P1, P2, P3, P4, and P5) to complete.

3

The table below shows the expected profit if a worker is assigned to a project.

For instance, if worker A is assigned to project P2, then the company earns $7K

as profit. What is the optimal, profit maximizing assignment of workers to

projects? Use the Hungarian algorithm to solve this, and document each step

of it.

4