Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества



Скачать 58.71 Kb.
Дата12.10.2012
Размер58.71 Kb.
ТипЛекция
Лекция 3.

Нахождение структуры многогранного множества, решение задачи об экстремуме линейной функции на многогранном множестве известной структуры.
§1. Структура многогранного множества.

Пример 3.1.1.


































; - вершины многогранного множества .

; gif" name="object19" align=absmiddle width=61 height=22> - направляющие векторы неограниченных рёбер.

- многогранник множества , выпуклая оболочка вершин.

- многогранник множества , коническая оболочка направляющих векторов , .

- структура многогранного множества .

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

- параметрическое представление многогранного множества .

Пример 3.1.2.

















- направляющий вектор предельного подпространства ; , - направляющие векторы предельного конуса; - многогранник.

- структура многогранного множества.

Если многогранное множество ограничено, то оно не имеет предельного подпространства и предельного конуса, является многогранником и совпадает с выпуклой оболочкой множества своих вершин :



















Пример 3.1.3. Исследовать структуру многогранного множества , задаваемого системой ограничений , получить для него параметрическое представление.

Из построения возьмём, что представляет собой тетраэдр , где ; ; ; . - многогранник, поэтому представляет собой выпуклую оболочку своих условных точек: - параметрическое представление множества .
§2. Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры.

Теорема 3.2.1.

Пусть - линейная целевая функция - многогранное множество, характеризуемое набором своих угловых точек ; набором направляющих векторов полуограниченных рёбер и набором образующих предельного подпространства . Тогда :



  1. Если найдётся хотя бы один вектор , для которого , то целевая функция не ограничена на ни сверху, ни снизу.

(3.1)

т.к. соотношения (3.1) достигаются на прямой , входящей в состав .

  1. Пусть для всех выполняется равенство . Если найдётся хотя бы один вектор , для которого , то целевая функция не ограничена на сверху: (3.2), т.к. равенство (3.2) достигается на луче , входящем в состав . Т.о., чтобы задача имела конечное решение, необходимо, чтобы выполнялись условия: . (3.3)

Аналогично, чтобы задача имела конечное решение (отличное от ), необходимо, чтобы выполнялось условие:

  1. Предположим, что условие (3.3) выполняется. Найдём максимум целевой функции на конечном множестве условных точек

(3.4)

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

Решение:

  1. Вычислим целевую функцию на направляющих векторах предельного конуса:

,

,



Таким образом решение данной задачи ограничено .

  1. Вычислим целевую функцию в угловых точках области определения:

;

;

.

Таким образом , . Максимальное значение целевой функции равно 4 и достигается в бесконечном числе точек, а именно, на отрезке
§3. Нахождение структуры многогранного множества.

Пусть многогранное множество задано системой линейных равенств и неравенств:

(3.6)

Пусть - матрица ограничений.

Если , то предельного подпространства в составе нет. В дальнейшем будем предполагать, что , т.е. матрица ограничений – полного ранга.

Пусть - набор строк матрицы , т.е. - столбец, состоящий из строк. Систему (3.6.) можно записать в виде:

(3.7)
Теорема 3.3.1. Для того, чтобы точка была вершиной многогранного множества , необходимо и достаточно, чтобы имелись ограничений из состава (3.7), которые для точки выполнялись как равенства, а остальные ограничения из (3.7) также выполнялись, т.е. точка была бы при этом допустимой. Без доказательства.
Пример 3.3.1. Найти условные точки многогранного множества , задаваемого системой неравенств:

(3.8)

Решение:

Рассмотрим все возможные системы по 2 равенства, образованные из ограничений (3.8). Их будет .

1) , точка недопустима, т.к. не выполняется 3 правило

2) - верно. Все ограничения выполнены. - первая найденная вершина;

3) - верно. - вторая вершина.

4) - верно. - третья вершина.

5) уже исследованная точка;

6) - уже исследованная точка;

- треугольник;
















Похожие:

Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconУчебно-методическое пособие Саранск 2012 Элементы теории множеств: Множества. Операции над множествами Сведения из теории
Можно говорить о множестве стульев в аудитории, о множестве деревьев в парке, о множестве машин на улицах города, о множестве людей...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconФакультет
Отображения множеств. Счетные и несчетные множества. Функции множества. Мера множества. Измеримые множества и функции. Интеграл Лебега....
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconПонятие функции
Определение: Если каждому элементу Х множества Х () ставится в соответствие вполне определенный элемент y множества y (), то говорят,...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества icon2 Симплекс-метод и его модификации 2 Симплекс-метод
Решение задачи лп (3), согласно теоремам 2, 3, 4, достигается в вершине многогранного множества. Теорема 2 дает простое описание...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconПредел функции Пусть функция определена на множестве. Определение
Определение. Точка – называется предельной точкой множества или точкой сгущения множества, если в любой окрестности существует точка...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconПредел функции Пусть функция определена на множестве. Определение
Определение. Точка – называется предельной точкой множества или точкой сгущения множества, если в любой окрестности существует точка...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconЛабораторная №6 Измеримые функции. Интеграл Лебега
...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества icon№ задания структура Проверяемые этапы (план экз работы) Шаги выполнения
Суть: нахождение производной функции, записанной в виде произведения линейной функции и тригонометрической
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества icon5. Неопределенный интеграл 1 Первообразная и неопределенный интеграл
К числу важных прикладных задач относятся задачи определения закона движения частицы по известной скорости и определения скорости...
Решение задачи об экстремуме линейной функции на многогранном множестве известной структуры. Структура многогранного множества iconКак найти множество значений функции
Егэ неизменно содержат 2-3 задачи на нахождение множества значений функции или сводящиеся к ним задачи. Такие задачи вызывают у учащихся...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org