ࡱ> :<789q` \bjbjqPqP .::]NNNNPNQQQQQQQQEGGGGGG$hl\kQQQQQkQQJrJrJrQQQEJrQEJrJr DٝQQ rNn`Z M&E0NsfȦjLȦLٝȦٝlQQJrQQQQQkkn6QQQNQQQQ$KNN  The Simplex Algorithm and the Dual Simplex Algorithm: Mathematical Foundations and Examples1 Linear Programming (LP): The Simplex Algorithm Primal and Dual (LP) Problems Definition 1. An LP problem is said to be primal if it has the form maximize f(x) = " j=1 cjxj + d (1) subject to " j=1 aijxj d" bi, 1 d" i d" m, xj e" 0, 1 d" j d" n, 1) This is based on Peter Morris (Chapter 3) where A = (aij) is an m x n coefficient matrix, c is an n-tuple of numbers, d is a constant, and b is an m-tuple of numbers. Definition 2. Consider the primal problem (1). The dual problem corresponding to it is: minimize g(y) = "mi=1 biyi + d (2) subject to "mi=1aijyi e" cj, 1 d" j d" n, yi e" 0, 1 d" i d" m. Theorem 1 If both the primal problem and its corresponding dual are feasible, then f(x) d" g(y), for any feasible vector x of the primal and any feasible vector y of the dual. Thus, max f(x) d" min g(y). Proof. Compute f(x) = "nj=1cjxj + d d" "nj=1"mi=1 aijyixj + d = "mi=1("nj=1 aijxj)yi + d d" "mi=1 biyi + d = g(y). The second inequality is obtained by maximizing over x on the left and then minimizing over y on the right. k Corollary 2. The following statements hold: If both the primal and its corresponding dual are feasible, then both are bounded. If the primal is unbounded, then the dual is infeasible. If the dual is unbounded, then the primal is infeasible. Proof. For a fixed feasible vector y for the dual, f(x) is bounded above by g(y), and thus the primal problem is bounded. Similarly, the dual problem is bounded. The other two statements follow easily from the first. k Example 1. Consider the problem maximize x1 " x2 " x3 + x4 subject to x1 " x3 d" 0 x2 " x4 d" 1, x1, x2, x3, x4 e" 0. Is it feasible? Is it bounded? Solution: The problem is primal; it is feasible because (0, 0, 0, 0) satisfies the constraints. It is unbounded because taking x4!", the objective function goes to ". By Corollary 2(2) its dual is infeasible. j Basic Forms and Pivots Consider a primal LP problem (1). For each of the m constraints define a slack variable by xn + i = bi " "nj=1 aijxj. Notice that x =(x1, & , xn) is a feasible vector if and only if xk e" 0, 1 d" k d" n + m. Using the slack variables, we rewrite (1) as maximize f(x) = "nj=1cjxj + d (3) subject to "nj=1 aijxj " bi = " xn+i,1 d" i d" m, xj e" 0, 1 d" j d" n. This form of the primal problem is called the (primal) basic form. We emphasize that it is mathematically equivalent to the original primal form in the sense that solving one is the same as solving the other. In the context of basic forms, the variables on the right-hand side of the constraints are called basic variables while the other variables are called nonbasic variables. The set of basic variables is called the basis corresponding to the basic form. With the use of linear algebra, we can compute a new basis from an old one. To do so, choose in basic form (3) any nonzero coefficient akl, where 1 d" k d" m and 1 d" l d" n. Thus akl is the coefficient of xl in the equation for " xn+k. Since akl `" 0, we can solve the equation to get xl in terms of xn+k and the remaining nonbasic variables. Then we substitute for xl in the other constraints and in the objective function. The result is another basic form, different from the first in that a basic variable and a nonbasic variable have traded places. The operation we have just carried out is called a pivot, and we say that we pivot on the coefficient akl. It is important to realize that the new basic form is again mathematically equivalent to the old one, and thus to the original primal problem. There are, in general, many basic forms for each primal problem. In the general case where there are n unknowns in the primal problem and m constraints, the total number of possible bases corresponding to basic forms is the binomial coefficient Cmm+n. The actual number of basic forms might be less than this quantity. Given a basic form, the basic variables and the objective functions are expressed in terms of the nonbasic variables. If arbitrary values are assigned to the nonbasic variables, then the values of the basic variables are determined, and so we obtain an (n + m)-tuple (x1, & , xn+m). In case each xk e" 0, we say that this (n + m)-tuple is feasible. If (x1, & , xn+m) is feasible, then the vector (x1, & , xn) is, as already noted, a feasible vector. The most important case of this computation appears when the value zero is assigned to each nonbasic variable. Definition 3. Given a basic form for a primal LP problem with n unknowns and m constraints, the corresponding basic solution is the (m + n)-tuple obtained by setting the n nonbasic variables to zero and then solving the m basic variables from the constraints. Note that the value of the objective function at the basic solution is the constant term in its equation. Definition 4. A basic form is feasible if its basic solution is feasible. A feasible basic solution is optimal if the value of the objective function at the basic solution is a maximum. In this case, the basic form is also called optimal. Our further goal is to describe the simplex algorithm, which is a numerical method for solving primal problems. The idea of it is to start with a feasible basic form and then to pivot in such a way that the new basic form is still feasible and gives a larger value of the objective function. This process is repeated until the maximum is reached. The algorithm includes a simple method for deciding which coefficient to pivot on next. In order to recognize feasible and optimal basic forms, we need Theorem 3. The following hold: A basic form is feasible if and only if the constant term in each constraint is nonpositive. Suppose a basic form is feasible. If each coefficient (of a nonbasic variable) in the equation for the objective function is nonpositive, then the basic form is optimal. Proof. (1) This is clear since the value of a basic variable in the basic solution is the negative of the constant term in its equation. (2) We can write the objective function as f(x) = "m+nk=1 ckxk + d, where ck = 0 if xk is basic (since basic variables do not appear in the equation for the objective function). Our hypothesis is that ck d" 0 for each k. Now, if z is the basic solution, we have f(z) = d. Then if x is any feasible vector, we have, since each xk e" 0, f(x) = "m+nk=1 ckxk + d d" d = f(z). Thus, max f(x) = f(z). k Example 2.Consider the problem maximize " x3 " 2x2 + x6 + x4 + 1 subject to " 2x2 + x6 + x4 " 1 = "x5 x3 + 3x2" x6 " 2x4 " 1 = "x1, xi e" 0, i = 1,& , 6. Its basis is {x5, x1}. This basic form is feasible but not optimal. Pivot on coefficient of x4 in the equation for "x5 gives a basic form both feasible and optimal for which: max f = 2, x1 = 3, x2 = x3 = 0, x4 = 1. j Dual Basic Forms Consider a dual problem (2). For each of the n constraints, define a surplus variable by ym+j = "mi=1 aijyi " cj. We see that (y1,& , ym) is a feasible vector for the dual problem iff yk e" 0 for 1 d" k d" m + n. We write the dual problem as minimize "mi=1 biyi + d subject to ym+j = "mi=1 aijyi " cj, 1 d" j d" n, yi e" 0, 1 d" i d" m. This is a dual basic form. The variables on the left-hand side of the equality signs are basic and the others are nonbasic. Just in the primal case, we can pivot so as to interchange a basic variable and a nonbasic variable and produce a new basic form. Given a dual basic form, the definition of feasible (n + m)-tuple is the same as in the case of primal basic forms. Also, the basic solution corresponding to a dual basic form is obtained by setting the nonbasic variables equal to zero, and then solving for the basic variables. Clearly, the value of a basic variable in a basic solution is simply the constant term in its equation. We define a basic solution (y1,, ym+n) (and its dual basic form) to be feasible if yk e" 0 for 1 d" k d" m + n. The value of the objective function at the basic solution is clearly equal to the constant term in its equation. A feasible basic solution (and its dual basic form) is optimal if the value of the objective function is a minimum. Theorem 4. The following are true: A dual basic form is feasible if and only if the constant term in each constraint equation is nonnegative. Suppose a dual basic form is feasible. If each coefficient (of a nonbasic variable) in the equation for the objective function is nonnegative then the dual basic form is optimal. The Simplex Algorithm We need a more compact way of writing a basic form. It is called a tableau. When the primal problem has n unknowns and m constraints, the size of the tableau is (m + 1)x (n + 1). All column but the last one are labeled by the nonbasic variables; the last column is labeled " 1. This label will be explained shortly. The first rows but the last one are labeled on the right by the basic variables  = " xt . The last row is labeled by the objective function = f. Each row is to be read as an equation the numbers in the row are multiplied by the labels at the tops of the corresponding columns, and these products are added. Example 2 (continuation). The optimal basic form in Example 2 is maximize "x3 " x2 " x5 + 2, subject to " 2x2 + x6 + x5 " 1 = "x4 x3 " x2 + x6 + 2x5 " 3 = "x1, xi e" 0, i = 1,& , 6. The corresponding tableau is x3 x2 x6 x5 "1 0 "2 1 1 1 = "x4 1 "1 1 2 3 = "x1 "1 "1 0 "1 "2 = f j The basic solution is readily read off the tableau. The values of the basic variables are simply the numbers in the corresponding right-hand column; the value of the objective function is the negative of the number in the lower right-hand corner. The next theorem translates Theorem 3 into the context of tableaus. Theorem 5. Consider a tableau of size (m + 1)x(n + 1). Then we have: The tableau is feasible if and only if each entry in the right-hand column (not containing the bottom one) is nonnegative. Suppose that the tableau is feasible. If each entry in the bottom row (not containing the right-hand one) is nonpositive, then the tableau is optimal. The next theorem shows how to compute, when pivoting, the numbers in the new tableau from the old one. Theorem 6. Let T be a tableau of size (m+1)x(n+1). Suppose a pivot is carried out on entry tkl. In other words, the pivot is on the coefficient of the nonbasic variable xp (labeling column l) in the constraint equation for the basic variable xq (labeling row k). Of course, 1 d" k d" m, 1 d" l d" n, and tkl `" 0. Let T be the tableau resulting from the pivot. Then, if 1 d" i d" m + 1 and 1 d" j d" n + 1, we have: t kl = 1/ tkl. If j `" l, then t kj = tkj/tkl. If i `" k, then t il = " til/tkl. If i `" k and j `" l, then t ij= (tijtkl " tiltkj)/ tkl. Proof. We prove only (4), since the other cases are similar but easier. To do this, let  be the label of column j. Thus  is either one of the nonbasic variables other than xp, or the constant "1. Also, let  be the label on row i. Thus  is either the negative of a basic variable other than xq, or the objective function. Now, solving for xp from the constraint equation for " xq, we have xp = " (tkj/tkl)  + , (4) where  is a sum of terms not involving . Then, from row i of T, we have  = tilxp + tij + , where  is a sum of terms not involving xp or . Substituting from (4) we obtain  = til ["(tkj/tkl) + ] + tij + . Thus,  = {(tijtkl " tiltkj)/tkl} + , where  consists of terms not involving . Since t ij is the coefficient of  in the equation for , the proof is complete. k The rules for pivoting in a tableau are summarized in the following algorithm. Algorithm 1 (The pivoting algorithm) We are given a tableau T of size (m+1)x(n+1), and an entry tk l`" 0.We are to compute a new tableau T of the same size as T. Interchange the labels of column l and row k. The other labels on T are the same as on T. t kl = 1/tkl. If j `" l, then t kj = tkj/tkl. If i `" k, then t il = " til/tkl. If i `" k and j `" l, then t ij = (tijtkl " tiltkj)/tkl. Theorem 7 Consider a feasible tableau for a primal problem with n unknowns and m constraints. Suppose that one of the first n entries in the bottom row of the tableau is positive, but all the other entries in the column containing that entry are nonpositive. Then the problem is unbounded. Proof. Suppose that it is column j which has a positive entry at the bottom and which has all nonpositive entries otherwise. Then column j is labeled by some nonbasic variable , say xq. Given any positive number x, define an (m + n)-tuple as follows: To xq, assign the value x; to a nonbasic variable xl, l `" q, assign the value zero; then solve for the basic variables from their constraint equations. Then each basic variable in this (m + n)-tuple is nonnegative because of the condition on the entries in column j. Since the coefficient of xq in the objective function is positive, the objective function has limit +" as x ! ". Thus, the objective function is unbounded. k Example 3.Consider the problem max x1 subject to x1 " x2 d" 1, x1, x2 e" 0. The initial tableau is x1 x2 "1 1 "1 1 = "x3 1 0 0 = f This tableau is feasible but not optimal. Theorem 7 does not indicate that the problem is unbounded. Pivot on the coefficient of x1 in the equation for "x3 gives the tableau x3 x2 "1 1 "1 1 = "x1 "1 1 "1 = f This tableau is feasible. Theorem 7 tells us that the problem is unbounded.j Algorithm 2 (The Simplex Algorithm) We are given a feasible tableau T of size (m+1)x(n+1). If tm+1,j d" 0 for 1 d" j d" n, then STOP (the tableau is optimal). Choose any l with 1 d" l d" n such that tm+1,l > 0. (The nonbasic variable labeling column l is called the entering variable.) If til d" 0 for 1 d" i d" m, STOP (the problem is unbounded). Choose any k with 1 d" k d" m such that tkl > 0 and tk,n+1/tkl = min {ti,n+1/til| 1 d" i d" m and til > 0}. (The basic variable labeling row k is called the leaving variable.) Pivot on tkl and replace T by the tableau resulting from this pivot. (Entry tkl is called the pivot entry.) Go to step (1). In the next theorem, we verify that the algorithm produces a sequence of feasible tableaus such that the values of the objective function are nondecreasing. Theorem 8. The following hold for the simplex algorithm: After each pivot [Step (5)], the new tableau is feasible. After each pivot, the value of the objective function for the new tableau is greater than or equal to that for the previous tableau. Proof. (1) We are pivoting on entry tkl of T to produce T. We must verify that ti,n+1 e" 0 for 1 d" i d" m. This is clearly true for i = k, so assume i `"k. Then t i,n+1 = (ti,n+1tkl " tiltk,n+1)/tkl. Now, we know that ti,n+1, tkl, tk,n+1 are all nonnegative. There are two possibilities. If til d" 0 then t i,n e" 0. On the other hand, if til > 0 then, by the choice of k, tk,n+1/tkl d" ti, n+1/til. Multiplying both sides by tkltil, we get tiltk.n+1 d" ti,n+1tkl. This implies that t i,n+1 e" 0. (2) The value of the objective function for T is "tm+1,n+1; for T , it is "t m+1,n+1. Now, t m+1,n+1 = (tm+1,n+1tkl " tm+1,ltk,n+1)/tkl d" tm+1,n+1tkl/tkl = tm+1,n+1. Taking negatives on both sides completes the proof. k Example 4. Solve the problem max x1 + 2x2 + 3x3 subject to x1 + x2 + x3 d" 3 "x1 + x2 d" 0, x1, x2, x3 e" 0. Hint: With a suitable choice of the pivot at the beginning you need one pivot. j Avoiding Cycles and Achieving Feasibility It is possible for the simplex algorithm to go into an infinite loop and never deliver a solution to the problem. There are several methods for avoiding this difficulty. After presenting one such method, we will discuss the question of how to find an initial feasible tableau so that the simplex algorithm can be started. Degeneracy and Cycles Definition 5. Let T be an (m+1)x(n +1) tableau. The pivot on entry tkl is said to be degenerate if tk,n+1 = 0. Theorem 9. If the tableau T is obtained from T by a degenerate pivot then t i, n+1 = ti, n+1, for all i with 1 d" i d" m + 1. In other words, the last column of T is identical to the last column of T. The proof should be obvious. Corollary 10. If the tableau T is obtained from T by a degenerate pivot then the basic solution corresponding to T is equal to the basic solution corresponding to T. Thus, the objective function has the same value for the two basic solutions. Proof. Since the pivot is degenerate, the value of the leaving variable in T is zero. This is also its value in T since it is nonbasic. The value of the entering variable remains zero; the values of the others clearly do not change. k Thus, doing a degenerate pivot while carrying out the simplex algorithm causes no improvement in the value of the objective function. This is usually harmless: degenerate pivots are eventually followed by nondegenerate ones, and the progression toward a solution continues. There is, however, a rare event which must be allowed for in the theory. It is called cycling and can put the algorithm into an infinite loop. A cycle consists of a sequence of feasible tableaus T0, T1,, Tk, such that each is obtained from the previous one by a degenerate pivot chosen according to the algorithm, and such that Tk has the same basis as T0. Thus, Tk can differ from T0 only in the order of its rows and columns. Now, if the pivot in Tk is chosen just as the one in T0 was, the result can be that the computation repeats the list of tableaus ad infinitum. In practice cycling is rare. For the theory, however, cycling is a serious problem because it blocks a proof that the algorithm stops. A simple way to avoid this problem is Blands Anticycling Rule Modify the simplex algorithm so that, whenever there is a choice of entering or leaving variable, we always choose the one with the smallest subscript. In general, Blands rule does not eliminate all degenerate pivots; it does, however, prevent cycles. Theorem 11. If the simplex algorithm is modified by Blands rule, then no cycle occurs. Proof. The strategy of the proof is to assume that there is a cycle T0, T1,,Tk, with pivots chosen according to Blands rule, and derive a contradiction. Define t to be the largest number of the set C = {i| xi enters the basis during the cycle}. Thus C consists of all i such that xi is basic for for some tableaus in the cycle, and nonbasic for others. Since the bases for T0 and Tk are identical, there is a tableau Tu in the cycle such that xt is basic in Tu and nonbasic in Tu+1. Also, there is a tableau Tv such that xt is nonbasic in Tv and basic in Tv+1. Let xs and xt trade places in the pivot in Tu which produces Tu+1. Note that s < t since s belongs to C. Now, the objective function equation in Tu has the form f(x) = d + "n+mk=1 ckxk, (5) where ck = 0 whenever xk is basic in Tu. Similarly, the objective function equation in Tv has the form f(x) = d + "n+mk=1c* k xk, (6) where c*k = 0 whenever xk is basic in Tv. The constant term in (5) and (6) are the same because the value of the objective function does not change after a degenerate pivot. For any (n + m)-tuple x satisfying the constraints, the two formulas ((5) and (6) must give the same value. That is, subtracting, "n+mk=1(ck " c*k)xk =0. (7) In particular, let us form x by setting xs = 1, setting all the other variables nonbasic in Tu equal to 0, and solving for the variables basic in Tu from their constraint equations. We see that if xi is basic in Tu, then the expression for xi has the form xi = bi " ai, where ai is the coefficient of xs in the constraint equation for "xi, and bi is the constant term in that equation. From (7), we get cs " c*s + "("c*i)(bi " ai) = 0, wher\^_qrv           " $ & ٪٪xj^jjhthU>|CJH*aJhthU>|6CJH*aJhthU>|CJH*aJhthU>|6CJaJ *hthU>|6CJaJ *hthU>|CJaJhthU>|CJaJhth5CJaJhthn\5CJaJhth^h5CJaJhthU>|5CJaJhthW95CJH*aJhthW95CJaJ ^_ & V X ` b ln$a$gdn \& " $ & ( : < B D T V X \ иꭡ|pdYhth=CJaJhth=CJH*aJhth]CJH*aJhth]6CJH*aJhth]6CJaJhth]CJaJhthi\6CJaJhthi\CJaJhthU>|6CJaJhthU>|CJH*aJhthU>|6CJH*aJhthU>|CJH*aJhthU>|CJaJhthAhCJaJ   $ & L N v x z  . X ^ ` t ߷߷߬~peehth3CJaJ *hthn 6CJaJhthAhCJaJhthn CJaJ *hthAhCJaJ *hthn CJaJhthU>|CJaJhthi\56CJaJhthi\6CJH*aJhthi\6CJaJhthi\CJaJhth=CJaJhthiRCJaJ$t v x z 68:>@DFJNPR^`fhjl螒xlhth:5CJaJ *hthAhCJaJhth]6CJH*aJhth]6CJaJhth]CJaJhth3CJaJhthAhCJH*aJhthAh6CJH*aJhthAh6CJH*aJhthAh5CJaJhthAhCJaJhthAh6CJaJ*NP  "$&(.<BDFJNPRXZ^`bdfhn۳۳۳۳۳۳۳۳hthAhCJH*aJhthAh6CJH*aJhthAh6CJH*aJ *hthAhCJaJhthAh6CJaJhthAh56CJaJhthAhCJaJBx24 MN~$a$gdAh $h^ha$gdAh $ & Fa$gdAh$a$gdn npxz|jlNTqs覚莃xhthnCJaJhth:CJaJ * hthnCJaJhthAh5CJaJ *hthAhCJaJhthAh56CJaJhthAhCJH*aJhthAh6CJH*aJhthAh6CJH*aJhthAhCJaJhthAh6CJaJ+"$&.PRTZ\^"BD`ŹţŐhthHCJaJhRCJaJhEMCJaJhthn%6CJH*aJhthn%6CJaJhthn%CJaJhth:6CJH*aJhth:6CJaJhth:CJaJhthR~VCJaJ50j$&"$02p^`$a$gdn &   "<ƺƬƺƺƇyk_SkSkƇhthK26CJaJhthK2CJH*aJhthK26CJH*aJhthK26CJH*aJhthK2CJaJhthAhCJH*aJhthAh6CJH*aJ *hthAh6CJaJhthAh6CJaJhthAhCJaJhthAh5CJaJhthCJaJhth:CJaJ * hthHCJaJ<>DFHTVFHJLVXZ^`bdfl "&(*024>@BDFPRXZ\^ͳͳͳۨ稜hth0V6CJH*aJhth0V6CJaJhth0VCJaJhthK2CJH*aJhthK26CJH*aJhthK26CJH*aJhthK26CJaJhthK2CJaJhthK256CJaJ8  "GOr t x *!,!.!0!2!B!D!H!!!!ĸĸޭޢ޸޸޸޸޸޸޸޸}޸޸hthK2CJH*aJhthK26CJH*aJhthuCJaJhthCJaJhthAhCJaJhthK26CJaJ *hthK26CJaJ *hthK2CJaJhthK2CJaJhth0V6CJaJhth0VCJaJ1!!!!!!""" ##$#,#-#=#>#@#8$:$]$_$j$l$$$$$$%%(&,&0&2&D&F&H&R&T&V&X&Z&z&|&~&&&&&&&& *hthF6CJaJhthF6CJaJhthFCJaJhth CJaJhthK26CJH*aJ *hthK26CJaJhthK2CJH*aJhthK26CJH*aJhthK26CJaJhthK2CJaJ3%D(E(I)J)))**,,,---...&/(/0000 $h^ha$gd0V $h^ha$gdF $ & Fa$gdF$a$gdn &&&&&&&&&'''@'B'D'N'P'R'C(D(E(R((((((((((((((!)"))))))*%*&*****,,--. *hthFCJaJ *hthF6CJaJ *hthFCJaJhthK2CJaJhthDfCJaJhthFCJH*aJhthF6CJH*aJhthF6CJaJhthFCJaJ5....../// / ////// /"/4/6/8/:/H/J/N/204060R0T0h0j00000000000:1<1>1P1R1T1V1`1b1d1f1h1n1p1r1t1v1|111¶¨ިިިިިި¶¨ިިhthFCJH*aJhthF6CJH*aJhthFCJH*aJhthF6CJH*aJhthF56CJaJhthF6CJaJhthFCJaJhth0VCJaJ=0L1N11111:2<222033f5h555>6@6z6|6v7x7778 8`8$a$gdn  $h^ha$gdF111111111111111111282:2<2>2R2T2V2^2`2b2h2j2l2r2t2v22222222222222222233÷ìhthn%6CJH*aJhthn%6CJaJhthoCJaJhthn%CJaJ * hthnCJaJhthnCJaJ *hthFCJaJhthF56CJaJhthFCJaJhthF6CJaJ5333 3 33333(3*3,3.303Z3\3^3j3l333333:4<4>4j4l4n444444455 5555 5"5$505b5d5f5ĶĶĶĶĶĶЫz * hth9CJaJhth9CJaJhthv6CJH*aJhthv6CJaJhthvCJaJhthsh6CJH*aJhthsh6CJaJhthshCJaJhthn%6CJaJhthn%CJaJhthn%6CJH*aJ0f5h555555666H6J6L6N6P6X6Z6\6`6b6d6h6j6l6r6t6v66666667 7 7&7*7.72767877777777777777777ҸƪҐƪƪƪƪƪƪҐƪƪƪhthlY6CJH*aJhthlYCJH*aJhthlY6CJH*aJ *hthlY6CJaJhthlY6CJaJhthlYCJaJhthF5CJaJhthlY5CJaJhthnCJaJ877777777777777888888:8<8R8T8Z8\8`8v8889 9H9X99999\:d:f:g:j:k:::.;H;O;xhth,BbCJaJhthU=CJaJ *hthlY6CJaJhth0V6CJH*aJhth0V6CJaJhth0VCJaJhthlY6CJaJhthlYCJH*aJhthlY6CJH*aJhthlY6CJH*aJhthlYCJaJ/`8b8880:1:>>)>*>>I?J?`?a?BBCC6DDD0E2E $h^ha$gd1 $h^ha$gdu$a$gdh6 $ & Fa$gdu$a$gdn O;;;;;;;;;<< < <<<(<*<0<2<8<:<===>>>>I?J?a?????۶{odXhthu5CJaJhth1CJaJ *hthuCJaJhthK2CJaJ *hthu6CJaJhthu6CJaJhthuCJaJhth#3vCJaJhthoACJaJ *hthlY6CJaJhthlYCJH*aJhthlY6CJH*aJhthlY6CJaJhthlYCJaJ"?????@@ @@@@8A:AAAA,B-BBBBBCDDDDDD D&D(D*DRDTDVD\D^D`DfDhDjDzD豥{m{m{m{m{m{mhthv6CJH*aJhthv6CJaJhthbBCJaJhthvCJaJhh6CJaJ * hthnCJaJhthnCJaJhthu6CJH*aJhth, CJaJhthHCJaJhEMCJaJhthuCJaJhthu6CJaJ*zD|D~DDDDDDDDDDDDDDDDD EEEE0EnE|E~EEEEEEEEEEEEF@FzFFF GGGGHõõõõϩõõϞϒ|hthsCJaJhthuCJaJ * hth9CJaJhth2CJaJhth9CJH*aJhth96CJH*aJhth96CJaJhth9CJaJhthvCJaJhthv6CJH*aJhthv6CJaJ02ElEnEEEBFFGGGHHHHHIII#J$JJJ MM $ & Fa$gdu $h^ha$gd9gd9 &d P gd9 $h^ha$gduHHHHHHHHJJJJJJJJJJJJ6K7K8KJKKKKKKKKKKL LLLL L&L(L4L6L:LNLRLLLLLLLLL踬hthe^56CJaJhthlJCJaJhthe^6CJH*aJhthe^6CJaJhthe^CJaJhthu6CJH*aJhthu6CJaJhth, CJaJhthuCJaJ *hthuCJaJ4LL M MMMM"M$M(M*M,M2M4M:MRTRZRbRdRhRjRlRrRtRxRRRR6S8S`B`D`FaHaJavaxazaaaaaaaaaŧӛhth;6CJH*aJhth;6CJaJhthi'5CJaJhthYCJaJhthh6CJaJhi'CJaJhthi'6CJH*aJhthi'6CJaJhthbBCJaJhth@CJaJhthi'CJaJ1__`B`D`aaaaa$b&bbbb|c~ccc $h^ha$gdY $ & Fa$gdY $h^ha$gdu $h^ha$gde^$h$d &d N P ^ha$gde^$h&d P ^ha$gd;aaaabb b"bbbbbb ccNcPcdcfcpcrczc|cccccccccc"d$d8d:d@dBdXd||||nbn|||||hthYCJH*aJhthY6CJH*aJhthY6CJaJhthYCJaJhthY5CJaJ *hthY5CJaJhthuCJaJhthi'5CJaJ * hth;CJaJhthbBCJaJhth;6CJH*aJhth;6CJaJhth;CJaJ&ccc deee>e@eeeeffffgghhh $h^ha$gd$a$gd=6t $h^ha$gd% $ & Fa$gd $8^8a$gdY $ & Fa$gdY $h^ha$gdYXdZd\dbddddddeeeee0e6e8e:eeeeeeeeeeeeeefffff f"f&f(f*fεzqehthCJH*aJh5(%6CJaJhth=6tCJaJhth6CJH*aJhth2CJaJhth%CJaJhth6CJaJhthCJaJ *hthY6CJaJhthYCJaJhthYCJH*aJhthY6CJH*aJhthY6CJaJ'*f.f>f@fBfDfFfJfLfNfRf^fbfdfjfrftfxffff g"g$g*g0g2gBgDggggggggJhKhhhhiiiiiiiiiiiiiijj稜琶 *hthCJaJhth5CJaJ *hth5CJaJhthnCJaJ *hth6CJaJhthCJH*aJhth6CJaJhthCJaJhth6CJH*aJ8hhhhiiiii&j(jjjjjkk`lblllll4m6m$a$gd $h^ha$gd@ $ & F a$gd $h^ha$gdj j"j$j(jZj\jbjdj|jjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkk k"k$k(k.k0k2k4k:kkkkkĮhth>_6CJaJhthK=CJaJhth>_CJaJhth%CJaJhthCJH*aJhth6CJH*aJhth@CJaJhth6CJaJhthCJaJ6kkkkkkkkkll$lZl\l^l`lllnltlxlzl|lllllllllllllllm mmmmm m&m*m,m0mnmrmxm~mmmmmmmmmmm nn n$n&n,n.n2nhthnCJaJhthCJaJhthK=CJaJhth>_CJH*aJhth>_6CJaJhth>_CJaJhth>_6CJH*aJD6m\m`mmm@nBnnnnnoo pp4plppprr.r/rqs$a$gdrXcgd]$a$gd@$a$gdrXc $h^ha$gd>_$a$gdn$a$gd2nBnFnHnNnPnTn\n^n`nfnhnlnnnrnxnzn|nnnnnnnnnnnnnnnnnnnnnnnnnnooooo p ppppphth;6CJaJhth @CJaJhth;CJaJ * hth@CJaJhthrXcCJaJ *hth>_CJaJhth>_CJH*aJhth>_6CJH*aJhth>_6CJaJhth>_CJaJ5pp"p$p&p.p0p2p4p6pJpLpNpTpVpXp^p`pbpjpppppppppppppppppppppq*qhq~qqqqqrr纮ţŘŁhth@CJaJ * hth]CJaJhth(_1CJaJhthDCJaJhthD6CJaJhth L,CJaJhth]CJaJhth @CJaJhth;6CJaJhth;CJaJhth;6CJH*aJ1rr-r.r/rqsssssssssssssssssssss t*t,tĸwk``T`HhthPN|6CJaJ *hthPN|CJaJhthPN|CJaJhthPN|CJH*aJhthPN|6CJH*aJ *hth#6CJaJhth#6CJH*aJhth#6CJaJhth#CJaJ *hth#CJaJhth#5CJaJhthrXcCJaJhthY5CJaJhthrXc5CJaJhth]5CJaJqsrsssssttttuuuuvvxxQ|}}}}}}~~v~$a$gdPN|gd4 $a$gdrXc,tRtTtttttttttttttttJuPuuuuuuuu v v vvv#v5v^v`vvvvv.w/wSwUwxx*x.xjxxxkzrzszz *hthPN|6CJaJhth%CJaJhth@CJaJhth@6CJaJhthK=CJaJ *hthPN|CJaJhthPN|CJH*aJhthPN|6CJH*aJhthPN|6CJaJhthPN|CJaJ5zzzzzzzzzzz^{_{`{w{x{y{{{{{{{{{{{{{}}}}}}}}}~)~w~}~~~~۳ۋthth2uCJaJ *hthPN|CJaJ *hthPN|6CJaJhthPN|5CJaJ *hthPN|5CJaJ *hth5CJaJhth&6CJaJhthPN|6CJH*aJhthPN|CJaJhthPN|6CJaJ *hthPN|6CJaJ+v~w~@AstVWZ\*,zprrt$a$gdrXc~~~~~~~DEIJLMNyz !":;<IJK\]^`{|}ۀڸhth2uCJH*aJh 146CJH*aJh 146CJaJhth2u6CJH*aJhthPN|CJaJhth2uCJaJhth2u6CJH*aJhth2u6CJaJ?ۀ܀݀ FGH[\]^b *FNVXhjl 468:BDLRTVX岦ڲڛڦ岦hth5oCJaJhth2uCJH*aJhth2u6CJH*aJhth2u56CJaJhth2uCJH*aJhth2uCJaJhth2u6CJH*aJhth2u6CJaJ=XZ\^`bdfƃȃʃz $&(*,.0XεڵΧshthCJH*aJhthCJH*aJhth6CJH*aJhth56CJaJhth2u6CJH*aJhth2uCJaJhth6CJH*aJhth2u6CJaJhth2u6CJH*aJhthCJaJhth6CJaJ-Xf†ĆƆ*,.FHRTV&(*68:‰ƉʉЉԉ։ډ܉މддд¤hyo}CJaJhcCJaJhth6CJH*aJhth6CJH*aJhth6CJaJhth56CJaJhthCJaJhth5oCJaJ@\^`(*,@Vnpr VX\`nprv4ҷҫҒhth`>CJaJhth`>6CJH*aJhth`>6CJaJhth%CJaJhth6CJH*aJUhthCJaJhyo}CJaJhth6CJH*aJhth6CJaJ9e the sum here is over all variables basic in Tu, and we have used the fact that ci = 0 when xi is basic in Tu. Now, c*s d" 0 because, otherwise, xs would be a nonbasic variable in Tu eligible to enter the basis. However, xt actually enters the basis. Since s < t, Bland s rule is violated. Also, cs > 0 since xs enters the basis in the pivot in Tu. We conclude that cs " c*s > 0, and so "c*i(bi " ai) > 0. We choose any r so that xr is basic in Tu and c*r(br " ar) > 0. It follows that c*r `" 0 and so xr is nonbasic in Tv. Thus, br = 0 implying that c*rar < 0. Now, r `" t because at > 0 (it is the pivot entry in Tu) and c*t > 0 (xt is the entering variable in Tv). Since xr is basic in Tu and nonbasic in Tv, r belongs to C and so r < t. Finally, if ar > 0, xr is eligible to leave the basis in the pivot on Tu. Since r < t, the choice of xt violates Bland s rule. Thus ar < 0 and so c*r > 0. But this means that xr is eligible to enter the basis in the pivot on Tv (instead of xt). Again, Bland s rule is violated. k To state this theorem differently, if we modify the simplex algorithm using Bland s rule, then no basis ever appears more than once. Since there are only finitely many bases, the algorithm must terminate after finitely many iterations. The initial feasible tableau It might happen that the initial basic form is infeasible although the primal problem itself is feasible. To find an initial feasible tableau we introduce an auxiliary variable u, and use it to construct the auxiliary problem whose objective function is  maximize "u and whose constraints are obtained from the previous one by adding  "u to the left-hand side. If the tableau of this auxiliary problem is infeasible, it is easy to find a feasible one. Then we apply the simplex algorithm. We notice that the auxiliary problem always has a solution since its objective function is bounded above by zero. When we find the solution for the auxiliary problem in which the value of the auxiliary objective function is zero and the auxiliary variable is nonbasic, we simply erase the column labeled by u and replace its objective function by the original objective function. Example 5.Consider the problem maximize 2x1 " x2 + 2x3 subject to x1 + x2 + x3 d" 6 "x1 + x2 d" "1 "x2 + x3 d" "1, x1, x2, x3 e" 0. Its basic form is maximize 2x1 " x2 + 2x3 subject to x1 + x2 + x3 " 6 = "x4 "x1 + x2 + 1 = "x5 "x2 + x3 + 1 = "x6, xi e" 0, 1 d" i d" 6. This basic form is infeasible, although the problem itself is feasible [(2, 1, 0) is a feasible vector]. Its auxiliary problem is maximize f = "u subject to x1 + x2 + x3 " u " 6 = "x4 "x1 + x2 "u + 1 = "x5 "x2 + x3 "u + 1 = "x6, xi e" 0, u e" 0. The corresponding tableau is x1 x2 x3 u "1 1 1 1 "1 6 = "x4 "1 1 0 "1 "1 = "x5 0 "1 1 "1 "1 = "x6 0 0 0 "1 0 = f This tableau is infeasible, but pivot on the entry in column 4 and row 2 results in the following tableau x1 x2 x3 x5 "1 2 0 1 "1 7 = "x4 1 "1 0 "1 1 = "u 1 "2 1 "1 0 = "x6 1 "1 0 "1 1 = f This tableau is feasible, but the auxiliary variable u is basic. After two pivots on it we get x6 u x3 x5 "1 2 "4 3 1 3 = "x4 "1 1 "1 0 1 = "x2 "1 2 "1 "1 2 = "x1 0 "1 0 0 0 = f This tableau is optimal and the auxiliary variable is nonbasic. We erase the column labeled by u and replace the bottom line by the coefficients of the original objective function after replacing x1 and x2 by the formulas from them given by the constraint equations in the previous tableau. Thus, 2x1 " x2 + 2x3 = 2(x6 + x3 + x5 + 2) " (x6 + x3 + 1) + 2x3 = x6 + 3x3 + 2x5 + 3. The initial tableau for the problem is then x6 x3 x5 "1 2 3 1 3 = "x4 "1 "1 0 1 = "x2 "1 "1 "1 2 = "x1 1 3 2 "3 = f This problem can be solved in three pivots if we use Bland s rule, or in one pivot if we do not. j We formalize this method as follows. Algorithm 3 (The feasibility algorithm). We are given an infeasible primal basic form. (This is called the original problem.) Introduce an auxiliary variable u. Define the auxiliary objective function to be "u. For each constraint in the original problem, form an auxiliary constraint by adding "u to the left-hand side. Define the auxiliary problem to be that of maximizing the auxiliary objective function subject to the auxiliary constraints. Set up the tableau for the auxiliary problem. Choose a row (not the bottom one) so that the right-hand entry is smallest (the most negative); pivot on the entry in this row and in the column labeled by u. (The result is a feasible tableau.) Apply the simplex algorithm to solve the auxiliary problem. If the maximum value of the auxiliary objective function is negative, STOP (the original problem is infeasible). Carry out a pivot so that the auxiliary variable is nonbasic (if necessary). Set up a feasible tableau for the original problem by erasing the column labeled by the auxiliary variable, and then replacing the auxiliary objective function by the original one (written in terms of the nonbasic variables). The following theorem summarizes the previous results. Theorem 12. If a primal LP problem is both feasible and bounded, then it has a solution. Moreover, a solution can be computed by using the feasibility algorithm (if necessary) together with the simplex algorithm, modified by Bland s rule. Duality We describe the dual versions of the results obtained for primal versions and reveal the connection between primal and dual problems (besides Theorem 1 and its corollary). Example 6 Consider the problem minimize 2y1 " y2 subject to y1 " y2 e" 1 y1 " 3y2 e" 0 y1 " y2 e" 0 "y1 + 2y2 e" "1, y1, y2 e" 0. This problem is feasible since (1, 0) is a feasible vector. Its dual basic form is minimize 2y1 " y2 subject to y3 = y1 " y2 " 1 y4 = y1 " 3y2 y5 = y1 " y2 y6 = "y1 + 2y2 + 1, yi e" 0, 1 d" i d" 6. The dual tableau for this dual basic form is y1 1 1 1 "1 2 y2 "1 "3 "1 2 "1 "1 1 0 0 "1 0 = y3 = y4 = y5 = y6 = g j Theorem 13. Consider a dual tableau of size (m + 1)x(n + 1). Then we have: The tableau is feasible if and only if each entry in the bottom row (not counting the last one) is nonpositive. Suppose the tableau is feasible. If each entry in the right-hand column (not counting the bottom one) is nonnegative, then the tableau is optimal. Example 6 (continuation) The dual tableau in example 6 is not feasible. A pivot on the first entry in the first row produces the following tableau (feasible and optimal): y3 1 1 1 "1 2 y2 1 "2 0 1 1 "1 "1 "1 "1 0 "2 = y1 = y4 = y5 = y6 = g j Algorithm 4 (The Dual Simplex Algorithm) We are given a feasible tableau T of size (m+1)x(n +1). If ti,n+1 e" 0 for 1 d" i d" m. then STOP (the tableau is optimal). Choose any k with 1 d" k d" m such that tk,n+1 < 0. (The nonbasic variable labeling row k is called the entering variable.) If tkj e" 0 for 1 d" j d" n, then STOP (the problem is unbounded). Choose any l with 1 d" l d" n such that tkl < 0 and tm+1,l/tkl =min{tm+1,j/tkj|1d" j d" n and tkj<0}. (The basic variable labeling column l is called the leaving variable.) Pivot on tkl and replace T by the dual tableau resulting from this pivot. (Entry tkl is called the pivot entry.) Go to Step (1). If this algorithm is modified by Bland s rule, then cycles are impossible, and so the computation always terminates after finitely many iterations. There is a dual version of the feasibility algorithm. If the initial dual basic form is infeasible, we construct an auxiliary problem by introducing an auxiliary variable v, an auxiliary objective function +v, and auxialiary constraints formed from the original constraints by adding v. Then we pivot on the entry in the row labeled by v and a suitable column to obtain a feasible tableau and go on with pivoting to obtain an optimal tableau where the auxiliary variable v is nonbasic. To obtain the initial feasible tableau for the original problem, we erase the row labeled by v and replace the auxiliary objective function by the original one written in terms of the nonbasic variables. Theorem 14. A dual LP problem which is both feasible and bounded has a solution. Moreover, a solution can be computed by using the dual feasibility algorithm (if necessary), together with the dual simplex algorithm modified by Bland s rule. Consider a dual/primal pair of problems, and introduce slack and surplus variables to obtain a primal and a dual basic form. The (primal) tableau and the dual tableau corresponding to these basic forms consist of the same (m+1)x(n+1) matrix, and differ only in the labels. This suggests that we combine the two tableaus into one dual/primal tableau. This is done by putting both sets of labels on the matrix. Example 7. Consider the primal problem maximize "x1 + 2x2 " 3x3+ 4x4 subject to x3 " x4 d" 0 x1 " 2x3 d" 1 2x2 + x4 d" 3 "x1 + 3x2 d" 5, xi e" 0, 1 d" i d" 4. The dual/primal tableau is x1 x2 x3 x4 "1 y1 0 0 1 "1 0 = "x5 y2 1 0 "2 0 1 = "x6 y3 0 2 0 1 3 = "x7 y4 "1 3 0 0 5 = "x8 "1 "1 2 "3 4 0 = f =y5 =y6 =y7 =y8 =g Given the notation, we can simultaneously carry out pivots on both problems: it is simply a matter of keeping track of both sets of labels. A pivot on the second entry in the third row of the dual/primal tableau, produces the tableau x1 x7 x3 x4 "1 y1 0 0 1 "1 0 = "x5 y2 1 0 "2 0 1 = "x6 y6 0 0 3/2 = "x2 y4 "1 "3/2 0 "3/2 = "x8 "1 "1 "1 "3 3 "3 = f =y5 =y3 =y7 =y8 = g Theorem 15 (The duality theorem). If either of a dual/primal pair of problems has a solution, then so does the other; moreover, if they have solutions, the optimal values of the two objective functions are equal to each other. Proof. Suppose first that the primal problem has a solution. Set up the dual/primal tableau and carry out a sequence of pivots which produces an optimal feasible tableau for the primal. This is possible by Theorem 12. The final tableau of this sequence has all nonnegative entries in the last column (not counting the bottom row), and all nonpositive entries in the bottom row (not counting the last column). But, then, by Theorem 13, the dual tableau is both feasible and optimal. This proves that the dual problem has a solution. Also, the optimal values of both objective functions are equal to the negative of the bottom right-hand entry in the tableau, and thus are equal to each other. The proof that the primal problem has a solution if the dual does (and that the optimal values are equal) is identical to what we have just done, except for obvious changes. j Homework. Solve the following dual problem and its primal minimize y1 " y2 + y3 subject to "y1 + y2 e" 0 "y2 + y3 e" "1, y1, y2, y3 e" 0. "$XZDF "$^`68vxR$a$gdR$a$gdrXc48:<>@FHJvx~ "BDFHJVXZǻǻǻǻǻǻǗǻǻǗǻǻnjh{hRCJ,aJ,hRCJ(aJ(hRhR6CJH*aJhRhR6CJH*aJhRhR6CJaJhRhRCJaJhRCJaJhth`>CJaJhth`>6CJH*aJhth`>6CJaJ7$&(bdfxz~ ".02*.0dfh02ڹڮhth2uCJaJhyCJaJhth`>6CJH*aJhth}|3CJaJhth`>CJaJhth`>6CJH*aJhth`>6CJaJD2@B"$\^`      $ & t v x z   <  : R    *RT48Ltƺޕޕފފފފފފshhth}|3CJaJ * hth5oCJaJhth5oCJaJhth6CJaJ *hth2u6CJaJhthdCJaJhth2u5CJaJhthd5CJaJhth25CJaJhth2u6CJaJhth2uCJaJ *hth2uCJaJhth?)CJaJ(tvxz  0468:@BD`dnprxzӜhthQ(CJaJhth CJaJhth CJaJhCJaJhth}|36CJH*aJhth}|36CJaJhthe0CJaJhth}|3CJaJhth5oCJaJ=R4248^r*tJL"$&d P a$gdfml$a$gdfml$a$gdrXc .024JNPTXZ\bdfhx "$*2ŠŘŠŹйРhVCJaJhth CJaJhth 6CJH*aJhth 6CJaJhth CJaJhthQ(CJaJhth}|36CJH*aJhth}|36CJaJhth}|3CJaJ9248:JLNRTVZ^`tvxz|.0DFHJPRTXZj꼣꼣꼣꼣꼣꼣꼣걛꼣꼣h`1F6CJH*aJh`1FCJaJhth 6CJH*aJhth;bCJaJhth 6CJaJhth&6CJaJhth&CJaJhthI0CJaJhth CJaJhth2CJaJ8jlnr"*.nprFJ$.08:BDJLT\`ڼhfmlhfmlCJH*aJhfmlhfml6CJH*aJhfmlhfml6CJaJhfmlhfmlCJaJhthfmlCJaJh CJaJhth;bCJaJhth:CJaJhth CJaJhth 6CJH*aJhth 6CJaJ2"$\0z|:<>v>$a$gdrXc$a$gdN-$&d P a$gdfml$a$gdfml*,.0<vz8:>HJZ\dfnvz8:<>JHJ "&ڻhN-hN-6CJH*aJhN-hN-6CJaJhN-CJ,aJ,hN-hN-CJaJhfmlCJaJhfmlhfmlCJH*aJhfmlhfmlCJaJhfmlhfml6CJH*aJhfmlhfml6CJaJ< 024:<>PRTZ\^fhjrtv  BDFzźź~phth6CJH*aJhth6CJaJhthCJaJhth:6CJH*aJhth:6CJaJhth CJaJhth:CJaJhth2CJaJhfmlh:CJaJhN-hN-6CJaJhN-hN-CJaJhN-hN-6CJH*aJ, H  !!N!!"##n%%&f',).)) $h^ha$gd $ & F a$gd6$a$gdrXc$&d P a$gdrXcz|~   X   !!H!J!N!x!!!""\"^" %"%,)ĸuiϚi^iihthyACJaJhth66CJaJ *hth66CJaJ *hth6CJaJhth2uCJaJhth6CJaJhthfmlCJaJh5oCJaJ * hth:iCJaJhth:iCJaJhthI0CJaJhthCJaJhth6CJH*aJhth6CJaJ"))|+++++,,,-.-V---.P...2/4/6/8/d///*0x0$a$gd!eV$a$gdrXc $h^ha$gd,))))|+~++++++,,-.-0-@-B-D-F-H-J-P-R-T-V-X-n-ҺwlwalwUGwUGwlwhth:i6CJH*aJhth:i6CJaJhth;bCJaJhth *CJaJhth:iCJaJ * hth:iCJaJhth:i5CJaJh!eVh!eVCJaJhL5CJaJhthPN|5CJaJhthL5CJaJhth2u6CJaJhth2uCJaJ *hthCJaJ *hth2CJaJhthCJaJn-r-t-v-z-|-~------------------....(.*...0.2.4.6.>.@.B.j.r.t.v.|.~....0/2/ȴȴۏЄhth2CJaJhth6CJaJhthACJaJhthA6CJH*aJhthA6CJaJh:iCJaJhACJaJhth:iCJaJhth:i6CJH*aJhth:i6CJaJhth;bCJaJ02/6/8/:/J/R/T/V/X/^/`/b/d/f/z////////////////////00000000$0&0(0F0N0P0R0T0\0^0`0h0j0l0000000001 1˽˽˽˽˽˽˽˽˽˽˽˽˽˽˽צhthcCJaJhth ~c6CJaJhth:i6CJH*aJhth:i6CJaJhth:iCJaJhth ~cCJaJhthCJaJhCJaJAx000 1"1n111B222F3&4L5N5667j7 &dPgddgdd $ & Fa$gdsl$$d &d N P a$gdrXc$&dPa$gdrXc$a$gdrXc 1"1(1*1.1j1n1t1v1 2222222&2(2*2224262<2B2n2222222 3 33364鹮|qeqeqhthsl6CJaJhthslCJaJhthsl5CJaJ *hthsl5CJaJhth:i5CJaJ * hth>CJaJhth>CJaJhth>6CJaJhthcCJaJhthCJaJhthc6CJH*aJhthc6CJaJhth<CJaJ#64J5N5~5 6d6r6v6666666 7 77777777777778 8 8888b8d8~888øíˡ˭{oco *hthcCJaJ *hthslCJaJhth>5CJaJ * hthdCJaJhth6CJH*aJhth6CJaJhthCJaJhthusCJaJhusCJaJhOGCJaJhth>CJaJ * hth>CJaJhthslCJaJhth:iCJaJ&j778b8d88&9(90929f9h999:::;;R;T;$a$gdQ* $8^8a$gd1 $h^ha$gd1 $ & Fa$gd c,$a$gdrXcgdd$d &d N P gdd8888 9999$9&9(9092949>9X9Z9`9b9999999999: :^:`:~::::::::::::;ȼȼȼȣ~p~ *hthQ*6CJaJhthQ*6CJH*aJhthQ*6CJaJhthQ*CJaJhth c,CJaJhth16CJH*aJhth16CJaJhth1CJaJhthdCJaJhthu 6CJaJhthu CJaJhthcCJaJ,;T;`;j;l;;;;;;;;;;;;;;;;;;;;;;<<<<<< <t<x<<<<<<<<<<\=^=b=====>>@@B@@@"A$AAAABhth,oCJaJhth c,6CJaJhthdCJaJ *hthQ*6CJaJhthQ*6CJH*aJhthQ*6CJaJhth c,CJaJhthQ*CJaJ>T;;;;*<,<<===>>NDPD2F4F6F8F:FnIpIIIZJ $h^ha$gd$a$gd}6 $h^ha$gd c, $h^ha$gdQ* $ & Fa$gd c,BB6C8CpCrCLDNDPDfDhDtDvDzD|D2F6F8F:FPFFGGGGGHHHHlInIpIĸ袗ttf[hthKHCJaJ *hth96CJaJhth96CJaJhth9CJaJhth6X6CJaJhth6XCJaJhthFCJaJhth2CJaJhth,o5CJaJ *hth,o5CJaJhth c,CJaJhth ~cCJaJhth,oCJaJhth,o6CJaJ pIIIIIIIIIIIIIIIIIIJJJJ@JBJDJFJLJNJPJXJZJvJJJJJJJJJJJJJJJJJJJKKKKKK!>?>@>S>U>i>j>>>>> ?!????????@@@@@BB-B.BBBBBCC&C'CCCDDEEHIIII;J `enru}6>P[imv{~%)27:<acnoEMA I !!I!K!###$$7%9%&&J'K'Q'R'''V*a*F+I+++++++,,],^,,,,,,,,,,,,,,,,,,-- - --------..A.C.q.s.......//./3/6/:/i/k/////////////00"1$111111111122 2224282<2B2E2K2M2P2K3V33344.404a4f4v4x44445955566883969C9D9999999<:?:::>;K;l<o<<<<<<<==6=9=~========>>>>rBuBBBBCCCCCEETFaFfGhGGGHH[H]HIIIIHJOJJJHKJKlKsKKKLL+L.LOLWLLLLLLLLLLLLM MMMMM M8M:M?MAM_MaMMMMMMM,N.NmNoNNNNNNNNNvO{OOOOPJPLPrPzP~PPPPPP5Q7Q@QBQYQ[QQQQQQQRR:Rs:tBttuuuxx'y(yyyyyH{I{||||~~_nut+2npadw}vjp     ^ i   acim% #%ckil !ac!!K"U"M$O$&4&]&e&y&&&&&&''''')1)T)V)**+++,-!-....A/F/////// 1122x3~34)444=6@6H6O6n6p66677`8b8r8u8888839699999N;X;H<N<S<U<<<<<0=2=====6>8>_>a>>>>>????????@@.B;BMBOBBBBBC CCCC8DDDE FbGeGJJJKGKJKLMMMNNmNoNNNNNOP+Q-Q:Q?QQQQQ\RRdSfSsSvSSSSS T TTTTTT5UkUUUUVVWWZZZZ ["[E[R[^[e[[[R\S\\\\\3]5]f]h]]]]]]]]]^^^^^^^^_ _________``aabb+b/bbcggiiii"j-jjjjj8k:kkkAlLlslulmmrotoooooooTpWplpppppppKrZruuvvwwwwww+x-xxxxx=yAyjynyyyyyz zzz{{{{| |1|6|I|j|.}4}ʀ̀րހ<>_333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333uu? ? AB##F$G$4&5&++y6z6z7{799LLPPPP7Q8Q:Q@QQQQQS4T5T5TjUkUZZ[[[[[[[[\\\\] ]A]B]C]aaabbh_iiiiiiiijjjxkykzkzk nn"n9nnnonqnnnnwww x)x+x.x8x>xEx[xfxjxsxxxxxxxxxxx;y=y?y?yhyjylylyyyyyyyyy{{\_uv? @ BD##F$G$I$J$3&5&8&9&++x6{6z7799LLPPPP7Q8Q:Q@QQQQQS4T5T5TjUkUZZ[[[[[[[[\\\\] ]A]B]C]aaabbh_iiiiiiiijjjxk|k nn"n9nnnonununnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnwww x)x+x.x8x>xEx[xfxjxsxxxxxxxxxxx;y=y?y?yhyjylylyyyyyyyyy{{Q_r jIBm4& x 6Qrf~+foB<+c2<:$)`cA>8OB|a$6IIxg ]`KTh]к1fe\V`q@L$Vz808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`06o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.h hh^h`hH.h 88^8`hH.h L^`LhH.h   ^ `hH.h   ^ `hH.h xLx^x`LhH.h HH^H`hH.h ^`hH.h L^`LhH.G!G^G`!o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.h0^`0o(()h 88^8`hH.h L^`LhH.h   ^ `hH.h   ^ `hH.h xLx^x`LhH.h HH^H`hH.h ^`hH.h L^`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.h808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.h808^8`0o(()h ^`hH.h pLp^p`LhH.h @ @ ^@ `hH.h ^`hH.h L^`LhH.h ^`hH.h ^`hH.h PLP^P`LhH.h0^`0o(()h 88^8`hH.h L^`LhH.h   ^ `hH.h   ^ `hH.h xLx^x`LhH.h HH^H`hH.h ^`hH.h L^`LhH.h hh^h`hH.h 88^8`hH.h L^`LhH.h   ^ `hH.h   ^ `hH.h xLx^x`LhH.h HH^H`hH.h ^`hH.h L^`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.808^8`0o(() ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.+f$6II1fec2r m4& V`q8OBh]<oVz6Q ]`cA j        ς         j                 zz        Cnt        bvZI        Cnt         j        Cnt         /̘         j        Cnt                 ̜        Cnt        9, 4 u Dfn 3]c:i>_V$$1o a"#5(%i'Q(?) * L, c,N-I0e0(_1K2}|3 145]6W9<U=K=m>o'@oAyA`1FOG(KD2KiR\nR0V!eVR~VP W6XlY!\i\C^N`;b,BbrXc ~cPd,Lh^hshfmlsl,o5o=6tuv#3vU>|PN|yo}jF~%:=Ahy`>FFt3 us; :2RD2uKHc>u&Run;h6Y]9bBL'SDn% Ys7oe^H1 @dEM6n\scYQ*}61lJ% @VA2:@xxxxxEEE E E E EEEEEEEEEEE!E"E$E%^&^(+,-./012489:<=>?@BCEFMNOPQ]@ (@<@ D@&P@.02468t@<|@@@D@LNPRTVX@\df@jlnp@t@x@@UnknownGz Times New Roman5Symbol3& z Arial"qh;f6NnBNnB!242QHX ?s72 OR-Curs2_0910RodicaRodicaL           Oh+'0t  0 < HT\dlOR-Curs2_0910RodicaNormalRodica24Microsoft Office Word@0@. f@Nn՜.+,0 hp  AcasaB OR-Curs2_0910 Title  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&()*+,-.0123456;Root Entry F=1TableWordDocument.SummaryInformation('DocumentSummaryInformation8/CompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q