2.5 Integer Solutions for Linear Programming Problems

Note: if you cannot remember how to analyse linear programming problems using graphical methods, revise notes for 2.4 Graphical Method for Solving Linear Programming Problems.

Integer Solutions for Linear Programming Problems

  • When using graphical methods for solving linear programming problems, we are presented with a region which encompasses all possible solutions. If the decision variables are continuous any point within this region it corresponds to a feasible solution. However, if we are dealing with discrete variables, only a finite number of points within this region will correspond to values the variables can actually take on.
  • If the region is sufficiently small, it is possible for us to find all possible solutions for a linear programming problem with integer solutions.
Read More »2.5 Integer Solutions for Linear Programming Problems

2.4 Graphical Method for Solving Linear Programming Problems

Note: if you cannot remember how to setup a linear programming problem, revise notes for 2.3 Linear Programming.

Sliding Line Method

  • By drawing lines on a graph representing the minimum/maximum conditions as allowed by the systems inequalities, we bound a region. This region is known as the feasible region.
  • Any point within the feasible region represents a possible solution to this system. However, in general, we do not want just any possible solution, we want the “best” solution, known as the optimal solution. Often this is the combination of decision variable values that produces a maximum or minimum allowed value from the objective function.
  • If we substitute a point from the feasible region into the objective function we get a possible value for the quantity being optimised. If we then equate the objective function to this value, we produce a line of the form where a, b and c are constants and x and y are the decision variables. If we do this for another point, we will produce another equation which is parallel to the one just derived with the only difference being a different c value shifting the line upwards or downwards.
Read More »2.4 Graphical Method for Solving Linear Programming Problems

2.3 Linear Programming

Note: these notes cover the formulation and understanding of linear programming questions, methods for determining solutions to these problems are covered in notes for 2.4 Graphical Method for Solving Linear Programming Problems and 2.5 Integer Solutions for Linear Programming Problems.

Linear Programming and its Practical Applications

  • Linear programming describes a process whereby we wish to maximise the value of a particular function, known as the objective function.
  • The objective function is based on a number of variables, known as the decision variables. In the scope of Further Maths, we will analyse situations with two decision variables.
Read More »2.3 Linear Programming

2.2 Graphs of Linear Inequalities

Graphs of Single Variable Inequalities

  • Inequalities can be represented graphically as a shaded area.
  • For single variable inequalities, the shaded area is enclosed by two vertical (for x inequalities) or horizontal (for y inequalities) lines.

Example

Below is a graph representing the inequality -2 \leq x \leq 1:

Picture 1

Graphs of Two-Variable Inequalities

Read More »2.2 Graphs of Linear Inequalities

2.1 Linear Inequalities

Single Variable Inequalities

  • Inequalities provide a range of values that a variable can possess.
  • Inequalities of the form x>a or x<a where x is a variable and a is a constant tell us that x is greater than a or less than a, respectively.
  • Adding a line beneath the inequality symbols indicates that the variable can also be equal to the value it is being equated to e.g. x \geq a means x is greater than or equal to a.
  • Inequalities can also be used to represent a finite range of values using the form:

a<x<b

Read More »2.1 Linear Inequalities