SEN301!OPERATIONS!RESEARCH!I! LECTURE!NOTES!

1 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak ! ! SEN301!OPERATIONS!RESEARCH!I! lecture !NO TES!(2015-2016) Y.! lker!Topcu,! !&! zg r!Kabak,! ! Acknowledgements:!We#would#like#to#ackno wledge#Prof.# #Winston's#" operations # research :#Applica tions#and#Algorithms"#and#Prof.# #Beasley's# lecture # notes #which#greatly#i nfluence#these# #We#retain#responsibility#for#all#errors #and#would#love#to#hear#from#visitors#of #this#site!#Istanbul#Technical#Universit y#OR/MS#team# SEN301 2015-2016 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak i CONTENTS!1.!INTRODUCTION!TO!OPERATONS!RE SEARH!..!1! !TERMINOLOGY ..1! !THE#METHODOLOGY#OF#OR ..1! !HISTORY#OF#OR ..2!2.!BASIC!OR!CONCEPTS!..!6!3.!FORMULA TING!LINEAR!PROGRAMS!..!11! !LINEAR#PROGRAMMING#EXAMPLES ..12! !Giapetto#Example ..12! !Advertisement#Example ..14! !Diet#Example ..14! !Post#Office#Example ..15! !Sailco#Example ..16! !Customer#Service#Level#Example.

2 17! !Oil#Blending#Example ..18! !ADDING#ABSOLUTE#VALUES#TO#LP#FORMULATIO N ..19! !Formulation ..19! !Plant#Layout#Example ..20! !PIECEWISE#LINEAR#FUNCTIONS ..20! !Representing#Piecewise#Linear#Convex#Fu nctions#in#an#LP ..20! !Transformation#of#Nonlinear#Convex#Func tions ..22! !Oil#Shipment#Example ..22!4.!SOLVING!LP!..!25! !LP#SOLUTIONS:#FOUR#CASES ..25! !THE#GRAPHICAL#SOLUTION ..25! !THE#SIMPLEX#ALGORITHM ..30! !THE#BIG#M#METHOD ..35! !TWO]PHASE#SIMPLEX#METHOD ..38! !UNRESTRICTED#IN#SIGN#VARIABLES ..45!5.!SENSITIVITY!ANALYSIS!AND!DUALITY !..!46! !SENSITIVITY#ANALYSIS ..46! !Reduced#Cost ..46! !Shadow#Price ..46! !Conceptualization ..46!SEN301 2015-2016 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak ii !Utilizing#Lindo#Output#for#Sensitivity ..47! !Utilizing#Graphical#Solution#for#Sensit ivity ..49! !The#100%#Rule ..49! !DUALITY ..49! !Primal# #Dual ..49! !Finding#the#Dual#of#an#LP ..49! !The#Dual#Theorem.

3 51! !Economic#Interpretation ..51! !DUALITY#AND#SENSITIVITY ..52! !COMPLEMENTARY#SLACKNESS#THEOREM ..52! !DUAL#SIMPLEX#ALGORITHM ..54! !Three#uses#of#the#dual#simplex ..54! !Steps ..54! !Adding#a#Constraint ..55! !Solving#a#normal#minimization#problem ..57!6.!ADVANCED!TOPICS!IN!LP!..!58! !REVISED#SIMPLEX#ALGORITHM ..58! !Representation#of#the#Simplex#Method#in #matrix#form ..58! !Steps#of#Revised#Simplex#Method ..60! !The#Revised#Simplex#Method#in#Tableau#F ormat ..64! !UTILIZING#SIMPLEX#FOR#SENSITIVITY ..68!7.!TRANSPORTATION!PROBLEMS!..!74! !FORMULATING#TRANSPORTATION#PROBLEMS ..74! !Formulating#a#Balanced#Transportation#P roblem ..75! !Balancing#an#Unbalanced#Transportation# Problem ..76! !FINDING#A#BFS#FOR#A#TRANSPORTION#PROBLE M ..77! !Northwest#Corner#Method ..78! !Minimum#Cost#Method ..79! !Vogel s#Method ..80! !THE#TRANSPORTATION#SIMPLEX#METHOD ..82! !SENSITIVITY#ANALYSIS#FOR#TRANSPORTATION #PROBLEMS.

4 85! !TRANSSHIPMENT#PROBLEMS ..88! !ASSIGNMENT#PROBLEMS ..91! !LP#Formulation ..91!SEN301 2015-2016 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak iii !Hungarian#Method ..91!8.!INTRODUCTION!TO!NETWORK!MODELS!. .!95! !SHORTEST]PATH#PROBLEM ..95! !LP#formulation#of#shortest#path#problem ..96! !Dijkstra s#Algorithm ..96! !MAXIMUM]FLOW#PROBLEM ..97! !LP#formulation#of#maximum#flow#problem ..98! !MINIMUM]COST#NETWORK#FLOW#PROBLEM ..99!9.!PROJECT!MANAGEMENT!..!101! !CONCEPTS ..101! !THE#PROJECT#NETWORK ..102! !CPM/PERT ..103! !CPM ..106! !Crashing#the#Project ..111! !PERT ..112! !Probability#Analysis#For#CP ..114! #SEN301 2015-2016 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak 1 1.!INTRODUCTION!TO!OPERATONS!RESEARH! !TERMINOLOGY!The# British/Europeans# refer# to# "operational# research ",# the# Americans# to# " operations # research "#]#but#both#are#oft en#shortened#to#just#"OR"#(which#is#the# term#we#will#use).

5 #Another# term# which# is# used# for# this# field# is# "management# science"# ("MS").# The#Americans#sometimes#combine#the#term s#OR#and#MS#together#and#say#"OR/MS"#or# "ORMS".##Yet#other#terms#sometimes#used# are#"industrial#engineering"#("IE"),#"de cision#science"#("DS"),#and# problem#solving .#In#recent#years#there#has#been#a#move# towards#a#standardization#upon#a#single# term#for#the#field,#namely#the#term#"OR" .# operations # research # (Management# Science)# is#a# scientific# approach# to# decision#making# that# seeks# to# best# design# and# operate# a# system,# usually# under# conditions#requiring#the#allocation#of#s carce#resources. #A" system" is" an" organization" of" interdependent" components" that" work" together" to"accomplish"the"goal"of"the"system."# !THE!METHODOLOGY!OF!OR!When# OR# is# used# to# solve# a# problem# of# an# organization,# the# following# seven# step#procedure#should#be#followed:#Step# 1.

6 #Formulate#the#Problem#OR# analyst# first# defines# the# organization's# problem.# Defining# the# problem#includes#specifying#the#organiza tion's#objectives#and#the#parts#of#the#o rganization#(or#system)#that#must#be#stu died#before#the#problem#can#be#solved.#S tep#2.#Observe#the#System#Next,# the# analyst# collects# data# to# estimate# the# values# of# parameters# that# affect# the#organization's#problem.#These#estima tes#are#used#to#develop#(in#Step#3)#and# evaluate#(in#Step#4)#a#mathematical#mode l#of#the#organization's#problem.###SEN30 1 2015-2016 Dr. Y. lker Topcu ( ) & Dr. zg r Kabak 2 Step#3.#Formulate#a#Mathematical#Model#o f#the#Problem#The# analyst,# then,# develops# a# mathematical# model# (in# other# words# an# idealized#representation)# of# the# problem.#In# this# class,# we# describe# many# mathematical#techniques#that#can#be#used #to#model#systems.#Step#4.#Verify#the#Mo del#and#Use#the#Model#for#Prediction#The #analyst#now#tries#to#determine#if#the#m athematical#model#developed#in#Step#3#is #an#accurate#representation#of#reality.

7 #To#determine#how#well#the#model#fits#re ality,#one#determines#how#valid#the#mode l#is#for#the#current#situation.#Step#5.# Select#a#Suitable#Alternative#Given#a#mo del#and#a#set#of#alternatives,#the#analy st#chooses#the#alternative#(if#there#is# one)#that#best#meets#the#organization's# objectives.##Sometimes#the#set#of#altern atives#is#subject#to#certain#restriction s#and#constraints.#In#many#situations,#t he#best#alternative#may#be#impossible#or #too#costly#to#determine.#Step#6.#Presen t#the#Results#and#Conclusions#of#the#Stu dy#In#this#step,#the#analyst#presents#th e#model#and#the#recommendations#from#Ste p#5#to#the#decision#making#individual#or #group.#In#some#situations,#one#might#pr esent#several#alternatives#and#let#the#o rganization#choose#the#decision#maker(s) #choose#the#one#that#best#meets#her/his/ their#needs.#After#presenting#the#result s#of#the#OR#study#to#the#decision#maker( s),#the#analyst#may#find#that#s/he#does# not#(or#they#do#not)#approve#of#the#reco mmendations.

8 #This#may#result#from#incorrect#definiti on#of#the#problem#on#hand#or#from#failur e#to#involve#decision#maker(s)#from#the# start#of#the#project.#In#this#case,#the# analyst#should#return#to#Step#1,#2,#or#3 .#Step#7.#Implement#and#Evaluate#Recomme ndation#If#the#decision#maker(s)#has#acc epted#the#study,#the#analyst#aids#in#imp lementing#the#recommendations.# The# system# must# be# constantly# monitored# (and# updated#dynamically# as# the# environment# changes)# to# ensure# that# the# recommendations# are#enabling#decision#maker(s)#to#meet#h er/his/their#objectives.### !HISTORY!OF!OR!(Prof.#Beasley s# lecture # notes )#OR#is#a#relatively#new# discipline.#Whereas#70#years#ago#it#woul d#have#been#possible#to#study#mathematic s,#physics#or#engineering#(for#example)# at#university#it#would#not#have#been#pos sible#to#study#OR,#indeed#the#term#OR#di d#not#exist#then.#It#was#only#SEN301 2015-2016 Dr. Y. lker Topcu ( ) & Dr.

9 Zg r Kabak 3 really#in#the#late#1930's#that#operation al# research #began#in#a#systematic#fashio n,#and#it#started#in#the#UK.##Early#in#1 936#the#British#Air#Ministry#established #Bawdsey# research #Station,#on#the#east#c oast,#near#Felixstowe,#Suffolk,#as#the#c entre#where#all#pre]war#radar#experiment s#for# both# the# Air# Force# and# the# Army# would# be# carried# out.# Experimental# radar#equipment#was#brought#up#to#a#high #state#of#reliability#and#ranges#of#over #100#miles#on#aircraft#were#obtained.#It #was#also#in#1936#that#Royal#Air#Force#( RAF)#Fighter#Command,#charged#specifical ly#with#the#air#defense#of#Britain,#was# first#created.#It#lacked#however#any#eff ective#fighter#aircraft#]#no#Hurricanes# or#Spitfires#had#come#into#service#]#and #no#radar#data#was#yet#fed#into#its#very #elementary#warning#and#control#system.# It#had#become#clear#that#radar#would#cre ate#a#whole#new#series#of#problems#in#fi ghter#direction#and#control#so#in#late#1 936#some#experiments#started#at#Biggin#H ill#in#Kent#into#the#effective#use#of#su ch#data.

10 #This#early#work,#attempting#to#integrat e#radar#data#with#ground#based#observer# data#for#fighter#interception,#was#the#s tart#of#OR.#The#first#of#three#major#pre ]war#air]defense#exercises#was#carried#o ut#in#the#summer#of# 1937.# The# experimental# radar# station# at# Bawdsey# research # Station# was# brought#into#operation#and#the#informati on#derived#from#it#was#fed#into#the#gene ral#air]defense#warning#and#control#syst em.#From#the#early#warning#point#of#view #this#exercise#was#encouraging,# but# the# tracking# information# obtained# from# radar,# after# filtering# and#transmission#through#the#control#and #display#network,#was#not#very#satisfact ory.#In#July#1938#a#second#major#air]def ense#exercise#was#carried#out.#Four#addi tional#radar#stations#had#been#installed #along#the#coast#and#it#was#hoped#that#B ritain#now#had#an#aircraft# location# and# control# system# greatly# improved# both# in# coverage# and#effectiveness.