Reading the Simplex Final Tableau Primal and Dual Variables

Linear Programming Methods for Optimum Blueprint

Jasbir S. Arora , in Introduction to Optimum Blueprint (2nd Edition), 2004

Solution. The final tableau for the problem is given in Tabular array 6-19. The graphical solution for the problem is given in Fig. half dozen-8. In the tableau, x _three is a slack variable for the first constraint, x ₄ is a surplus variable for the third constraint, x ₅ is an artificial variable for the second constraint, and ten ₆ is an bogus variable for the third constraint. For the first constraint, ten ₃ is the slack variable, and therefore, alphabetize j for use in Inequalities (6.24) is adamant equally 3. Using the aforementioned procedure as for Example six.17, the ranges for Δ₁ and b ₁ are calculated every bit −2 ≤ Δ₁ ≤ ∞ and 3 ≤ b ₁ ≤ ∞.

Read full affiliate

URL:

https://www.sciencedirect.com/science/article/pii/B9780120641550500069

Further Topics in Linear Programming

Bernard Kolman , Robert Eastward. Beck , in Elementary Linear Programming with Applications (Second Edition), 1995

Phase 2

The initial tableau for Phase 2 is the final tableau of Phase 1 with the post-obit modifications.

(a)

Delete the columns from the final tableau of Phase 1 that are labeled with the nonbasic bogus variables.

(b)

Supervene upon the row above the column labels with the coefficients of the original objective function, assigning 0 equally a cost for each of the bones bogus variables.

(c)

Form the vector c _B from the new row of objective function coefficients.

(d)

Summate the entries in the new objective row every bit $z_j-c_j={\text{c}}_{\text{B}}^{\text{T}}{\text{t}}_j-c_j.$

As we go on with the simplex method for Phase two we must ensure that the remaining artificial variables do not have on positive values. This would happen when 1 of these variables remained basic and the pivotal emptying gave a positive entry in x _B for the position labeled past the bogus variable. Suppose that x _thou is to exist the entering variable and that the rows labeled by artificial variables are i _ane, i _ii, …, i _p . Denote the 1000th column of the current tableau by

${\text{t}}_{\text{k}}=\left[\begin{array}{c}{t}_{\mathrm{one}\mathrm{chiliad}}\\ t_{\mathrm{ii}k}\\ ⋮\\ t_{mk}\end{array}\right].$

It can exist shown (Practice 18) that if

$t_{i_{1}k}\ge 0,t_{i_{2}k}\ge 0,\dots ,t_{i_{p}k}\ge 0,$

and so none of the artificial variables that are basic will accept on a positive value. If, still, nosotros have

$t_{i_r\mathrm{thousand}}<0$

for some r, r = i, 2, …, p, then the usual simplex procedure could crusade the bogus variable that labels row i _r to have on a positive value. Consequently, we must modify the usual simplex procedure. The new procedure for selecting a departing variable is as follows. If at least one of the entries in the entering variable column corresponding to a row labeled by an bogus variable is negative, choose one of these bogus variables as the departing variable. Otherwise, apply the usual simplex process to obtain a finite optimal solution or to discover that such a solution does not exist.

Example 2.

In Section 2.3 we showed that the problem given in Example v ended with an artificial variable in the basis. Nosotros rework this example using the two-stage method. The original trouble in approved form is

Maximize z = x ₁ + iix _ii + x ₃

field of study to

3x _ane + 10 ₂ − ten _iii = 15

8x ₁ + 4ten ₂ − ten ₃ = 50

2ten _i + iiten ₂ − x ₃ = xx

x _ane ≥ 0, x ₂ ≥ 0, x ₃ ≥ 0.

The new problem for Phase 1 is

Minimize z = y ₁ + y ₂ + y ₃

subject to

3x ₁ + ten _ii − x _three + y ₁ = 15

8x ₁ + ivx ₂ − ten _iii + y ₂ = fifty

210 ₁ + twox _ii + x ₃ + y ₃ = 20

10 _j ≥ 0, j = 1,2,3; y _i ≥ 0, i = 1,2,iii.

Nosotros rewrite the objective office equally

Maximize z = − y ₁ – y ₂ – y _iii

to have a maximization problem.

We now have the following sequence of tableaux (Tableaux 3.7–3.x) for Phase one. The objective row of the initial tableau is computed by using z _j – c _j . Since the initial basic variables are y _ane, y ₂, and y ₃, we have

${\text{c}}_{\text{B}}=\left[\begin{array}{c}-1\\ -1\\ -\mathrm{i}\end{array}\right]$

and

$z_{\mathrm{one}}-c_1=\left[-\mathrm{i}-1-1\right]\left[\begin{array}{c}\mathrm{three}\\ 8\\ 2\end{array}\right]-0=-13.$

Similarly,

$z_{\mathrm{ii}}-c_{\mathrm{ii}}=\left[-\mathrm{i}-1-1\right]\left[\begin{array}{c}1\\ \mathrm{four}\\ 2\end{array}\right]-0=-7$

and

z₃ − c_iii = i.

Tableau three.7.

Tableau 3.8.

Tableau 3.9.

Tableau 3.10.

For the basic variables y ₁, y ₂, and y _iii we have

$z_4-c_4=\left[-1-1-1\right]\left[\begin{array}{c}\mathrm{ane}\\ 0\\ 0\end{array}\right]-\left(-\mathrm{ane}\right)=0$

and, similarly, z _v – c _v = 0 and z ₆ – c ₆ = 0.

The value of the objective part is

$\left[-1-1-1\right]\left[\begin{array}{c}\mathrm{fifteen}\\ 50\\ \mathrm{twenty}\end{array}\right]=-85.$

The results of these computations are shown in Tableaux three.7–three.x.

Thus, Phase ane has an optimal solution with x _ane = 7, x _iii = 6, y _one = 0 and value 0 for the objective function. The artificial variable y ₁ appears equally a basic variable in the optimal solution.

The initial tableau for Phase ii is shown in Tableau 3.xi. The columns corresponding to y ₂ and y _three have been deleted and a cost of 0 has been assigned to y _ane. The objective row has been filled in, using z _j – c _j .

Tableau 3.11.

We now apply the simplex method to Tableau three.11. In selecting the parting variable we make certain the entry in the row labeled past y ₁ and the pivotal column is nonnegative. If it is not, we will choose y _ane as the departing variable. We get Tableau 3.12.

Tableau 3.12.

An optimal solution to the original problem is therefore

$\begin{array}{l}{x}_{\mathrm{one}}=\frac{5}{2}\\ {\mathrm{10}}_2=\frac{15}{\mathrm{ii}}\\ {\mathrm{10}}_3=0,\end{array}$

which gives $\frac{35}{2}$ every bit the optimal value of the objective function.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124179103500061

The Simplex Method

Bernard Kolman , Robert E. Beck , in Simple Linear Programming with Applications (2nd Edition), 1995

Phase 2

We assume that no artificial variable is a basic variable at the end of Stage one and the value of the objective part of the auxiliary problem is zero. The optimal solution obtained in Stage ane is used to obtain an initial basic feasible solution for the original problem (ten), (eleven), (12). By deleting the y _i 's from the optimal solution, nosotros obtain a bones viable solution to the original problem because we accept assumed that no artificial variables appear in the optimal solution. The initial tableau for Phase 2 is the final tableau of Phase 1, with the following modifications.

(a)

Delete the columns labeled with artificial variables.

(b)

Calculate a new objective row as follows. Start with the objective function of the original problem (ten). For each of the basic variables in the last tableau of Phase 1, make the entry in the objective row in the column labeled by that basic variable equal to zero by adding a suitable multiple of the row labeled by that basic variable.

These two steps construct an initial tableau for Stage 2. Nosotros can at present apply the simplex algorithm to this tableau.

Case two (Continued).

We now form the initial tableau for Phase 2 from Tableau 2.28. We delete the columns labeled with y _one, y ₂, and y ₃ and and so employ the original objective function,

z = x ₁ − 2x ₂ − iiix ₃ – ten ₄ – x _v + iix ₆.

The objective row would be

(26).

But the entries in the second, 3rd, and sixth columns must be zeroed for the optimality criterion to concur, since x ₂, 10 ₃, and x ₆ are basic variables. Nosotros exercise this by adding − 2 times the x ₂ row to (26); also, we add −3 times the 10 ₃ row and 2 times the 10 ₆ row to (26). This calculation yields

−ane	2	3	1	1	−two	0	[Equation (26)]
−1	−2	0	0	−1	0	−6	(− ii times x 2 row)
0	0	−3	− $\frac{3}{2}$	0	0	−9	(− three times 10 3 row)
0	0	0	1	ii	ii	18	(2 times ten 6 row)
−2	0	0	$\frac{\mathrm{i}}{2}$	2	0	3	(objective row for Stage 2).

We then have the initial tableau for Stage ii (Tableau 2.29), in which, as usual, nosotros have not included the z column.

Tableau 2.29.

We at present continue with the simplex algorithm to discover an optimal solution. The adjacent tableau is Tableau two.30 (verify).

Tableau 2.thirty.

Since the objective row in Tableau 2.30 has no negative entries, nosotros have found an optimal solution,

x ₁ = six, x ₂ = 0, ten ₃ = three, x ₄ = 0, 10 ₅ = 0, x _vi = 9,

which gives z = 15 every bit the value of the objective function.

Nosotros had originally put an artificial variable in every equation. This method requires no determination steps but may cause more than tableaux to be computed. If some of the equations take a variable that can be used as a bones variable, and then it is not necessary to introduce an artificial variable into each of those equations.

EXAMPLE three.

In the problem discussed in Instance 2, we run across that x _vi can be used as a basic variable. That is, information technology appears in merely ane equation and, in that equation, has a coefficient of +1. Consequently, we need to introduce artificial variables only into the first and third equations. Doing this, we obtain the auxiliary problem

Minimize z′ = y ₁ + y ₂

subject to

ten _one + twoten _ii + 2x _three + x ₄ + x ₅ + y ₁ = 12

x ₁ + 2x ₂ + ten ₃ + x _four + 2x _v + x ₆ = 18

iiix ₁ + 610 ₂ + 2x ₃ + x _four + threex ₅ + y ₂ = 12

x_j ≥ 0, j = one,2,…,6; y ₁ ≥ 0, y _two ≥ 0.

As before, we must eliminate the basic variables from the objective function, rewritten as in (24) past adding −one times each of the constraints that includes an bogus variable to the rewritten objective function. We obtain

z − 4x ₁ − 8x ₂ − ivten ₃ − 2x ₄ − 4x ₅ = −36.

This now leads to the sequence of Tableaux 2.31, 2.32, and 2.33.

Tableau ii.31.

Tableau 2.32.

Tableau 2.33.

In Tableau 2.33 we take an optimal solution to the auxiliary problem in which all the artificial variables have value zero and are nonbasic variables. Thus, a basic feasible solution to the original problem is

[0 3 three 0 0 nine]^T,

as nosotros obtained in Example two.

The organisation of equations (eleven) that gives the constraints for the approved form of a linear programming trouble always must have a solution

if thou ≤ s and if there are m linearly contained columns in the coefficient matrix. But it is possible that none of the solutions satisfies the nonnegative criterion (12). When the artificial variables are added to the system of constraints (14), there is always a solution,

[0 0 … 0 b ₁ b ₂ … b _m ]^T,

that satisfies the nonnegativity weather condition (fifteen). A solution to the system in (xiv) is a solution to the organisation in (11) if all the artificial variables take values equal to cypher. We use the simplex algorithm to try to notice a solution to (14) in which all the artificial variables are zero. The simplex algorithm is designed to notice simply solutions that satisfy the nonnegativity requirements. Thus, if one of the y _i is positive when the simplex algorithm reaches an optimal solution to the auxiliary problem, this indicates that in that location are no solutions to (eleven) that satisfy the nonnegativity constraints (12). In this case, the original problem (10), (eleven), (12) has no feasible solutions. The post-obit case illustrates this situation.

Example iv.

Consider the general linear programming trouble

Maximize z = 2ten ₁ + 5x _ii

subject to

2x _one + 3x ₂ ≤ 6

x ₁ + ten _two ≥ 4

x ₁ ≥ 0, x ₂ ≥ 0.

By inserting slack variables ten ₃ and x ₄, we tin can write the trouble in approved grade every bit

Maximize z = 2x _i + 510 ₂

bailiwick to

2x ₁ + 3x ₂ + ten ₃ = 6

x _i + ten _two – x _four = 4

10 _j ≥ 0, j = 1,2,3,iv.

We insert an bogus variable y into the second equation; ten ₃ can serve as the basic variable in the first equation. The auxiliary problem and then has the form

Minimize z′ = y

field of study to

210 ₁ + 3x ₂ + 10 ₃ = 6

10 ₁ + x _ii – 10 ₄ + y = 4

10 _j ≥ 0, j = 1,two,3,iv; y ≥ 0.

Afterwards calculation −i times the second constraint to the rewritten objective role, nosotros obtain

z′ – 10 _ane – x ₂ + x ₄ = −4.

We then calculate the sequence of Tableaux 2.34, two.35, and 2.36.

Tableau 2.34.

Tableau 2.35.

Tableau 2.36.

Tableau 2.36 represents an optimal solution to Phase ane in which the bogus variable y has the value ane. This means that the given problem has no viable solution. When we look at the graphs of the constraints (Figure ii.4), nosotros see that at that place is no intersection betwixt the two half-spaces. The gear up of viable solutions is empty.

Effigy 2.iv.

We have already pointed out that an artificial variable tin can appear in an optimal solution to the auxiliary trouble with a value of naught. In this case the given problem has a feasible solution. The following example illustrates these ideas. We can consummate Phase 1 in this department; in Department 3.3 we will develop tools for treatment Phase 2.

EXAMPLE v.

Consider the linear programming problem in canonical course

Maximize z = x _i + iix _two + x ₃

discipline to

3x _i + x ₂ – x ₃ = 15

8x ₁ + fourx _ii – x _iii = 50

twoten _ane + 2x ₂ + x ₃ = 20

ten ₁ ≥ 0, x _two ≥ 0, x ₃ ≥ 0.

In this trouble we must innovate an bogus variable in each of the constraint equations. We obtain the auxiliary problem

Maximize z′ = y _ane + y _ii + y ₃

subject to

3ten ₁ + x ₂ – 10 ₃ + y ₁ = 15

8x ₁ + fourx _two – x _three + y ₂ = 50

2ten ₁ + 2ten ₂ + x ₃ + y _iii = twenty

x _j ≥ 0, j = 1,two,3; y _i ≥ 0, i = 1,2,3

Rewriting the objective function in the same manner as earlier, we obtain the initial tableau (Tableau two.37) for the auxiliary problem. At the cease of Phase one we obtain Tableau 2.38 which represents an optimal solution to the auxiliary problem with y ₂ = 0 as a basic variable.

Tableau 2.37.

Tableau 2.38.

Figure 2.5 gives a flowchart and Figure 2.six, a structure diagram that summarizes the two-phase method.

FIGURE two.5. Flowchart of the two-phase algorithm.

Effigy ii.6. Structure diagram of the 2-phase algorithm.

Read total chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012417910350005X

Linear Programming Methods for Optimum Design

Jasbir S. Arora , in Introduction to Optimum Design (3rd Edition), 2012

8.seven.ane Changes in Constraint Limits

Recovery of Lagrange Multipliers

Commencement, we study how the optimum value of the cost part for the problem changes if we change the right-side parameters, b _i (too known as resource limits), of the constraints. The Constraint Variation Sensitivity Theorem 4.7 can be used to study the consequence of these changes. Use of that theorem requires knowledge of the Lagrange multipliers for the constraints. Theorem 8.5 gives a way of recovering the multipliers for the constraints of an LP problem from the final tableau . Calculation of the new values of the design variables for the changed trouble is explained subsequently.

Theorem viii.five

Lagrange Multiplier Values Let the standard linear programming problem be solved using the Simplex method:

one.

For "≤ blazon" constraints, the Lagrange multiplier equals the reduced cost coefficient in the slack variable column associated with the constraint.

2.

For "=" and "≥ type" constraints, the Lagrange multiplier equals the reduced cost coefficient in the bogus variable cavalcade associated with the constraint.

3.

The Lagrange multiplier is always≥0 for the "≤ type" constraint, e'er≤0 for the "≥ type" constraint, and free in sign for the "= type" constraint.

Change in Cost Role

In Department four.7, the physical meaning of the Lagrange multipliers was described. At that place, the Lagrange multipliers were related to derivatives of the toll function with respect to the right-side parameters. Equality and inequality constraints were treated separately, with v _i and u _i as their Lagrange multipliers, respectively. Withal, in this section, we utilize a slightly different notation divers as follows:

e _i  the right-side parameter of the ith constraint

y _i  the Lagrange multiplier of the ith constraint

Using this notation and Theorem four.seven, we obtain the following derivative of the price function with respect to the right-side parameters, and the change in the optimum cost function:

(8.21) $\frac{\partial f}{\partial e_i}=-y_i\mathrm{;}\mathrm{\Delta }f=-y_i\mathrm{\Delta }{\mathrm{east}}_i=-y_i({\mathrm{due\; east}}_{i\text{new}}-{\mathrm{eastward}}_{i\text{sometime}})$

It is noted here that Eq. (eight.21) is applicable merely for minimization of the cost part. Besides, Theorem 8.5 and Eq. (8.21) are applicable merely if changes in the right-side parameters are inside certain limits; that is, there are upper and lower limits on changes in the resource limits for which Eq. (8.21) is valid. The changes need not be small, as was stipulated for nonlinear problems in Section iv.vii. Calculations for the limits are discussed later in this department. Note that the adding for Δf remains valid for simultaneous changes to multiple constraints; in that case all the changes are added.

Information technology is also noted that Theorem 4.vii and Eq. (8.21) were discussed in Section 4.vii for the full general problem written as the minimization of a toll function with "≤ type" and equality constraints. Nonetheless, Eq. (eight.21) is applicable to "≥ type" constraints besides, as long every bit intendance is exercised in using the appropriate sign for the Lagrange multiplier y _i and the change in right side Δe _i . We will demonstrate utilize of Theorem eight.v and Eq. (8.21) with examples.

Information technology is as well important to note that if an inequality is inactive at the optimum, then its slack or surplus variable is greater than 0. Therefore, its Lagrange multiplier is 0 to satisfy the switching condition, y _i s _i =0 (except for the abnormal case, where both the Lagrange multiplier and the constraint function have aught value). This ascertainment can help in verifying the correctness of the Lagrange multipliers recovered from the final LP tableau. Example viii.eighteen describes the recovery of the Lagrange multipliers from the last tableau for the "≤ type" constraints.

The Lagrange multipliers are also chosen the dual variables (or dual prices) for the problem. The concept of duality in linear programming is described in Chapter 9. Example 8.nineteen demonstrates recovery of Lagrange multipliers for equality and "≥ blazon" constraints.

Example 8.xviii

Recovery of Lagrange Multipliers for "≤ Blazon" Constraints

Consider the problem:

Maximize

(a) $z=5x_1-\mathrm{ii}{x}_{\mathrm{two}}$

subject to

(b) $\mathrm{ii}{x}_1+x_{\mathrm{ii}}\le \mathrm{ix}$

(c) $x_1-2x_2\le \mathrm{ii}$

(d) $-3{\mathrm{10}}_{\mathrm{i}}+2{\mathrm{10}}_{\mathrm{ii}}\le 3$

(e) $x_{\mathrm{ane}}\text{,}{x}_2\ge 0$

Solve the problem by the Simplex method. Recover the Lagrange multipliers for the constraints.

Solution

Constraints for the trouble and cost function contours are plotted in Figure eight.7. The optimum solution is at bespeak C and is given every bit ten _ane=4, x _two=1, z=xviii. The problem is transformed into the standard form as

Minimize

(f) $f=-5x_{\mathrm{i}}+2x_2$

subject area to

(g) $2x_1+{\mathrm{10}}_2+x_3=9$

(h) $x_1-2x_{\mathrm{two}}+{\mathrm{ten}}_4=\mathrm{ii}$

(i) $-3x_{\mathrm{i}}+\mathrm{two}{x}_{\mathrm{ii}}+x_5=3$

(j) ${\mathrm{ten}}_i\ge 0\mathrm{;}i=1\text{to}5$

where x ₃, x _four, and x ₅ are the slack variables. Solving the problem using the Simplex method, nosotros obtain the sequence of calculations given in Table 8.22 . From the terminal tableau,

Basic variables: x ₁=4, ten _two=i, x _v=13

Nonbasic variables: x ₃=0, ten ₄=0

Objective function: z=18 (f=−xviii)

Effigy eight.7. Graphical solution to the LP problem of Example 8.18.

Table viii.22. Solution to Case eight.eighteen by the Simplex method

Initial tableau: x iv is identified to be replaced with 10 1 in the basic set
Basic↓	x one	x 2	ten iii	ten 4	10 5	b
1. x 3	ii	1	1	0	0	9
two. x four	$\begin{array}{c}1\end{array}$	−ii	0	ane	0	2
3. 10 5	–3	2	0	0	1	3
4. Cost	$\begin{array}{c}-\mathrm{five}\end{array}$	two	0	0	0	f−0

Second tableau: x 3 is identified to be replaced with x 2 in the basic set
Basic↓	x 1	x 2	x three	ten 4	x 5	b
5. x iii	0	$\begin{array}{c}5\end{array}$	ane	−2	0	5
6. x 1	1	−2	0	ane	0	two
seven. x 5	0	−iv	0	iii	1	9
8. Cost	0	$\begin{array}{c}-8\end{array}$	0	5	0	f+10

Third tableau: Reduced cost coefficients in nonbasic columns are non-negative; the tableau gives optimum point
Basic↓	x 1	x 2	ten 3	10 4	x 5	b
9. x ii	0	one	0.ii	−0.iv	0	one
x. x i	1	0	0.4	0.2	0	iv
eleven. 10 v	0	0	0.8	ane.four	ane	13
12. Cost	0 (c′1)	0 (c′2)	i.6 (c′iii)	1.eight (c′4)	0 (c′5)	f+18

x _iii , x ₄ and x _v are slack variables.

In the trouble conception, x ₃, x ₄, and x _five are the slack variables for the iii constraints. Since all constraints are "≤ type," the reduced toll coefficients for the slack variables in the final tableau are the Lagrange multipliers as follows:

1.

For 210 _ane+ten _two≤9:

(yard) $y_{\mathrm{i}}=\mathrm{1.half\; dozen}(c{\prime }_3\text{in}\text{column}{x}_3)$

2.

For 10 ₁−iix _ii≤two:

(l) $y_{\mathrm{ii}}=\mathrm{i.8}(c{\prime }_{\mathrm{iv}}\text{in}\text{column}{\mathrm{ten}}_4)$

3.

For −3ten ₁+2x ₂≤3:

(m) $y_3=0(c{\prime }_5\text{in}\text{column}{x}_5)$

Therefore, Eq. (8.21) gives partial derivatives of f with respect to e _i equally

(n) $\frac{\partial f}{\partial {\mathrm{due\; east}}_1}=-1.6\mathrm{;}\frac{\partial f}{\partial {\mathrm{eastward}}_{\mathrm{two}}}=-\mathrm{i.8}\mathrm{;}\frac{\partial f}{\partial e_3}=0$

where f=−(5ten _one−twox ₂). If the right side of the first constraint changes from ix to ten, the cost role f changes by

(o) $\mathrm{\Delta }f=1.6({\mathrm{east}}_{1\text{new}}-{\mathrm{east}}_{1\text{onetime}})=-\mathrm{1.vi}(10-9)=-\mathrm{ane.half-dozen}$

That is, the new value of f volition be −19.six (z=xix.6). Indicate F in Effigy 8.7 gives the new optimum solution to this case.

If the right side of the 2nd constraint changes from two to 3, the cost role f changes by Δf=−i.8(3−2)=−1.8 to −19.eight. Indicate Yard in Figure viii.7 gives the new optimum solution. Note that any pocket-sized change in the right side of the tertiary constraint volition have no effect on the cost function. When the right sides of the first and second constraints are inverse to 10 and 3 simultaneously, the internet change in the cost part is −(ane.6+1.viii) (i.e., new f volition exist −21.4). The new solution is at bespeak H in Figure 8.7.

Instance 8.19

Recovery Of Lagrange Multipliers For "=" And "≥ Type" Constraints

Solve the following LP problem and recover the proper Lagrange multipliers for the constraints:

Maximize

(a) $z=x_{\mathrm{i}}+4x_2$

subject to

(b) ${\mathrm{ten}}_1+\mathrm{two}{x}_2\le 5$

(c) $\mathrm{ii}{\mathrm{10}}_{\mathrm{one}}+x_2=4$

(d) $x_1-x_{\mathrm{ii}}\ge 1$

(e) ${\mathrm{ten}}_1\text{,}{x}_2\ge 0$

Solution

Constraints for the problem are plotted in Figure viii.8. It is seen that line Eastward–C is the feasible region for the problem and point Due east gives the optimum solution. The equality constraint and the "≥ type" constraint in Eq. (d) are active at the optimum point. The optimum point, calculated using the agile constraints, is given equally (5/3, two/3).

Effigy viii.8. Constraints for the LP problem from Example viii.19. Viable region: line E–C.

This problem was solved in Example 8.13 using the two-phase Simplex method. The optimum point was reached afterward two Simplex iterations, where Phases I and Two concluded simultaneously. The Simplex iterations are given in Table eight.17 . The final tableau for the problem is copied from Table 8.17 into Table eight.23, where x ₃ is the slack variable for the "≤ type" constraint in Eq. (b), x ₄ is the surplus variable for the "≥ blazon" constraint in Eq. (d), and x ₅ and x _six are artificial variables for the equality and "≥ type" constraints, respectively. Note that the artificial variable column (x _six) is the negative of the surplus variable column (x ₄) for the "≥ type" constraint in Eq. (d). The solution from the final tableau is

Basic variables:

(f) $x_{\mathrm{ane}}=5\mathrm{/}3\text{,}{x}_2=\mathrm{two}\mathrm{/}3\text{,}{x}_3=\mathrm{two}$

Nonbasic variables:

(thou) $x_4=x_{\mathrm{five}}=x_6=0$

Toll function:

(h) $f=-\mathrm{thirteen}\mathrm{/}\mathrm{iii}$

Tabular array 8.23. Final tableau for Example eight.19

Basic↓	10 1	x 2	10 3	x 4	x 5	ten 6	b
xi. x 3	0	0	i	−ane	−1	1	two
12. x two	0	1	0	$\frac{\mathrm{ii}}{\mathrm{three}}$	$\frac{\mathrm{one}}{\mathrm{three}}$	$-\frac{2}{3}$	$\frac{2}{3}$
thirteen. x 1	i	0	0	$-\frac{1}{3}$	$\frac{1}{\mathrm{iii}}$	$\frac{1}{3}$	$\frac{5}{\mathrm{three}}$
xiv. Cost	0 (c′i)	0 (c′two)	0 (c′three)	$\frac{7}{3}({c\prime }_4)$	$\frac{5}{3}({c\prime }_5)$	$-\frac{7}{\mathrm{iii}}({c\prime }_{\mathrm{vi}})$	$f+\frac{13}{3}$

Notation: x ₃ =slack variable; x ₄ =surplus variable; x ₅ , x ₆ =artificial variables.

Using Theorem 8.5, the Lagrange multipliers for the constraints are

1.

For 10 ₁+210 _two≤5:

(i) $y_{\mathrm{one}}=0(c{\prime }_3\text{in the slack variable column}{x}_{\mathrm{three}})$

2.

For 2x ₁+x _ii=4:

(j) $y_{\mathrm{two}}=\frac{\mathrm{v}}{3}(\mathrm{c}{\prime }_{\mathrm{5}}\text{in the artificial variable column}{x}_5)$

3.

For x ₁−x _ii≥one:

(thou) $y_{\mathrm{iii}}=-\frac{7}{\mathrm{three}}(\mathrm{c}{\prime }_{\mathrm{half\; dozen}}\text{in the bogus variable column}{x}_6)$

When the right side of the third constraint is changed to two (x ₁−10 ₂≥two), the cost function f=(−ten _one−4ten _ii) changes past

(l) $\mathrm{\Delta }f=-y_3\mathrm{\Delta }{\mathrm{east}}_{\mathrm{three}}=-\left(-\frac{\mathrm{vii}}{\mathrm{three}}\right)(2-\mathrm{i})=\frac{\mathrm{seven}}{\mathrm{iii}}$

That is, the price function will increase by 7/3 from −13/iii to −2 (z=ii). This tin also exist observed in Effigy 8.eight. We volition demonstrate that the same outcome is obtained when the third constraint is written in the "≤ form" (−x ₁+x _two≤−1). The Lagrange multiplier for the constraint is 7/3, which is the negative of the preceding value.

Annotation that information technology is as well c′_iv in the surplus variable cavalcade x ₄. When the right side of the 3rd constraint is changed to ii (i.east., it becomes −x ₁+ten _ii≤−two), the cost function f=(−x _ane−4x ₂) changes by

(m) $\mathrm{\Delta }f=-y_3\mathrm{\Delta }{\mathrm{east}}_3=-\left(-\frac{7}{3}\right)\mathrm{[}-2-\mathrm{(}-\mathrm{ane}\mathrm{)}\mathrm{]}=\frac{7}{3}$

which is the same as earlier.

When the correct side of the equality constraint is inverse to 5 from 4, the cost office f=(−x _i−4x ₂) changes by

(n) $\mathrm{\Delta }f=-y_2\mathrm{\Delta }{e}_{\mathrm{two}}=-\frac{5}{\mathrm{iii}}(\mathrm{five}-\mathrm{four})=-\frac{5}{\mathrm{iii}}$

That is, the price part will decrease by five/3, from −thirteen/3 to −6 (z=6).

Read full chapter

URL:

https://www.sciencedirect.com/scientific discipline/article/pii/B9780123813756000085

More on Linear Programming Methods for Optimum Design

Jasbir S. Arora , in Introduction to Optimum Design (Third Edition), 2012

9.3.6 Use of the Dual Tableau to Recover the Primal Solution

It turns out that we practise not demand to follow the preceding process (Theorem ix.4) to recover the primal variables. The final dual tableau contains all of the information to recover the fundamental solution. Similarly, the final primal tableau contains all of the information to recover the dual solution. Looking at the concluding tableau in Table 9.4 for Example nine.v, we observe that the elements in the concluding row of the dual tableau lucifer the elements in the last cavalcade of the key tableau in Table 9.iii. Similarly, the reduced toll coefficients in the final cardinal tableau match the dual variables. To recover the central variables from the final dual tableau, we use reduced price coefficients in the columns corresponding to the slack or surplus variables. We note that the reduced cost coefficient in column y ₄ is precisely x ₁ and the reduced cost coefficient in column y ₅ is precisely 10 ₂.

Reduced cost coefficients corresponding to the slack and surplus variables in the final dual tableau give the values of the primal variables.

Similarly, if we solve the primal trouble, we can recover the dual solution from the final primal tableau. Theorem nine.5 summarizes this result.

Theorem 9.5

Recovery of the Central Solution From the Dual Tableau Let the dual of the standard primal defined earlier in Eqs. (9.19) and (9.xx) (i.due east., maximize d ^T x subject to Ax≤e, 10≥0) be solved past the standard Simplex method. And so the value of the ith fundamental variable equals the reduced price coefficient of the slack or surplus variable associated with the ithursday dual constraint in the final dual tableau. In improver, if a dual variable is nonbasic, then its reduced toll coefficient equals the value of the slack or surplus variable for the corresponding central constraint.

Note that if a dual variable is nonbasic (i.e., has a zero value), then its reduced cost coefficient equals the value of the slack or surplus variable for the respective central constraint. In Instance 9.five, y _three, the dual variable corresponding to the third primal constraint, is nonbasic. The reduced cost coefficient in the y ₃ column is 13. Therefore, the slack variable for the third primal constraint has a value of 13; that is, the constraint is inactive. This is the aforementioned as obtained from the final primal tableau. We likewise note that the dual solution tin can exist obtained from the terminal primal tableau using Theorem 9.5 every bit y _ane=one.six, y _two=1.viii, y ₃=0, which is the same solution as earlier. While using Theorem nine.five, the following additional points should be noted:

1.

When the final primal tableau is used to recover the dual solution, the dual variables correspond to the primal constraints expressed in the "≤" form only. However, the primal constraints must be converted to standard Simplex grade while solving the problem. Recall that all of the right sides of the constraints must be non-negative for the Simplex method. The dual variables are non-negative only for the constraints written in the "≤" course.

2.

When a primal constraint is an equality, it is treated in the Simplex method by adding an artificial variable in Stage I. There is no slack or surplus variable associated with an equality. We also know from the previous discussion that the dual variable associated with the equality constraint is unrestricted in sign. And so the question becomes how to recover the dual variable for the equality constraint from the terminal fundamental tableau. There are a couple of means of doing this.

The first procedure is to convert the equality constraint into a pair of inequalities, as noted previously. For example, the constraint 210 ₁+ten _two=four is written as the pair of inequalities 2x _one+x ₂≤four, −2x ₁−10 ₂≤−four. The two inequalities are treated in a standard manner in the Simplex method. The corresponding dual variables are recovered from the terminal primal tableau using Theorem 9.5. Let y ₂≥0 and y ₃≥0 be the dual variables associated with the two inequality constraints, respectively, and y _ane be the dual variable associated with the original equality constraint. And then y ₁=y ₂−y _three . Accordingly, y _one is unrestricted in sign and its value is known using y _two and y _iii .

The second mode of recovering the dual variable for the equality constraint is to behave forth its bogus variable column in Phase II of the Simplex method. And so the dual variable for the equality constraint is the reduced cost coefficient in the artificial variable column in the final primal tableau. We illustrate these procedures in Case nine.6.

Example ix.6

Utilise of The Terminal Primal Tableau to Recover Dual Solutions

Solve the following LP problem and recover its dual solution from the final cardinal tableau:

Maximize

(a) $z_p=x_1+4x_2$

field of study to

(b) ${\mathrm{ten}}_1+\mathrm{two}{x}_2\le \mathrm{v}\text{,}$

(c) $2x_1+x_2=4\text{,}$

(d) $x_1-x_2\ge 1\text{,}$

(e) ${\mathrm{ten}}_1\text{,}{x}_{\mathrm{two}}\ge 0$

Solution

When the equality constraint is converted into a pair of inequalities—that is, 2x ₁+x _two≤4, −2x ₁−x ₂≤−iv—the trouble is the same as the one solved in Example 8.17 . The final tableau for the problem was given in Table 8.21. Using Theorem 9.v, the dual variables for the preceding 4 constraints are

1.

x ₁+2x ₂≤v: y _i=0, reduced price coefficient of 10 ₃, the slack variable

2.

twoten ₁+x ₂≤four: y ₂=5/three, reduced cost coefficient of x ₄, the slack variable

3.

−twox ₁−x ₂≤−4: y _iii=0, reduced cost coefficient of ten ₅, the surplus variable

4.

−x ₁+x ₂≤−1: y ₄=seven/3, reduced cost coefficient of ten _{half dozen}, the surplus variable

Thus, from the to a higher place discussion, the dual variable for the equality constraint two10 _i+x ₂=iv is y ₂−y _iii=v/3. Note also that y ₄=seven/3 is the dual variable for the fourth constraint, written as −10 ₁+x _ii≤−i, and not for the constraint x _ane−x ₂≥one.

Now let the states re-solve the aforementioned trouble with the equality constraint as it is. The problem is the same as the one solved in Example 8.19. The last tableau for the problem is given in Table 8.23. Using Theorem 9.5 and the preceding discussion, the dual variables for the given three constraints are

one.

x ₁+2x _two≤5: y _i=0, reduced toll coefficient of x ₃, the slack variable

ii.

2ten _ane+10 ₂=4: y _ii=5/three, reduced cost coefficient of x ₅, the artificial variable

3.

−x ₁+ten ₂≤−one: y ₃=7/iii, reduced cost coefficient of x ₄, the surplus variable

Nosotros see that the foregoing 2 solutions are the same. Therefore, we do not have to replace an equality constraint by 2 inequalities in the standard Simplex method. The reduced toll coefficient corresponding to the artificial variable associated with the equality constraint gives the value of the dual variable for the constraint.

Read total chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123813756000097

Integer Programming

Bernard Kolman , Robert E. Brook , in Elementary Linear Programming with Applications (Second Edition), 1995

4.3 Branch AND BOUND METHODS

If the set of feasible solutions to the related linear programming problem of a mixed integer programming problem is divisional, then the integer valued variables can take on only finitely many values in this region. We had previously discussed solving a linear programming problem by enumerating the extreme points of the set up of feasible solutions and and then choosing an optimal solution from amongst these. Nosotros dismissed this beast forcefulness method in favor of the simplex algorithm that listed only some of the extreme points and chose an gild for the list in which the value of the objective office improved each fourth dimension. However, using cutting planes and the simplex algorithm can involve very lengthy computations. Thus, it may be advantageous to once more consider some enumerating technique.

We examine the possibility of cleverly enumerating the integer values that should exist considered for a mixed integer programming problem. The cleverness is needed then that the task does non get overwhelming. 1 technique that is used is that of implicit enumeration. This involves generating a list of some of the feasible integral solutions and saving the best solution in the list for comparison with lists that volition be generated subsequently.

A set S of feasible solutions to a mixed integer programming problem is said to exist implicitly enumerated if S does non comprise any solution that is better than the best currently known solution. Our strategy volition be to partition the set of feasible solutions into several subsets and so to dismiss many of these subsets considering they are implicitly enumerated. Nosotros can derive certain relations from the constraints of the problem and the value of the best current solution. These relations will exist violated by whatever gear up of solutions that is implicitly enumerated; that is, these relations requite conditions that are necessary for a solution to satisfy if information technology is to amend the value of the objective function. If many subsets of the set of feasible solutions can be implicitly enumerated, we can greatly limit the number of solutions that accept to be explicitly examined.

Information technology will be easiest to draw the enumeration technique if nosotros initially limit ourselves to a aught–one programming problem. Consider such a problem and assume that information technology has northward variables. The set of all feasible solutions, S, can be partitioned into two subsets, South ₀ and Due south ₁, where

S ₀ = {ten ∈S | ten ₁ = 0}

Likewise, both S ₀ and S _ane tin can be partitioned into two subsets—say, S ₀ is divided into Southward ₀₀ and S ₀₁, and South _i is divided into S ₁₀ and South ₁₁. We define S ₀₀ by

S ₀₀ = {ten ∈ S | 10 ₁ = 0 and x ₂ = 0}.

Similarly,

Due south ₀₁ = {x ∈ S | x ₁ = 0 and ten ₂ = i}

S ₁₀ = {x ∈ South | 10 ₁ = 1 and ten _ii = 0}

S ₁₁ = {x ∈ S | x ₁ = 1 and x ₂ = i}.

Each of the 4 subsets S_ij , i, j = 0 or one, can be partitioned further. We tin draw this procedure with a tree diagram, every bit shown in Figure four.ii. The numbered circles are called nodes; the lines connecting them are chosen branches. Node 1 represents the set Southward of all feasible solutions. The partitioning of S into S ₀ and S _one is represented by the branches leading to nodes two and 3. Node 2 represents S ₀ and node 3 represents S ₁.

FIGURE 4.2.

A sequence of nodes and branches from node 1 to any other node k is called a path to node k. Each branch represents the imposition of one constraint on the variables (setting 1 variable equal to 0 or 1). Node k represents the set up of all solutions to the original constraints that also satisfy the constraints imposed by the branches in the path to node k. For instance, node 9 represents

{x ∈ S | ten _ane = 0, x ₂ = 0, x ₃ = 1}.

If two nodes are connected by a path, the lower node represents a subset of the solutions that are represented by the college node.

If all possible values for the n variables in a cipher-one programming trouble are enumerated, we have to generate 2 ⁿ paths. The bottom node of each path would correspond to exactly one value for 10, and this value may be infeasible depending on the nature of the constraints. Our enumeration strategy will try to eliminate every bit many of these paths every bit possible from consideration. Nosotros describe one method that might be used to perform this elimination.

Suppose our nada–one programming problem has an optimal solution for which the value of the objective function is z ^*. Assume that we have institute a feasible solution to the problem that has an objective function value of z _L. Apparently, z ₅₀ ≤ z ^*. Go along in listen that z ^* is unknown and is precisely what we are trying to find. At this point we know that we practise not have to consider any set of solutions whose objective function values are smaller than z _L. Consider the prepare of solutions to the nothing–ane problem that is represented by node k. We tin notice an upper leap z ^yard _U for the values of the objective part at the solutions represented by node g past solving a related linear programming trouble. If

$z_U^k\le z_{\text{Fifty}},$

then no path that includes node k will yield an improved solution; the objective function values will all be no larger than $z_U^{\mathrm{1000}}$ . Consequently, we can eliminate all paths through node thousand without explicitly evaluating the objective part at each solution on the path. This set of solutions has been implicitly enumerated. In this case, node chiliad is called a final node.

Node k is besides called a terminal node if there are no viable solutions satisfying the constraints imposed at node k. Besides the original constraints and those imposed past the path leading to node k, we often add together the constraint

${\text{c}}^{\text{T}}\text{10}\ge z_{\text{L}}$

since nosotros are interested only in solutions that are better than the current best feasible solution. Finally, node k is called a concluding node if it represents a single feasible solution—that is, if all the variables have been assigned a unique value.

Both branch and bound methods and methods that search in the tree of solutions generate the nodes of the tree until all paths end in terminal nodes. At that indicate all solutions will take been explicitly or implicitly enumerated and the best solution establish is an optimal solution. The divergence between the two types of methods is the manner in which the nodes are generated. Search methods follow a path until it ends at a terminal node before examining another path. Branch and bound methods examine the nodes in a less straightforward manner. They may generate, more or less simultaneously, many unlike paths. Branch and bound methods use more reckoner storage than search methods do, but they have much more flexibility in examining the nodes and thus may be faster.

We will requite the details of one branch and bound method for solving an arbitrary mixed integer programming problem. This method was developed in 1966 by R. J. Dakin and is a modification of the Land–Doig method. Information technology is widely used in the computer codes for integer programming.

Consider the mixed integer programming trouble

(ane) $\begin{array}{l}\text{Maximize}z={\text{C}}^{\text{T}}\text{x}\\ \text{subject\hspace{0.17em}to}\\ Ax=b\\ x\ge 0\\ x_j,j\in I,\text{integral,}\end{array}\}$

where A is m × s, b is m × ane, c is southward × 1, and x is s × 1.

Dakin'southward method volition generate a tree very similar to the one we formed for the zero–ane programming trouble. For each node there will exist two branches to cheque. If neither of the branches ends in a terminal node, the method follows the most promising branch. The other branch is called dangling and must exist examined before the algorithm terminates. Dakin'due south method proceeds as follows:

Step ane

(Initial Solution). Solve the problem given past (ane) as a linear programming problem, ignoring the integrality restrictions. If all x_j , j ∈ I, have integral values, we are done. If non, go to Step two.

Pace 2

(Branching Variable Selection). Choose, from among those variables, x_j , j ɛ I, that do not accept integral values at this node, ane variable to be used to grade the branching constraints. An easily implemented rule for this pick is to use the variable whose value has the largest fractional function. At that place are other more than complicated rules that may even involve one iteration of the dual simplex method to decide which variable to choose. The x_j , selected must be a bones variable; otherwise, its value would exist zero. Suppose it is the i th basic variable in the final tableau for the node, and then that its value is x_Bi . We can write

$x_{Bi}=\left[x_{Bi}\right]+f_i,$

where 0 < f_i < i. Since x_j must have an integral value, it must satisfy either

(two) $x_j\le \left[x_{Bi}\right]$

or

(3) ${\mathrm{ten}}_j\ge \left[x_{Bi}\right]+1.$

Step iii

(Formation of New Nodes). We create ii new mixed integer bug represented by the node nether consideration in Stride 2. One problem is formed by adding constraint (2) and the other trouble is formed by adding constraint (three). Solve each of these problems equally a linear programming problem using the dual simplex method.

Step 4

(Exam for Last Node). Each of the nodes formed in Stride three may exist a concluding node for 1 of two reasons. Commencement, the trouble represented by the node may have no feasible solutions. Or the values of x_j , j ∈ I, are all integers. In the sometime case, label the nodes as terminal nodes and go to Step v. In the latter case, also labeling the nodes, compare the values of the objective function with the current best value. If the objective part value for the new node is better, replace the current all-time value with information technology. Become to Footstep v.

Step v

(Node Selection).

(a)

If both nodes were final nodes in Pace four, the next node to be considered is the next one on the listing of dangling nodes. If this dangling node has an objective function value larger than the current best value, and then employ this node and go to Stride 2. Otherwise, cheque the next node in the listing of dangling nodes. When the listing of dangling nodes is exhausted, end. The current best value is the optimal solution.

(b)

If exactly i node in Stride 4 was terminal, use the nonterminal node and go to Step two.

(c)

If both nodes in Step four were nonterminal, we choose the more than promising i. Usually the node with the largest objective role value is considered more promising. The other node is recorded in the list of dangling nodes to be considered afterwards.

Instance 1

Consider the pure integer programming problem

Maximize z = 7x ₁ + 3x _ii

subject to

2x _i + 5x _two ≤ xxx

viii10 ₁ + 3x ₂ ≤ 48

10 ₁ ≥ 0, x ₂ ≥ 0 and integers.

We solve the related linear programming problem and obtain the terminal tableau shown in Tableau 4.11. From this tableau we run across that an optimal solution is

$x_1=4\frac{7}{17},{\mathrm{10}}_2=\mathrm{iv}\frac{4}{17},z=43\frac{\mathrm{ten}}{17}.$

Tableau 4.eleven.

We cull ten ₁ as the branching variable, since it has the largest fractional role. The constraints to be added are

x ₁ ≤ 4 and x ₁ ≥ 5.

To carry out Step 3 we add together each of these constraints in plough to the concluding tableau in Step one. Nosotros get the tableaux shown in Tableaux four.12 and iv.13. For Tableau four.12 we take written

${\mathrm{ten}}_1=\frac{75}{17}+\frac{\mathrm{iii}}{34}{\mathrm{10}}_{\mathrm{three}}-\frac{5}{34}{\mathrm{10}}_4$

Tableau 4.12.

Tableau 4.13.

from the 2d row of Tableau 4.xi and then introduced a slack variable, u _i, then that our new constraint is

ten ₁ + u _ane = four

or

$\frac{\mathrm{three}}{34}{x}_3-\frac{\mathrm{v}}{34}{x}_4+u_1=4-\frac{75}{17}=-\frac{7}{17}.$

In the aforementioned style the new constraint for Tableau 4.13 becomes

$-\frac{3}{34}{\mathrm{10}}_3+\frac{\mathrm{five}}{34}{\mathrm{10}}_4+u_{\mathrm{one}}=-5+\frac{75}{17}=-\frac{10}{17}.$

We now apply the dual simplex method to each of these tableaux to obtain Tableaux 4.14 and 4.15, respectively.

Tableau iv.14.

Tableau four.15.

At this point nosotros have the tree in Figure 4.iii. The objective function value in node iii is larger than that in node ii. Consequently, node ii is recorded in our list of dangling nodes and we go on from node 3. We add the constraints

ten ₁ ≤ 2 and x ₂ ≥ three

Figure 4.3.

to the problem represented by node 3 to form two new problems. As before, we write

$x_2=-\frac{1}{3}{x}_{\mathrm{four}}-\frac{\mathrm{viii}}{3}{u}_1+\frac{8}{3}$

from the first row of Tableau four.15. Then past adding a slack variable to each of the constraints, we accept

x _ii + u _two = 2 and −x ₂ + u ₂ = − 3

or

(4) $-\frac{1}{3}{x}_4-\frac{8}{\mathrm{iii}}{u}_1+u_2=\mathrm{two}-\frac{8}{3}=-\frac{2}{\mathrm{three}}$

and

(5) $\frac{\mathrm{ane}}{3}{x}_4+\frac{8}{\mathrm{three}}{u}_1+u_2=-\mathrm{iii}+\frac{8}{3}=-\frac{1}{\mathrm{iii}}.$

We add each of constraints (four) and (5) to Tableau iv.xv to form Tableaux 4.16 and 4.17. We utilise the dual simplex method on each of these tableaux to try to restore feasibility. Tableau four.18 is obtained from Tableau 4.sixteen by this procedure. However, Tableau 4.17 represents an infeasible solution that satisfies the optimality criterion, because there are no negative entries in the pivotal row (labeled by u _ii). Thus, Tableau 4.17 represents a concluding node.

Tableau four.16.

Tableau iv.17.

Tableau four.18.

At this point we accept the tree in Effigy 4.4. Note that in node 3, x ₁ had an integer value, but in node iv, the value of ten _i is no longer an integer. Thus, we cannot expect a variable once it has an integer value to continue having an integer value.

FIGURE iv.4.

We now use Pace 2 on node 4, adding the constraints

ten ₁ ≤ five and ten ₁ ≥ 6.

We obtain Tableaux iv.19 and iv.20 later on introducing the slack variable u _iii and rewriting these constraints. We use the dual simplex algorithm on each of these tableaux to try to restore feasibility. Tableau 4.21 is obtained from Tableau 4.19, and Tableau 4.22 is obtained from Tableau 4.20 by this process. Since both Tableaux 4.21 and 4.22 give integer solutions, they correspond to final nodes. The solution

x _one = half-dozen, x ₂ = 0, z = 42

Tableau iv.19.

Tableau four.20.

Tableau four.21.

Tableau four.22.

from Tableau 4.22 is the better 1, since it gives a larger objective part value. We and so bank check the list of dangling nodes to see whether other branches of the tree must exist pursued. The simply dangling node has the objective function value z = 41 1/v, which is smaller than the value obtained in Tableau four.22. Branching at this dangling node will non increase the objective role value. Therefore, we have found an optimal solution to the original problem:

x _i = 6, x _ii = 0, z = 42.

The tree of problems that was constructed by the branch and jump algorithm for this example is given in Figure 4.5.

FIGURE iv.five.

The post-obit problem shows an application of the branch and bound algorithm to a mixed integer programming problem.

Example 2

Consider the mixed integer programming problem

Maximize z = twox ₁ + ten _ii + threeten ₃

field of study to

ivx _one + threeten ₂ − iiix ₂ ≤ half-dozen

2x ₁ + 3x ₂ + threex _iii ≤ iv

ten ₁ ≥ 0, j = one,2,3; x ₁, x ₃, integers.

Solution. The branch and leap method yields the tree shown in Figure 4.6. Notice that node 4 represents a possible solution to the problem since ten ₁ and x ₃ both have integer values. However, node five gives an objective function value that is larger than the one in node 4, so we might have a solution in which x ₁ and x _three have integer values with an objective office value greater than $\mathrm{three}\frac{1}{3}$ . Thus, we must generate nodes 6 and 7. We do not have to go across node 6 since its objective role value is smaller than that of node 4 and any farther branching will not increase the value of the objective function. Thus, node 4 represents the optimal solution to the given problem:

$x_1=0,x_2=\frac{1}{\mathrm{three}},x_3=\mathrm{i},z=\mathrm{iii}\frac{1}{3}.$

FIGURE iv.half dozen.

Read total chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124179103500073

clarkbefoulot.blogspot.com

Source: https://www.sciencedirect.com/topics/mathematics/final-tableau

Share this post