$30.00
Description
You may solve the problems using your choice of software, state which software package/language(s) you used and provide the code or spreadsheet. There is no submission to TEACH this week.

Shortest Paths using LP: (7 points)
Shortest paths can be cast as an LP using distances dv from the source s to a particular vertex v as variables.

We can compute the shortest path from s to t in a weighted directed graph by solving.
max dt
subject to
ds = 0
dv – du ≤ w(u,v) for all (u,v) E

We can compute the singlesource by changing the objective function to
max ∑_{ ∈ }
Use linear programming to answer the questions below. State the objective function and constraints for each problem and include a copy of the LP code and output.

Find the distance of the shortest path from G to C in the graph below.

Find the distances of the shortest paths from G to all other vertices.

2
F
3
5
C
A
10
7
4
3
8
18
4
9
B
D
10
H
2
3
9 25
G E
7
1

Product Mix: (7 points)
Acme Industries produces four types of men’s ties using three types of
material. Your job is to determine how many of each type of tie to make each month. The goal is to maximize profit, profit per tie = selling price – labor cost – material cost. Labor cost is $0.75 per tie for all four types of ties. The material requirements and costs are given below.
Material 
Cost per yard 
Yards available 

per month 

Silk 
$20 
1,000 

Polyester 
$6 
2,000 

Cotton 
$9 
1,250 

Type of Tie 

Product Information 
Silk = s 
Poly = p 
Blend1 = b 
Blend2 = c 

Selling Price per tie 
$6.70 
$3.55 
$4.31 
$4.81 

Monthly Minimum units 
6,000 
10,000 
13,000 
6,000 

Monthly Maximum units 
7,000 
14,000 
16,000 
8,500 

Material 
Type of Tie 

Silk 
Polyester 
Blend 1 
Blend 2 

Information in 

yards 
(50/50) 
(30/70) 

Silk 
0.125 
0 
0 
0 

Polyester 
0 
0.08 
0.05 
0.03 

Cotton 
0 
0 
0.05 
0.07 
Formulate the problem as a linear program with an objective function and all constraints. Determine the optimal solution for the linear program using any software you want. Include a copy of the code and output. What are the optimal numbers of ties of each type to maximize profit?
2

Transshipment Model (10 points)
This is an extension of the transportation model. There are now intermediate transshipment points added between the sources (plants) and destinations (retailers). Items being shipped from a Plant (pi) must be shipped to a Warehouse (wj) before being shipped to the Retailer (rk). Each Plant will have an associated supply (si) and each Retailer will have a demand (dk). The number of plants is n, number of warehouses is q and the number of retailers is m. The edges (i,j) from plant (pi)to warehouse (wj) have costs associated denoted cp(i,j). The edges (j,k) from a warehouse (wj)to a retailer (rk) have costs associated denoted cw(j,k).
The graph below shows the transshipment map for a manufacturer of refrigerators. Refrigerators are produced at four plants and then shipped to a warehouse (weekly) before going to the retailer.

R1
R2
P1
W1
R3
P2
W2 _{R4}
P3
R5
W3
P4
R6
R7
Below are the costs of shipping from a plant to a warehouse and then a warehouse to a retailer. If it is impossible to ship between the two locations an X is placed in the table.
cost 
W1 
W2 
W3 
P1 
$10 
$15 
X 
P2 
$11 
$8 
X 
P3 
$13 
$8 
$9 
P4 
X 
$14 
$8 
3
cost 
R1 
R2 
R3 
R4 
R5 
R6 
R7 
W1 
$5 
$6 
$7 
$10 
X 
X 
X 
W2 
X 
X 
$12 
$8 
$10 
$14 
X 
W3 
X 
X 
X 
$14 
$12 
$12 
$6 
The tables below give the capacity of each plant (supply) and the demand for each retailer (per week).
P1 
P2 
P3 
P4 

Supply 
150 
450 
250 
150 

R1 
R2 
R3 
R4 
R5 
R6 
R7 

Demand 
100 
150 
100 
200 
200 
150 
100 
Part A: Determine the number of refrigerators to be shipped from the plants to the warehouses and then warehouses to retailers to minimize the cost. Formulate the problem as a linear program with an objective function and all constraints. Determine the optimal solution for the linear program using any software you want. What are the optimal shipping routes and minimum cost?
Part B: Due to old infrastructure Warehouse 2 is going to close eliminating all of the associated routes. What is the optimal solution for this modified model? Is it feasible to ship all the refrigerators to either warehouse 1 or 3 and then to the retailers without using warehouse 2? Why or why not?
Part C: Instead of closing Warehouse 2 management has decide to keep a portion of it open but limit shipments to 100 refrigerators per week. Is this feasible? If so what is the optimal solution when warehouse 2 is limited to 100 refrigerators?
Note: Include a copy of the code for all parts of the problem.
4

Making Change (6 points)
Given coins of denominations (value) 1 = v1 < v2< … < vn, we wish to make change for an amount A using as few coins as possible. Assume that vi’s and A are integers. Since v1= 1 there will always be a solution. Solve the coin change using integer programming. For each the following denomination sets and amounts formulate the problem as an integer program with an objective function and constraints, determine the optimal solution. What is the minimum number of coins used in each case and how many of each coin is used? Include a copy of your code.

V = [1, 5, 10, 25] and A = 202.

V = [1, 3, 7, 12, 27] and A = 293
5