В7 Параметрическое программирование. Постановка и геометрическая интерпретация задачи. Аналитическое решение задачи.

Алгоритм решения задачи c предыдущего вопроса состоит из двух этапов.

Этап I. Параметру t дают фиксированное значение, например t=a. Этим задача приводится к задаче линейного программирования. Решая эту задачу симплекс-методом, находят вершину, в которой f _t достигает максимума.

Этап II. Определяют интервал изменений параметра t, для которого максимум f_t достигается в одной и той же вершине многогранника W. Найденный интервал исключают из отрезка [a;b]. Для оставшейся части отрезка снова решают задачу симплекс-методом, т. е. переходят к этапу I. Решение продолжается до тех пор, пока весь отрезок [a;b] не будет разбит на частичные интервалы.

Подробно алгоритм решения рассмотрим на примере.

Пример 1. Найти интервалы изменения параметра t на отрезке [a;b] для которых достигает максимума в одной и той же вершине области допустимых решений системы ограничений

Решим задачу в два этапа.

Этап 1.

1. Полагаем t=a. Тогда функция будет иметь вид:

Все данные задачи заносим в жорданову таблицу. В строке f_a этой таблицы в каждый столбец записываем число, равное сумме чисел c_j и d_ja. Кроме того, добавим в таблицу две строки для записи функций f_t с произвольным параметром t. При этом в предпоследней строке записываем коэффициенты c j, а в последней – d j. Чтобы получить

f t, нужно умножить коэффициенты последней строки на t и сложить их с коэффициентами предпоследней.

таблица 1

 

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

Предположим, что план, представленный в таблице 1, является оптимальным. Тогда все коэффициенты f_a -строки неотрицательны:

таблица 2

 

Поскольку оптимальный план найден, переходим к выполнению действий этапа II.

 

Этап 2.

 

1. Находим значения параметра t, при которых план в таблице 2 будет оставаться оптимальным (максимум f t достигается в той же вершине). Для этого необходимо, чтобы все коэффициенты функции f t были неотрицательны:

 

Из этой системы видно, что во всех случаях, кроме q j =0 (при q j =0 неравенство p j + q_j t ³ 0 выполняется при любых значениях t; следовательно, на столбец, в котором находится q j =0, можно не обращать внимания), границей изменения параметра t служит отношение . Поэтому просматриваем элементы q_j последней строки таблицы: если все они больше нуля, переходим к п. 2; если все они меньше нуля, – к п. 3; если же среди элементов j q имеются и положительные, и отрицательные, – к п. 4.

2. Пусть все q j > 0. Среди отношений - выбираем наибольшее.

Таким образом,

В интервале [ a₁;a₂) функция достигает максимума в той же вершине, что и при t=a, следовательно, t Î[ a₁;a₂)

3. Пусть все q_j < 0. Среди отношений - выбираем наименьшее. Если взять , то все условия будут удовлетворены. Нижнейграницы для t в этом случае не существует, поэтому его можно уменьшатьбесконечно. Значит,

Как и прежде, t Î[ a₁;a₂).

 

4. Пусть среди элементов q_j имеются как положительные, так и отрицательные. Разделим систему неравенств на две подсистемы соответственно знакам коэффициентов q_j. Тогда из подсистемы неравенств с q_j > 0 получим , а из второй подсистемы q_j < 0 будем иметь Следовательно, вся система неравенств будет удовлетворяться, если t будет принимать значения:

В этом случае выделенный интервал, в котором функция достигает максимума в той же вершине, что и при t=a, является отрезком, tÎ[ a₁;a₂ ].

 

5. Сравниваем полученный интервал [ a₁;a₂ ] с заданным [ a;b ].Независимо от значения a1 левой границей первого интервала будет a, так как a ₁ больше a быть не может. Если a₂ ³ b, то весь интервал [ a;b ] попадает внутрь интервала [ a₁;a₂ ] и задача решена. Для любого значения параметра t Î[ a;b ] максимум функции f_t достигается в одной и той же вершине

6. Если a₂ < b, то в интервале [ a;a₁ ] максимум функции ft будет в найденной вершине (рисунок 8.2). Исключаем этот интервал из рассмотрения и решаем задачу для оставшегося интервала [ a2; b ]. Для этого придаем t значение a ₂ и заменяем строку fa строкой f a2. В результате замены получаем новую таблицу

За разрешающий столбец в новой таблице примем тот, по которому определено значение t=a₂ (в этом столбце на пересечении с f_a2 -строкой находится элемент, равный нулю). Если нули находятся в нескольких столбцах, то в качестве разрешающего можно брать любой из них.

Разрешающий элемент находим по наименьшему симплексному отношению и делаем один шаг модифицированных жордановых исключений. Получаем следующее по порядку оптимальное решение, так как все коэффициенты в строке f_a2 при преобразовании не изменятся.

Для найденного решения снова определяем интервал изменения параметра t, для чего переходим к п. 1.

Если в разрешающем столбце не окажется положительных коэффициентов, то функция f_t при t>a₂ не ограничена; задача на оставшемся интервале [ a2;b ] решения не имеет.

Замечание. При отыскании оптимального решения для t=a (при выполнении п. 2 этапа I алгоритма) может оказаться, что функция f_a сверху не ограничена. В этом случае в разрешающем столбце j₀ коэффициент f_a - строки отрицателен , а все остальные коэффициенты столбца j₀ неположительны.

При значениях t>a на пересечении строки f_t и столбца j₀ будет элемент . Нас интересуют значения этого элемента, так как они определяют поведение функции при . Выберем такое значение t=t₀, при котором коэффициент . Отсюда получаем .

Если значение элемента , то для всех коэф-т разрешающего столбца в строке f_t будет отрицательным . Следовательно, на всем заданном отрезке целевая функция f_t не ограничена (задача решения не имеет).

Если элемент , то при коэф-т, находящийся в разрешающем столбце и f_t -строке, будет отрицательным. Значит и в этом случае целевая функция не ограничена и задача решения не имеет.

При значении t=t₀ коэф-т , а при дальнейшем увеличении t, он будет положительным. К отрезку применяем последовательно алгоритм решения задачи.