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

| Категория реферата: Рефераты по математике
| Теги реферата: сочинение отец, антикризисное управление
| Добавил(а) на сайт: Гайдученко.

[pic](3) или, в матричной записи,

[pic](4) где [pic].

Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных [pic] столько же, сколько строк в матрице [pic] задачи (1). Матрица ограничений в (3) — транспортированная матрица [pic].
Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные [pic] накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.

Теорема равновесия. Пусть [pic]— оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если [pic] то

[pic]