MA 3231 Homework #4

MA 3231
Homework #4
1. In the following network of railroads, some railroads are one-way and some are two-way
railroads.
There are factories at vertex #2 and #3 which make cars. Each factory has 8 cars that need to
be shipped out. There is a ship with room for 6 cars waiting at the harbor at vertex #7, and a
bigger ship with room for 10 cars waiting at a different harbor at vertex #4.
The shipping cost (per car) and capacity of each railroad segment is given as “cost, capacity”.
Our goal is to transport all the cars to the waiting ships at the smallest possible cost.
a) formulate this problem as a linear program
b) Of course, you can only ship an integer-valued number of cars on each railroad. Is it true that
the linear programming problem in part (a) must have an integer-valued optimal solution? Or
do we need to add constraints that say that the variables must be integer-valued? Please
explain.
c) Find the optimal solution using MATLAB.
2. In the same network as problem #1, you just upgraded each of the two factories so that they
now each have 20 cars ready to ship out! However, the two boats still have room for the same
number of cars as before. Your goal is now to transport, at the minimum possible cost, just
some of the cars from the two factories in order to fill the two boats up so that they are
carrying as many cars as possible.
a) formulate this problem as a linear program
b) find the optimal solution on MATLAB
3. Consider one of the following networks of power lines, with un-directed edges (you can
choose whichever network you prefer—I added the smaller network to make it easier for you).
There is a power plant at the left-most vertex and a city at the right-most vertex.
a) Formulate a linear program which answers the following question: What is the minimum
number of power lines that one has to cut so that no electricity reaches the city? (note: your LP
does not need to tell you which power lines to cut, just how many) Please explain why your LP
gives the answer to this question.
b) Find the optimal solution to your Linear program in MATLAB
c) Since this is a relatively small network, you should be able to figure out how many power
lines need to be cut just by looking at the network. What is the minimum number of power
lines that need to be cut, and which ones would you cut? Does the minimum number of cuts
agree with your answer to part (b)?