Экономико-математические модели и методы


ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ



страница3/7
Дата06.06.2016
Размер0.62 Mb.
1   2   3   4   5   6   7

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

  1. Составление двойственных задач

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


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

;



;


Правила построения двойственной пары


  1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум.

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

  3. Число переменных в двойственной задаче равно числу соотношений в системе ограничений исходной задачи. Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче.

  4. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи и наоборот.

  5. Если на j переменную исходной задачи наложено уcловие неотрицательности , то j-тое ограничение двойственной задачи является неравенством. Если может принимать как положительные, так и отрицательные значения, то j-тое соотношение в системе ограничений двойственной задачи – уравнение.

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

    1. Основные теоремы двойственности


Теорема 1

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



Теорема 2

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

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

Примечание. Геометрическая интерпретация двойственных задач.

При решении двойственных задач возможны три случая:



  • обе задачи разрешимы;

  • области допустимых решений обеих задач пусты;

  • одна задача имеет неограниченную область допустимых решений, вторая – пустую.



Пример 2. Для данной задачи составить двойственную, решить ее графическим методом, и, используя теоремы двойственности, найти решение данной задачи.

;



Решение.

  1. Составим матрицу из коэффициентов при неизвестных, свободных членах и коэффициентах целевой функции (f).

  2. Транспонируем полученную матрицу (т. е. заменяем строки на столбцы).

  3. По транспонированной матрице составляем двойственную систему ограничений и целевую функцию (φ)

;
;

Функция φ минимизируется, так как целевая функция исходной задачи максимизируется.

Поскольку на переменные исходной задачи наложены условия неотрицательности , то соотношения (1) – (5) в системе ограничений двойственной задачи являются неравенствами. Переменные y1, y2 не должны удовлетворять условию неотрицательности, т.к. они соответствуют ограничениям- неравенствам исходной задачи.

Решим полученную задачу графическим методом. На рис. 2 изображены: область допустимых решений задачи, , линии уровня и оптимальное решение задачи, Y* = (-2; -5) и φ(Y*) = -22.



Рис. 2.

По первой теореме двойственности



Подставим оптимальное решение Y* = (-2; -5) в систему ограничений. Получим ограничения

1, 4, 5 выполняются как строгие неравенства. Согласно второй теореме двойственности соответствующие компоненты оптимального плана двойственной задачи, т.е. исходной задачи, равны нулю: . Учитывая это, из системы ограничений исходной задачи найдем ее оптимальное решение:

_______________







X* = (0; 2; 1; 0; 0).





Ответ: при X* = (0; 2; 1; 0; 0).




  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница