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

БП	СЧ
	6	2	0	1	0	0
	16	0	0	0	1	0
	6	-1	1	0	0	1
С			0	0	0

Таблица 3.1.3.

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

Определим значения

, при которых план, соответствующий таблице 3.1.3, останется оптимальным:

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

задача имеет оптимальное решение: Возьмем . Тогда столбец – разрешающий. Переходим к новому опорному плану:

Таблица 3.1.4.

БП	СЧ
	11	1	0	1/2	1/2	0
	16	0	0	0	1	1
	1	0	1	1/2	-1/2	0
С		0	0			0

Этот план оптимален при условии:

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

При имеем:

Таблица 3.1.5.

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

Этот план оптимален при условии:

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

2. Задача с параметром в свободных членах системы ограничений

Дана линейная функция и система линейных ограничений

(3.2.1)

(3.2.2)

Алгоритм решения задачи (3.2.1)-(3.2.2) подобен рассмотренному выше алгоритму решения задачи (3.1.1)-(3.1.2). Полагая значение параметра

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

и числа

и определены компонентами оптимального плана и зависят от :

.

Если при

задача (3.2.1) - (3.2.2) неразрешима, то либо целевая функция задачи (3.2.1) не ограничена на множестве планов, либо система уравнений (3.2.2) не имеет неотрицательных решений. В первом случае задача неразрешима для всех , а во втором случае определяем все значения параметра , для которых система уравнений (3.2.2) несовместна, и исключаем их из рассмотрения. После определения промежутка, в котором задача (3.2.1) - 3.2.2) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра , не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью двойственного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (3.2.1) - (3.2.2). Итак, процесс нахождения решения задачи (3.2.1) - (3.2.2) включает следующие основные этапы: