Задача для заданной задачи линейного программирования (ЛП, англ. Linear programming, lp) это другая задача линейного программирования, которая получается из исходной

ФАКУЛЬТЕТ “КОМПЬЮТЕР ИНЖИНИРИНГ”
КАФЕДРА “КОМПЬЮТЕРНЫЕ СИСТЕМЫ”

ПРЕДМЕТ:
«Проектирование алгоритма»
Практическая работа

Выполнил: Бурхонов .Ж

Группа: 627-21
Принял(а): Порубай . О


Фергана-2023

Практическая работа № 6. Двойная проблема для задач линейного программирования. Алгоритм и программа симплекс метода в решении задач линейного программирования. Описание циклических алгоритмов.

1. Цель работы
Сформировать представление о циклических алгоритмах, привести примеры из: повседневной жизни, литературного произведения, любой предметной области. 

2. Теоретический материал

Двойственная задача линейного программирования

Двойственная задача для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом:

• 
  Каждая переменная в прямой задаче становится ограничением двойственной задачи;
  
• 
  Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
  
• 
  Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.
  

Теорема о слабой двойственности утверждает, что значение двойственной задачи для любого допустимого решения всегда ограничено значением прямой задачи для любого допустимого решения (верхняя или нижняя граница, в зависимости от того, это задача максимизации или минимизации).
Теорема о сильной двойственности утверждает, что более того, если прямая задача имеет оптимальное решение, то двойственная задача имеет также оптимальное решение, и эти два оптимума равны.
Эти теоремы принадлежат более широкому классу теорем двойственности в оптимизации. Теорема о сильной двойственности является одним из случаев, в котором разрыв двойственности (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0.
О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна. Там же можно прочитать об экономическом смысле задачи.