Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Математические основы теории двойственности





 

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

1. Каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи

 

u₁↔a₁₁x₁+…+a₁jxj+…+a1nxn≤b1;

ui↔ai₁x₁+…+aijxj+…+ainxn≤bi

um↔am₁x₁+…+amjxj+…+amnxn≤bm (3.7)

xj≥0; j=1, n

F(x) x=c₁x₁+…+cjxj+…+cnxn→max

 

 

Каждой переменной исходной задачи ставится в соответствие ограничение двойственной задачи

 

 

x₁↔a₁₁u₁+…+ai1ui+…+am₁um ≥ c₁;

xj↔a₁ju₁+…+aijui+…+amjum ≥ cj;

xn↔a₁nu₁+…+ainui+…+amnum ≥ cn; (3.8)

ui≥0; i=1, m;

Z (u)=b₁u₁+…+biui+…+bmum→min

2. Левая часть ограничения двойственной задачи (3.8), соответствующая переменной xj, представляет собой сумму произведений коэффициентов столбца при переменной хj ограничений прямой задачи (3.7) на соответствующие им двойственные переменные. В качестве правой части этого же ограничения берется коэффициент целевой функции при переменной x j прямой задачи. Между левой и правой частями ограничения двойственной задачи ставится знак ≥.

3. Граничные условия на переменные двойственной задачи заключается в требовании их не отрицательности ui≥0; i=1,m.

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

Эти правила можно применить при построении задачи, двойственной к прямой, после ее приведения к нижеприведенной стандартной форме записи задачи линейного программирования.

Найти u=(u₁,…ui,…,um);

-a₁₁u₁-…-ai₁ui-…-am₁um≤-c₁;

-a₁ju₁-…-aijui-…-amjum≤-cj;

-a₁nu₁-…-ainui-…-amnum≤-cn;

ui≥0; i=1,m;

Z (u)’= -b₁u₁-…-biui-…-bmum→max. (3.9)

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

Это доказывает свойство сопряженности прямой и двойственной задачи, которое заключается в том утверждении, что двойственная задача к двойственной задаче является прямой задачей. В соответствии с этим свойством двойственную задачу можно считать прямой, а прямую задачу - двойственной к ней, т.е. названия «прямая задача» и «двойственная задача» не являются навсегда закрепленными названиями за той или иной задачей линейного программирования. Это оправдывает применяемый в дальнейшем термин «пара взаимодвойственных задач».







Date: 2015-07-27; view: 404; Нарушение авторских прав



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию