Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
В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; просмотров: 285; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.59.156.15 (0.008 с.) |