- 1
- 2
называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи. Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрицезадачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
Теорема равновесия. Пусть — оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда еслито
5
- 1
- 2
Похожие работы
Тема: Постановка задачи линейного программирования и двойственная задача линейного программирования. |
Предмет/Тип: Математика (Реферат) |
Тема: Математическая постановка транспортной задачи линейного программирования |
Предмет/Тип: Эконометрика (Реферат) |
Тема: Решение линейного программирования |
Предмет/Тип: Отсутствует (Отчет по практике) |
Тема: Двойственность линейного программирования |
Предмет/Тип: Математика (Реферат) |
Тема: Задачи линейного программирования 2 |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Интересная статья: Быстрое написание курсовой работы