University of Liverpool –
Question 1: (1 point)
Put the matrix (−335343)
into row echelon form: __________
Copyright By PowCoder代写 加微信 powcoder
Question 2: (1 point)
Find the gradient of the function f(x,y,z)=18×4+8yz3−12x2z−y2. ∇f(x,y,z)=
__________
Question 3: (0 points)
One method to find the minimum point of the quadratic function f(x)=x2−5x+10
is to differentiate and calculate where the gradient is 0.
Alternatively, we can identify the minimum by completing the square: f(x)=(x−52)2−(52)2+10=(x−52)2+154.
We know that, for any value of x, the squared term (x−5/2)2 is non-negative. The minimum value of f must occur where this term takes its minimum value. Taking x=5/2 gives us (x−5/2)2=0, so this is the location of the minimum point. We can also immediately see that f takes the value 15/4 at this point.
The key point in this method is not so much that the term is squared, but that we know it is non-negative. We can use the same reasoning in other contexts where we know that certain terms are non-negative. Consider the function
g(x,y,z)=−342−6x−xy−14z3
in the region x,y,z≥0. We can see immediately that all of the terms in this expression are negative. Therefore the maximum value g can take is −342, and this occurs at (x,y,z)=(0,0,0).
This is the approach we will be using later. We will use a method for re-writing the function we want to optimise until it becomes obvious what the maximum point is.
Question 4: (0 points)
Linear programs are a particular type of optimisation problem. The mathematics we will use to solve them sits in the overlap between maths and computer science. We will start by looking at an example.
An engineering company produces springs of a certain kind.
In re-equipping the factory, two spring-making machines are considered:
The company has a maximum budget of GBP40,000 to spent on new machines, and the work bay can accommodate at most 30 machines and at most 50 operators.
How many of each machine should the company buy in order to maximise the daily output? We will formulate this problem as a Linear Programming problem.
Let x1 be the number of machines purchased of type 1, and similarly let x2 be the number of machines purchased of type 2.
Then we want to:
maximise z=63×1+113×2,
where z is the number of springs produced per day.
The situation also gives us the following constraints:
8×1+15×2≤400(budget in GBP100)x1+x2≤30(machines)x1+2×2≤50(operators)x1,x2≥0(non-negativity)
We might be tempted not to write the non-negativity condition (or simply write it in words) if it is clear from the context that a negative number would not make sense, but it is good practice always to write these constraints and to remember that they are a part of our program.
Another implicit condition for this example is that x1 and x2 should be integers, but for our purposes we will treat these problems as continuous, as the corresponding integer problem is much more difficult.
A Linear Program is given by the following.
i. We have decision variables x1,…,xm, which are under our control and are usually assumed to be non-negative.
ii. There is an objective function z=f(x1,…,xm), which we are trying to maximise.
iii. The decision variables satisfy constraints in the form of inequalities gj(x1,…,xm)≤bj.
Here we require that f and each gj is a linear function of x1,…,xm (hence the name ‘linear’ programming). The model is called a Linear Program or an LP.
Any LP can be written in the form
maximise z=c1x1+c2x2+⋯+cmxm
subject to a1,1×1+a1,2×2+⋯+a1,mxm≤b1a2,1×1+a2,2×2+⋯+a2,mxm≤b2⋮an,1×1+an,2×2+⋯+an,mxm≤bn (structural constraints) and
x1,x2,…,xm≥0
(non-negativity constraints). We could re-write these in the form −xi≤0.
Daily output
Operators needed
63 springs
1 per machine
113 springs
2 per machine
In the case of the spring factory, we took a real-world example and expressed it as an LP. By setting
x=(x1⋮xm),c=(c1⋮cm),b=(b1⋮bn),
A=(aj,i),z=f(x)=cTx,
we can write our LP in the more compact form
LP=max{cTx:Ax≤b,x≥0},
where we use inequality of vectors as shorthand for inequalities of the corresponding components.
Question 5: (0 points)
The set of points (x1,x2,…,xm) that satisfy all of the constraints of a given LP is called the feasible region.
When there are only two decision variables, the feasible region is a subset of R2. We can therefore solve the LP graphically. We construct (a picture of) the feasible region, and then identify the point (or points) of the region that optimises the objective function.
For the spring factory, we formulated the following LP: maximise z=63×1+113×2
subject to 8×1+15×2≤400,×1+x2≤30,×1+2×2≤50,×1,x2≥0.
Here is a graph of the feasible region.
Taking different choices of z= constant, the equations
z=f(x1,…,xm)
define a collection of parallel lines.
From vector calculus we know that the direction in which z grows fastest is normal to these lines, in the direction of the gradient ∇f.
For the spring factory, we have ∇f(x1,x2)=(63,113).
We (mentally) move the line z= constant in the direction of ∇f as far as we can whilst keeping at least one point on the line inside the feasible region. The point(s) from which we cannot move further is(are) the optimal point(s).
In this case, the marked vertex at (x1,x2)=(10,20) gives the optimal solution with z=2890.
Question 6: (0 points)
In general we may have m>2 decision variables and will need different methods to solve our LP. However, we can use the intuition from the two variable case to describe the possible things that can happen in general.
Case i: The feasible region is empty. In this case there is no solution to the LP.
Case ii: The feasible region is unbounded (i.e. not closed). In this case the solution to the LP may also be
unbounded, i.e. it has no finite solution.
Case iii: If the feasible region is bounded and non-empty, there is an optimal solution at a vertex.
Note that in general there may be more than one optimal solution existing along an edge of the feasible region. (Correctly understood, this result still holds when the variables are required to be integers provided there is at least one integer point inside the feasible region.)
Exercise: What would each of these cases look like on the graph in the case m=2?
Question 7: (0 points)
Looking at the picture we drew for the spring factory, notice that the line with equation 8×1+15×2=400 does not touch the feasible region.
The real-life interpretation of this is that, in this case, we can never spend the full budget, because of the restriction on operators. The budget constraint 8×1+15×2≤400 has no impact on the solution, so is called a ‘redundant constraint’.
A redundant constraint is any inequality that can be removed from the LP without affecting the feasible region. That is, it is an inequality that is implied by other inequalities in the program.
The other two structural constraints are
x1+x2≤30,×1+2×2≤50.
From these we can deduce that
(x1+x2)+7(x1+2×2)≤30+7×50=380.
Since 380<400 the third constraint becomes redundant.
However, it turns out that the optimal solution satisfies both of the other constraints as equalities. These are called 'binding constraints'.
A constraint for an LP is a binding constraint if the optimal solution satisfies it as an equality. Exercise:
Is it possible to identify redundant constraints without first finding the optimal solution? Is it possible to identify binding constraints without first finding the optimal solution? Which constraints in the spring factory example are neither redundant nor binding?
If we change a redundant constraint slightly, the optimal solution does not change; if we change a binding constraint slightly, the optimal solution changes. Sensitivity analysis for linear programs, which we will cover later, involves tracking, explaining and interpreting these small changes.
Since each constraint adds to the complexity of the LP, it is useful in real-life applications to identify and remove redundant constraints (if this can be done quickly) to save on computing time. On the other hand, we may want to keep the constraint in our problem for when we consider sensitivity analysis, while keeping in mind that it is redundant.
Question 8: (0 points)
The graphical approach is useful for gaining an intuitive understanding of the underlying problem, but becomes rather difficult to implement when we have more than two variables. We prefer a more algorithmic approach. There are several possible algorithms we could discuss, but we will stick to a particular type of 'simplex method' known as the Primal Simplex Method using extended tableaux.
Let's again think about the LP we have been considering:
maximise z=63x1+113x2
subject to
8x1+15x2≤400(budget in GBP100)x1+x2≤30(machines)x1+2x2≤50(operators)x1,x2≥0(non-negativity).
We can rewrite each inequality as an equality by introducing more non-negative variables so that the LP becomes: maximise z=63x1+113x2
subject to
8x1+15x2+x3=400(budget in GBP100)x1+x2+x4=30(machines)x1+2x2+x5=50(operators)x1,x2,x3,x4,x5≥0(non- negativity).
The variables x3,x4,x5 are called slack variables.
Where does this name come from? Say we have a 1.2m length of rope and we are attaching it between pillars that are 1m apart. We have a little more rope than we need; we say the rope has 0.2m slack. This is exactly the same concept here. Slack variable measure/record how much slack there is for a given constraint.
For example, x4 tells us how many more machines we could have in principle (in the absence of other constraints).
If we think about the point (x1,x2)=(20,10), which is inside the feasible region, we can calculate the slack variables at this point: (x3,x4,x5)=(90,0,10). This shows us that if we chose (x1,x2)=(20,10) as a solution, we would have GBP9000 left from the budget and 10 operators spare, but we would have used all the available space for machines. That is, only the machines constraint would be tight at that point; the other two constraints still have some slack.
In general, we introduce a slack variable for each of the n structural constraints (i.e. one each for all constraints other than non-negativity constraints), so that overall we are working with variables
x1,...,xm,xm+1,...,xm+n.
While we may be tempted to give the slack variables their own letter (some authors call them s1,...,sn, we will shortly see that it is convenient just to continue with our previous list.
Question 9: (0 points)
For the primal simplex algorithm, we need to split the variables x1,...,xm,xm+1,...,xm+n into two types, basic
variables and non-basic variables. These labels will change as we run the algorithm.
Look carefully at our list of constraints after adding the slack variables (ignoring the non-negativity constraints for the
8x1+15x2+x3=400(budget in GBP100),x1+x2+x4=30(machines),x1+2x2+x5=50(operators).
If we are only thinking about meeting these requirements, we can see the variables x1 and x2 as independent of the others, in the sense that we can choose any values we like for these two variables. The other variables are dependent, in that once we have chosen (x1,x2) there is exactly one choice for (x3,x4,x5) that satisfies the constraints.
However, this is not the only way we can view these variables/equations. We could rearrange the equations to make it clear that we could instead choose the values of (say) x2 and x5, and then use those to determine the others.
At each point in the algorithm, the non-basic variables are the ones we are thinking of as independent (i.e. that we are free to choose the values of), and the basic variables are the ones we are thinking of as dependent (determined by the values chosen for the non-basic variables).
The algorithm works by repeatedly finding a 'better' selection of non-basic variables, until we reach the 'best' selection at the optimal point.
To start the algorithm, we take x1,...,xm as non-basic variables and we take xm+1,...,xm+n (the slack variables) as basic variables.
We say an LP is written in canonical form if
each basic variable appears in exactly one of the constraints;
each constraint contains exactly one basic variable (always with coefficient 1); and the basic variables do not appear in the objective function.
These definitions can feel a little confusing at first, but should become clearer as we work through examples.
Question 10: (0 points)
We are now going to run through the steps of the primal simplex algorithm, in general form. If you find them hard to follow at this stage, read this page alongside the next one (or two).
The algorithm will be presented in the form of a 'tableau' (plural 'tableaux', which means 'table' or 'matrix' in this context). We begin from an initial feasible solution (that is, a point we can easily identify as being a solution to the constraints, but not necessarily the optimal one). From this starting point, each iteration of the algorithm will change the tableau to one that is closer to showing us the optimal solution.
Suppose we have an LP: LP=max{cTx:Ax≤b,x≥0},
where x=(x1⋮xm),c=(c1⋮cm),b=(b1⋮bn), A=(aj,i),z=f(x)=cTx.
Assume that x=0 is a feasible solution. That is, assume that the origin is in the feasible region; it meets all the constraints, but isn't necessarily optimal. This is going to give our initial feasible solution; we will deal later with the possibility that it is not a suitable starting point.
Set up the following initial tableau: x1⋯xmxm+1xm+2⋯xm+nz−c1⋯−cm00⋯0f(0)xm+1a1,1⋯a1,m10⋯0b1xm+2a2,1⋯a2,m01⋱⋮b2⋮⋮⋮⋮⋱⋱0⋮xm+nan,1⋯an,m0⋯01bn This tableau contains all the information about the LP.
The top row lists all variables in the program, both non-basic and basic, and these will not change as we perform our iterations.
The second row contains the negatives of the coefficients of the objective function z, and the value of z when all non-basic variables are equal to zero.
The remaining rows contain all of the information from the inequalities after slack variables are introduced. The central column contains the coefficients from the left hand sides of the inequalities.
The right hand column contains the constants from the right hand side of the inequalities.
There is a good reason why we take the negatives of the coefficients of z, which will become clear later. Some authors do not do this, so be careful when using other resources.
There are two important features of the tableau in this form.
First, the basic variables are written in the first column. When the non-basic variables are set to zero, the values of the basic variables can be read from the final column of the tableau. For the initial feasible solution (x1,...,xm)=(0,...,0), we have xm+i=bi.
The second feature is that it is straightforward to see that the tableau corresponds to an LP written in canonical form: the central block of coefficients contains (the columns of) an identity matrix, and all entries above this in the z row are equal to zero. We described this in a rather more technical way earlier, but this should be clearer. Note that for a tableau to be in canonical form, the columns of the identity matrix do not need to be adjacent or in the correct order; it just means that we could, in principle, swap columns to bring it to that form.
We will describe the algorithm in terms of a general tableau (as we will not always be starting from the initial tableau): x1⋯xj⋯xm+nzq1...qj...qm+nrxi1p1,1⋯p1,j⋯p1,m+nd1⋮⋮⋮⋮⋮xikpk,1⋯pk,j⋯pk,m+ndk⋮⋮⋮⋮⋮xinpn,1⋯pn,j⋯pn,m+ndn
The algorithm takes a tableau as an input, and outputs a new tableau. Repeat as necessary.
Note that the slightly awkward notation xik is because we don't at this stage know what these variables will be; only that there will be n of them.
1. If all qj≥0, then stop.
An optimal solution has been found:
the values of the non-basic variables are zero,
the values of the basic variables can be read from the rows, and the maximum value of z is r.
Otherwise, continue.
2. Suppose that qj is the most negative element in the z row. That is, qj<0 and for all qs we have qj≤qs.
Then xj will become a basic variable; it is called the incoming variable and its column is the pivoting column.
3. Perform the ratio test to determine the pivoting row: with j fixed, find the minimum value of ds/ps,j where
Suppose the minimum occurs at pk,j; then xik is the leaving variable and its row is the pivoting row.
Let Rs denote 'row s' and perform the following row operations (collectively this operation is called pivoting):
For all s≠k, replace Rs with Rs−(ps,j/pk,j)Rk.
Do not change the variable names in the header column.
Replace the top row, Rz, with Rz−(qj/pk,j)Rk.
(This is essentially the same operation as the previous one.)
Replace Rk with (1/pk,j)Rk.
Also replace the leaving variable xik with the incoming variable xj in the row header.
These details may be hard to remember, but what you're essentially doing by pivoting is ensuring the next tableau is in canonical form.
You divide the pivot row so that the pivot becomes 1, and you subtract multiples of this row from all other rows so that all other entries in the pivoting column become zero.
4. Repeat from step 1.
A tableau is said to be primal feasible whenever (using the notation in the general tableau above) we have d1,...,dn≥0. This is equivalent to the non-negativity constraints on our basic variables. We will return to this idea later.
Question 11: (0 points)
Let's now find the optimal solution for the spring factory LP using tableaux:
maximise z=63x1+113x2
subject to
8x1+15x2+x3=400(budget in GBP100)x1+x2+x4=30(machines)x1+2x2+x5=50(operators)x1,x2,x3,x4,x5≥0(non- negativity).
The initial tableau is:
x1x2x3x4x5z−63−1130000x3815100400x41101030x51200150
We see that the most negative entry in the z row occurs in the x2 column, so this is our pivoting column.
Now 30/1>400/15>50/2, and each of 1,15,2>0, so the x5 row is our pivoting row (highlighted above). We then make the following row replacements:
Rz↦Rz+113/2R5R3↦R3−15/2R5R4↦R4−1/2R5R5↦1/2R5.
Remember also to change the variable in the row header from the leaving variable x5 to the incoming variable x2.
The next tableau in our procedure is therefore:
x1x2x3x4x5z−13/2000113/22825×31/2010−15/225×41/2001−1/25×21/21001/225
The order in which we write the variables doesn’t matter, so this tableau is in canonical form: we don’t permute any columns, but it would be possible to do so to create an identity matrix with only zeros above it in the z row.
Since there is a negative value in the z row, we continue.
The pivoting column is the x1 column (it is the only negative value and hence is the most negative value). Since 25/(1/2)>5/(1/2), the pivoting row is the x4 row. We make the following row replacements:
Rz↦Rz+13R4R3↦R3−R4R2↦R2−R4R4↦2R4,
again remembering to change the variable in the row header from the leaving variable x4 to the incoming variable x1.
This gives the next tableau:
x1x2x3x4x5z00013502890x3001−1−720×11002−110×2010−1120
Since there is no negative entry in the z row, we stop and read off the solution: the objective function achieves a maximum possible value of z=2890, and this occurs when (x1,x2)=(10,20).
(We can also see that (x3,x4,x5)=(20,0,0), but these variables were not part of the original question, so we are not as interested in their values.)
Question 12: (0 points)
To understand what’s happening in the tableaux, we will now explain the geometric intuition behind the simplex algorithm by considering the spring factory LP again. If it seems like this is unnecessarily long, that’s because it is. We have already seen the efficient methods; now we want to think about why the simplex method works.
Maximise z=63×1+113×2 subject to
8×1+15×2+x3=400(budget in GBP100)x1+x2+x4=30(machines)x1+2×2+x5=50(operators)x1,x2,x3,x4,x5≥0(non- negativity).
We first note (as before) that (x1,x2)=(0,0) is a feasible solution for the non-basic variables. For this feasible solution we can also evaluate the objective function and the basic variables:
z=0;x1=0,×2=0;x3=400,×4=30,×5=50.
This is clea
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com