Transcript Probabilistic OR Models and their Formulations

Probabilistic OR Models and
their Formulations
Prepared by Prof.Dr.Fetih YILDIRIM










Certainty and Uncertainty
Measurements
Randomness
Experiments- Random and nonrandom
experiments
What is probability?
What is a model?
What are the possible advantages of having
models?
Probabilistic and unprobabilistic Models
Probabilistic models in OR
Formulations of Some Probabilistic OR models
Introduction to experimentation

An experiment may be required to assist in clarifying a
number of questions,some of a general nature and others
more specific examples:
(i)How widely applicable is a particular theory?
(ii)At what temperature does a newly prepared alloy mely?
(iii)Can a technique for measuring a particular quantity be
improved kupon?
(iv)What happens to the magnetic properties of a material
when it is cooled to very low temperatures?




The importance of experiments in science and
engineering
Experimental work
The reasons for doing experiments
Possibhle difficulties
Stages of a typical
Experiment









The aim
The plan
Preparation
Preliminary experiment
Collecting data
Repeatability
Analysis of data
What do the data tell you?
Reporting the experiment
Dealing with Uncertainties
What are the uncertainties?
 Uncertainty in a single measurement: It is important to be
aware of resolution, reading and calibration uncertainties
when attempting to quote the uncertianty in a single
measurement.Such uncertainties exist whenever a
measurement is made in an experiment. However, to be
able to get a real feel for the variability in measurement,
more than one measurement should be made of each
quantity. Where this is possible we can use some results
from statistical analysis to allow us to quantify
experimental uncertainties.
 True value, accuracy and precision:
If a value is obtained from an experiment is called accurate,
then it is close to the true value but,unless given, the
uncertainty could be of any magnitude.
If a value is obtained from an experiment is called precise,
then it has a small uncertainty, but this does not mean
that it is close to the true value.

Cont.’n of Dealing with
Uncertainties
If a value is obtained from anexperiment is called
both accurate and precise, then it is close to true
value and with a small unceratinty. We would like
our experimental data to fall into this category.

Systematic and random uncertainties
Probabilistic models

A model means a system that simulates an
object under consideration.

A probabilistic model is a model that produces
different outcomes with different probabilities –
it can simulate a whole class of objects,
assigning each an associated probability.

In bioinformatics, the objects usually are DNA
or protein sequences and a model might
describe a family of related sequences
Probabilistic models




Probabilistic statements are fundamental to
many communities:
 Science
 Engineering
 Medicine
Probabilities are meaningful only within the
context of a stochastic model, which itself has a
context (not necessarily probabilistic).
Bayesian networks are an example of a
stochastic modeling technique for specifying
dependencies among random variables.
Probability is the language for expressing
the experimental results.
Decision Support



A decision tree can be used for specifying a
logical decision.
Decisions may involve uncertain
observations and dependent observations
so a simple decision tree will not be
accurate.
Influence diagrams


Bayesian network extended with utility
functions and with variables representing
decisions
The objective is to maximize the expected
utility.
Stochastic modeling
techniques
 Logic
programming
 Data modeling
 Statistics
 Programming languages
 World Wide Web
Logic Programming: ICL

Independent Choice Logic



Expansion of Probabilistic Horn abduction to
include a richer logic (including negation as
failure), and choices by multiple agents.
Extends logic programs, Bayesian networks,
influence diagrams, Markov decision
processes, and game theory
representations.
Did not address ease of use
Operations Research





OR is a scientific approach to decision making that
involves the operations of organizational systems.
"Research on Operations"
OR involves creative scientific research into the
fundamental properties of operations. Operations
research is also concerned with the practical
management of the organization.
It attempts to resolve the conflicts of interest among the
components of the organization in a way that is best for
the organization as a whole.
OR attempts to find the best or optimal solution to the
problem under consideration.
Team Approach - OR team to
undertake a full-fledged study
OR-team needs to include specialists in
mathematics, statistics and probability
theory, economics, business administration,
electronic computing, engineering and the
physical sciences, the behavioral sciences,
and the special techniques of OR.
OR is concerned with optimal decision making
in, and modeling of, deterministic and
probabilistic systems that originate from real
life.
Typical OR Approach is:
1) Formulating the problem. - From vague
description, determine objectives, goals, and
constraints
2) Constructing a mathematical model to
represent the system under study. - decision
variables, objective function, (mathematical)
constraints
3) Deriving a solution from the model. - optimizing
or satisfying, post-optimality analysis
4) Testing the model and the solution derived from
it. - validity
5) Establishing controls over the solution. sensitivity analysis
6) Putting the solution to work: implementation.
OR Methods Used in
• Mathematical Programming
(LP, IP, NLP, Multi-Objective)
• Transportation Problem
• Game Theory
• Dynamic Programming
• PERT-CPM
• Queuing Theory
• Forecasting
• Inventory
• Decision Analysis
• Reliability
• Simulation
Game Theory
Prisoner 2
Confess
Don't
Confess
Confess
(-5, -5)
(0, -20)
Don't
Confess
(-20, 0)
(-1,-1)
Prisoner 1
QUEUEING MODELS

A queuing problem arises whenever the
demand for customer service cannot
perfectly be matched by a set of welldefined service facilities.
Purpose of Queueing Model
 To help design a system that will minimize a
stated measure of performance such as the
sum of the costs of customer waiting and
costs of idle facilities.
QUEUEING THEORY
Serviced
Customers
Leaving
Customers
Arriving
Service
Facility
Discouraged
Customers
Leaving
Simple Queueing Theory
Queueing Models
 Kendall notation
 Steady state analysis
 Performance measures
 Different queue models

Queues and components





Queues are frequently used in simulations.
Population: The entity (“customers”) that
requires service
Server: The entity that provides the service
Queue: The entity that temporarily holds the
waiting “customers” before they are served.
Events: arrival, service, and leaving.
Purpose of Queueing
Models
Most models are to determine the
level of service
 Two major factors:

Cost of providing service: cannot
afford many idle servers.
 Cost of customer dissatisfaction:
customers will leave if queue is too
long.


Tradeoff between these 2 factors
Characteristics of Queue
models



Calling population
 infinite population: leads to simpler model, useful
when number of potential “customers” >> number of
“customers” in system.
 Finite population: arrival rate is affected by the
number of customers already in the system.
System capacity
 The number of customers that can be in the queue or
under service.
 An infinite capacity means no customer will exit
prematurely.
Arrival process
 For infinite population, arrival process is defined by
the interarrival times of successive customers
 Arrivals can be scheduled or at random times,
Poisson dist’n is used frequently for random arrivals,
and scheduled arrivals usually use a constant
interarrival rate.
Characteristics of Queue
models

Queue behaviour
 describes how the customer behaves while in the
queue waiting
• balking - leave when they see the line is too long
• renege - leave after being in the queue for too long
• jockey - move from one queue to another

Queue discipline
 FIFO - first in first out (most common)
 FILO - first in last out (stack)
 SIRO - service in random order
 SPT - shortest processing time first
 PR - service based on priority
Characteristics of Queue
models


Service Times
 random: mainly modeled by using exponential
distribution or truncated normal distribution (truncate
at 0).
 Constant
Service mechanism describes how the servers are
configured.
 Parallel - multiple servers are operating and take
customer in from the same queue.
 Serial - customers have to go through a series of
servers before completion of service
 combinations of parallel and serial.
Kendall Notations

Kendall defined the notations for parallel server
systems
A/B/c/N/K






A: interarrival distribution type
B: service time distribution type
Common symbols for A, B are M for exponential, D for
constant, Ek for Erlang, G for general or arbitrary.
c: for number of parallel servers
N: for system capacity
K: for size of calling population.