Сб, 29.07.2017, 14:43
Главная
Регистрация
Вход
აბაშის ხმა
Приветствую Вас Гость | RSS
Меню сайта
Категории раздела
Алгебра
Алгебра Дж. Буля
Алгоритмы
Анализ
Векторы
Вейвлеты
Геометрия
Графики
Дзета-функция Римана
Задача Лагранжа
Интегралы
Математика
Математическая интуиция
Математические игры
Методы Рунге Кутты
Нестандартный анализ
Теория Графов
Уравнения
Численные методы оптимизации
Геометрия в пространстве
Мини-чат
200
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Математика » Численные методы оптимизации

Формирование оптимального решения двойственной задачи на основе теоремы о двойственности
Формирование оптимального решения двойственной задачи
 на основе теоремы о двойственности

Оказывается, что для задач (7.2) - (7.4) и (7.5), (7.6), называемых двойственной парой, справедлива следующая теорема.

Теорема (первая теорема о двойственности). Если одна из задач двойственной пары

(7.2) - (7.4) и (7.5), (7.6) имеет решение, то другая задача также разрешима. При этом для любых оптимальных планов  и (здесь Мх, Му – множества планов соответственно прямой и двойственной задач) задач (7.2) - (7.4) и (7.5), (7.6) имеет место равенство

.                                                                                

Если линейная форма одной из задач не ограничена (для F(X) – сверху, для f(Y) - снизу), то другая 

задача не имеет ни одного плана.

Оптимальное решение двойственной задачи может быть найдено на основе следующего следствия 

из этой теоремы.

Следствие. Если вектор  является оптимальным опорным планом задачи (7.2) - (7.4), то 

вектор  (8.1), является оптимальным опорным планом задачи (7.5), (7.6).

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

вычисляется вектор 

. И если Х – оптимальный опорный план задачи (7.2) - (7.4), то в (m+1)-й строке, 

соответствующей основной таблице, находится решение задачи (7.5), (7.6).

Пусть двойственная задача имеет вид (7.8), (7.9).

Так как исходная задача (2.12), (2.13) имеет решение, то на основании рассмотренной теоремы о двойственности двойственная задача также разрешима.

Оптимальным опорным планом исходной является

 (см. п.4, п.6). При этом

;

; .

Вычислим

.

На основании следствия из теоремы о двойственности можно заключить, что

 является оптимальным планом двойственной задачи, 

при котором . Анализируя (m+1)-ю строку основной

 таблицы (см. табл. 6.3, шаг 5), можно убедиться в том, что оптимальный план двойственной 

задачи, сформированный на основе теоремы о двойственности, совпадает с оптимальным 

планом, найденном при решении исходной задачи вторым алгоритмом симплекс-метода. 

Это говорит о том, что оптимальный план задачи (7.8) - (7.9) найден верно.

Категория: Численные методы оптимизации | Добавил: nukria (25.04.2012)
Просмотров: 83 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Вход на сайт
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • | Copyright MyCorp © 2017 | |