HW 6 Solution

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.

1. (6 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 single-source 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.

    a) Find the distance of the shortest path from vertex 0 to vertex 7 in the graph below.

    b) Find the distances of the shortest paths from vertex 0 to all other vertices.






























1
CS 325 HW 6

2. (6 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
CS 325 HW 6

    3. (12 points) Veronica the owner of Very Veggie Vegeria is creating a new healthy salad that is low in calories but meets certain nutritional requirements. A salad is any combination of the following ingredients: Tomato, Lettuce, Spinach, Carrot, Smoked Tofu, Sunflower Seeds, Chickpeas, Oil

Each salad must contain:
At least 15 grams of protein

At least 2 and at most 8 grams of fat At least 4 grams of carbohydrates At most 200 milligrams of sodium At least 40% leafy greens by mass.

The nutritional contents of these ingredients (per 100 grams) and cost are


Ingredient
Energy
Protein
Fat
Carbohydrate
Sodium
Cost

(cal)
(grams)
(grams)
(grams)
(mg)
(100g)
Tomato
21
0.85
0.33
4.64
9.00
$1.00
Lettuce
16
1.62
0.20
2.37
28.00
$0.75
Spinach
40
2.86
0.39
3.63
65.00
$0.50
Carrot
41
0.93
0.24
9.58
69.00
$0.50
Sunflower Seeds
585
23.4
48.7
15.00
3.80
$0.45
Smoked Tofu
120
16.00
5.00
3.00
120.00
$2.15
Chickpeas
164
9.00
2.6
27.0
78.00
$0.95
Oil
884
0
100.00
0
0
$2.00


Part A: Determine the combination of ingredients that minimizes calories but meets all nutritional requirements.

    i. Formulate the problem as a linear program with an objective function and all constraints.

    ii. Determine the optimal solution for the linear program using any software you want. Include a copy of the code/file in the report.

    iii. What is the cost of the low calorie salad?

Part B: Veronica realizes that it is also important to minimize the cost associated with the new salad. Unfortunately some of the ingredients can be expensive. Determine the combination of ingredients that minimizes cost.

    i. Formulate the problem as a linear program with an objective function and all constraints.

    ii. Determine the optimal solution for the linear program using any software you want. Include a copy of the code/file in the report.

    iii. How many calories are in the low cost salad?



3
CS 325 HW 6

4. (6 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


P1  W1




P2


R2



R3
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


4
CS 325 HW 6



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





Determine the number of refrigerators to be shipped from the plants to the warehouses and then from the 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?

































5