Homework: #6 Solution

Problem 1: (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 weight 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 ∑𝑣∈𝑉 𝑑v

 

 

Use linear programming to answer the questions below. Submit a copy of the LP ode and output.

 

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

 

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

 

Problem 2: (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

 

 

 

Product  Information          Type of Tie

                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 Information in yards          Type of Tie

                Silk         Polyester                Blend 1

(50/50)   Blend 2

(30/70)

Silk         0.125      0              0              0

Polyester                0              0.08        0.05        0.03

Cotton   0              0              0.05        0.07

 



type     selling price     labor    material           profit per tie

silk s    6.7       0.75     2.5       3.45

poly p  3.55     0.75     0.48     2.32

blendl b           4.31     0.75     0.75     2.81

blend2 c          4.81     0.75     0.81     3.25

 

 

 

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 numbers of ties of each type to maximize profit? Include a copy of the code and output.

 

 

Problem 3: (7 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.

 

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.

 

 

The tables below give the capacity of each plant (supply) and demand for each retailer (per week).

 

Your goal is to determine the number of refrigerators to be shipped plants to 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. Include a copy of the code and output.

 

Problem 4: (9 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

 

 

Part A: Determine the combination of ingredients that minimizes calories but meets all nutritional requirements. 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 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. 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. How many calories are in the low cost salad? Include a copy of the code/ file with the HW.