Vertex Testing

Solving a linear programming problem using the simplex algorithm may give non integer solutions. Such solutions may not be practical, and we must look for integer solutions for each variable. The process of looking for integer solutions is called vertex testing. Suppose we have solved the linear programming problem:

Maximisesubject to the constraintsand

The simplex algorithm returns the solution

These are non integer solutions but we require integer solutions. We must test integer values of andclose to the solution above, to ensure that they satisfy the constraints and return a maximum value of

The points to test are

Point

Satisfies constraints?

2*12+3*3=33

4*12+3*3=57

yes

12+3=15

2*12+3*4=36

4*12+3*4=60

No

12+4=16

2*13+3*3=35

4*13+3*3=61

No

13+3=16

2*13+3*4=38

4*13+3*4=64

No

13+4=17

The only one of these points which satisfies the constraints isso the solution isand and the value ofis 15.