Problem 1: You are a local electricity provider company contracted to supply electric energy for your county. You have a forecast of 1230, 1190, 845, 935, 915, 1625, 1510 MWhr daily demands for the next week. You have your own power plants where you can generate energy in multiples of 50 MWhr up to 500 MWhr daily at a cost of $ 20/MWhr. You could also use rented power plants to produce electricity in multiples of 100 MWhr up to 600 MWhr daily, at a cost of $ 25/MWhr. You could also purchase electricity form the neighboring county for $ 45/MWhr, up to 500 MWhr daily. You can also store electricity in a new battery storage. It stores electricity at $ 2/MWhr/day. What is your optimal, cost minimizing production plan for the next week?
Model this problem as a transhipment problem, and solve it. You may build an ampl model and use the solver package.
Problem 2: Consider the following cutting stock problem, with input length L = 24. These 24-foot pieces are to be cut into smaller ones to fulfill the following orders:
|
length
(in feet)
|
ordered
#
|
|
3
|
12300
|
|
5
|
9800
|
|
12
|
3600
|
|
7
|
5750
|
|
8
|
15250
|
|
9
|
6700
|
Use the AMPL model to solve this problem. What is the optimal solution?
Problem 3: Let a ∈ Rn and b ∈ R+ be given parameters. Let us call a subset S ⊆ E = {1, 2, . . . , n} independent if a(S) = Σj∈S aj ≤ b.
- Show that this defines an independence system F ⊆ 2E.
- Consider n = 6, a = (1, 1, 1, 4, 4, 5), b = 8, and X = {1, 2, 3, 4, 5, 6}: What are the values of r(X) and ρ(X)?
- In the general case, how difficult is to compute r(X) for X ⊆ E?
- In the general case, how difficult is to compute ρ(X) for X ⊆ E?
- How bad "Best-In Greedy" can be on problems of this type? Construct an extremal example.
Problem 4: Let G = C5 be a chordless 5-gon, i.e., V(G) = {1, 2, 3, 4, 5} and E(G) = {(1, 2), (2, 3), (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?
Remember that the associated independence polytope is defined as
Write down the defining inequalities for PV(G),F. Eliminate the redundant ones.
Is the polytope PV(G),F integral?
Problem 5: Let us consider a bipartite graph G = (A ∪ B, E) where A has 15 vertices of degree 3, 18 vertices of degree 5, and 12 vertices of degree 15 (that is |A| = 45.) Every vertex in 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?