Ветвление множества D

;

- здесь .

- здесь .

6) Анализ множества D₁.

a) Определяем начальный план для :

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 500 миль, поэтому будет дробным: , => .

Таким образом, новый опорный план: .

;

б) Определяем начальный план для :

, ;

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 700 миль, поэтому будет дробным: , => .

Таким образом, новый опорный план: .

;

в) Определяем начальный план для :

, ;

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 100 миль, поэтому будет дробным: , => .

Таким образом, новый опорный план: .

;

г) Вычисление верхней и нижней границ.

Вычисляем верхнюю границу:

; – первое ограничение более жесткое.

Определяем опорные планы для первого ограничения:

– В этом случае .

– , ;

, ;

В последнем случае оставшееся после других городов расстояние равно 450 миль, поэтому . Таким образом: .

– , ;

, ;

В последнем случае оставшееся после других городов расстояние равно 100 миль, поэтому . Таким образом: .

Вычисляем нижнюю границу:

Т.к. , то ;

;

.

7) Анализ множества D₂.

Поскольку , то:

.

=> ;

a) Определяем начальный план для :

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 500 миль, поэтому будет дробным: , => .

Таким образом, новый опорный план: .

;

б) Определяем начальный план для :

, ;

, ;

, ;

Таким образом, новый опорный план: .

;

в) Определяем начальный план для :

, ;

В последнем случае оставшееся после других городов расстояние меньше 400 миль, поэтому будет дробным: , => . Таким образом, новый опорный план: .

;

г) Вычисление верхней и нижней границ.

Вычисляем верхнюю границу:

; – третье ограничение более жесткое.

Определяем опорные планы для третьего ограничения:

– , ;

В последнем случае оставшееся после других городов расстояние равно 50 миль, поэтому . Таким образом: .

– , ;

, ;

В последнем случае оставшееся после других городов расстояние равно 50 миль, поэтому . Таким образом: .

– В этом случае .

Вычисляем нижнюю границу:

Т.к. , то ;

;

.