tailieunhanh - Mechanism Design - Enumeration of Kinema Episode 1 Part 1

Tham khảo tài liệu 'mechanism design - enumeration of kinema episode 1 part 1', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Appendix A Solving m Linear Equations in n Unknowns In this appendix we develop a procedure for solving a system of m linear equations in n variables subject to a constraint that all the variables are nonnegative integers. We first discuss a method for solving one equation in n unknowns. Then we extend the method to solving a system of m equations in n unknowns. Solving One Equation in n Unknowns Consider the following linear equation C1X1 C2X2 C3X3 ----- CnXn k where Xis are the variables and Ci s are the coefficients. The Cis are nonnegative integers and k is a positive integer. We wish to solve for xi for i 1 2 . n subject to a constraint that all xis must be nonnegative integers. In addition the following constraint may be imposed xi qi constant . Since there are n unknowns in one equation we may choose n - 1 number of unknowns arbitrarily and solve Equation for the remaining unknown provided that all the solutions are nonnegative integers. This can be accomplished by a computer program using a nested-do loops algorithm to vary the value of each xi and check for the validity of the solutions. A more rigorous procedure for solving one linear equation in two unknowns can be found in 1 . 2001 by CRC Press LLC Table A Nested-do Loops Algorithm for Solving One Linear Equation in n Unknowns. FOR 71 0 TO q1 x 1 71 FOR 72 0 TO q2 x 2 72 FOR 73 0 TO q3 x 3 73 . . . FOR 7n-1 0TO qn-1 x n - 1 7n-1 x n k c 1 x 1 . c n 1 x n 1 c n . IF x n 0 DISCARD THE SOLUTION. IF x n 0 SAVE THE SOLUTION. NEXT 7n 1 NEXT 73 NEXT 72 NEXT 71 Solving m Equations in n Unknowns Next we consider a system of m linear equations in n unknowns ciixi C12x2 ----- C1nxn k1 c21x1 c22x2 c2nxn k2 cm1x1 cm2x2 cmnxn km where the coefficients cij s are nonnegative integers the constants ki s are positive integers and n m. Furthermore the solutions to the system of equations are subject to a constraint that all the variables xi for i 1 2 . n must be nonnegative integers. Writing .