Методы и способы решения задач целочисленного параметрического программирования (стр. 6 из 15)

1. Считая значение параметра

равным некоторому числу , находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.

2. Находят значения параметра

, для которых задача (3.2.1) - (3.2.2) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра исключают из рассмотрения.

3. Выбирают значения параметра

из оставшейся части промежутка и устанавливают возможность определения нового оптимального плана. В случае существования оптимального плана находят его двойственным симплекс-методом..

4. Определяют множество значений параметра

, для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра .

Пример 3.2.1. Для каждого значения параметра найти максимальное значение функции

Решение. Считая

, находим решение:

Таблица 3.2.1.

БП	СЧ
		1	1	1	0	0
		2	-1	0	1	0
		-2	2	0	0	1
С		10	-1	0	0	0

Таблица 3.2.2.

БП	СЧ
		2	0	1	0	-1/2
		1	0	0	1	1/2
		-1	1	0	0	1/2
С		9	0	0	0	1/2

Оптимальный план при

: Этот план будет оставаться оптимальным, пока среди его компонент не окажется отрицательного числа:

.

Следовательно, при

Исследуем, имеет ли задача оптимальные планы при . Если , то и, следовательно, не является планом задачи. Поэтому надо перейти к новому плану. Это можно сделать, когда в строке имеются отрицательные числа. В данном случае это условие выполняется. Переходим к оптимальному плану, применяя двойственный симплекс-метод.

Таблица 3.2.3.

БП	СЧ
		0	2	1	0	1/2
		0	1	0	1	1
		1	-1	0	0	-1/2
С		0	9	0	0	5

Этот план остается оптимальным при

.

Если

, то это решение не является планом, так как . Так как в строке нет отрицательных чисел, то исходная задача неразрешима.

При

, не является планом, так как . С помощью таблицы 3.2.2 переходим к следующему решению:

Таблица 3.2.4.

БП	СЧ
		-4	0	-2	0	1
		3	0	1	1	0
		1	1	1	0	0
С		11	0	1	0	0

Этот план оптимален при условии . При задача неразрешима, так как в строке нет отрицательных чисел.