Pesquisa operacional

Dual Simplex
Suppose we have the Pinocchio LP: maximize 3x1 + 2x2 s.t. 2x1 + x2 ≤ 100 x1 + x2 ≤ 80 x1 ≤ 40 Let’s take the dual (and introduce big M): minimize 100y1 + 80y2 + 40y3 + M a1 + M a2 2y1 + y2 + y3 − e1 + a1 ≥ 3 y1 + y2 − e2 + a2 ≥ 2 (5) (6) (7) (1) (2) (3) (4)

We could negate the objective, and follow through with the big-M’s, but let’s see if we can work directly on the dual.

Dual Simplex
Let’s remove the artificial variable and make the excess variables be the basic variables: min z = 100y1 + 80y2 + 40y3 e1 = −3 + 2y1 + y2 + y3 e2 = −2 + y1 + y2 (11) (8) (9) (10)

Note that the basic variables are negative. Also the objective function is too small. Let’s do simplex in a different way. We will choose a negative basic variable, and try to increase it, while keeping all the objective function coefficients positive. So we choose e1 to leave, and we choose the variable with the minimum ratio of objective function coefficient to row of e1 coefficient (among the variables with positive e1 row coefficient) to enter. This means that y3, with ratio 40 will enter. We perform the pivot and obtain: min z = 120 + 20y1 + 40y2 + 40e1 y3 = 3 − 2y1 − y2 + e1 e2 = −2 + y1 + y2 (12) (13) (14)

Dual Simplex, continued

min

z = 120 + 20y1 + 40y2 + 40e1 y3 = 3 − 2y1 − y2 + e1 e2 = −2 + y1 + y2

(15) (16) (17)

Notice that the coefficient of e1 is 40 and the objective function is 120, corresponding to the primal solution (40, 0). We continue pivoting. e2 is negative and will leave. To enter, we choose y1 with ratio 20. This yields min z = 160 + 20y2 + 40e1 + 20e2 y1 = 2 − y2 + + e2 y3 = −1 + y2 + e1 − 2e2 (18) (19) (20)

Dual Simplex

min

z = 160 + 20y2 + 40e1 + 20e2 y1 = 2 − y2 + + e2 y3 = −1 + y2 + e1 − 2e2

(21) (22) (23) This

We perform another iteration, with y3 leaving and y2 entering. yields: min z = 180 + 20y3 + 20e1 + 60e2 y1 = 1 − y3 + e1 − e2 y2 = 1 + y3 − e1 + 2e2

(24) (25) (26)

Notice now that all the basic variables are positive. We