Week 7 Homework Assignment

Section 8.1

Page 307 #1

Consider the graph in figure 8.2

Write dow the set of edges $E(G)$.

$E(G) = \big\{ab, af, ae, bd, bc, cd, df, de, ef\big\}$

Which edges are incident with vertex b?

Edges with incident with vertex $b = \big\{ab,bc, bd\big\}$

Which vertices are adjacent to vertex c?

Verives adjacent with vertex $c = \big\{b,d\big\}$

Compute $deg(a)$.

$deg(a) = 3 = \big\{af, ab, ae\big\}$

Computer $|E(G)|$.

$E(G) = 9 = \big\{ab, af, ae, bd, bc, cd, df, de, ef\big\}$

Section 8.5

Page 338 # 4

Wrtie down the linear program associated with solving maximum flow from s to t in the graph in Figure 8.37

Firstly, constraints of non-negative flow

$x_{ij}\geq0$ $\forall{ij}$ $\epsilon$ $A(G)$
$x_{sa}\geq0$
$x_{sb}\geq0$
$x_{ab}\geq0$
$x_{ac}\geq0$
$x_{bc}\geq0$
$x_{bd}\geq0$
$x_{ct}\geq0$
$x_{dt}\geq0$
$x_{cd}\geq0$

Secondly, constaints of linited flow capacity

$x_{ij}\leq u_{ij}$ $\forall{ij}$ $\epsilon$ $A(G)$
$x_{sa}\leq3$
$x_{sb}\leq5$
$x_{ab}\leq2$
$x_{ac}\leq6$
$x_{bc}\leq2$
$x_{bd}\leq4$
$x_{ct}\leq4$
$x_{dt}\leq5$
$x_{cd}\leq1$

Thirdly, constraints of flow conservcation
$\forall{j}\epsilon V(G)- \{ s+t \}$
\[\sum x_{xj} = \sum x_{jk}\] $x_{ab}+x_{ac} = x_{sa}$
$x_{ab}+x_{ac} = x_{sb}+x_{ab}$
$x_{ct}+x_{cd} = x_{ac}+x_{bc}$
$x_{dt} = x_{cd}+x_{bd}$

Objective Function

Maximize \[z = \sum_{j} x_{sj}\]

Maximize $z = x_{sa}+x_{sb}$

Therefore, maximum flow problem as a linerar program is as follows

Maximize \[z = \sum_{j} x_{sj}\]

Subject to $\forall{j}\epsilon V(G)- \{ s+t \}$
\[\sum_{i} x_{ij} =\sum_{k} x_{jk}\]

$x_{ij}\leq u_{ij}$ $\forall{ij}\epsilon A(G)$
$x_{ij}\geq0$ $\forall{ij}\epsilon A(G)$

Week 8 Homework Assignement

Section 9.3

page 364 #4

A big private oil company must decide whether to drill in the Gulf of Mexico. It costs 1 million dollars to drill, and if oil is found its value is estimate at 6 million dollars. At present, the oil company believes that there is a 45% change that oil is present. Before drilling begins, the big private oil company can hire a geologist for $100,000 to obtain samples and test for oil. There is only about a 60% chance that the geologist will issue a favorable report. Given that the geologist does issue a favorable report, there is an 85% chance that there is oil. Given an unfavorable report, there is a 22% chance that there is oil. Determine what the big private oil company should do.

Drill Descion Tree

$E(Drill-No Survey) = 0.45 * (6000000 - 1000000) + 0.55 * -1000000 = 1,700,000$

$\begin{eqnarray} E(Hire Geologist) = (0.6)*(0.85)*(6000000 - 1000000 - 100000) + (0.6)*(0.15)*(- 1000000 - 100000) + (0.4)*(0.22)*(6000000 - 1000000 - 100000) + (0.4)*(0.78)*(- 1000000 - 100000)\end{eqnarray}$

$E(Hire Geologist) = 2,488,000$

Drill Descion Tree Visualization

Nodes

node1 <- "master"
node2 <- "geo"
node3 <- "noGeo"
node4 <- "geoFav"
node5 <- "geoNoFav"
node6 <- "geoFavDrill"
node7 <- "geoFavNoDrill"
node8 <- "geoNoFavDrill"
node9 <- "geoNoFavNoDrill"
node10 <- "noGeoDrill"
node11 <- "noGeoNoDrill"
node12 <- "geoFavDrillOil"
node13 <- "geoFavDrillNoOil"
node14 <- "geoFavNoDrillOil"
node15 <- "geoFavNoDrillNoOil"
node16 <- "geoNoFavDrillOil"
node17 <- "geoNoFavDrillNoOil"
node18 <- "geoNoFavNoDrillOil"
node19 <- "geoNoFavNoDrillNoOil"
node20 <- "noGeoDrillOil"
node21 <- "noGeoDrillNoOil"
node22 <- "noGeoNoDrillOil"
node23 <- "noGeoNoDrillNoOil"

nodeNames <- c(node1,node2,node3,node4,node5,node6,node7,node8,node9, node10,
               node11, node12, node13, node14, node15, node16, node17, node18,
               node19, node20, node21, node22, node23)

Graph Object

rEG <- new("graphNEL", nodes=nodeNames, edgemode="directed")

Edges

rEG <- addEdge(nodeNames[1], nodeNames[2], rEG, 1)
rEG <- addEdge(nodeNames[1], nodeNames[3], rEG, 1)
rEG <- addEdge(nodeNames[2], nodeNames[4], rEG, 1)
rEG <- addEdge(nodeNames[2], nodeNames[5], rEG, 1)
rEG <- addEdge(nodeNames[4], nodeNames[6], rEG, 1)
rEG <- addEdge(nodeNames[4], nodeNames[7], rEG, 1)
rEG <- addEdge(nodeNames[5], nodeNames[8], rEG, 1)
rEG <- addEdge(nodeNames[5], nodeNames[9], rEG, 1)
rEG <- addEdge(nodeNames[3], nodeNames[10], rEG, 1)
rEG <- addEdge(nodeNames[3], nodeNames[11], rEG, 1)
rEG <- addEdge(nodeNames[6], nodeNames[12], rEG, 1)
rEG <- addEdge(nodeNames[6], nodeNames[13], rEG, 1)
rEG <- addEdge(nodeNames[7], nodeNames[14], rEG, 1)
rEG <- addEdge(nodeNames[7], nodeNames[15], rEG, 1)
rEG <- addEdge(nodeNames[8], nodeNames[16], rEG, 1)
rEG <- addEdge(nodeNames[8], nodeNames[17], rEG, 1)
rEG <- addEdge(nodeNames[9], nodeNames[18], rEG, 1)
rEG <- addEdge(nodeNames[9], nodeNames[19], rEG, 1)
rEG <- addEdge(nodeNames[10], nodeNames[20], rEG, 1)
rEG <- addEdge(nodeNames[10], nodeNames[21], rEG, 1)
rEG <- addEdge(nodeNames[11], nodeNames[22], rEG, 1)
rEG <- addEdge(nodeNames[11], nodeNames[23], rEG, 1)

eAttrs <- list()
q<-edgeNames(rEG)
eAttrs$label <- c("Geologist", "No Geologist", "Favorable, p=0.6",
                  "Unfavorable, p=0.4",rep(c("Drill", "No Drill"),3),
                  rep(c("Oil, p=0.85", "No Oil, p=0.15"),2),
                  rep(c("Oil, p=0.22", "No Oil, p=0.78"),2),
                  rep(c("Oil, p=0.45", "No Oil, p=0.55"),2))
names(eAttrs$label) <- c(q[1],q[2], q[3], q[4], q[5], q[6], q[7], q[8], q[9],
                         q[10],q[11],q[12],q[13],q[14], q[15],q[16],q[17],
                         q[18],q[19],q[20],q[21],q[22])
edgeAttrs<-eAttrs

Default Attributes

attributes<-list(node=list(label="", fillcolor="lightblue", fontsize="15", shape="ellipse"),
 edge=list(color="black", fontsize = "12"),graph=list(rankdir="LR"))

individual Node Atributes

nAttrs <- list()
nAttrs$label <- c("Max EV=$2.488M","EV=$2.488M","Max EV=$1.7M","Max EV=$4M",
                  "Max EV =$0.22M","EV=$4M",
                  "EV=-$0.1M","EV=$0.22M","EV=-$0.1M","EV=$1.7M","EV=$0M", 
                  "$4.9M","-$1.1M","-$0.1M", "-$0.1M","$4.9M","-$1.1M",
                  "-$0.1M", "-$0.1M","$5M", "-$1M", "$0M", "$0M")
names(nAttrs$label) <- nodes(rEG)
nAttrs$shape <- c(master = "box", geo = "circle", noGeo = "box", geoFav = "box",
                  geoNoFav = "box", geoFavDrill = "circle", geoFavNoDrill = "circle",
                  geoNoFavDrill = "circle", geoNoFavNoDrill = "circle",
                  noGeoDrill = "circle",noGeoNoDrill = "circle")

Plot

plot(rEG, nodeAttrs=nAttrs, edgeAttrs=eAttrs, attrs=attributes)

Section 9.4

page 373, #1

Give the following payoff matrix, show all work to answer parts a and b.

prob <- c(0.35,0.3,0.25,0.1)
a <- c(1100,900,400,300) 
b <- c(850,1500,1000,500)
c <- c(700,1200,500,900)
mydf <- data.frame(states = 1:4, prob=prob, A=a, B=b, C=c)

cnames <- c("State", "Probability", "Alt A", "Alt B", "Alt C")
kable(mydf,  col.names = cnames, format.args=list(big.mark = ",", scientific = F)) %>%
  kable_styling("striped")

State	Probability	Alt A	Alt B	Alt C
1	0.35	1,100	850	700
2	0.30	900	1,500	1,200
3	0.25	400	1,000	500
4	0.10	300	500	900

Which alternative do we choose if our criterion is to maximize the expected value?

Expected Value A

EV.a <- with(mydf, sum(A*prob))
EV.a

## [1] 785

Expected Value B

EV.b <- with(mydf, sum(B*prob))
EV.b

## [1] 1047.5

Expected Value C

EV.c <- with(mydf, sum(C*prob))
EV.c

## [1] 820

Expected Max Value

max(EV.a, EV.b, EV.c)

## [1] 1047.5

Find the opportunity loss (regret) table and compute the expected opportunity loss (regret) for each alternative. What decision do you make if your criterion is to minimize expected regret?

Regret Matrix

regret.a <- c(0,600,600,600)
regret.b <- c(250,0,0,400)
regret.c <- c(400,300,500,0)
prob <- c(0.35,0.3,0.25,0.1)

mydf <- data.frame(rbind(regret.a, regret.b, regret.c))

names(mydf) <- c(1,2,3,4)  
row.names(mydf) <- c('A','B','C')

kable(mydf, format = 'html',format.args=list(big.mark = ",", scientific = F)) %>%
  kable_styling("striped") %>%
  add_header_above(c("You"=1,"Nature"=4))

You	Nature
	1	2	3	4
A	0	600	600	600
B	250	0	0	400
C	400	300	500	0

Expected Regret A

EVReg.A <- sum(regret.a * prob)
EVReg.A

## [1] 390

Expected Regret B

EVReg.B <- sum(regret.b * prob)
EVReg.B

## [1] 127.5

Expected Regret C

EVReg.C <- sum(regret.c * prob)
EVReg.C

## [1] 355

Expected Min Regret

min(EVReg.A, EVReg.B, EVReg.C)

## [1] 127.5

If the goal is to minimize expected regret, then alternative B should be selected.

Data 609 Assignment #4

Joseph Simone

3/19/2020