Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

5.9. Решение двойственной задачи как оценки влияния

Покажем, что при некоторых изменениях компонент вектора ограничений b в задаче (5.1) компоненты решения двойственной задачи (5.6) могут быть интерпретированы, как оценки влияния этих изменений на величину минимума целевой функции задачи (5.1).

Рассмотрим задачу

(5.20)

и двойственную к ней:

(5.21)

В предположении, что задача (5.20) разрешима при некотором z, обозначим


Пусть при z = z* существует решение х* задачи (5 20) и, следовательно, существует y* - решение задачи (5 21)

Теорема 5.3. Если задача (5.20) не вырождена, то существует такая окрестность U (z*) точки z*, что для всех z ∈ U (z*) будет

μ(z)=<z, y*>

Доказательство. Так как при z = z* задача (5.20) разрешима, то, согласно теореме 4.8, существует оптимальная угловая точка х*. Пусть х* имеет вид


где


Ей соответствует базис В = [а1, а2, ..., аm], detB≠0,


Выберем следующую окрестность:


Покажем, что точка

xT=(xTB 0, ..., 0),

где XB = B-1z будет оптимальной для задачи (5.20) при любом z ∈ U (z*). Действительно,


где норма выбрана следующим образом:


Получаем, что

х*i - хi≤α, (i=1,..., m),

то есть


Таким образом, x≥0. И, кроме того, по построению, Ax=z, то есть x∈R0(z).

Докажем, что х оптимален для задачи (5.20). Из условий (4.6) следует, что каждому х*i > 0 (i = 1,...,m) соответствует

(ATy*)i=ci

Тогда


И так как x∈R0(z), a ,y*∈Q0 из теоремы 4.4 вытекает оптимальность точек х и y* и

μ(z)=<y*, z>

Теорема доказана. Очевидно, что


поэтому увеличение zi приводит к увеличению или уменьшению величины μ(z) в зависимости от знака y*i. При этом скорость изменения μ(z) определяется величиной |y*i|.

Двойственный симплексный метод называют также методом последовательного уточнения оценок, поскольку угловые точки задачи (5.6), возникающие при итерациях можно рассматривать, как приближенные значения точной оценки y*, то есть как приближенные оценки влияния условий задачи (5.1) на величину минимума целевой функции.

предыдущая главасодержаниеследующая глава






Выпущен открытый сервер навыков 0Mind для упрощения разработки ИИ

Создатель Всемирной паутины выступил против Facebook и Google

В Китае построят суперкомпьютер, способный выполнять квинтиллион вычислений в секунду

Использование нейронной сети для восстановления повреждённых изображений

В Китае робот сдал тест для поступления в университет

Россия будет защищена от внешнего отключения Рунета к 2021 году

О конференции Strata AI: будущее искусственного интеллекта

Китайский самообучающийся процессор сможет имитировать работу нервных клеток человека

Илон Маск работает над интерфейсом для подключения мозга к компьютеру

Загадка QWERTY: почему буквы на клавиатуре расположены не в алфавитном порядке

Нейронную сеть научили практически идеально копировать человеческий голос





© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"