**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*