Review for Last Exam

ISE 302

Dynamic Programming

Define the stages and states of a system that can be modeled as a Dynamic Program
For the last stage, find the readily obtainable min/max value for each state.
Use recursion to find the min/max value of each state of the intermediate stages.
When at the first stage, need only to find value using the initial state.
Backtrack through results to find the optimal policy for each stage.
Example Problem
Use Dynamic Programming to solve the classic knapsack problem. The knapsack problem is to maximize the reward/value of what can be carried in a sack which has a maximum weight which can be carried.

Given the following items, their value and their weight, what is the maximum value that can be achieved given a weight limit of 10 pounds?

ItemWeightReward/Value

137

246

3510

4611

538

Integer Programming

Formulate IP
Solve binary IP using branch and bound.
Solve general integer IP by branching on decision variables with non-integer solutions to the LP relaxed problem.
Example Problem
The university is in the process of forming a committee to handle the students’ grievances. The directive received from the administration is to include at least one female, one male, one student, on administrator, and one faculty member. Then individuals (identified, for simplicity by letters a to j) have been nominated. The mix of these individuals in the different categories is given as follow:
Females – a,b,c,d,e
Males – f,g,h,I,j
Students – a,b,c,j
Administrators – e,f
Faculty – d,g,h,i

The university wants to form the smallest committee with representation from each of the five categories. Formulate this problem as an IP.

Min Z = 2x1 + 6x2 – 3x3 -2x4 –x5

St x1 + x2 + 2x3 <= 2

X3 + 2x4 + 2x5 <= 3

X1, x2, x3, x4, x5 = 0 or 1

Random/Markov Processes

Define all states.
Develop one step probability transition matrix.
How do you find the steady state probabilities?
Given steady state probabilities and cost of being in a state, determine expected cost of system.
Given system in a particular state, find probability of being in another state after n transitions.

Queuing

Describe a queuing system using rate transition diagram.
Define the following in terms of probabilities for a given rate transition diagram:
Throughput rate
Reject rate
Expected number of busy servers
Server utilization
L – expected number of customers in the system
Lq – expected number of customers in the queue
W – expected time in the system
Wq – expected time in the queue
Example Problem
A system consists of two servers and a queue of maximum length 1. Server 1 on average performs a service in 2 minutes, while server 2 takes 3 minutes to complete a service. There are two types of customers who arrive. Type one customers arrive at a rate of 10 customers per hour, while type two customers arrive at a rate of 6 customers per hour. If both servers are available, a type one customer will choose server 1 while a type two customer will choose server 2.
Draw the rate transition diagram.
Define the parameters listed above in terms of lambda, mu and state probabilities (Throughput rate,…. , Wq).

LP Formulation