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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

В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, так как a 1 больше a быть не может. Если a2 ³ b, то весь интервал [ a;b ] попадает внутрь интервала [ a1;a2 ] и задача решена. Для любого значения параметра t Î[ a;b ] максимум функции ft достигается в одной и той же вершине

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

За разрешающий столбец в новой таблице примем тот, по которому определено значение 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; просмотров: 259; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

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