Introduction to linear programming

13. Describe the linear programming model (3 parts). 3 parts of model: a) Objective (target) function – a linear mathematical relationship describing an objective of the firm, in terms of decision variables – this function is to be maximized or minimized. The decision maker will use it to evaluate alternative solutions to the problem. b) Constrains (conditions) consist of variables, are in form of inequalities a) capacityc. (<=) b) requirement (<=) c) exact value (=) d) balance (compering variables to each other)

c) Nonnegativity constrains (every x >=0)

14.Describe the constraints and the objective function in the linear programming model.

objective function a linear mathematical relationship describing an objective of the firm, this function is to be maximized or minimized. The decision maker will use it to evaluate alternative solutions to the problem.

Which are the basic groups of applications of the linear programming model?

The shift pattern problem,The cutting problem, Transportation problem, travelling salesman problem, shortest path problem, optimization, maximum flow problem

16.Describe the shift pattern problem. The production manager wants to devise a shift pattern for his workforce, objective is to simply find a feasible schedule to satisfy all constraints, have the minimum work-force.

17. Describe the cutting problem. The goal of this is to cut product into required size with minimum waste and sell it with maximum profit (as much pieces as possible)

 

 

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

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.

What is the graphical presentation of the feasible region?

Graphical representation of the feasible region

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.

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:

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.

 

SIMPLEX METHOD

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 ≥

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

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

 

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 ≥

POST OPTIMAL ANALYSES

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

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

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