Shout here for any help on D1…
|
||||||
Decision Maths21 comments to Decision Maths |
||||||
|
Copyright © 2010 The Sydenham High School Mathematics Department Blog - All Rights Reserved |
||||||
|
||||||
Decision MathsShout here for any help on D1… 21 comments to Decision Maths |
||||||
|
Copyright © 2010 The Sydenham High School Mathematics Department Blog - All Rights Reserved |
||||||
D1 glossary
Glossary for D1
1 Algorithms
In a list containing N items the ‘middle’ item has position [1/2 (N + 1)] if N is odd [1/2(N + 2)] if N is even, so
that if N = 9, the middle item is the 5th and if N = 6 it is the 4th.
2 Algorithms on graphs
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
If a graph has a number associated with each edge (usually called its weight) then the graph is called a
weighted graph or network.
The degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd
(even) degree.
A path is a fi nite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex
of the next, and in which no vertex appears more then once.
A cycle (circuit) is a closed path, ie the end vertex of the last edge is the start vertex of the first edge.
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are
connected.
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
A tree is a connected graph with no cycles.
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
A minimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as
possible. (MST is sometimes called a minimum connector.)
A graph in which each of the n vertices is connected to every other vertex is called a complete graph.
4 Critical path analysis
The total float F(i, j) of activity (i, j) is defi ned to be F(i, j) = l j – e i – duration (i, j), where ei is the earliest
time for event i and l j is the latest time for event j.
6 Matchings
A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y,
not vertices within a set. (If there are r vertices in X and s vertices in Y then this graph is Kr,s.)
A matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. If
every member of X is paired with a member of Y the matching is said to be a complete matching.
Hi Mrs Tibble,
I am doing D1, ex 6A question 6 and i need help please!
Thanks
Hi Emily,
Sorry – only just seen this. Don’t have text book here; what is the question about?
JT
Chair supplies make three types of wooden chairs. each type is manufactured in a four stage process. the company is able to obtain all the raw materials it needs. The available production capacity during the 60-hour production work week is as follows
Weekly capacity in number of chairs
Process Chair A Chair B Chair C
1 400 or 600 or 900
2 1800 or 400 or 300
3 200 or 900 or 600
4 600 or 400 or 450
It is assumed that there are 60 hours of labour available for each process. the profits on each of the three types of chair are £15, £20, £25 respectively. Formulate this as a linear programming problem given that the profit is to be maximised.
Answers
Maximise P=15x +20y + 25z
Subject to 9x+6y+4z less than or = 3600
2x + 9y + 12z less than or = 3600
18x + 4y + 6z less than or = 3600
6x + 9y + 8z less than or equal to 3600
then non-negativity constraints
I don’t understand the subject to constraints
Thank you
Don’t bother with that question – especially at this time of night!! It’s evil. I’ll show you my solution next lesson. The data is presented in a very confusing way.
Have an early night instead!
JT
Ok thank you! Emily
Hi mrs Tible,
in a bapartite graph, if all the values in y are connected but not all values of x are, is it still complete, because in the defenition it says:
‘If every member of X is paired with a member of Y the matching is said to be a complete matching.’
but doesnt say that if all members of y are paired with members of x it is complete?
Hi Megan,
Yes it’s complete as it isn’t possible to add any more edges into the matching. All the vertices in one set are saturated.
JT
thankyou
i have a few more questions
1) whats the reason why a network can’t have an odd number of vertices of odd degrees?
2)i used the vertex method and one of the points was x=6.857.. , y= 3.428..
should u round up both numbers as its talking about people?
and should you round up before putting it into the profit formula, or round the final value?
Hi Megan,
When you sum the degrees for the whole network, you are counting the ends of all the edges. Every edge has 2 ends, so the total has to be even. You need 2 odds to make an even, so the odd vertices have to occur in twos.
For the rounding, yes, you will need integers for people, but you have to stay inside the feasible region, so it depends where that is in relation to your lines.
You put your x and y value answers in the profit equation, so if your answers have to be integers, you use the integers.
JT
thankyou, i understand the first part but am still slightly confused on the rounding
i’m doing question 7ei on friday the 12th january 2007 paper
The number of children is represented by x and the number of adults by y.
constraints
x < 10
2 (and equal to)10
x (and equal to) 24
it says find the minimum numner of passengers
if i were to look at poitn A (x=6.857.. , y= 3.428..) for intergers in the feasable reason, the cordiates could be
(7,4)
or (6, 4) – this value looks like its on the line, how would you check that its in the feasible area? and if its on the line is it still in the region?
also when i put x=6 and y=4 it into the profit equation p=2x+3y it came up with 24 which is the same as another point (point B), these are both the smallest points so which one would you use.(if i use the ruller method, point B is the smallest and point A isnt, suggesting (6,4) isn’t a solution but how do i know that?)
sorry for the long question, i hope it makes sense
also if it has to be an integer is there any point working it out simultaneously, couldn’t you just look at the graph?
Hi Megan,
If you need integer solutions and 2 points give the same max or min in the objective function, then give both solutions. The lines are part of the feasible region if they are solid, but not if they are dashed (strict inequality) so if a point is on a solid line, that’s fine – a vertex is on 2 lines!
You can sometimes just look at the graph – draw an integer grid on it then you can see clearly where the possibilities are.
Does that help?
Tea Lady
Thanks that does help, but the answer only says there is one solution when i get two?
When I used the vertex method there were two solutions and when I used the ruler method there was one solution, and in the answer booklet there was only one solution, so i’m not sure if I’m doing something wrong? :S
do you not get marks for doing a simultaneous equation if you just look at the graph? most of the questions need intergers so most of the time you dont need to do simultaneous equation’s?
Are you sure there were two? Was one of them on a dashed line and therefore not possible?
Hey Miss Tibble,
Just wondering if you have any frees in tomorrow morning? Just got a couple of questions on some exam papers I have done. Or I can see you at lunchtime if that is easier.
Thanks.
Laura
Laura, I do have some frees in theory, but they have already been booked. You should have come to your last lesson to get your questions answered. You can see me before school if you want ie 8am, or put them on here.
JT
Laura, try beginning of period 1. JT
i found the problem the question said find the minimum number of passengers not profit, it makes sense now
thanks mrs tible
Well done! Don’t stay up late!
Sorry, can’t make it in for first period.
Thank you though. Laura