Linear Programming and Network Flows
Language: English
Pages: 704
ISBN: 0471636819
Format: PDF / Kindle (mobi) / ePub
This work addresses the problem of minimizing or maximizing a linear function in the presence of linear equality or inequality constraints. It provides methods for modeling complex problems via effective algorithms on modern computers. The general theory and characteristics of optimization problems are presented, along with effective solution algorithms. The text also explores linear programming and network flows, employing polynomial-time algorithms and various specializations of the simplex method. Includes many numerical examples to illustrate theory and techniques.
A Mathematical Look at Politics
Role of Mathematics in Science
A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics, Volume 138)
half-space is a collection of points of the form {x : px > k}, where p is a nonzero vector in R" and & is a scalar. A half-space can also be represented as a set of points of the form {x : px < k}. The union of the two half-spaces {x : px > k} and {x : px < k} is R". Referring to a fixed point x 0 in the hyperplane defining the two halfspaces the latter can be represented as {x : p(x - x 0 ) ^ 0} or as {x : p(x - x 0 ) < 0}, as shown in Figure 2.8. Note that the first half-space consists of
inverse? If the answer is yes, find A~ : "1 - 4 4 0" 2 5 0 1 0 2 0 1 1 3 2 2_ [2.6] Find the inverse of the following triangular matrix: "2 0 0 0 4 - 3 -Λ 4 3 2 0 2 5 0 0-1 84 Chapter 2 [2.7] Let A be a 3 x 5 matrix. Consider the matrix C obtained by weighting the columns of A with scalars 1, 3/2, - 2 , 4, and - 1 , respectively, and adding them up. Write C as a matrix product. Similarly, let D be the weighted sum of the rows of A, using weights 2, - 2 , and 3/2, respectively. Write
the space—give rise to the following four points: 3 3 » 6 0 0 3 1 and These four points are illustrated in Figure 3.2. Note that these points are precisely the extreme points of the feasible region. In this example, the possible number of basic feasible solutions is bounded by the number of ways of extracting two columns out of four columns to form the basis. Therefore the number of basic feasible solutions is less than or equal to 4! 2!2! = 6. Out of these six possibilities, one point
Equation (3.8). If the vector y^ has any positive component(s), then the corresponding basic variable(s) are decreased as xk is increased. Therefore, the nonbasic variable xk cannot be indefinitely increased, because otherwise, the nonnegativity of the basic variables will be violated. Recall that a basic variable xB that first drops to zero is called a blocking variable because it blocks the further increase of xk. Thus, xk enters the basis and xB leaves the basis. Example 3.5 Minimize 2x\ - *2
solutions. Hence, prescribe a general rule to solve a knapsack problem of the type to Maximize n n X CjXj, subject to Σ ajxj ^b, x,· > 0 for y = 1,...,n, where b > 0, c,· > 0, V/, and a. > 0, V/, based on the ratios c.· la,, j = \,...,n. Comment on how you would treat the case c ,· < 0 for any/, or c > 0 and a ■ < 0 for any/. [3.10] Consider the polyhedral set consisting of points (x{,x2) Χγ + 2x2 xj, x2 ^ such that 2 unrestricted. Verify geometrically and algebraically that this set has
