Двойственность в линейном программировании

Исходная  задача:

Zmin = 2x1 + x2 + 5x3 при ограничениях

-x1 + x2 + x3 ³ -4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

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

fmin = -4x1 + 5x2 + 6x3 при ограничениях

-y1 + y2 + 2y3 £ 2,

y1 –  5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3).

2y1 + y2 + 3y3 £ 5,

Приведем  без доказательства следующую теорему. Теорема: если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.

Если  i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.  
 
 
 
 
 
 
 
 

5. Двойственный симплексный  метод

     В п. 2 и п. 3 было сказано , что для получения решения исходной задачи можно перейти к двойственной и используя оценки ее оптимального плана, определить оптимальное решение исходной задачи.

Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным  дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана исходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит название двойственного симплексного метода,

     Пусть необходимо решить исходную задачу линейного  программирования, поставленную в общем  виде: минимизировать функцию Z =СХ при АХ = A0, Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA £ С. Допустим, что выбран такой базис D = (A1, А2, ., Аi, ., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ., xi, ., xm) отрицательная (например, xi < 0), но для всех векторов Aj выполняется соотношение Zj – Cj £ 0 (i = 1,2, ., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.

     Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствующий отрицательной оценке,— включить в базис двойственной задачи.

     Для выбора вектора, включаемого в базис  исходной задачи, просматриваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q0j= min (xi/xij) ³ 0 и определяем вектор, соответствующий max q0j(Zj — Cj) при решении исходной задачи на минимум и min q0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой.

Если  q0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за разрешающий элемент только в том случае, если xij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X. Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

     В процессе вычислений по алгоритму двойственного  симплексного метода условие Zj – Cj £ 0 можно не учитывать до исключения всех хi < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все хi < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j= max (xi/xij) > 0.

     Двойственным  симплексным методом можно решать задачи линейного программирования, системы ограничений которых при положи­тельном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размеры симплексной таблицы.  
 
 
 
 

6. Список используемой литературы: 

1. Солодовников  А.С., Бабайцев В.А., Браилов А.В.  Математика в экономике. «Финансы  и статистика», 1998 г. 

2. Кузнецов  Ю.Н., Кузубов В.И., Волощенко А.Б.  Математическое программирование. «Наука», 1980 г. 

3. http://www.textreferat.com/referat-2819-4.html