## Description

## Problem 1 – Max Flow Modeling

A Dungeon Master (DM) is trying to plan for the next three campaigns she is running. She runs campaigns for four different groups, and she is hoping to finish the groups’ campaigns in the next six months.

- Group 1’s campaign must be completed no later than 4 months from now and will require 20 total hours of play-time
- Group 2’s campaign must be completed no later than 5 months from now and will require 18 total hours of play-time
- Group 3’s campaign must be completed no later than 6 months from now and will require 13 total hours of play-time
- Group 4’s campaign must be completed no later than 3 months from now and will require 14 total hours of play-time

Each month, 12 hours are available for playing games. During a given month, no more than 8 hours can be spent on the same campaign.

Formulate a *maximum flow problem* whose solution will determine whether or not all four campaigns can be completed on time. Your answer should clearly draw the network, the source node, the sink node, and capacity on each arc in the network. Upload a picture of the network with your solution.

## Problem 2 – The Duality of Plushies

Assemble-an-Animal is currently producing four plushies: pandas, panthers, pangolins, and penguins.

A pangolin for reference:

The profit contribution, labor hours, and raw material usage (in square feet) per plushie for each type of animal are given below:

| Plushie| Profit ()|Labor(Hr.)|RawMaterial(ft)|𝐿𝑎𝑏𝑜𝑟(𝐻𝑟.)|𝑅𝑎𝑤𝑀𝑎𝑡𝑒𝑟𝑖𝑎𝑙(𝑓𝑡^2$)| |:—|:—|:—|:—| |Panda| 70 | 2 | 5| |Panther |110 |3 | 5| |Pangolin | 300 | 3 | 10| |Penguin | 250 | 5 | 15|

A maximum of 10,000 labor hours and 35,000 square feet of raw material are available annually. Each panda plushie spends an average of 0.25 year in storage; panther plushies an average of 1 year; pangolin plushies, an average of 2 years; penguin plushies, an average of 3.5 years. The warehouse can handle an average inventory level of 5,000 total plushies. Determine how much of each type of plushie should be produced annually to maximize Assemble-an-Animal’s profit.

A linear program model for this problem is:

max s.t. z=70x12x15x10.25x1x1≥0,++++110x23x25x2x2 x2≥0,++++300x33x310x32x3x3≥0,++++250x45x415x43.5x4x4≥0≤10000≤35000≤5000max 𝑧=70𝑥1+110𝑥2+300𝑥3+250𝑥4s.t. 2𝑥1+3𝑥2+3𝑥3+5𝑥4≤100005𝑥1+5𝑥2+10𝑥3+15𝑥4≤350000.25𝑥1+𝑥2+2𝑥3+3.5𝑥4≤5000𝑥1≥0, 𝑥2≥0,𝑥3≥0,𝑥4≥0

where xj𝑥𝑗 is the number of plushies of type j𝑗 to produce each year.

In the sensitivity analysis questions below, answer each question *independently* (e.g., when answering part (c), consider only the changes suggested in part (c), not those in addition to the ones considered in part (b)).

(a) Solve this model in Julia/JuMP and give the optimal primal and dual solutions, and the optimal objective function value.

(b) What is the maximum amount Assemble-an-Animal should be willing to pay for an additional hour of labor?

(c) The marketing department is considering running an advertising campaign that would increase the profit per panther plushie by $10 and panda plushie by \$15. Provide an estimate of the new optimal profit (z∗NEW𝑧𝑁𝐸𝑊∗) after this change and indicate if your estimate is a lower or upper bound on the new optimal profit. Your answer should be of the form z∗NEW≥–––––𝑧𝑁𝐸𝑊∗≥_ or z∗NEW≤–––––𝑧𝑁𝐸𝑊∗≤_, where you fill in a number in the blank.

(d) Assemble-an-Animal is considering a facility redesign that would decrease the labor availability by 1000 hours, but increase the raw material availability by 4000 square feet. Provide an estimate of the new optimal profit (z∗NEW𝑧𝑁𝐸𝑊∗) after this change and indicate if your estimate is a lower or upper bound on the new optimal profit. Your answer should be of the form z∗NEW≥–––––𝑧𝑁𝐸𝑊∗≥_ or z∗NEW≤–––––𝑧𝑁𝐸𝑊∗≤_, where you fill in a number in the blank.

## Problem 3 – Duality and complementarity

Consider the following linear program:

(1) Give the dual of this linear program.

(2) Find a complementary dual solution to the primal solution: x^:=(x^1,x^2,x^3)=(285,0,35)𝑥^:=(𝑥^1,𝑥^2,𝑥^3)=(285,0,35)

(3) Is your dual solution feasible? What can you conclude about x^𝑥^?

(4) Draw the feasible region to the dual you derived in (1). Find the optimal dual solution by the graphical method.

(5) Use complementary slackness and your dual solution from (4) to fimd the optimal primal solution.