ТОП 10:

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



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

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

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

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

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

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

Этап 1.

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

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

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

таблица 1

 

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

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

таблица 2

 

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

 

Этап 2.

 

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

 

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

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

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

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

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

Как и прежде, tÎ[a1;a2).

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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







Последнее изменение этой страницы: 2016-07-14; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.200.226.179 (0.004 с.)