# Linear programming

?
• Created by: amy
• Created on: 17-03-13 13:51

## Linear programming

• The aim is to produce an optimal solution to a problem. eg. to find the solution that gives the maximum profit to a manufacturer.
• The descion variables are the numbers of the things that can be varied.eg. different types of books- is represented byx,y,z.
• The constraints are the factors that limit the problem. eg. limited amount of workers available. - they are written as inequalities in terms of the desicion variables. Usually they can't be negative.
• The objective function is what you are trying to maximise or minimise. eg. maximise profit, minimise the cost. It is usually in the form of an equation in terms of the desicion variables
• A feasable solution is a solution that satisfies all the constraints. It will give you a value for each of the desicion . On a graph the set of feasible solutions lie in the feasible region
• You are aiming to optimise the objective function- finding a solution within the feasible region that maximises or minimises the objective function- the optimal solution.
• To formulate a problem as a linear programming problem: define the desicion variables, state the objective (maximise/ minimise), write the constraints as inequalities.
1 of 8

## Linear programming graphically

• Equations of the form ax + b= c or y = mx + c are called linear equations, because their graphs are straight lines.
• Plotting the constraints on a graph is the easiest way to solve a linear programming problem.

1. Draw each of the constraints as a line on the graphh.

2. Decide which bit of the graph you want- whether the solution is above or below the line.        for y< mc+c you want the bit underneath the line                                                           for y>mx+c you want the bit above the line

3. shade the region you dont want. This way the feasible region is the unshaded region.

4. If the inequality is < or > use a dotted line. - this means you dont include the line in the region                                                                                                                                If the inequality is < or > (with line under) use a normal line. - this means you include the line in the range of solutions.

5. Once all the constraints are drawn, you can solve the problem.

2 of 8

## Feasible region and optimal point

• Since all of the points in the feasible region obey the constraints, they are all potential solutions to the linear programming problem.
• Objective line method

1. Draw the straight line Z= ax+by (maximise or minimise- objective function), choosing a fixed value of Z. This is called the objective line

2. Move the line to the right, keeping it parallel to the original line. As this happens, the value of Z increases. If you move it to the left, the value of Z decreases

3. If you are trying to maximise z, the optimal solution will be the last point within the feasible region that the line touches as you slide it to the right.

4. If you are trying to minimise z, the optimal solution will be the last point within the feasible region that the line touches as you slide it left.

• For a maximum point, look for the last point covered by an objective line as it leaves the feasible region.
• For a minimum point, look for the first point covered by an objective line as it enters the feasible region.
3 of 8

## Vertex testing

• The second method is vertex testing to locate the optimal point

1. First find the coordinates (x and y) of all the verticies in the feasible region. (by simultaneous equations of the lines that intersect at each vertex)

2. Put these values into the objective function Z=ax +by to find the value f Z.

3. Select the vertex that gives the optimal value of the objective function. Depending on your objective function, this might be either the smallest (if you are minimising) or the largest (if you are maximising).

4 of 8

## Determining solutions that need integer values

• There is an additional constraint in some problems- the solution has integer values
• In such cases the optimal point of the objective may not be an acceptable solution, so you have to find the optimal integer solution.
• You can use either the objective line method or the vertex method.
• Use the objective line method the same as before, but instead of looking for the last vertex the line touches, you look for the last point with integer coordinates in the feasible region
• If using the vertex method you consider all the points with integer coordinates that are close by. Make sure to check whether they satisfy the constraints- test this befroe you but the values into the objective function.
5 of 8

## Modelling matchings using a bipartite graph

• A bipartite graph has two sets of nodes.
• Arcs may connect nodes from different sets, but never connect nodes in the same set.
• A bipartite graph can be drawn even if the number of nodes in each set is not the same.
• You can use a bipartite graph to model a situation, and you can look at pairing some, or all the verticies to form a matching
• A matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y.
• 1 to 1 means that each paired element of set X is paired with just one element of set Y.
• A matching 'pairs off' nodes.
• If both sets have n nodes, a complete matching is a matching with n arcs.
6 of 8

## Maximum matching algorithm

• When you have drawn a bipartite graph, you find an initial matching, then apply the maximum matching algorithm to find an improved matching.
• An alternating path starts at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately 'not in' or 'in' the initial matching.

The algorithm:

2. Search for an alternating path.

3. If an alternating path can be found, use it to create an improved matching by changing the status of the arcs. If an alternating path can't be found, stop.

4. List the new matching, which consists of the result of applying the alternating path together with any unchanged elements of the initial matching.

5. If the matching is now complete, stop. Otherwise return to step 2.

7 of 8

## Maximum matching algorithm

• Each time you apply the maximum matching algorithm and find an alternating path, you increase the number of matched pairs by one
• If there is more than one pair of unmatched nodes you will need to find more than one alternating path.

1. An alternating path starts at a node on one side of the graph that isnt included in the inital matching and finishes at a node on the other side that also isnt included.

2. To get from the start node to the finishing node, you have to alternate between arcs that are not in and in the initial matching. So the first arc you use is not in the matching, the second arc is, the third isnt...

3. When you reach a finish node, you can stop - you have made a breakthrough

4. Now use the alternating path to construct an improved mathing. Take the path and change the status of the arcs, so any arcs not in the initial matching are in the new matching, and arcs that were in the initial are not in the new one.

5. The improved mathing should include two nodes that werent in the initial matching, and have one extra arc.

8 of 8