**Introduction to Decision Theory and Operations Research**

Rona Pfeffer

Fall 2014-2015

**1**

**2**

**3**

**4**

**5**

Linear Programming

Formulating LP Problems

Solving LP Problems

The Simplex Algorithm

Sensitivity Analysis

integer Programming

Network theory

Dynamic Programming

Decision theory

1

2

3

The Transportation Problem

Linear Programming Model

Assumptions

Let's begin with the following "Diet Problem":

The Standard LP Model:

Class Exercise

Formulate the following problems using an LP model

The Assignment Problem

assumptions

formulation

Transportation Problem - Example

class exercise

find the solution for the above problem, for different values of C1

General

Shortest Path

Maximum Flow

Minimum Spanning Tree

shortest path example

The recursive formula

Class exercise

Probabilistic DP

The IP Model

OR definition

example

product

1

2

3

4

volume

22

30

50

70

profit

10

15

20

30

per box

$ per box

Maximize Z = 10X1 + 15X2 + 20X3 + 30X4

subject to:

22X1 + 30X2 + 50X3 + 70X4 <=100

Optimization Problems

Maximize Z = 10X1 + 15X2 + 20X3 + 30X4

Maximize Z = 10X1 + 15X2 + 20X3 + 30X4

subject to:

22X1 + 30X2 + 50X3 + 70X4 <=100

(a non-linear function)

22X1 + 30X2 + 50X3 + 70X4 <=100

history

psychology

economics

computer science

engineering

mathematical model

components of a mathematical model:

decision variables

objective function

constraints

parameters

related disciplines

mathematics

statistics

management

course site

contact information

where and when

assignments

reading materials

prerequisites

General Information

introduction

1. graphic solution method

4. using excel's solver

2. solution for LP problems

3. the case of a single constraint

Types of problems on networks

Course Outline

Formulating IP Problems

Set-Covering

Bin-Packing

Solving IP Problems

Rounding?

Branch and Bound

Branch and Bound

Routing Problems

Locating problems

Planning Problems

1 function Dijkstra(Graph, source):

2 dist[source] := 0 // Initializations

3 for each vertex v in Graph:

4 if v ≠ source

5 dist[v] := infinity // Unknown distance from source to v

6 previous[v] := undefined // Predecessor of v

7 end if

8 PQ.add_with_priority(v,dist[v])

9 end for

10

11

12 while PQ is not empty: // The main loop

13 u := PQ.extract_min() // Remove and return best vertex

14 for each neighbor v of u: // where v has not yet been removed from PQ.

15 alt = dist[u] + length(u, v)

16 if alt < dist[v]

17 dist[v] := alt

18 previous[v] := u

19 PQ.decrease_priority(v,alt)

20 end if

21 end for

22 end while

23 return previous[]

DIjkstra's Algorithm

Ford-Fulkerson's Algorithm

Example

Max-Flow - Min Cut

LP Formulation

Example

IP Formulation

Pseudo-Code

Complexity