HMC Math 187: Operations Research (Fall, 2000)
Homework

### Assignment #11 (Due 12/08/00):

Chapter 14 (pg 875): 28abc, 30ab, 32abce
11A: Solve the following LP using LINDO. Describe complimentary slackness and verify that these conditions are satisfied by the optimal solution to this LP and its dual.
```   max 30x + 20y
s.t. x + 2y <= 6
2x + y <= 8
y <= 2
-x + y <= 1
x, y >= 0
```
11B: Solve the problem posed in #9-26 on pg. 472 using dynamic programming. You do not need to do parts (a)-(e), but you should read (a) for a hint.
11C: Suppose you are considering investing in stocks A and/or B. You have \$1 to start, and can make only (at most) one investment per year, and then can only invest \$1 (any extra money is left idle). Probablilities of investment returns for a year's investment are as follows:
 Investment Amt Returned Probability A \$0 0.3 \$2 0.7 B \$1 0.9 \$2 0.1
(i) Find the investment policy that maximizes the expected amount of money you will have after three years.
(ii) Find the investment policy that maximizes the probability that you will have at least \$2 after three years.
BONUS: Write a computer program to solve the game of blackjack. The program should give the optimal play strategy given any hand you are currently holding, and any card the dealer is showing. You may assume we are playing out of an infinite deck. Assume that the dealer will hit on a 15 or lower, and stand on a 16 or higher. Extra bonus points for including the options of splitting and doubling down. If you want to try this, you may want to see me for further instructions.

### Assignment #10 (Due Fri. 12/01):

Chapter 13 (pg 781): 10, 23ab, 28aeg
Chapter 14 (pg 875): 4a, 6a, 25bd
10A: Prove (but not too rigorously) that if grad(f)(x) = 0 and H(x) is positive definite, then x is a local minimum of f.
(Here, grad(f)(x) is the gradient of f at x, and H(x) is the Hessian of f at x.)

### Assignment #9 (Due 11/22/00):

Chapter 13 (pg 781): 3a, 18, 20, 31bcd, 33abc

### 2nd Midterm: Takehome, Due Monday, Nov. 20

(No homework due Wed. 11/15)

### Assignment #8 (Due 11/8/00):

Chapter 10 (pg 543): 17ac, 19, 23
8A: In the network shown in Figure 8A, find the maximum flow, and prove that it is maximum by finding a source/sink cut with capacity equal to the flow.
8B: In the network shown in Figure 8B, arc capacities are drawn over the arcs, and a current feasible flow is shown in boxes. Find three flow-augmenting paths from source (1) to sink (11).
8C: For the network in Figure 8A, let all arcs be undirected. Given that, use Dijkstra's Algorithm to find the shortest path from node 2 to every other node in the network (note that you only need to run the algorithm once). For each node, be sure to keep track of its predecessor and its distance from node 2.

8D: Consider the Transportation Problem in the second GIF ("more for less" paradox)
(i)Draw the transportation network indicated by the table.
(ii) Use LINDO to find the optimal flow in this network.
(iii) Formulate the dual of this program, and verify that the dual solution given by LINDO is dual-feasible.
(iv) Add 5 to a_2 and b_1 (i.e. change supply from 10 to 15, and demand from 11 to 16). Resolve in LINDO.
The net cost decreases! We have MORE goods to ship, but we pay less! Weird. Any idea what's going on here?

Solutions to HW#8

### Assignment #7 (Due 11/1/00):

Chapter 10 (pg 543): 3, 7, 8acd, 9, 11, 13a
Solutions to HW#7

### Assignment #6 (Due 10/25/00):

WARNING: These are multi-part problems, and this assignment is longer than it appears.
Chapter 7 (pg 363): 20, 23
6A: For the following LP
```    Max z = 5x + 12y + 4w
st      x +  2y +  w <= 10
2x -   y + 3w  =  8
x, y, w >= 0
```
You are given that the optimal basis has basic variables x and y
(and thus non-basic `w` and slack `v`). Without using LINDO (though you may
use it to check your answers) Determine the following:
(i) Optimal B inverse.
(ii) The optimal bfs and optimal z.
(iii) The optimal solution to the dual lp.
(iv) How much can we vary b_1 (currently 10) before the basis changes?
(v) How much will z change if b_1 decreases by 2? decreases by 8? (bounds are okay)
(vi) How much can we vary c_3 (currently 4) before the bfs changes?
(vii) How much can we vary c_1 (currently 5) before the bfs changes?
(viii) How much will z change if c_1 increases by 2? increases by 20? (bounds are okay)
Solutions to HW#6

### Assignment #5 (Due 10/4/00):

Chapter 4 (pg 165): 22
Chapter 7 (pg 363): 14a, 16cf, 17
5A: (i) Use the simplex method to solve the following LP:
```      max z = -3x + 6y
s.t.     5x + 7y <= 35
-x + 2y <= 2
x ,  y >= 0
```
(ii) Do one more simplex pivot to find a second basic optimal solution to this program.
Graph the feasible region to determine that these are the only basic optimal solutions,
and then describe the set of all optimal solutions.
5B: Refer to the simplex tableau in problem 5.7, where x_1 and x_3 are indicated as basic.
Here you will be doing one iteration of the revised simplex method, so no simplex tableaus allowed!.
(i) What are the matrices and vectors B, N, c_B and c_N relative to this basis?
(ii) Compute "B inverse", the basic feasible solution, the objective value of this solution, and the reduced cost vector "c bar".
(iii) By examining "c bar" and then doing the ratio test, determine the entering and leaving basic variables at this step.
5C: In class we proved Weak Duality using the "normal form" of an LP (i.e. with Ax <= b).
Using that proof as a template, construct a similar proof for an LP in standard form (Ax = b).
Note that you will need to find the general dual form of a primal LP in standard form before proceeding.
This is actually a better proof of general Weak Duality, since we've seen that any LP may be put in standard form.
Solutions to HW#5

### Assignment #4 (Due 9/27/00):

Chapter 4 (pg 165): 23
Chapter 5 (pg 245): 11, 14, 22
Also do "5.14(d) Find a feasible ray in an improving objective direction."
Note: In problem 5.22(e), "l" is the limiting ratio which determines the pivot row, or alternately,
the amount by which the entering basic variable increases as it enters.
4A: Use the "Big M" variation of the simplex method to solve the LP in problem 5.16a of the text.
4B: Use the "Big M" method to conclude that the LP in problem 5.19 of the text is infeasible.
4C: (i) Use the simplex method to solve the following LP:
```      max z = x + 2y
s.t.   2x +  y <= 8
-x + 2y <= 6
-2x +  y <= 3
x ,  y >= 0
```
(ii) Plot the feasible region graphically, and show the progress of the simplex method on the graph.

### Assignment #3 (Due 9/20/00):

Chapter 4 (pg 165): 5, 8a, 13, 15ab
Chapter 5 (pg 245): 3bf, 4, 9

### Assignment #2 (Due 9/13/00):

Chapter 2 (pg 64): 4, 6, 12, 32, 34

### Assignment #1 (Due 9/8/00):

For this assignment, I want you to download the LINDO optimization package from the www
and use it to solve the "punch" LP from class:
```   max 30x + 20y
s.t. x + 2y <= 6
2x + y <= 8
y <= 2
-x + y <= 1
x, y >= 0
```
The free demo version of LINDO may be downloaded from their website www.lindo.com.
Select the "Download" tab, select "LINDO", and then the appropriate operating system.
After filling out the registration form, you will be able to download a self-installing executable.
Run this and follow the instructions.
WARNING: This is a Windows 3.1-style application, and the installation does not support
long file names. Thus if you want to install it in C:\Program Files\Lindo, you'll have to tell the
installation program that you want it installed in C:\Progra~1\Lindo.
Once installed, you can read the program's help to get started. Most of what you need to know
for this assignment should be found under the "Entering a Model" topic in the Help Contents.
Once you've got it solved (you should get the same solution we did in class), print out the window
with the LP and the Reports Window (or better still, copy and paste them both into a single file
and save a sheet of paper!). Turn in your print-out(s). You are now done.

Return to: Math 187 Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu