Introduction to operations research

INTRODUCTION TO OPERATIONS RESEARCH

1. Explain the terms:

Unique matrix: determinant =1, all rows and columns are linearly independent,– square matrix nxn with 1 in diagonal

Reduced echelon form: a matrix is in this form if it satisfies conditions: a) It is row echelon form, b) every leading coefficient is 1 and is only nonzero entry in its column, May be computed by Gauss-Jordan elimination

- Is unique and doesn’t depend on the algorithm used to compute it

Coefficient matrix: the matrix formed by the coefficients in a linear system of equations, for example:

2x-3y=8 →2 -3 4x+5y=1 4 5

Right hand side vector (RHS):values of conditions, has to be behind inequality sign(<=) created by for example maximal capacity of something, or minimum of something

Augmented matrix: a matrix form of a linear system of equations obtained from the coefficient matrix. It is created by adding an additional column for the constants on the right of the equal signs. The new column is set apart by a vertical line.

 

What is the matrix form of the system of linear equations?

Ax=b is A is [mxn] matrix;

x column vector with n entries;

b column vector with m entries

Apply the Frobenius theorem in the solution of the system of linear equations.

• Frobenius theorem: System of linear equations has at least one solution if and only if the rank of matrix of system is equal to the rank of augmented matrix of system.

• The rank of matrix is number of linearly independent rows (columns) in matrix.

• The rank of matrix can be set as number of nonzero rows (columns) in row echelon form of matrix.

 

Describe the algorithm of the Gauss-Jordan total elimination.

GAUSSÐJORDAN ELIMINATION

Step 1. Choose the leftmost nonzero column and use appropriate row operations to get a 1 at the top.

Step 2. Use multiples of the row containing the 1 from step 1 to get zeros in all remaining places in the column containing this 1.

Step 3. Repeat step 1 with the submatrix formed by (mentally) deleting the row used in step 2 and all rows above this row.

Step 4. Repeat step 2 with the entire matrix, including the mentoly deleted rows. Continue this process until it is impossible to go further.

Goal of the elimination: one variable is isolated in each row.

 

Describe the algorithm of finding the inverse matrix.

FINDING A^-I BY ROW REDUCTION - Algorithm of finding the inverse of an n x n matrix:

1. Form an augmented n x 2n matrix by writing the nxn identity matrix right of A

2. Performing row operations on the augmented matrix transform A to the identity matrix I;

3. The matrix I that we added will be automatically transformed to A^-I; If it is impossible to transform A into identity, A is not invertible

 

Which are the phases of the decision making process?

-Intelligence, design, choice, implement

 

7. Describe the Anthony´s classification of the decision making. Draw the Anthony´s pyramid.

Robert N. Anthony classification: a) Strategic Planning(top) b) Tactical Planning(middle) c)Operations Control (bottom)

 

Which are the typical features of the strategic planning, tactic planning and operational control?

Which are the typical decisions in those groups?

Strategic planning:,extremely important, long-time long-lasting effect - uncertainties and risk attitudes (more than 3 years), nonrepeatable, high uncertainity,aggragated info, managerial policies - high managerial level, Examples: major capital investments in new production capacity and expansions of existing capacity, determination of location and size of new plants, distribution facilities, development and introduction of new products, and issuing of bonds and stocks.

Tactic planning: medium time (1-3 years), significant aggregation of info, The basic problem to be resolved is the effective allocation of resources (e.g., production, storage, and distribution capacities; work-force availabilities; marketing, financial, and managerial resources) to satisfy demand and technological requirements

Operational control: day-to-day, after making an aggregate allocation of the resources of the firm, it is necessary to deal with the day-to-day operational and scheduling decisions. complete disaggregation of the information generated at higher levels into the details consistent with the managerial procedures followed in daily activities, at this level are the assignment of customer orders in the work shop, inventory accounting and inventory control activities, dispatching, expediting and processing of orders, vehicular scheduling, and credit granting to individual customers.

 

Compare programmed and non programmed decisions.

• Programmed decisions are those that occur routinely and repetitively, they can be structured, they can be delegated on the lower echelons of the organization.

• Nonprogrammed decisions are complex, unique, and unstructured, large amount of good judgment and creativity, normally, top managers are responsible

 

Compare the main kinds of the mathematical models (operational exercise, gaming, simulation, analytical model).

Operational exercise: operates directly with the real environment in which the decision is under the study, the modeling involves (zahrnuje) designing (navrhování) a set of experiments to be conducted (prováděny) in that environment, and measuring and interpreting the results of those experiments, research in the natural sciences, observations of a given phenomenon (jev),Operational exercises are on highest degree of realism of any form of modeling approach, and are expensive to implement (realizovat).

gaming: representation of the real environment. The model is simply a device that allows the decision-maker to test the performance of the various alternatives. However, the cost of processing each alternative has been reduced, and the speed of measuring the performance of each alternative has been increased, is used mostly as a learning device

simulation: the models are similar to gaming models except that all human decision-makers are removed from the modeling process, many simulation models take the form of computer programs, where logical arithmetic operations are performed in a prearranged sequence.

analytical model: problem is represented completely in mathematical terms, normally by means of a criterion or objective, which we seek to maximize or minimize, subject to a set of mathematical constraints that portray (zobrazit) the conditions under which the decisions have to be made, the model computes an optimal solution, that is, one that satisfies all the constraints and gives the best possible value of the obj. fun.

Which are the main types of the variables in the mathematical model?

Decision Variables are under the control of the decision-maker, the parameters, are beyond (mimo) the control of the decision-maker and are imposed by the external environment.

Parameters:

Exogenous Variables (external) are factor controlled from outside (economic conditions, actions of competitors (konkurence), prices of raw materials).

Policies and Constraints A decision-maker often operates within constraints imposed by company policy, legal restraints, or physical limitations.

Performance Measures (výkon) Managers always have objectives or goals that they are trying to achieve.

Intermediate Variables They are used to relate the decision variables and exogenous variables to the performance measures.

 

What is the goal of the linear programming model?

To find production levels that will produce the max profit or min cost, the model will clearly represent the real situation.

APPLICATIONS OF LINEAR PROGRAMMING

Which are the phases of application of the linear programming model?

1)identifying problem as solvable by linear programming

2) formulating a mathematical model

3) solving the model

4)implementation

What is the graphical presentation of the feasible region?

Graphical representation of the feasible region

SIMPLEX METHOD

POST OPTIMAL ANALYSES

GRAPH THEORY

45. Describe the graph called network. It is a connected graph, free of circuits. Weight with positive weights. Has exactly one starting point(it is single sourced) and one final point(eg sink)

46. Describe the graph called spanning tree. A tree whose edge (okraj) set is a subset of the edge set of the graph - at any undirected connected weighted graph, there is a minimum spanning tree, subgraph of a tree type with minimal sum of arc weights.

NETWORK MODELS

INTRODUCTION TO OPERATIONS RESEARCH

1. Explain the terms:

Unique matrix: determinant =1, all rows and columns are linearly independent,– square matrix nxn with 1 in diagonal

Reduced echelon form: a matrix is in this form if it satisfies conditions: a) It is row echelon form, b) every leading coefficient is 1 and is only nonzero entry in its column, May be computed by Gauss-Jordan elimination

- Is unique and doesn’t depend on the algorithm used to compute it

Coefficient matrix: the matrix formed by the coefficients in a linear system of equations, for example:

2x-3y=8 →2 -3 4x+5y=1 4 5

Right hand side vector (RHS):values of conditions, has to be behind inequality sign(<=) created by for example maximal capacity of something, or minimum of something

Augmented matrix: a matrix form of a linear system of equations obtained from the coefficient matrix. It is created by adding an additional column for the constants on the right of the equal signs. The new column is set apart by a vertical line.