Math Models of Operations Research, MATP 4700/ DSES 4770.

Third Exam, Friday, December 10, 2004.

You may use any result from your notes or a homework that is clearly stated. You may use one sheet of handwritten notes, but no other sources. The exam consists of six questions, and lasts one hundred minutes.

1. (20 points)

   A pharmaceutical manufacturer must supply 30 batches of its new medication in the next quarter, then 25, 10, and 35 in successive quarters. Each quarter in which the company makes product requires $100,000 setup, plus $3000 per batch produced. There is no limit on production capacity. Batches can be held in inventory, but the cost is a high $5000 per batch per quarter. The company seeks a minimum total cost production plan.

   1. (5 points)

      Explain why this problem can be approached by dynamic programming, with states $k=1,\ldots,5$ representing the reaching of quarter $k$ with all earlier demand fulfilled and no inventory on hand.

   2. (10 points)

      Sketch the digraph corresponding to the dynamic program structure of part (a). Include costs on all arcs.

   3. (5 points)

      Explain why the feasible production plans correspond exactly to the paths from node $k=1$ to node $k=5$ in your digraph.

2. (20 points)

   A node packing on a graph $G=(V,E)$ is a subset of the vertices so that no two vertices in the subset share an edge. If each vertex $v$ has a weight $w_v$, the weighted node packing problem on a graph is to choose a node packing $P \subset V$ of maximum weight $\sum_{v \in P} w_v$. This can be formulated as an integer programming problem by introducing a binary variable $x_v$ for each vertex $v \in V$ and then solving the problem
   

   $$\begin{array}{lrclr} \min & - \sum_{v \in V} w_v x_v \\ \mb... ...d (WNP) \\ & x_v && \mbox{binary } \forall v \in V \end{array}$$
   
   

   Let $G$ be the complete graph on three vertices $V=\{1,2,3\}$, so $G$ has undirected edges (1,2), (2,3), and (1,3). Let $w_1=5$, $w_2=4$, and $w_3=3$. Solving the linear programming relaxation of $(WNP)$ for this problem gives an optimal tableau
   

   $$M = \begin{tabular}{\vert l\vert rrrrrr\vert} \multicolumn{2... ... \\ 0.5 & 0 & 0 & 1 & -0.5 & 0.5 & 0.5 \\ \hline \end{tabular}$$
   
   
   where $s_1$, $s_2$, and $s_3$ are the slack variables in $(WNP)$.
   1. (10 points)

      Why is the inequality $x_1+x_2+x_3 \leq 1$ a valid inequality that could be added to $(WNP)$?

   2. (10 points)

      Add the inequality $x_1+x_2+x_3 \leq 1$ to $M$ and reoptimize. (You should obtain an integral solution.)

3. Consider the integer programming problem
   
   $$\begin{array}{lrcrclr} \max & 5x_1 & + & 3x_2 \\ \mbox{subj... ...lumn{3}{r}{x_1, x_2} & \geq & 0 \mbox{ and integer} \end{array}$$
   
   
   1. (20 points)

      Solve this integer program using branch-and-bound. It is acceptable to solve the LP relaxations graphically or by inspection; the problem is illustrated below.

      
      
      

   2. (15 points)

      Solve $(IP)$ using dynamic programming. Be sure to state the recursion you use to get $f_1(s,x_1)$ in terms of $f_2(s)$, and to explain your stages and state variable(s).

4. (25 points)

   The linear programming problem
   

   $$\begin{array}{lrcrcrcrcllr} \min & -2x_1 & - & x_2 \\ \mbox... ... &&&&&&& x_i & \geq & 0 & \mbox{for } i=1,\ldots,4 \end{array}$$
   
   
   has dual
   
   $$\begin{array}{lrcrcrr} \max & 8y_1 & + & 6y_2 \\ \mbox{subj... ...d (D) \\ & y_1 &&& \leq & 0 \\ &&& y_2 & \leq & 0 \end{array}$$
   
   
   1. (3 points)

      Let $\bar{x}=(3,2,0,5)$ and $\bar{y}=(-1,0)$. Show that this is an optimal solution to the primal-dual pair $(P)$ and $(D)$.

   2. (3 points)

      Is $\bar{x}$ a basic feasible solution? Justify your answer.

   3. (3 points)

      Find two optimal basic feasible solutions to $(P)$, graphically. Label $\bar{x}$ on your graph.

   4. (3 points)

      Show that $(D)$ is degenerate, graphically. Label $\bar{y}$ on your graph.

   5. (3 points)

      Give an integral feasible interior point for $(P)$.

   6. (10 points)

      Let $\tilde{x}=(3-\epsilon,2-\epsilon,3\epsilon,5+\epsilon)$ and $\tilde{y}=(-1-\epsilon,-\epsilon)$, where $0 < \epsilon < 0.1$ Let $\tilde{z}$ denote the corresponding dual slacks. Show that all complementary slackness terms $\tilde{x}_i \tilde{z}_i$ lie between $2\epsilon$ and $6\epsilon$. Hence argue that $\tilde{x}$ is close to being an optimal solution to the log barrier problem
      

      $$\begin{array}{lrcrcrcrcllr} \min & -2x_1 & - & x_2 & - & \mu... ... &&&&&&& x_i & \geq & 0 & \mbox{for } i=1,\ldots,4 \end{array}$$
      
      
      (Hint: For example, you could argue that $\tilde{x}$ almost satisfies the optimality conditions for $(LBP)$.)