3 Applications of linear programming

18. 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

19.Describe the steps in the graphical solution of the linear programming model.

1) Graphical Representation of the feasible solution: a) construction the lines and the planes corresponding with the constrains b) Finding the intersection

2) Finding an Optimal Solution: a)Choose the level of z

. b)construction the straight line corresponding with the goal function with the chosen righ hand side.

C)Construction of parallel line that intercepts the farthest point from the origin within the feasible region.

20.What is the graphical presentation of the feasible region?

Graphical representation of the feasible region

21. Which solutions of the lp model are feasible, which are optimal and which are suboptimal?

• A solution is feasible if it respects all the constraints

• optimal if it maximizes the objective among feasible solutions.

• Subomtimal – something what is close to optimal solution, but has different basis and same účelová funkce

22. How many optimal solutions can have the LP model? It is possible to have more than just one optimal solutions. But only 1 optimal solution value. This may occur when the objective function has the same slope as one its binding constraints.

23. What is a shadow price on a constraint? In graphical representation.

(zj-cj)-test of optimality, means how the OF would change with every unit of the variable (if the variable entered the basis), The shadow price on a particular constraint represents the change in the value of the objective function per unit increase in the right hand-side value of that constraint. For example, suppose that the number of hours of molding-machine capacity was increased from 60 hours to 61:

24.What is integer LP model and mixed integer LP model?

Integer LP model: when we need additional integrality constraints to make it real.

Mixed integer LP: only some of the variables are constrained to be integers, while other variables are allowed to be non-integers.

4 SIMPLEX METHOD

25. How we can change the set of inequations into a set of equations in the simplex algorithm?

Slack or surplus variables convert any inequality to equality form.

Slack ≤

Surplus ≥

26. What is the real interpretation of the slack and surplus variables?

excess of the minimum requirement and is called a surplus variable. = variable that is substracted from an inequality constraint to transform it to an equality

slack variable = variable that is added to an inequality constraint to transform it to an equality !!!it has 0 value, overproduction, non used capacity, -s=over production

27. Which are the basic variables in the simplex algorithm?

Entering variable: Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative.

Departing variable(leaving)- Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any nonnegative value with the solution remaining feasible. In this case the objective function is unbounded below and there is no minimum.

28. Why do we use artificial variables in the simple method? We use it when we need to get a canonical form, which is matrix, where should be an identity matrix(010101) and because of condition, that every s has to be positive > or = zero, so we add it to surplus or to equation

29. Describe the “big M” method. for the objective function

An- variables: MAX cost = -M, MIN cost= M (large number), use it in simplex table The "Big M" refers to a large number associated with the artificial variables, represented by the letter M.

1. Modify the constraints so that the RHS of each constraint is nonnegative. Identify each constraint that is now an = or ≥ constraint. 2. Convert each inequality constraint to standard form (add a slack variable for ≤ constraints, add an excess variable for ≥ constraints). 3. For each ≥ or = constraint, add artificial variables. Add sign restriction ai ≥ 0. 4. Let M denote a very large positive number. Add (for each artificial variable) Mai to min problem objective functions or -Mai to max problem objective functions.

5. Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex.

Remembering M represents a very large number, solve the transformed problem by the simplex.

M min (100) M max (-100) I use this in simplex table

30. How will the slack, surplus an artificial variables change the objective function?

They will not change it because they have zero value the slack: ≤ surplus: ≥ artificial variables: When converting lp into cannonical form - Artificial variable = and ≥

5 POST OPTIMAL ANALYSES

31. Describe the optimality test in the simplex algorithm (calculation of zj-cj)

Zj-cj= test of optimality (c^bvektor x x_nvektor) - c_n, Cb – cost coefficient (costs of the variables in basis)

Xn vektor-leading element and then for example x₁,x₂,x₃ columns and so on, Cn – objective function, to co je nad x1,x2, Xb – basic of achal table, consists of some of the variagles

32. Which information brings the optimality test in the simplex algorithm?

Is the solution optimal or not, which is the pivot column and which variable enters the base

33. Describe the test for unbounded objective function in the simplex algorithm (calculation of Ω_min).

RHS/leading column, then choosing minimum value in omega and the point where is the lowest value of omega is leading row

34. Which information brings the test for unbounded objective function in the simplex algorithm? Determine leaving variable

35. How can we assign the entering and departing variable in the simplex algorithm?

Entering: The reduced profits are minus the coefficients of the non-basic variables in the Z-equation. MAX: the highest negative value. MIN: The highest positive value

Departing: Non-basic variables will become basic variables and vice versa

35. 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

36. 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)

37. 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