Archive for July, 2014

Solving a Nonstandard Problem

Solving a Nonstandard Problem

a. If necessary, convert the problem to a maximization problem.

b. Add slack variable and subtract surplus variables as needed.

c. Write the initial simplex tableau.

d. If any basic variable has a negative value, locate the nonzero number in the variable’s column, and note what row it is in.

e. In the row located in Step d, find the positive entry that is farthest to the left, and note what column it is in.

f. In the column found in Step e. Choose a pivot by investigating quotients.

g. Use row operation to change the other number in the pivot column to 0.

h. Continue Steps d through g until all basic variables are nonnegative. If it ever becomes impossible to continue, then the problem has no feasible solution.

i. Once a feasible solution has been found, continue to use the simplex method until the optimal solution is found.

 

Solving a Standard Minimum Problem with Duals

 

Solving a  Standard Minimum Problem with  Duals

a. Find the dual standard maximization problem.

b. Solve the maximization problem using the simplex  method.

c. The minimum value of the objective function w is the maximum value of the objective function z.

d. The optimum solution is given by the entries in the bottom row of the columns corresponding to the slack variables, so long as the entry in the z column is equal to a.

 

Theorem of Duality

 

Theorem of  Duality

The objective function w of a minimization linear programming problem takes on a minimum value if and only if the objective function z of the corresponding dual maximization problem takes on a  maximum value. The maximum value. The maximum value of z equals the minimum value if w.

Standard Minimum Form

Standard Minimum Form

A linear programming problem is in standard minimum form if the following conditions are satisfied.

a. The objective function is to be minimized.

b. All variables are nonnegative.

c. All remaining constraints are stated in the form

 

a1y1 + a2y2 + ……….+anyn  ≥  b with b  ≥  0.

 

Simplex Method

Simplex Method

 

a. Determine the objective function.

b. Write all the necessary constraints.

c. Convert each constraint into an equation by adding slack variables.

d. Set up the initial simplex tableau.

e. Locate the most negative indicator. If there are two such indicators, choose the one father to the left.

f. From the necessary quotients to find the pivot. Disregard any quotients with 0 or a negative number in the denominator. The smallest nonnegative quotient gives the location of the pivot. If all quotients much be disregarded, no maximum solution exists. If two quotients are both equal and smallest, choose the pivot in the row nearest the top of the matrix.

g. Use row operations to change all other numbers in the pivot column to zero by adding a suitable multiple of the pivot row to a multiple of each row.

h. If the indicators are all positive or 0, this is the final tableau. If not, go back to Step 5 and repeat thr process until a tableau with no negative indicators is obtained.

i. Read the solution from the final tableau.

 

Standard maximum Form

Standard maximum Form

A linear programming problem is in standard maximum form if the following conditions are satisfied.

a. The objective function is to be maximize.

b. All variables are nonnegative (xi ≥ 0).

c. All remaining constraints are stated in the form

a1x1 + a2x2 + ……….+anxn ≤  b with b ≥ 0.

 

Finding a Production Matrix

Finding a Production Matrix

 

To obtain the production matrix, X, for an open input-output model, follow these steps:

a. Form the n  \times  n input-output matrix, A, by placing in each column the amount of the various commodities required to produce 1 unit of a particular commodity.

b. Calculate I – A, where is the n \times n identity matrix.

c. Find the inverse, (I – A)-1.

d. Multiply the inverse on the right by the demand matrix, A, to obtain X = (I- A)-1 D.

To obtain a production matrix, X, for a closed input-output model, solve the system (I – A) X = 0.

 

Finding a Multiplicative Inverse Matrix

Finding a Multiplicative Inverse Matrix

To obtain A-1 for any n $\times$ n matrix A for which A-1 exist, follow these steps.

a. From the augmented matrix [A | I ], where I is the n $\times$ n identity matrix.

b. Perform row operation on [A | I] to get a matrix of the form [I | B], if this is possible.

c. Matrix B is A-1.

 

Inverse Matrix A-1

Inverse  Matrix A-1

AA-1 = I   and A-1 A = I ?

A = \begin{bmatrix}  2 & 3\\  7&5  \end{bmatrix}

A-1 = \begin{bmatrix}  2 & 7\\  3&5  \end{bmatrix}

Note:- A-1 does not mean  \frac{1}{A}; here , A-1 is just the notation for the multiplicative inverse of matrix A. Also, only square matrices can have inverses can have inverses because both A-1 A and AA-1 must exist and be equal to I.

 

Identity Matrix

Identity Matrix

If I is a the identity matrix, both of the products AI and IA must equal A.

This means that an identity matrix exists only for square matrices. The 2 x 2 identity matrix that satisfies these conditions is

I =  \begin{bmatrix}  1 & 0\\  0 & 1  \end{bmatrix}.

To check that I, as defined above, is really the 2 x 2 identity.