- •1 Introduction to operations research
- •Explain the terms:
- •What is the matrix form of the system of linear equations?
- •X column vector with n entries;
- •Apply the Frobenius theorem in the solution of the system of linear equations.
- •Describe the algorithm of the Gauss-Jordan total elimination.
- •Describe the algorithm of finding the inverse matrix.
- •Which are the phases of the decision making process?
- •Describe the Anthony´s classification of the decision making. Draw the Anthony´s pyramid.
- •Which are the typical features of the strategic planning, tactic planning and operational control?
- •Compare programmed and non programmed decisions.
- •Compare the main kinds of the mathematical models (operational exercise, gaming, simulation, analytical model).
- •11. Which are the main types of the variables in the mathematical model?
- •11. Describe the process of formulation and application of the linear programming model.
- •What is the goal of the linear programming model?
- •2 Introduction to linear programming
- •14. Describe the constraints and the objective function in the linear programming model.
- •15.Which are the basic groups of applications of the linear programming model?
- •3 Applications of linear programming
- •18. Which are the phases of application of the linear programming model?
- •19.Describe the steps in the graphical solution of the linear programming model.
- •20.What is the graphical presentation of the feasible region?
- •21. Which solutions of the lp model are feasible, which are optimal and which are suboptimal?
- •23. What is a shadow price on a constraint? In graphical representation.
- •38. Describe the process of solution (steps) of the transportation problem.
- •39. What is the number of basic and decision variables in the transportation problem?
- •40.Describe the optimality test in the transportation problem. Which information it provides?
- •40. What is the purpose of the Dantzig loop (closed path)?
- •41.How do we solve the situation when the sum of sources is not equal to the sum of demands?
- •43. How do we solve the situation when one or more communication routes are not available?
- •44. How do we solve transportation problems with degeneration?
- •7 Graph theory
- •47. Describe the graph called Hamiltonian circuit. In which method it is applied?
- •8 Network models
- •50.What are the differences between the transportation problem and assignment problem?
- •51.What is total opportunity cost matrix? In which method it is used? How does it look?
- •52. What is the goal of the assignment problem? What are the prerequisites?
- •54. How can be applied the Vogel approximation for the travelling salesman problem?
- •55.Describe the maximal flow problem and its solution.
- •56.Describe the shortest path problem and its solution.
- •57. Describe the Dijkstra algorithm. For what it is applied?
38. Describe the process of solution (steps) of the transportation problem.
Check if the problem is balanced – if not, it needs to be balanced by adding additional supplier/customer – “dummy” (not real)
2)Find the initial solution of the problem: a) North-west corner rule (not effective, but very easy) b) Least – cost method (quite simple / effective) c) Vogel approximation method (most effective/difficult) 3) Check degeneracy – deal with that by adding some additional artifial variable M 4) Check if the solution is optimal – is optimal – end, is not optimal 5) Find more perspective solution
39. What is the number of basic and decision variables in the transportation problem?
The constraint set is composed of (m+n-1) independent equations, and corresponding nondegerate basic solution will have exactly (m+n-1) basic variables.
40.Describe the optimality test in the transportation problem. Which information it provides?
ui,vj... dual costs, Determine the values of dual variables, ui and vj, using ui + vj = cij, put 0 anywhere and fill the others u,v so u + v = cost for unoccupied cells, Check the sign of each opportunity cost. If the opportunity costs of all the unoccupied cells are either positive or zero, the given solution is the optimum solution. On the other hand, if one or more unoccupied cell has negative opportunity cost, the given solution is not an optimum solution and further savings in transportation cost are possible. Select the unoccupied cell with the smallest negative opportunity cost as the cell to be included in the next solution.
40. What is the purpose of the Dantzig loop (closed path)?
It is used in transportation problem, vogel approximation method. When I am turning 90 degrees(in non empty cells) while walking in table, I am determining or removing numbers and creating new ones and so by this there will be created improvement.
41.How do we solve the situation when the sum of sources is not equal to the sum of demands?
We add “dummy row” which is not real
42. Describe the Vogel approximation. Where it is applied? transp.problem and travelling salesman problem
Salesman: A selection bases on the difference between the two lowest-cost arcs leaving an origin or entering a destination. This difference indicated where departure from the lowest-cost allocations will bring the highest increase in cost. Therefore one assigns the maximum possible amount to that arc that has the lowest cost in that row or column having the greatest cost difference. It is used in transportation problem, it is used to reduce the transportation costs by interpreting in a mathematical table the transport. costs from one place to another.
43. How do we solve the situation when one or more communication routes are not available?
If it is impossible to ship any goods from source I to destination j, we assign a very high cost to the corresponding variable xij, that is cij=M – M is a very large number, if these prohibited routes cannot be eliminated from the optimal solution, then the problem is infeasible.