Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 37

Let us analyze the effect of modifying the vector b. In other words, we shall study the behavior of the solution of the modified problem when b is replaced by = b+Δb.

[1.16]

Let xB be the basic variables of the solution. Our goal is to determine a condition that guarantees that the basis B will remain optimal. In fact, this is easy. The vector b only appears in the optimality condition [1.16]. Therefore, the basic variables xB remain optimal for the modified problem if

[1.17]

EXAMPLE 1.12.– Consider the LP:

[1.18]

[1.19]

In matrix form with slack variables, this can be written as:

Suppose that the optimal basis is B = {x₁,x₂}. Then

Compute xB:

Compute the reduced costs

The solution xB = (2, 4)T is therefore optimal, i.e. x = (2, 4, 0, 0, 0)T.

We will have if and only if

2 + 2a ≥ 0 and 4 − a ≥ 0.

This gives an interval for the parameter b₁: −1 ≤ a ≤ 4.

What is the interval for b₂?

We will have B ≥ 0 if and only if

2 − a ≥ 0 and 4 + a ≥ 0.

This gives the interval for the parameter b₂: −4 ≤ a ≤ 2.

What is the effect on the minimum value of the objective function?

The effect is: