What is the goal of the Gauss-Jordan elimination?

The goal in Gauss-Jordan Elimination is to use row operations (interchange two rows, multiply a row by a nonzero constant, add two rows, or add a multiple of one row to another row) to change the augmented matrix to row reduced echelon form (rref), Gauss – dole, Jordan –nahore

 

What contains the vector of basic optimal solution? Which are the values of non-basis variables?

Non basic variables are equal to 0, Basis variables have some value

Basic solution: = x_bvector X1(123) X2(232) X3(200) S1(100) S2(0) S3(0) A3(0)

 

Interpret the shadow prices of the slack variables.

Shadow price is the change in the optimal value of objective function per unit increase in the right hand side value for that constraint, all other problem data remaining unchanged, the right hand side for every constraint can be analysed in this way, so that the shadow price for a particular constraint is the zj-cj coeff.of the appropriate slack variable in the final tableau.

 

 

6 TRANSPORTATION PROBLEM – finding the optimal way of transporatation

Describe the process of solution (steps) of the transportation problem.

1) 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

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.

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.

 

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.

 

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.

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.

 

How do we solve transportation problems with degeneration?

Degeneracy problem is when the number of filled cells is less than number of columns minus one (m+n-1) Degeneracy appears at the moment when we cross the row and column at the same time(while finding initial solution) we need to add (occupy) more cells. M must be placed somewhere in row/ column where the degeneracy appeared, preferably to the cells with the lowest distance

 

 

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.

Describe the graph called Hamiltonian circuit. In which method it is applied?

Circuit through all arcs=a graph cycle(ie closed loop) through a graph that visits each node exactly once, the problem of finding an optimal Hamilton circuit in a complete weighted graph is often called Travelling problem or nearest neighbour algorithm.(vogel approxim.)

48. What is a coincidence matrix? Describe it. Tableau (matrix) = rewrites graph into the matrix, example: when doing shortest path problem, I can draw it like a graph or write it as a matrix – it is the same

49. What is weighted graph? What is the meaning of the weights in the maximal flow problem? Ohodnoceny graf, graph with values, and each plumb´s value means maximal flow trough this plumb from a to b

 

NETWORK MODELS

What are the differences between the transportation problem and assignment problem?

the transportation problem: deals with the distribution of goods from several points of supply(sources) to a number of points of demand(destinations).

Capacities (suppliers or sources),requirements are customers, destinations and demands. Demands have requirements and suppliers have capacities and I have to divide it so everybody is satisfied.

Models can also be used when a firm is trying to decide where to locate a new facility.

Good financial decisions concerning facility location also attempt to minimize total transportation and production costs for the entire system, I have requirements of demand

assignment problem: refers to the class of LP problems that involves determining the most efficient assignment of: people to projects, sales people to territories, jobs to machines etc. the objective is most often to minimize total costs or total time of performing the tasks at hand.

One important characteristic of as. problem is that only one job or worker is assigned to one machine or project. Capacitiy, requirements = 1 – always offering 1 and I want 1

What is total opportunity cost matrix? In which method it is used? How does it look?

When we have at least one zero in every row and column=zero opportunity cells more competent for assignment. In Vogel´s approximation method.

Jobs x y z

A 0 1 2

B 6 0 3

C 5 4 0

What is the goal of the assignment problem? What are the prerequisites?

Goal is to get 0 in each row and column, find the distance(shortest)-not path!!!

53.What is the goal of the travelling salesman problem? The aim is to find a simple cycle containing all nodes and minimizing the total distance. How to travel through all places(nodes), come back and travel with the shortest way.

How can be applied the Vogel approximation for the travelling salesman problem?

We calculate the difference between the two lowest-cost arcs leaving an origin or entering a destination.

We choose the field(arc) that has the lowest cost in that row or column having the greatest cost difference (add this arc into the tour). Then we delete all the other connections in the line and column of the chosen field. Delete the connection which closes the circle before all places are included.