• 検索結果がありません。

MA Chapter8 Applications

N/A
N/A
Protected

Academic year: 2018

シェア "MA Chapter8 Applications"

Copied!
38
0
0

読み込み中.... (全文を見る)

全文

(1)

Chapter 8

Applications

Section 8.1 Linear Programming

Example 8.1.1 My special diet requires that all the food I consume comes from one of the four ‘basic food groups’ - chocolate, ice cream, soft drink, cheesecake. At present, the following four foods are available for consumption - chocolate chip cookies, chocolate ice cream, root beer, cheesecake.

My dietician insists that I must ingest at least 500 calories, 6 ounces of chocolate, 10 ounces of sugar and 8 ounces of fat daily (sigh!). The nutritional content per unit of each type of food, together with their costs is shown in the following table.

Calories Chocolate (oz) Sugar (oz) Fats (oz) Cost (cents)

Chocolate chip 400 3 2 2 50

cookies (per packet)

Chocolate ice 200 2 2 4 20

cream (per scoop)

Root beer 150 0 4 1 30

(per bottle)

Cheesecake 500 0 4 5 80

(per piece)

Suppose I would like to satisfy my dietary requirements with the minimum cost, how should I plan my diet? If I let

x1 = the number of packets of chocolate chip cookies consumed daily; x2 = the number of scoops of chocolate ice cream consumed daily; x3 = the number of bottles of root beer consumed daily;

x4 = the number of pieces of cheesecake consumed daily,

(2)

we have the following Linear Program or LP:

Minimize z= 50x1+ 20x2+ 30x3+ 80x4 (cost) such that

400x1+ 200x2+ 150x3+ 500x4 500 (Calorie constraint)

3x1+ 2x2 6 (Chocolate constraint)

2x1+ 2x2+ 4x3+ 4x4 ≥ 10 (Sugar constraint) 2x1+ 4x2+ x3+ 5x4 ≥ 8 (Fat constraint) x1, x2, x3, x4 0 (Sign restrictions) Discussion 8.1.2 Typically, a LP involves the following

(i) decision variables x1, x2, ..., xn;

(ii) a linear function involving some or all the decision variables, which we would like to maximize or minimize. This function is known as the objective function;

(iii) a set of constraints involving some or all the decision variables, each of which must be a linear inequality or equality;

(iv) any other implicit restrictions on the decision variables (≥ 0, ≤ 0, unrestricted in sign, integer values etc.)

If the LP we are trying to solve involves only two variables x1 and x2, we may use the following graphical method. Note that the Simplex Method developed later (see Discus- sion 8.1.5) is essentially a generalization of the graphical method which allows us to handle LPs with more than two variables.

Example 8.1.3 Consider the following LP:

Maximize z= 3x1+ 2x2 such that

x1+ 2x2 6 (1) 2x1+ x2 8 (2)

−x1+ x2 ≤ 1 (3) x2 2 (4)

x1, x2 0 (5)

(3)

We draw a feasible region (shaded below) defined by the set of constraints.

By increasing the value of z in the equation 3x1+ 2x2, we can draw a series of parallel lines moving through the feasible region. Note that for any value of z, any point (x1, x2) on

the line z = 3x1+ 2x2 that also lies in the feasible region is a feasible solution to the LP that will give the objective function a value of z.

Thus, the largest value z such that the line z= 3x1+ 2x2 will still have at least a point

(4)

(x1, x2) lying in the feasible region will give us a solution to the LP. For this example, the optimum solution is z = 1223 obtained at the point (313,113).

Remark 8.1.4

(i) An optimum solution of a LP (regardless of the number of variables) can always be identified with one of the extreme points of the feasible region.

(ii) The graphical approach cannot be realistically applied for LPs with more than two variables.

(iii) The following Simplex Method has close relations with elementary row operations and matrix algebra.

Discussion 8.1.5 (Simplex Method)

In order to apply Simplex Method, we first need to convert the given LP into standard form. A LP in standard form has the following properties.

(i) The objective function can either be maximized or minimized. (A minimization problem can be easily converted into a maximization and vice versa. Do you know how?) ; (ii) All variables are non negative (i.e. ≥ 0). Any variable that is originally not non negative

can be modified in the following way.

xi≤ 0 ⇔ xi= −xi≥ 0;

xi unrestricted in sign ⇔ xi= xi− x′′i where xi, x

′′ i ≥ 0

When performing the above change of variables, remember to modify the objective function also.

(iii) All constraints are equations (rather than inequalities).

x1+ x2− 3x3≤ 6 ⇔ x1+ x2− 3x3+ s1= 6, s1≥ 0;

x1+ x2− 3x3≥ 6 ⇔ x1+ x2− 3x3− s2= 6, s2≥ 0.

In the examples above, s1 and s2 are called slack and surplus variables respectively. Problem 8.1.6 Convert the LPs from Example 8.1.1 and Example 8.1.3 into standard form. Discussion 8.1.7 (Simplex Method continued)

Consider the following LP in standard (from Example 8.1.3). Maximize z= 3x1+ 2x2

such that

(5)

x1+ 2x2+ s1 = 6 (1)

2x1+ x2 + s2 = 8 (2)

−x1+ x2+ s3 + s3 = 1 (3)

x2+ s4 + s4 = 2 (4)

x1, x2, s1, s2, s3, s4 0 (5)

For the next step of Simplex Method, we need to find a feasible starting solution. Consider the set of constraints, which is essentially a linear system with m equations and n unknowns. Usually, we assume m ≤ n. In the example above, m = 4, n = 6.

A basic solution is obtained by setting n − m of the variables to be equal to zero and then solving for the remaining m variables. The n − m variables set to be zero are called the non basic variables while the remaining m variables are called the basic variables.

Let x1 = x2 = 0 (non basic variables) and solving (by inspection) for s1, s2, s3, s4 (basic

variables), we have

x1= x2= 0, s1= 6, s2= 8, s3= 1, s4= 2.

Note that all the variables satisfy the non negativity condition. Thus, this is a feasible solution. If any of the variables violates the non negativity condition, our solution is said to be infeasible. Since the above solution is feasible, we may use it as our feasible starting solution.

Remark 8.1.8

(i) Very often, obtaining a feasible starting solution is not easy and special techniques are needed. For example, try obtaining a feasible starting solution for the LP in Example 8.1.1.

(ii) Interested students may refer to the following books for a more detailed description of how these situations are handled.

1. Operations Research: an introduction by Hamdy A. Taha.

2. Operations Research: Applications and Algorithms by Wayne L. Winston. Discussion 8.1.9 (Simplex Method continued)

Let us return to the feasible starting solution

x1= x2= 0, s1= 6, s2= 8, s3= 1, s4= 2

obtained for Example 8.1.3. Note that the feasible starting solution corresponds to the origin (x1, x2) = (0, 0).

At each iteration of the Simplex Method, we choose one variable x, which is currently a basic variable and replace it with another variable y, which is currently a non basic variable. The essence of the Simplex Method is to determine the choice of appropriate entering and leaving variables at each iteration so as to arrive at the optimum solution after a small number of iterations.

To proceed with the next step of Simplex Method, we construct the following table using our feasible starting solution.

(6)

Basic z x1 x2 s1 s2 s3 s4 Solution

z 1 −3 −2 0 0 0 0 0

s1 0 1 2 1 0 0 0 6

s2 0 2 1 0 1 0 0 8

s3 0 −1 1 0 0 1 0 1

s4 0 0 1 0 0 0 1 2

We next decide the entering variable and the leaving variable. The entering variable is decided by checking the optimality condition.

(i) If we have a maximization problem, the entering variable is the non basic variable with the most negative coefficient in the objective z equation. In our example, since we have a maximization problem, the entering variable chosen in this iteration is x1. In a maximization problem, when all the non basic variables have positive coefficients in the objective z equation, we have reached optimality.

(ii) If we have a minimization problem, the entering variable is the non basic variable with the most positive coefficient in the objective z equation. In a minimization problem, when all the non basic variables have negative coefficients in the objective z equation, we have reached optimality.

The leaving variable is decided by checking the feasibility condition.

(i) Take the ration of the current value of each basic variable with the coefficient corre- sponding to the entering variable. Basic variables with zero or negative denominators cannot be selected

(ii) For both maximization and minimization problems, the leaving variable corresponds to the basic variable with the smallest ratio. In our example, the leaving variable is s2.

Basic z x1 x2 s1 s2 s3 s4 Solution

z 1 −3 −2 0 0 0 0 0 Ratio

s1 0 1 2 1 0 0 0 6

6 1 = 6

s2 0 2 1 0 1 0 0 8

8

2 = 4 (leaving var.)

s3 0 −1 1 0 0 1 0 1 N.A. (−ve denominator)

s4 0 0 1 0 0 0 1 2 N.A. (zero denominator)

To update the table for the next iteration, we

(i) Replace the leaving variable (s2) with the entering variable (x1) in the basic variable column.

(ii) Multiply the row containing the entering variable by a suitable constant so that the entry in the row corresponding to the entering variable column is 1 (we call this entry the pivot).

(7)

(iii) Perform elementary row operations to change all other entries in the same column as the pivot to 0.

As a result, the table for the next iteration will be as follows.

Basic z x1 x2 s1 s2 s3 s4 Solution

z 1 0 −12 0 32 0 0 12

s1 0 0

3

2 1 −12 0 0 2

x1 0 1

1

2 0 12 0 0 4

s3 0 0

3

2 0 12 1 0 5

s4 0 0 1 0 0 0 1 2

Remark 8.1.10

(i) When we check the optimality condition, we know we have reached optimality when there are no more entering variables.

(ii) When we check the feasibility condition, we need to find a variable to become a non basic variable in the next iteration so that all other basic variables in the next iteration are still feasible. This explains why we choose the basic variable with the smallest ratio as the leaving variable.

(iii) Note that the current solution corresponds to another extreme point in the feasible region, (x1, x2) = (4, 0).

Problem 8.1.11 Proceeding from the end of Discussion 8.1.9, determine the next set of entering and leaving variables using the optimality and feasibility conditions. Show that the next iteration results in the optimum solution.

Discussion 8.1.12 (Block multiplication) Let A be a m × n matrix and B a n × p matrix, we know that we can pre-multiply A to B to obtain a m × p matrix AB. Suppose we partition A and B in the following way:

A=

✒ A11 A12

A21 A22

B=

✒ B11 B12

B21 B22

✓ . Then the product AB can be expressed as

AB=

✒ A11B11+ A12B21 A11B12+ A12B22

A21B11+ A22B21 A21B12+ A22B22

provided the sub-matrices A11, A12, A21, A22, B11, B12, B21, B22 are of sizes such that the products in the expression above are valid. This method of multiplying partitioned matrices is called block multiplication.

(8)

Example 8.1.13 Let

A=

−10 −32 14 52

1 5 6 1

❆ B=

❇❇

2 1 4

−3 5 2

7 −1 5

0 3 −3

❈❈

be partitioned as shown above. Compute AB by block multiplication.

Solution

−1 2

0 −3

✓ ✒2 1

−3 5

✓ +

✒1 5 4 2

✓ ✒7 −1

0 3

=

✒−1 23 37 −13

✓ .

1 5✁ ✒ 2 1

−3 5

+ 6 1✁ ✒7 −1

0 3

= 29 23.

AB=

−137 −1323

29 23 ∗

❆ .

Problem 8.1.14 Continue with Example 8.1.13 and show that

AB=

−137 −1323 −108

29 23 41

❆ .

Remark 8.1.15 In general, matrices A and B can be partitioned into more than 2 rows and columns and block multiplication can be carried out similarly.

Discussion 8.1.16 (Basic solution and Bases) Suppose we are given a LP where all m constraints are of the type ‘≤’, in this case, we will add a total of m slack variables, one to each constraint in order to obtain the LP in standard form. For example (Example 8.1.3),

Maximize z= 3x1+ 2x2

such that

x1+ 2x2+ s1 = 6

2x1+ x2 + s2 = 8

−x1+ x2+ s3 + s3 = 1

x2+ s4 + s4 = 2

x1, x2, s1, s2, s3, s4 0

(9)

We can express this LP in matrix form as follows: Maximize z= CX such that

(A, Im) = b X≥ 0 where

C= 3 2 0 0 0 0 X= x1 x2 s1 s2 s3 s4

T

A=

❇❇

1 2

2 1

−1 1

0 1

❈❈

b=

❇❇

❅ 6 8 1 2

❈❈

❆ .

Recall that in solving the LP using Simplex Method, we obtain a basic solution by setting n− m (in this case 2) variables to be zero and then solve the m equations for the remaining munknowns.

For the linear equation (A, Im)X = b, any m linearly independent column vectors of (A, Im) would correspond to a basic solution of (A, Im)X = b. Consequently, these m column vectors form a basis for Rmand the associated sub-matrix of (A, Im) must be invertible.

For example, our starting solution by Simplex Method was Non basic variables: x1, x2 (equal 0)

Basic variables: s1, s2, s3, s4

The 4 columns of (A, I4) that the basic variables correspond to are columns 3 to 6, which forms I4. Note that a basic solution of (A, I)X = b is also feasible if it satisfies X ≥ 0. Discussion 8.1.17 (Simplex table in matrix form) Suppose we partition the matrix X into XI and XI I where XI I corresponds to the elements of X (i.e. the variables) in the starting basis (i.e. the basic variables).

X= x1 x2 s1 s2 s3 s4

T

= (XI|XI I)T.

We will denote this basis (for this section only) by the matrix B = I. We further partition C into CI and CI I to correspond to XI and XI I.

C= 3 2 0 0 0 0 = (CI|CI I) . Now the LP in standard form can be written as

✒1 −CI −CI I

0 A I

✓ ✵❅XzI

XI I

❆ =0 b

(1)

(10)

During any iteration of Simplex Method, let XB represent the (set of) current basic variables with B (the matrix) being its associated basis. Correspondingly, let CB be the elements of C associated with XB.

For example, while solving Example 8.1.3 by Simplex Method, after the first iteration: Non basic variables: s2, x2 (equal 0)

Basic variables: s1, x1, s3, s4

So

XB= s1 x1 s3 s4

T

CB= 0 3 0 0 B=

❇❇

1 1 0 0

0 2 0 0

0 −1 1 0

0 0 0 1

❈❈

❆ .

We thus obtain

BXB=

❇❇

1 1 0 0

0 2 0 0

0 −1 1 0

0 0 0 1

❈❈

❇❇

❅ s1

x1

s3

s4

❈❈

❆ =

❇❇

❅ 6 8 1 2

❈❈

❆ = b.

CBXB= 0 3 0 0

❇❇

❅ s1

x1

s3

s4

❈❈

❆ = 3x1= z.

In matrix form,

1 −CB

0 B

✓ ✒ z XB

=

✒0 b

(2)

Since

1 CBB−1 0 B−1

✓ ✒1 −CB

0 B

=

✒1 0 0 I

= I,

✒1 CBB−1 0 B−1

is the inverse of

✒1 −CB

0 B

✓ .

Pre-multiply both sides of (2) by

✒1 CBB−1 0 B−1

, we have

✒ z XB

=

✒1 CBB−1 0 B−1

✓ ✒0 b

=

✒CBB−1b B−1b

(3) We can now fill in (partially) the simplex table at this iteration.

Basic z x1 x2 s1 s2 s3 s4 Solution

z CBB−1b

XB B−1b

(11)

To complete the other sections of the table, pre-multiply both sides of (1) by

✒1 CBB−1 0 B−1

✓ .

✒1 CBB−1 0 B−1

✓ ✒1 −CI −CI I

0 A I

✓ ✵

❅XzI XI I

❆ =1 CBB−1 0 B−1

✓ ✒0 b

which gives

✒1 CBB−1A− CI CBB−1− CI I

0 B−1A B−1

✓ ✵❅XzI

XI I

❆ =CBB−1b B−1b

We can now complete the simplex table at this iteration

Basic z x1 x2 s1 s2 s3 s4 Solution

z 1 CBB−1A− CI CBB−1− CI I CBB−1b

XB 0 B−1A B−1 B−1b

We thus have the matrix representation of the simplex table at any iteration.

Problem 8.1.18 Verify the simplex table you have obtained for Example 8.1.3 in each iter- ation using the matrix representation derived in Discussion 8.1.17.

Remark 8.1.19 Following the derivation in Discussion 8.1.17, we see that to obtain the simplex table at any iteration, the only new information required, after deciding the set of basic variables XB, is the computation of the matrix B−1.

Discussion 8.1.20 Let Bi be a square matrix corresponding to some basis in iteration i of the Simplex Method. From previous discussion, we know that the basis in iteration i + 1 differ from the basis in iteration i by only one vector, since exactly one variable leaves and one enters the set of basic variables to replace the leaving one.

Thus, if Bi+1 is a square matrix corresponding to the basis in iteration i + 1, Bi and Bi+1would differ in only one column. If we have already computed Bi

−1in iteration i, can we use it to compute Bi+1

−1in iteration i + 1?

Theorem 8.1.21 Let B be an invertible square matrix of order m and B= [b1 b2 · · · br · · · bm]

where bi, i = 1, 2, ..., m is the ith column of B. Suppose v (column vector) is a vector in Rm such that

Bnext = [b1 b2 · · · v · · · bm]

(12)

is invertible. Then the rth component of B−1vis non zero. Proof Let

B−1v= c =

❇❇

❇❇

❇❇

❅ c1

c2

: cr

: cm

❈❈

❈❈

❈❈

❆ .

We will show that cr 6= 0. Now

B−1v= c ⇔ v= Bc

⇔ v= c1b1+ c2b2+ ... + crbr+ ... + cmbm.

If cr = 0, then v is a linear combination of b1, ..., br −1, br+1, ..., bm which implies that the matrix Bnext = [b1 b2 · · · v · · · bm] is singular, a contradiction. Thus cr6= 0.

Theorem 8.1.22 Let B be an invertible square matrix of order m and B= [b1 b2 · · · br · · · bm]

where bi, i = 1, 2, ..., m is the ith column of B. Suppose v (column vector) is a vector in Rm such that

Bnext = [b1 b2 · · · v · · · bm] is invertible. Then

(a) BF = Bnext where

F = [e1 e2 · · · er −1 B

−1v er+1 · · · em]

where {e1, ..., em} is the standard basis for Rm. (b) Let

x= B−1v= x1 x2 ... xr ... xm

T

; y= 1

xr

−x1 −x2 ... 1 ... −xm

T

; E= [e1 e2 · · · er −1 y er+1 · · · em], then EF = I, and EB−1= B−1next.

Proof

(13)

(a)

BF = B[e1 e2 · · · er −1 B

−1v er+1 · · · em]

= [Be1 Be2 · · · Ber −1 BB

−1v Ber+1 · · · Bem]

= [b1 b2 · · · br −1 v br+1 · · · bm]

= Bnext

Note that by Theorem 8.1.21 and the definition of F , we know that det(F ) 6= 0, so F is invertible.

(b)

EF = E[e1 e2 · · · er −1 B

−1v er+1 · · · em]

= [Ee1 Ee2 · · · Eer −1 EB−1v Eer+1 · · · Eem]

= [e1 e2 · · · er −1 EB

−1v er+1 · · · em]

EB−1v = E

❇❇

❇❇

❇❇

❅ x1

x2

: xr

: xm

❈❈

❈❈

❈❈

= x1e1+ x2e2+ ... + xry+ ... + xmem

=

❇❇

❇❇

❇❇

❅ x1

0 : 0 : 0

❈❈

❈❈

❈❈

❆ +

❇❇

❇❇

❇❇

❅ 0 x2

: 0 : 0

❈❈

❈❈

❈❈

❆ + ... +

❇❇

❇❇

❇❇

−x1

−x2 : 1 :

−xm

❈❈

❈❈

❈❈

❆ +

❇❇

❇❇

❇❇

❅ 0 0 : 0 : xm

❈❈

❈❈

❈❈

=

❇❇

❇❇

❇❇

❅ 0 0 : 1 : 0

❈❈

❈❈

❈❈

= er.

Thus EF = I and consequently, since BF = Bnext and F = E−1, we have EB−1= B−1next

Example 8.1.23 Find C−1 if

B=

20 12 00 4 0 1

❆ B−1=

1

214 0 0 12 0

−2 1 1

❆ , C=

20 12 21 4 0 5

❆ .

(14)

Solution

x = B−1

21 5

❆ =

3 4 1 2

2

y = 1

2

3 4

12

1

❆ =

3 8

14 1 2

E =

1 0

3 8

0 1 −14

0 0 12

C−1 = EB−1

=

1 0

3 8

0 1 −14

0 0 12

1

214 0

0 12 0

−2 1 1

=

5

45838 1

2 1 414

−1 12 1 2

❆ .

Section 8.2 Graphs and networks

Discussion 8.2.1 There are many examples of sets with finitely many members in which some relation exists among certain members of the set. For example, if we consider the set of all students taking MA1508, and two particular students are said to be ‘related’ if their birthdays fall on the same month. The relation between members of the set could be directed or undirected, so for the example above on birthdays, the relation is undirected (since person A having the same birthday month as person B means that person B would also have the same birthday month as A).

On the other hand, if the set consists of 6 colleagues {x1, x2, x3, x4, x5, x6} in a company and there is a relation from xito xjif xisent an email to xjon a particular day. In this case, the relationship is clearly directed.

Definition 8.2.2 A (undirected) graph G is denoted by G = (V, E), where V (or V (G)) is the vertex set of G and E (or E(G)) is the edge set. A directed graph H is denoted by H = (V, A), where V (or V (H)) is again the vertex set of H and A (or A(H)) is the arc set.

For our purposes, all graphs are undirected unless otherwise stated.

(15)

Example 8.2.3 G is a graph and H is a directed graph with edge set E(G) = {(1, 4), (1, 5), (2, 3), (3, 5), (4, 5)} and arc set A(H) = {(x1, x2), (x2, x5), (x3, x2), (x3, x4), (x4, x6), (x5, x3)} respectively. Note

that in E(G), the edge (1, 4) can be similarly represented by (4, 1) while in A(H), the arc (x1, x2) is not the same as (x2, x1).

Definition 8.2.4 Several notations and definitions are required before moving on.

(a) For a graph G = (V, E), if u, v ∈ V (G) and there is an edge between u and v in G, we say that u and v are adjacent. We also write uv ∈ E(G) and also say that the edge uv is incident to u (or v). If H is a digraph and there is an arc from u to v then u is said to be adjacent to v and v is adjacent from u. In this case, we write uv ∈ A(H). (b) The order of a graph G (or directed graph H) is the number of vertices in G (or H).

The size of G (or H) is the number of edges (or arcs) in G (or H).

The main reason matrix algebra can be useful in the theory of graphs is because all the information contained in a graph or digraph can be represented in the form of a matrix. We will start with directed graphs.

Definition 8.2.5 Given a directed graph H with order n and size m, if the vertices are labeled x1 to xnand arcs are numbered a1 to am, the incidence matrix B of H is a m × n matrix such that for i = 1, ..., m, j = 1, ..., n,

bij=

✽❁

1 if arc aiis directed to vertex xj;

−1 if arc aiis directed from vertex xj; 0 otherwise.

It should be noted that in every row of B, there is exactly one −1 and one 1, with all other entries equal to 0.

(16)

Example 8.2.6 Consider the following digraph H with V (H) = {x1, x2, x3, x4, x5} and

A(H) = {a1, a2, a3, a4, a5, a6, a7}.

The incidence matrix for H is

B=

❇❇

❇❇

❇❇

❇❇

−1 1 0 0 0

0 −1 1 0 0

0 0 −1 1 0

0 0 0 1 −1

−1 0 0 0 1

0 −1 0 0 1

0 0 −1 0 1

❈❈

❈❈

❈❈

❈❈

❆ .

Remark 8.2.7

(i) For graphs considered in our course, we assume m ≥ n.

(ii) By investigating the fundamental subspaces associated with the incidence matrix of a directed graph H, if we consider H to represent an electrical circuit, we will see several interesting connections with basic electrical circuit laws.

(Nullspace of incidence matrix B)

Theorem 8.2.8 If B is the incidence matrix of a directed graph H of order n and size m, then nullity(B) = 1.

Proof Note that since B is a m × n matrix, the nullspace of B is a subspace of Rn. Let y= (y1, y2, ..., yn)T be a vector in the nullspace of B and bi, i = 1, ..., n be the i-th row of B. Then

By= 0 ⇔ y1b1+ y2b2+ ... + ynbn = 0. (1)

(17)

Since every row of B has one −1 and one −1 with the rest 0, we see that every row of B adds up to 0. Thus (y1, y2, ..., yn)T = (1, 1, ..., 1)T is a solution to (1), that is, (1, 1, ..., 1)T belongs to the nullspace of B.

Now if we think of yi, i = 1, 2, ..., n as the potential at vertex i in the electrical circuit H,

By= 0 ⇔ the difference in potential across each arc in H is zero. For example, if H is the digraph in Example 8.2.6, we have

By= 0 ⇔

✽❃

❃❃

❃❃

❃❃

❃❁

❃❃

❃❃

❃❃

❃❃

y2− y1 = 0 y3− y2 = 0

y4− y3 = 0

y4− y5 = 0

y5− y1 = 0 y5− y2 = 0 y5− y3 = 0.

(2)

From above, we have already seen that if the potential at all vertices are set at 1, then (2) is satisfied. So any change in the potential at any vertex i from 1 to c, c ∈ R will result in the potential at all other vertices to change to c also. Thus, all solutions to By = 0 are multiples of (1, 1, ..., 1)T which implies

nullspace of (B) = span{(1, 1, ..., 1)T} i.e. nullity(B) = 1.

Discussion 8.2.9 (Column space of incidence matrix B)

By Theorem 8.2.8 and Theorem 4.3.3, we know that the rank of any m × n incidence matrix B is n − 1, that is, the dimension of its column space is n − 1. What properties must u∈ Rmhave to be in the column space of B?

Consider the incidence matrix in Example 8.2.6. If u = (u1, ..., u7)Tis in the column space of B, then By = u for some y ∈ R5.

By= u ⇔

✽❃

❃❃

❃❃

❃❃

❃❁

❃❃

❃❃

❃❃

❃❃

y2− y1 = u1

y3− y2 = u2

y4− y3 = u3

y4− y5 = u4

y5− y1 = u5

y5− y2 = u6

y5− y3 = u7.

(18)

Performing Gaussian Elimination on (B|u),

❇❇

❇❇

❇❇

❇❇

−1 1 0 0 0 u1

0 −1 1 0 0 u2

0 0 −1 1 0 u3

0 0 0 1 −1 u4

−1 0 0 0 1 u5

0 −1 0 0 1 u6

0 0 −1 0 1 u7

❈❈

❈❈

❈❈

❈❈

Gaussian

−→ Elimination

❇❇

❇❇

❇❇

❇❇

−1 1 0 0 0 u1

0 −1 1 0 0 u2

0 0 −1 1 0 u3

0 0 0 1 −1 u4

0 0 0 0 0 u5+ u4− u1− u2− u3

0 0 0 0 0 u6+ u4− u2− u3

0 0 0 0 0 u7+ u4− u3

❈❈

❈❈

❈❈

❈❈

❆ .

Thus for u to belong to the column space of B, we must have

✽❁

u5+ u4− u1− u2− u3 = 0 u6+ u4− u2− u3 = 0 u7+ u4− u3 = 0.

(3)

Recall that for each i = 1, ..., 7, uican be thought of as the difference in potential across arc ai. The three expressions on the left hand side of (3) corresponds to the following three loops in H.

We now state the following theorem concerning the column space of B.

Theorem 8.2.10 The column space of an incidence matrix B contains vectors u such that the components of u, thought of as the difference in potential across the arcs in H, are such that the sum of potential difference around any loop in H is zero.

This is in fact, the much celebrated Kirchoff ’s Voltage Law.

Example 8.2.11 Examples of vectors belonging to the column space of the incidence ma- trix B from Example 8.2.6 are (1, 0, 1, 1, 1, 0, 0)T and (−1, 1, 0, 1, −1, 0, −1)T. For u = (1, 0, 1, 1, 1, 0, 0)T, we can use the row-echelon form of (B|u) above to solve for yi, that is, the potential at each vertex i in H. From the row-echelon form of (B|u), we have four non zero

(19)

equations, and five unknowns y1, ..., y5. By setting y1= 0 (arbitrarily), we have the following solution:

y1= 0, y2= 1, y3= 1, y4= 2, y5= 1.

Problem 8.2.12 Solve for the potentials at each vertex corresponding to the vector (−1, 1, 0, 1, −1, 0, −1) in the column space of B.

Discussion 8.2.13 (Row space of the incidence matrix B)

The row space of B is a subspace of Rnand every vector v that belongs to the row space of B is a linear combination of the row vectors of B. Since every row vector of B has the property that the sum of all its components is equal to zero, v also has this property. Next, recall that w = (1, 1, ..., 1)T ∈ Rn spans the nullspace of B, thus if v = (v1, v2, ..., vn)T,

v∈ row space of B ⇔ v1+ v2+ ... + vn= 0

⇔ vTw= 0

v· w = 0

⇔ vis orthogonal to the nullspace of B.

The above result is in fact true for any matrix A and not just for incidence matrices. Theorem 8.2.14 For any matrix A, the nullspace of A and the row space of A are orthog- onal. That is, if w and v are vectors in the nullspace and row space of A respectively, then w· v = 0.

Proof Suppose A has n rows. Let ri, i = 1, 2, ..., n represent the i-th row of A. Since v belongs to the row space of A, v = c1r1+ c2r2+ ... + cnrn for some scalars c1, c2, ..., cn. Since w belongs to the nullspace of A,

Aw= 0 ⇔

❇❇

❅ r1

r2

: rn

❈❈

❆ w = 0 ⇔ ri· w = 0 for i = 1, 2, ..., n.

Thus

w· v = w· (c1r1+ c2r2+ ... + cnrn)

= c1(w · r1) + c2(w · r2) + ... + cn(w · rn)

= 0.

We now turn our attention to matrices associated with undirected graphs.

(20)

Definition 8.2.15 Given a graph G of order n, with V (G) = {1, 2, ..., n}, the adjacency matrix A of G is a n × n matrix such that

aij=

✚ 1 if vertex i and j are adjacent; 0 otherwise.

Note that the adjacency matrix of any graph G is always symmetric.

A n × n adjacency matrix A can also be defined for a directed graph H, with V (H) = {x1, x2, ..., xn} in the following way.

aij=

✚ 1 if vertex xiis adjacent to vertex xj; 0 otherwise.

Note that the adjacency matrix of a directed graph is not necessarily symmetric.

Example 8.2.16 The adjacency matrices of the graph G and the directed graph H in Ex- ample 8.2.3 are

❇❇

❇❇

0 0 0 1 1

0 0 1 0 0

0 1 0 0 1

1 0 0 0 1

1 0 1 1 0

❈❈

❈❈

and

❇❇

❇❇

❇❇

0 1 0 0 0 0

0 0 0 0 1 0

0 1 0 1 0 0

0 0 0 0 0 1

0 0 1 0 0 0

0 0 0 0 0 0

❈❈

❈❈

❈❈

respectively.

There are several structural quantities relating to a graph of directed graph that we are often interested in. Some of these are defined below.

Definition 8.2.17

1. A walk in a graph G is an alternating sequence

W : v0, e1, v1, e2, ..., vn−1, en, vn n≥ 1

of vertices vi, i = 0, ..., n in V (G) and edges ej, j = 1, ..., n in E(G) such that for each i = 1, ..., n, ei = vi−1vi is an edge in G between vi−1 and vi. We say that W is a v0− vn walk. The length of such a walk is n. Sometimes, if there is no confusion, we may simply represent the walk W as v0v1...vn−1vn(without explicitly writing the edges between successive vertices in W ).

We may also define a walk W in a directed graph H similarly, W : x0, a1, x1, a2, ..., xn−1, an, xn n≥ 1 where each arc ai, i = 1, ..., n must be an arc in A(H) from xi−1 to xi.

(21)

2. A path is a walk where no vertices is repeated in W . A directed path in a directed graph can be defined similarly.

3. A cycle is a walk where no vertices is repeated in W and v0= vn, that is, the starting vertex and the ending vertex of the walk are identical. A directed cycle in a directed graph can be defined similarly.

4. For a vertex v0 in a graph G, the degree of v0 is the number of vertices in G that are adjacent to v0. If H is a directed graph and x0 is a vertex in H, then the in-degree of x0 is the number of vertices in H that are adjacent to x0. The out-degree of x0 is the number of vertices in H that is adjacent from x0.

5. A graph G is said to be connected if for any pair of vertices u, v ∈ V (G), there is a u− v path in G.

Example 8.2.18 Consider the graph G and the directed graph H shown below.

(i) v0v1v2v0v3 is a v0− v3 walk of length 4 in G while x0x1x2x3x0x4 is a x0− x4 walk of length 5 in H.

(ii) v0v1v2v3is a path of length 3 in G while x0x1x2x3 is a directed path of length 3 in H. (iii) v0v3v4v0 is a cycle of order 3 in G while x0x4x3x0 is a directed cycle of order 3 in H.

Note that we often call a cycle of order 3 a triangle.

(iv) The degrees of vertices v0, v1, v2, v3, v4 are 4, 2, 3, 3, 2 respectively. The out-degree of x0

is 3 while the in-degree of x2 is 2. (v) G is a connected graph.

(22)

Discussion 8.2.19

Consider the graph G from Example 8.2.3. Notice that if A is the adjacency matrix for G, then the (i, j) entry of A is 1 if and only if there is a walk of length 1 from vertex i to vertex j in G. In this case, a walk of length 1 is simply an edge.

Consider the matrices

A2=

❇❇

❇❇

0 0 0 1 1

0 0 1 0 0

0 1 0 0 1

1 0 0 0 1

1 0 1 1 0

❈❈

❈❈

❇❇

❇❇

0 0 0 1 1

0 0 1 0 0

0 1 0 0 1

1 0 0 0 1

1 0 1 1 0

❈❈

❈❈

=

❇❇

❇❇

2 0 1 1 1

0 1 0 0 1

1 0 2 1 0

1 0 1 2 1

1 1 0 1 3

❈❈

❈❈

.

A3=

❇❇

❇❇

2 0 1 1 1

0 1 0 0 1

1 0 2 1 0

1 0 1 2 1

1 1 0 1 3

❈❈

❈❈

❇❇

❇❇

0 0 0 1 1

0 0 1 0 0

0 1 0 0 1

1 0 0 0 1

1 0 1 1 0

❈❈

❈❈

=

❇❇

❇❇

2 1 1 3 4

1 0 2 1 0

1 2 0 1 4

3 1 1 2 4

4 0 4 4 2

❈❈

❈❈

.

Why is the (1, 2) entry of A2 equal to 0 while the (1, 3) entry of A2 is 1? What does the (4, 1) entry of A3represent? In general, for k ≥ 1, what does the (i, j) entry of Ak tell us? Theorem 8.2.20 If A is the adjacency matrix of a graph G of order n, then the (i, j) entry of Ak, k ≥ 1, denoted by ak,ij, is the number of i − j walks in G of length k.

Proof We will prove the statement by mathematical induction. The statement is clearly true when k = 1, since the (i, j) entry in A is 1 if and only if there is an edge between vertex i and j. Assume that the statement is true for k = r − 1, that is, ar−1,ijis the number of walks in Gfrom vertex i to j of length r − 1.

(23)

Consider the (i, j) entry in Ar. Since Ar= Ar−1A,

ar,ij= ar−1,i1a1,1j+ ar−1,i2a1,2j+ ar−1,i3a1,3j+ ... + ar−1,ina1,nj=

n p=1

ar−1,ipa1,pj. (1)

For each p = 1, ..., n, a1,pj= 1 if and only if there is an edge in G between vertex p and j. So if ar−1,ipis the number of i − p walks in G of length r − 1, ar−1,ipa1,pjis the number of i − j walks in G of length r with vertex p preceding vertex j in each walk. Summing ar−1,ipa1,pj

over all p = 1, ..., n (i.e. expression (1)), gives the total number of i − j walks of length r in G. Thus the statement is true when k = r and the proof is complete.

Example 8.2.21 Consider the directed graph H in Example 8.2.18. The adjacency matrix for H is

A=

❇❇

❇❇

0 1 1 0 1

0 0 1 0 0

0 0 0 1 0

1 0 0 0 0

0 0 0 1 0

❈❈

❈❈

.

Consider

I− A =

❇❇

❇❇

1 −1 −1 0 −1

0 1 −1 0 0

0 0 1 −1 0

−1 0 0 1 0

0 0 0 −1 1

❈❈

❈❈

.

It can be verified that det(I − A) = 0, so the matrix I − A is singular.

Suppose we reverse the arc from x3 to x0 so that the directed graph H is as follows.

(24)

With the updated adjacency matrix A, we find that

I− A =

❇❇

❇❇

1 −1 −1 −1 −1

0 1 −1 0 0

0 0 1 −1 0

0 0 0 1 0

0 0 0 −1 1

❈❈

❈❈

is now invertible (find its inverse).

In general, if A is the adjacency matrix of a directed graph H, what does the invertibil- ity/singularity of I − A tell us about H?

Theorem 8.2.22 If A is the adjacency matrix of a directed graph H, then I −A is invertible if and only if H does not contain any directed cycles.

Definition 8.2.23 A graph G is said to be bipartite if its vertex set V (G) can be partitioned into two sets V1(G) and V2(G) (that is, V (G) = V1(G) ∪ V2(G) and V1(G) ∩ V2(G) = ∅) such that every edge in E(G) is an edge between a vertex in V1(G) and a vertex in V2(G). Example 8.2.24 It is clear (from the way it is drawn) that G1 is a bipartite graph. G2 is also a bipartite graph (can you find a way to partition V (G2)?). However, G3is not a bipartite graph. (Why?)

Definition 8.2.25 Given a bipartite graph G with V (G) = V (G1) ∪ V (G2) and |V (G1)| =

|V (G2)| = k for some integer k. We say that G has a complete matching if there are k edges in E(G) such that each of the vertices in V (G) is incident to exactly one of the k edges.

(25)

Example 8.2.26 Consider the bipartite graph G1 in Example 8.2.24. G1 has a complete matching as shown below.

Example 8.2.27 (Dating Problem)

Consider the scenario where a group of k men are being selected to be matched to k women in a dating agency. After looking at the bio-data of the k men available, each of the k women has indicated which of the k men they are willing to date (each women may choose more than one men). The problem is, given each women’s preference, can the dating agency successfully match all the k women with a man each?

We may represent the k women and k men, together with the women’s preferences using a bipartite graph G where V (G) = {w1, w2, ..., wk} ∪ {m1, m2, ..., mk} and there is an edge wimj in E(G) if woman wihas indicated she is willing to date man mj. The dating problem now reduces to finding a complete matching in G.

We may also represent the women’s preferences using a k×k matrix. Consider the following bipartite graph G. We may represent G by the compatibility matrix C where cij = 1 if and

only if women wiindicated that she is willing to date man mj.

C=

❇❇

1 0 0 0

1 1 1 0

0 0 0 1

0 0 0 1

❈❈

❆ .

(26)

Does G have a complete matching?

It turns out that there is a necessary and sufficient condition for such bipartite graphs (where |V (G1)| = |V (G2)| = k) to have a complete matching.

Theorem 8.2.28 A complete matching exists if and only if for every subset of r women (1 ≤ r ≤ k), there are at least r men whom, among these r women, are willing to date. Example 8.2.29 The bipartite graph in Example 8.2.27 does not have a complete matching since {w3, w4} are only willing to date {m4}. Note that if we consider the compatibility 4 × 4 matrix C, we are able to cover all the 1s in the matrix with less than 4 horizontal or vertical lines.

The following theorem is equivalent to Theorem 8.2.28, stated in terms of the compatibility matrix C.

Theorem 8.2.30 A complete matching exists if and only if the minimum number of hori- zontal or vertical lines required to cover all the 1s in C is k.

Problem 8.2.31 For each of the following bipartite graphs, write down its compatibility matrix C. Using Theorem 8.2.30, determine if a complete matching exists.

The dating problem above is actually a special case of the more general assignment problem, introduced in the next section.

(27)

Section 8.3 Assignment Problems

Example 8.3.1 Suppose I want to buy three household electrical items (an oven, an electric kettle and a television) from my local neighborhood. There are three stores in my neighbor- hood and each of them has all the three items that I want but at different prices. In order not to offend each of the store owners, I decided that I will buy one item from each store, with the objective to minimize my total expenditure. The prices of each item at each store is as follows.

Store A Oven: $40 Kettle: $16 Television: $299 Store B Oven: $38 Kettle: $19 Television: $305 Store C Oven: $41 Kettle: $20 Television: $302 If I put the information above into a cost matrix D,

D=

4038 1619 299305 41 20 302

the problem now is how to choose three entries from D such that the total of the three entries is minimized but there is exactly one entry chosen from each row and column.

For this example, there are a total of 6 (why?) possible combinations, so it is still reasonable to do this by considering the costs of all the combinations.

4038 1916 299305 41 20 302

4038 1619 305299 41 20 302

3840 1619 299305 41 20 302

$40+19+302=$361 $40+305+20=$365 $16+38+302=$356

3840 1619 299305 41 20 302

4038 1619 305299 41 20 302

4038 1916 299305 41 20 302

$299+38+20=$357 $16+305+41=$362 $299+19+41=$359

In this case, I have found an optimum way of minimizing my cost subject to the given re- striction. This is an example of an assignment problem. Unfortunately, as the number of combinations increases (think of buying 6 items from 6 stores), this way of considering the costs of all the possible combinations is no longer feasible. We will next consider a way of dealing with this.

Remark 8.3.2 Consider an assignment problem with the following cost matrix

D=

❇❇

❇❇

0 4 6 0 4

0 1 0 3 5

6 0 4 2 1

7 5 3 0 0

2 2 0 0 2

❈❈

❈❈

.

(28)

Although the size of D is larger than the one in the previous example, it is much easier to find an optimum solution to this assignment problem (why?). Can you find an optimum solution? Very few assignment problems actually have costs matrices that are so easy to solve as in the matrix above. However, the following theorem leads us to a method to find optimum solutions to any assignment problem.

Theorem 8.3.3 If a constant c is added or subtracted from all the entries of any row or any column of a cost matrix D, resulting in another cost matrix D, then an optimum assignment corresponding to D is also an optimum assignment corresponding to D.

We now introduce a method known as the Hungarian method, which is a five step procedure that repeatedly changes the entries in a given cost matrix D of order n. The result is a cost matrix D with non negative entries that contains an optimum assignment consisting entirely of zero entries. By Theorem 8.3.3, such an assignment would be an optimum assignment to the original cost matrix D.

Algorithm 8.3.4

Step 1 For each row of D, let k be the minimum of all the entries in the row. Subtract k from all entries in the row. Let the resulting matrix be D1.

Step 2 For each column of D1, let r be the minimum of all the entries in the column. Subtract rfrom all entries in the column. Let the resulting matrix be D2.

Note that after steps 1 and 2, each row and column of D2 would have at least one zero entry and all other entries non negative.

Step 3 Draw the minimum number of lines (horizontal or vertical) so that all the zero entries of D2are covered.

Step 4 If the minimum number of lines used in Step 3 is n, an optimum assignment of zeros exists and we are done. If the minimum number of lines is less than n, an optimum assignment of zeros is not yet possible. Proceed to Step 5.

Step 5 Determine the smallest entry not covered by lines drawn in Step 3. Suppose the entry is m. Subtract m from all uncovered entries in D2 and add m to all entries covered by botha horizontal and a vertical line. Return to Step 3.

Remark 8.3.5

1. There are existing algorithms that determines the minimum number of lines required in Step 3 and they are used when the cost matrix concerned is large. For our purposes, we will use trial and error.

2. If an optimum assignment of zeros exists in Step 4, there are again algorithms which will find such an assignment. These will not be discussed here.

(29)

3. In Step 5, what we are effectively doing is subtracting m from each uncovered row and then adding m to each covered column. By Theorem 8.3.3, the optimum assignment is not affected by such an operation.

Example 8.3.6 Apply the Hungarian method to the following cost matrix D to obtain an optimum assignment.

D=

❇❇

❇❇

12 9 7 7 10

15 11 8 13 14

9 6 5 12 12

6 9 13 7 10

8 13 12 9 13

❈❈

❈❈

.

1. Subtract 7 from the first row, 8 from the second row, 5 from the third row, 6 from the fourth row and 8 from the fifth row.

D1=

❇❇

❇❇

5 2 0 0 3

7 3 0 5 6

4 1 0 7 7

0 3 7 1 4

0 5 4 1 5

❈❈

❈❈

.

2. Subtract 1 from the second column and 3 from the fifth column.

D2=

❇❇

❇❇

5 1 0 0 0

7 2 0 5 3

4 0 0 7 4

0 2 7 1 1

0 4 4 1 2

❈❈

❈❈

3. It is clear that we cannot cover all the zero entries with 1,2 or 3 lines. We can do so with 4 lines.

D2=

❇❇

❇❇

5 1 0 0 0

7 2 0 5 3

4 0 0 7 4

0 2 7 1 1

0 4 4 1 2

❈❈

❈❈

4. Since the number of lines required is less than 5, we do not have an optimum assignment of zeros yet.

(30)

5. The smallest entry not covered by any line is 1, so we subtract 1 from all uncovered entries and add 1 to all entries covered by both horizontal and vertical lines. Update D2.

D2=

❇❇

❇❇

6 1 1 0 0

7 1 0 4 2

5 0 1 7 4

0 1 7 0 0

0 3 4 0 1

❈❈

❈❈

.

6. We can no longer cover all the zeros with less than 5 lines (try it!). Thus we have an optimum assignment of zeros (not unique) as follows.

❇❇

❇❇

6 1 1 0 0

7 1 0 4 2

5 0 1 7 4

0 1 7 0 0

0 3 4 0 1

❈❈

❈❈

.

This corresponds to an optimum assignment to the original cost matrix D with a total cost of 39.

❇❇

❇❇

12 9 7 7 10

15 11 8 13 14

9 6 5 12 12

6 9 13 7 10

8 13 12 9 13

❈❈

❈❈

.

Remark 8.3.7 The examples seen so far are standard assignment problems which have sev- eral assumptions regarding the problem and the cost matrix D. In actual fact, there are variants to the standard problem which we may also solve using the Hungarian method.

(a) The cost matrix D does not have to be a square matrix. In other words, the number of assigned items may be larger or smaller than the number of entities that these items are assigned to (see Problem 8.3.8).

(b) The entries in D do not have to be integers. In fact, they do not have to be non negative. (c) The assignment problem does not have to be one of minimization (see Problem 8.3.8).

Problem 8.3.8 I have four rare gems that I wish to sell via an auction (highest bidder wins). I invited five potential buyers to bid for my gems and each of them submitted their respective bids to me. I would like to sell at most one gem to each bidder. Their bids for my gems (labeled G1, G2, G3 and G4) are as follows.

(31)

Bid for G1 Bid for G2 Bid for G3 Bid for G4

Bidder 1 $150 $65 $210 $135

Bidder 2 $175 $75 $230 $155

Bidder 3 $135 $85 $200 $140

Bidder 4 $130 $70 $190 $130

Bidder 5 $170 $50 $200 $160

(a) How should I assign my gems to the five bidders so as to maximize my total sales? (b) Suppose I am willing to sell at most two gems to Bidder 2 (only). Is there any change

to my optimum assignment?

Section 8.4 Markov Chains

Discussion 8.4.1 Consider the matrix A =

✒0.96 0.01 0.04 0.99

used in the population example in Chapter 6 (Example 6.1.1). The matrix belongs to a special class of matrices known as stochastic matrices defined in Exercise 6 Question 14, reproduced below. Such matrices are the subject of discussion in this section.

Definition 8.4.2 A square matrix (aij)n×nis called a stochastic matrix if all the entries are non negative and the sum of entries in each column is 1, i.e. a1i+ a2i+ ... + ani= 1 for i= 1, 2, ..., n.

Example 8.4.3 Market research has shown that a small town’s population exhibit the fol- lowing preferences when it comes to choosing fresh milk. Of those using Brand A in any month, 70% continue to use it the following month, while 30% switch to Brand B; of those using Brand B in any month, 80% continue to use it the following month while 20% switch to Brand A.

These findings can be represented as in the diagram below.

参照

関連したドキュメント

As we have said in section 1 (Introduction), using the mentioned tree T , Barioli and Fallat gave the first example for which the equivalence between the problem of ordered

Specifically, our main result in this case, Theorem 2.4, establishes the pre- cise convergence rate of the normalised probability mass function of the approximating Markov chain to

Following Speyer, we give a non-recursive formula for the bounded octahedron recurrence using perfect matchings.. Namely, we prove that the solution of the recur- rence at some

The focus has been on some of the connections between recent work on general state space Markov chains and results from mixing processes and the implica- tions for Markov chain

A related model is the directed polymer in a random medium (DPRM), in which the underlying Markov chain is generally taken to be SSRW on Z d and the polymer encounters a

, 6, then L(7) 6= 0; the origin is a fine focus of maximum order seven, at most seven small amplitude limit cycles can be bifurcated from the origin.. Sufficient

We will show that under different assumptions on the distribution of the state and the observation noise, the conditional chain (given the observations Y s which are not

Key words and phrases: higher order difference equation, periodic solution, global attractivity, Riccati difference equation, population model.. Received October 6, 2017,