Determination of the minimum of a linear function...

Determining the minimum of a linear function

In determining the minimum of a linear function Z, there are two possible ways:

1) determine the maximum of the function F, assuming F = -Z and taking into account that ;

2) modify the simplex method: at each step, reduce the linear function due to the non-primary variable that enters the expression for a linear function with a negative coefficient.

Consider this in the following example:

5.2. To solve the simplex method:

under constraints:

Solution. We introduce additional non-negative variables y - and y 6 with a minus sign, since the inequalities are of the form & quot ;. We obtain a system of equations:

If additional variables are taken as the basic ones for step I, we get an unacceptable basic solution: (0; 0; 0; 0; -2; -3). In this case, it is convenient to take the variables y3 and y4 as the basic ones (this agrees with the rule for choosing the basic variables formulated in Section 5.2), the coefficients of y3 and y> y A are positive, so in As an initial one, we get an admissible basic solution.

I step. Basic variables: y y y y

Non-basic variables: y v y 2 , y 5 , y 6.

We express the main variables via non-basic ones:

V, = (0; 0; 3; 2/3; 0; 0) is the first basic solution, it is admissible. We express a linear function through non-basic variables:

Ζ, = Z (T,) = 29 - this value is not minimal, since the function Z can be reduced by transferring to the basic of any of the variables y, or y 2, having in expression for Z negative coefficients. Since y x has a larger absolute coefficient, we start with this variable. For her, the greatest possible value is: y l = min {3/3; 2/3; 1/3} = 1, i.e. the first equation is resolving; y 3 becomes a non-primary variable, ΔΖ, = -4-1 = -4.

Step II. Basic variables: y y y 4.

Non-basic variables: y T y : i , y., y ().

We get after the transformations

Z = 25- (5/3) & frac34; + (4/3) & frac34; + 7 & frac34; + (11/3) & frac34; Is a linear function. With the basic solution Y2 = (1; 0; 0; 1/3; 0; 0), we get Z2 = Z (Y 2) = 25. Z2 - Z, = 25-29 = -4 = ΔΖ ,. We translate the variable y 2 into the basic ones, since it enters the expression for Z with a negative coefficient. The largest possible value of y 2 = min {3; 3/5} = 3/5, the second equation resolving, and y A goes to non-primary variables; ΔΖ2 = (3/5) (-5/3) = -1.

Step III: Basic variables: y y y 2.

Non-basic variables: y. A , y 4 , y-, y 6.

We get after the transformations

Z = 24 + y 3 +3 y A +6 y 5 + 4d/6. The basic solution Y., = (4/5; 3/5; 0; 0; 0; 0) is optimal, since in the expression for Z there are no non-basic variables with negative coefficients. Therefore, Z mjn = Z 3 = Z (Y 3 ) = 24. Ζ3 -Ζ2 = 24-25 = -1 = ΔΖ2. ► We formulate the criterion of optimality for finding the minimum of a linear function: If in the expression of a linear function through non-basic variables there are no negative coefficients for non-basic variables, then the solution is optimal.

Note . At each step of the simplex method, any non-basic variable is converted to basic, and each equation of the constraint system determines the finite or infinite largest possible value of this variable-the estimated ratio. In problems 5.1 and 5.2, there were various cases of estimating the growth of a non-primary variable, which depended on the signs and values ​​of the free term and the coefficient of the variable being transferred. We formulate all possible cases. We denote by x, the transferable non-basic variable, b ■ is the free term, a ~ is the coefficient of x. In the general form, the equation x - =/ .. + in ^ xr + ... determines the largest possible value of x by the following rules:

1) Xj = | fy/eJ if bj na ~ of a different sign and a T) * 0, ! & gt; ■ # 0; for example: x3 = 8 - 2x2 + ...; x 2 = 8/2 = 4 or x3 = -8 + 2x2 + ...; x 2 = 8/2 = 4;

2) x, - = oo, if bj and ay have the same sign and a-φ 0, bj φ 0; for example: X 3 = 8 + 2x2 + ...; X2 = oo,

3) x i = 0 if b = 0 and a T & lt; 0; for example: x3 = 0-2.x2 + ...; x2 = 0;

4) X/= о® if b. = 0 and ay & gt; 0; for example: x3 = 0 + 2x2 + ...; X 2 = oo,

5) x (. = oo, if aj = 0, for example: x3 = 5 + 0-x2 + ...; x3 = -5 + 0-x2 + ...; x2 = oo.

thematic pictures

Also We Can Offer!

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)