Problem 1

Which point maximizes the objective function:

max x + 5y

subject to the constraints

x + 2y = 0

options:

a.) (0,5) b.) (2,4) c.) (3,0) d.) (1,3) e.) (2,6)

Problem 2

The Acme Company produces four types of widgets: A, B, C and D. The profit per widget and the resource usage of each type of widget is given in the table below:

Widget Type	A	B	C	D
profit ($)	10	15	7	8
Labor (hrs)	2	1	3	1.5
Material (lbs)	3	2.5	6	5
Water (gallons)	10	12	8	9

There are 100 hours of labor, 500 lbs of material and 1000 gallons of water available. If the goal is to maximize the total profit then the objective function is: (the variables A, B ,C & D are the number of widgets of each type producead)

Options

a.) min 10A + 12B + 8C + 9D b.) min 10A + 15B + 7C + 8D c.) max 10A + 15B + 7C + 8D d.) max A + B + C + D

Problem 3

Consider the single-pair shortest path problem in a weighted directed graph G=(V, E) from a vertex s to t, where s denotes the source vertex and t represents the target/sink vertex. Let d_v denote the distance of any vertex v from the source vertex s. Moreover, let w(u,v) represent the weight of the edge (u,v). For each vertex z s, consider the set Distances_z, where

Distances_z = { d_(u,z) | where d_(u,z) = d_u + w(u,z) for each edge (u,z) in E }

To solve the single-pair shortest path problem using linear programming, we create the following linear program:

maximize d_t

subject to

d_v - d_u w(u,v) for each edge (u,v) in E

d_s = 0

Is it ok that we maximize d_t ? Why?

Select all that applies.

MULTI-CHOICE - SELECT ALL THAT APPLY:

(a) Yes, because minimizing it would result in an optimal solution where the distances of all vertices would be zero.

(b) No. We should formulate it as a minimization linear program.

(c) Yes, because an optimal solution requires the distance of the vertex z (i.e., d_z) to be the largest value that is less than or equal to the minimum of the values in Distances_z .

(d) Yes, because both minimization and maximization would find the shortest path.