# 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 by*x,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.

## Linear programming graphically

- Equations of the form a
*x*+ b*y*=*c*or*y*= m*x*+*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.

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

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

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

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

## 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:

1. Start with any initial matching.

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.

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

## Comments

No comments have yet been made