Геометрический метод, Двойственная задача - Линейное программирование

Применяется для задач с двумя переменными. Метод решения состоит в следующем:

На плоскости строятся прямые, которые задают соответствующие ограничения:

A11 x1 + a11 x2 + ...... + a11 xn = b1,

A21 x1 + a22 x2 + ...... + a2n xn = b2,

................................................

Am1 x1 + am2 x2 + ...... + amn xn = bm.

Находим множество всех точек х1, х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки

Двойственная задача

Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

Где D определяется системой уравнений и неравенств:

... .... ...

... ... ...

,

То двойственной по отношению к ней называется общая задача ЛП:

Где D* определяется системой уравнений и неравенств:

... ... ...

... ... ...

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

    1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот. 2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами. 3. Матрица ограничений задачи А транспонируется. 4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче определяют номера ограничений, имеющих форму неравенств в двойственной задаче. 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче.

Из приведенного определения вытекает важное свойство -- симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей.

((D*)*, (f*)*)?(D, f),

Основные теоремы:

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

Теорема 2 ( о дополняющей нежесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения:

Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)

Похожие статьи




Геометрический метод, Двойственная задача - Линейное программирование

Предыдущая | Следующая