University of Liverpool – Question 1: (0 points)
When we looked at the Primal Simplex Algorithm last week, we made a number of assumptions about the LP we were solving. We will now look at how to adapt the same method to more general settings.
First, let’s consider the objective function z=f(x)z=f(x). Suppose our aim is to minimise zz with respect to some constraints. Using the elementary property of inequalities
a≤b⇔−a≥−b, a≤b⇔−a≥−b,
Copyright By PowCoder代写 加微信 powcoder
we note that the LP is equivalent to maximising −z−z with respect to the same constraints. So we only need to discuss methods for maximising an objective function.
For example, the LP:
minimise z=x1−4x2z=x1−4×2 subject to 2×1+3×2≤5×1,x2≥0
2×1+3×2≤5×1,x2≥0
can be re-written as:
maximise z=−x1+4x2z=−x1+4×2 subject to 2×1+3×2≤5×1,x2≥0.
2×1+3×2≤5×1,x2≥0.
Question 2: (0 points)
Last week we made the assumption that x=0x=0 is a feasible solution to our LP.
That is, we assumed that the constants in the structural constraints are all non-negative, so that taking each non- basic variable to be 00 gives non-negative values for all of the slack variables.
We are now ready to drop this assumption. The simplex method does not explicitly require us to start at the origin; we may start at any feasible point. However, spotting and checking that a point is feasible is non-trivial, and this can be avoided by modifying our problem in such a way that the ‘origin’ is a feasible solution of the modified problem.
Suppose the constraints are of the standard form Ax≤bAx≤b. If the ithith constraint gi(x)≤bi
has bi<0bi<0, we can multiply both sides of the inequality by −1−1 to get −gi(x)≥−bi,
−gi(x)≥−bi,
where −bi>0−bi>0. In this fashion, we can write each constraint as either a ‘less than or equal to’ or ‘greater than or equal to’ constraint with the constant term on the right hand side always positive (or at least non-negative).
As earlier, every ‘less than or equal to’ inequality is replaced with an equality by adding a slack variable. Now, every ‘greater than or equal to’ inequality is replaced by an equality by subtracting a surplus variable in the same fashion.
But this solves only one of our problems: the origin is still not a feasible solution. So we also add what is called an artificial variable to the left hand side of the equality, allowing us to take an initial feasible solution with x=0x=0 and all surplus values also equal to zero. The constraints of the LP will therefore be written in canonical form, with the slack variables and the artificial variables as basic variables, and the decision variables and the surplus variables as non-basic variables.
But that’s not quite the end of the story. The artificial variables have no real meaning in our original problem; they are introduced only to make life easier. In our optimal solution we require them all to equal zero.
To ensure this will happen, we subtract such a large multiple of them from our objective function that any optimal solution requires the artificial variables to be zero. The multiple we take is usually denoted by MM, hence this
method is called the ‘Big MM Method’.
Note that the first steps are always to substitute away any artificial variables in the objective function in order to bring the program into canonical form; this may be done algebraically or in tableaux form, and both methods will be shown in the following example.
Question 3: (0 points)
We wish to maximise z=2×1+x2
subject to 3×1+4×2≤5−x1−x2≤−1, 3×1+4×2−x1−x2≤5≤−1, where x1,x2≥0x1,x2≥0.
This is already a ‘maximise’ problem so we don’t need to change the objective function just yet. However the right hand side of one of our ‘less than or equal to’ inequalities is negative, so we multiply it by −1−1 to replace it with a ‘greater than or equal to’ inequality. The problem becomes:
subject to
3×1+4×2≤5×1+x2≥1,
3×1+4x2x1+x2≤5≥1,
where x1,x2≥0x1,x2≥0.
We follow the rules for the big ‘M’ method:
add a slack variable x3x3 to the ‘≤≤’ constraint;
subtract a surplus variable x4x4 from the ‘≥≥’ constraint and also add an artificial x5x5 to it; and subtract Mx5Mx5 from the objective function, where MM is a very large (unspecified) positive number.
The scalar MM is chosen to be so large that any non-zero value of an artificial variable incurs a large penalty in the objective function. If we need more than one artificial variable to solve a linear program, we can use the same MM for each one (because we can always choose MM to be as large as we need).
The modified problem is: maximise z=2×1+x2−Mx5 z=2×1+x2−Mx5
subject to
3×1+4×2+x3=5×1+x2−x4+x5=1,
3×1+4×2+x3x1+x2−x4+x5=5=1,
where x1,x2,x3,x4,x5≥0x1,x2,x3,x4,x5≥0.
We make the substitution x5=1−x1−x2+x4x5=1−x1−x2+x4 into zz so that zz becomes z=2×1+x2−Mx5=2×1+x2−M(1−x1−x2+x4)=(2+M)x1+(1+M)x2−Mx4−M z=2×1+x2−Mx5=2×1+x2−M(1−x1−x2+x4)=(2+M)x1+(1+M)x2−Mx4−M
The non-basic variables are the decision and surplus variables x1x1, x2x2 and x4x4, and the basic variables are the slack and artificial variables x3x3 and x5x5. The origin is a feasible solution for the modified problem, and we solve using the primal simplex method with extended tableaux.
We could alternatively complete this final modification in the tableau format. The initial tableau is as follows.
x1x2x3x4x5z−2−100M0x3341005x5110−111 zx3x5x1−231×2−141x3010x400−1x5M01051
This tableau is not in canonical form as the identity matrix (columns x3x3 and x5x5) does not have zeros above it in the zz row. We fix this by the row operation
Rz↦Rz−MRx5.
Rz↦Rz−MRx5.
The resulting tableau is canonical, and so we can proceed with the simplex algorithm. Note that this tableau exactly represents the program after we substituted away the artificial variable from the objective function. It is probably a little easier to remember to do this process, and to remember how to do it, by row operations rather than by algebraic substitution.
Pivoting operations continue as follows.
x1x2x3x4x5z−2−M−1−M0M0−Mx3341005x5110−111
zx3x5x1−2−M31x2−1−M41x3010x4M0−1×5001−M51
x1x2x3x4x5z010−22+M2x30113−32×1110−111
zx3x1x1001x2111x3010x4−23−1×52+M−31221
x1x2x3x4x5z05/32/30M10/3×401/31/31−12/3×114/31/3005/3
zx4x1x1001x25/31/34/3×32/31/31/3x4010x5M−1010/32/35/3
Since the top row contains no negative entries, the maximum value of zz for this LP is 10/310/3, and this occurs when (x1,x2)=(5/3,0)(x1,x2)=(5/3,0).
Question 4: (0 points)
The potential obstacles, introduced last week, to finding a solution to an LP, namely having an unbounded LP or an empty feasible region, can be identified from features of the tableaux.
If, after selecting a pivot column, it is impossible to select a pivot row because all entries in the column are negative, then the objective function is unbounded and approaches ∞∞.
If an artificial variable does not vanish (that is, end up as 00) in an optimal solution, then the feasible region is empty.
Question 5: (0 points)
The Big ‘M’ Method can also be used to deal with ‘equality’ constraints. That is, suppose that we are maximising f(x)f(x) and that one of our constraints is of the form
Using the same method, we instead maximise f(x)−Mxm+1f(x)−Mxm+1 with the constraint above replaced by
g(x)+xm+1=b.
g(x)+xm+1=b.
We don’t need a slack or surplus variable since we require equality. However, introducing the MM allows us to solve such a linear program using the simplex algorithm with 00 as an initial feasible point.
You might be wondering why we don’t just substitute a variable away if we have an equality constraint. For a small number of variables and constraints this is probably what we’d do in real life, but for a larger number of variables and constraints it is more efficient just to go directly to the simplex algorithm without the added complexity of substitutions.
Question 6: (0 points)
Once we have found an optimal solution to an LP, we can apply sensitivity analysis to it to see how robust the solution is under small changes in the parameters of the problem.
In the spring factory example from last week, the total number of machines was capped at 3030. We could ask: what would happen to the optimal solution if space for one more machine was added, increasing the cap to 3131? That is, what happens to the objective function if we modify the constant in the constraint given by the limit on the number
of machines? Would the profit increase enough to cover the cost of obtaining the extra space?
Shadow prices are an idea that helps us address questions of this sort. The idea comes from economics, and can be thought of as ‘what is the maximum price the company would reasonably be expected to pay to obtain additional resources?’ In real-world situations, there isn’t a single straight-forward answer to questions like this.
In this case, we are asking how much it is worth spending to rent additional work space. While the company might be willing to pay a certain amount to hire space for 11 more machine, that doesn’t mean they will be willing to pay 100100 times as much to hire space for 100100 more machines. The limit on total spending would stop the company expanding that far, for example. On the other hand, the market value of factory space should not depend on the capital one particular company has. Likewise, if the company’s funds would only stretch to hiring half the space for a machine, which is clearly not a sensible decision in practice, that shouldn’t affect the market price.
Given this, the shadow price records the infinitesimal change in the objective function from increasing the available resources.
This is similar to the derivative for a function f(x)f(x), which records the infinitesimal change in ff as xx increases. What we calculate is an instantaneous rate of change at a particular point.
However, unlike a derivative, for linear programs we can get away with finding the effect of an increase of 11 unit, rather than needing to take a limit. Also unlike the derivative, the shadow price will always be non-negative.
Let us calculate how much our optimal solution z⋆=2890z⋆=2890 for the spring factory LP would (theoretically) increase by if we (instead) had capacity for one more operator. Recall that the original LP is
maximise z=63×1+113×2
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),
8×1+15×2+x3x1+x2+x4x1+2×2+x5x1,x2,x3,x4,x5=400=30=50≥0(budget in GBP100)(machines)(operators)(non-negativity), and the final tableau in the solution to this using the simplex algorithm is: x1x2x3x4x5z00013502890x3001−1−720×11002−110×2010−1120 zx3x1x2x10010x20001x30100x413−12−1×550−7−112890201020
The third constraint now becomes
x1+2×2+x5=51.
x1+2×2+x5=51.
This is equivalent to taking our original constraint, but replacing x5x5 by x5−1×5−1; so as we start with x5=0x5=0 (a non-basic variable in the final tableau) we will set x5=−1×5=−1.
Recall that we encoded the inequality constraint by specifying that the slack variable x5x5 must be non-negative. Considering the effect of adding in an additional worker corresponds to considering the effect of allowing x5x5 to become negative, expanding the feasible region.
From the first line of the tableau, we can read our objective function as: z=0x1+0x2+0x3−13×4−50×5+2890. z=0x1+0x2+0x3−13×4−50×5+2890.
Evaluating at
x1=10,×2=20,×3=20,×4=0,×5=−1, x1=10,×2=20,×3=20,×4=0,×5=−1, we get
and hence the shadow price of this constraint is 5050 (units).
It is no coincidence that this is exactly what appears beneath the corresponding slack variable, and we can simply read the shadow prices from the tableau: the shadow price corresponding to the budget constraint is 00, since this constraint introduced the slack variable x3x3 and 00 appears in the top of the the tableau under x3x3. Similarly, the operators constraint has a shadow price of 1313. What this tells us is that, in principle, for every 11 unit that we increase the machine capacity, the output increases by 1313 units; for every 11 unit that we increase the operator
capacity, the output increases by 5050 units.
Hence, in a real life situation, if the cost to increase capacity is less than the additional income from producing these extra units then the company should probably make the investment to do so. Recall that the budget constraint in this example was shown to be redundant: hence increasing our budget, whilst fixing everything else, will not lead to any increase in output.
As we said before, these are nominal figures that we cannot entirely rely on for larger increases. The graph below shows that if the right hand side of the operators constraint increases by 1010 then the budget constraint is no longer redundant, but the operators constraint is.
Question 7: (0 points)
The shadow prices tell us the result of allowing the option for the optimal point to move out of the feasible region across the boundaries created by the structural constraints. We can ask the same question about the boundaries created by the requirements that the decision variables are all non-negative. This gives us the reduced cost of each decision variable.
In the spring factory example, the reduced costs for both of the decision variables are 00. As with the shadow price, this can be read from the final tableau, by looking in the columns for the decision variables.
We can also see this by observing that the optimal solution is (x1,x2)=(10,20)(x1,x2)=(10,20), so the non-negativity constraints are not binding.
The LP to which we applied the Big ‘M’ Method provides us with an example where the reduced costs are not all 00: x1x2x3x4x5z05/32/30M10/3×401/31/31−12/3×114/31/3005/3 zx4x1x1001x25/31/34/3×32/31/31/3x4010x5M−1010/32/35/3
The reduced cost for the variable x2x2 is 5/35/3. To see this algebraically, notice that
z=−5×2/3−2×3/3−Mx5+10/3. z=−5×2/3−2×3/3−Mx5+10/3.
Evaluating this at
x1=5/3,×3=x5=0,×4=2/3
x1=5/3,×3=x5=0,×4=2/3
after replacing x2=0x2=0 with x2=−1×2=−1, we get z=5/3+10/3=z⋆+5/3.
z=5/3+10/3=z⋆+5/3.
Note that x2=0x2=0 in the optimal solution to this LP, so the non-negativity constraint for x2x2 is binding.
How can we interpret these results? The answer to this will depend on the context.
For the spring factory, it doesn’t seem very meaningful to consider having −1−1 members of staff or space for −1−1 machines.
But in our second example we have not been given the context, and setting x2=−1×2=−1 could have a sensible meaning.
For example, perhaps a local government regulation specifies that all manufacturers must have a certain number of people present at any one time, say 33, for health and safety purposes, and x2x2 records the number of workers above this minimum. In such a setting, the reduced cost can be thought of as telling us about the cost of the regulation.
For another interpretation, consider again the derivative of a function f(x)f(x). This tells us as much about what happens if we decrease xx as it does about what happens if we increase xx, provided we remember to consider the signs carefully.
(As with shadow prices, reduced costs are always non-negative.)
We can also think of the reduced cost of x2x2 as the decrease in the objective function if we tighten the constraint to x2≥1×2≥1, reducing the feasible region.
Evaluating the formula for zz at x1=5/3,×3=x5=0,×4=2/3 x1=5/3,×3=x5=0,×4=2/3
after replacing x2=0x2=0 with x2=1×2=1, we get z=−5/3+10/3=z⋆−5/3.
z=−5/3+10/3=z⋆−5/3.
So increasing x2x2 by one unit forces us to accept a non-optimal solution, and the reduced cost indicates by what
In the column for the artificial variable, the value we find is MM; any increase or decrease of an artificial variable incurs a large penalty. This is entirely to be expected since it is by construction; this is exactly why we introduced the artificial variable into the objective function in the first place.
Question 8: (0 points)
There is a relationship between the reduced costs and the shadow prices, which we will use later when we discuss dual programs. Let’s set some notation. Recall that in our existing notation for a linear program,
z=c1x1+⋯+cmxm,
z=c1x1+⋯+cmxm,
aj,1×1+⋯+aj,mxm≤bj,for 1≤j≤n.
aj,1×1+⋯+aj,mxm≤bj,for 1≤j≤n.
We will write yjyj for the shadow price for the jth constraint, corresponding to the jth slack/surplus variable, and ̄ci for the reduced cost of the decision variable xi.
We will also write Rj for the row of the initial tableau for the jth constraint, Rz for the z row of the initial tableau, and Rz⋆ for the z row of the final tableau.
Then Rz has a value of 0 in the column for every slack or surplus variable, and for the value of z. Moreover, the column for each slack or surplus variable contains a single 1 in the corresponding row, and all other values are 0.
At each stage of the simplex method, we modify the tableau using row operations. Therefore, Rz⋆ is given by Rz plus a linear combination of the other rows.
In the column for a slack/surplus variable, the value in Rz⋆ can only have been generated by copies of the original 1 in that column. That is, the value records the coefficient of the corresponding row in the linear combination. On the other hand, this value is the shadow price of the corresponding constraint. That is,
Rz⋆=Rz+n∑j=1yjRj.
Reading off the values of the reduced costs and the optimal value z⋆, we find that ̄ci=−ci+n∑j=1aj,iyj
and z⋆=n∑j=1bjyj.
Question 9: (0 points)
The objective function to an LP is given by z=cTx=c1x1+⋯+cmxm,
which we want to maximise. Suppose that a coefficient, say cs, is decreased by an amount Δs, so that the objective function becomes
z=cTx=c1x1+⋯+(cs−Δs)xs+⋯+cmxm
By how much will this change the optimal solution?
Intuitively, if −Δs is large and negative this means that xs>0 would incur a large penalty. On the other hand, if −Δs is large and positive then we prefer xs to be as large as possible. So we will consider the critical values of Δs between these two states. The result differs depending on whether xs is basic or non-basic in our optimal solution.
As we have just seen, the final z row of our optimal simplex tableau is obtained by adding a linear combination of the other rows to the original objective, and so adding −Δs to our initial tableau is exactly the same as adding −Δs to our final/optimal tableau, in the appropriate position. We will proceed by example.
An LP given in terms of variables x1,x2,x3≥0 has, after adding slack variables x4,x5≥0, the optimal tableau: x1x2x3x4x5z1050210x400−21−15×211−3015
We first consider the effect of changing a coefficient for a non-basic variable. Let’s choose x1, and increase the coefficient of x1 in the objective function by −Δ1 (i.e., we decrease the coefficient by Δ1, but writing this way allows us to avoid a negative sign in the tableau). The tableau becomes:
x1x2x3x4x5z1+Δ1050210×400−21−15×211−3015
Since x1 is a non-basic variable this tableau is in canonical form. Values of Δ1 such that 1+Δ1≥0 leave the optimal solution the same as we are not forced to apply the simplex algorithm again. That is, the optimal value of z is unchanged whenever
The situation is a little trickier when dealing with a basic variable. Let’s now instead choose x2, and increase its coefficient in the objective function by −Δ2.
x1x2x3x4x5z1Δ250210×400−21−15×211−3015
This tableau is not in the form required by the simplex algorithm: as x2 appears in the left-hand column (it is a basic variable) its column should contain a single 1 and 0 everywhere else. Hence we must subtract Δ2R2 from Rz to get:
x1x2x3x4x5z1−Δ205+3Δ202−Δ210−5Δ2×400−21−15×211−3015
Now that the tableau is in canonical form, we look to make a similar observation as before, namely, to ensure that all of the entries in the top row are non-negative so that the optimal solution is as stated, albeit as a function of Δ2. Thus, none of the following conditions may be violated:
1−Δ2≥0,5+3Δ2≥0,2−Δ2≥0. That is, Δ2≤1,Δ2≥−5/3,Δ2≤2. Thus, for
−5/3≤Δ2≤1,
the optimal solution is as above.
We can generalise the
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com