Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Теоремы двойственности и их применение

Теоремы двойственности и их применение. Фундаментальные свойства, которыми обладают двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности.

Теорема 1.4. Если х, и— допустимые планы для пары двойственных задач (D,f) и (D*,f*), тo f(x) ≤ f(u).

Доказательство.

Достаточно доказать теорему для случая, когда задача (D, f) является канонической. Рассмотрим пару двойственных задач

Из того, что вектор и является допустимым планом задачи (D*, f*), следует, что иАс. Умножив левую и правую части данного неравенства на вектор х ≥ 0 , получим равносильную систему неравенств

Одновременно для вектора х, являющегося допустимым планом задачи (D, f), справедливо равенство Ax=b. Тем самым доказано, что иb ≥ сх.A

Замечание. Теорема 1.4, разумеется, верна и для оптимальных планов взаимно двойственных задач: f(x*) ≤ f*(u*), где х* и u*—любые оптимальные планы задач (D, f) и (D*,f*). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).


  • Разделы

  • Партнеры