АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Понятие двойственности

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

Алгоритм обследования хирургических больных особенно важен в экстренных ситуациях. Он включает следующие этапы:

1. Опрос (сбор жалоб и анамнеза).

2. Объективное исследование, прежде всего:

- оценка общего состояния;

- исследование повреждённой системы (с помощью осмотра, пальпации, перкуссии и аускультации).

3. Специальные методы обследования. Выбирают, в первую очередь, самые простые, но информативные методы.

Следует отметить, что после выполнения каждого этапа появляется возможность коррекции следующего. Так, ещё при сборе жалоб и анамнеза врач определяет повреждённую систему, а часто и несколько патологических состояний, наличие которых может обусловливать жалобы. При объективном исследовании он уже целенаправленно проверяет симптомы, характерные для подозреваемых заболеваний, а при назначении специальных методов диагностики, по существу, пытается найти подтверждение своим предположениям или исключить возможность определённых состояний.

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

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

Понятие двойственности

Рассмотрим задачи линейного программирования в стандартной форме, записанные в матричной форме:

max CX

,

где С = (с₁... с_n), X = , B = , A =

min YB

,

где Y = (y₁... y_m).

Здесь X, Y - переменные*; A, B, C - константы.

Задача (21) и любая эквивалентная ей задача линейного программирования называется двойственной задаче (20) и любой эквивалентной ей задаче.

Подчеркнем, что новых переменных вводится ровно столько, сколько в задаче (20) ограничений, т.е. m.

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

Исходную задачу, по отношению к которой строится двойственная, иногда еще называют прямой задачей.

Теорема (о сопряженных задачах). Задача, двойственная двойственной, эквивалентна исходной.

Доказательство. Построим задачу линейного программирования, двойственную (21). Поскольку определение дает возможность построить двойственную задачу только для задачи в той же форме записи, что и задача (20), вначале преобразуем задачу (21) таким образом, чтобы форма ее записи была такой же.

Приведем задачу (21) к стандартной форме на максимум:

mах Y(-B)

Транспонируем входящие сюда величины, чтобы порядок действий над векторами и матрицами был таким же, как и в задаче (20):

mах -B^ТY^Т

Теперь можно построить двойственную задачу в соответствии со сформулированным определением. Введем строку переменных Z.

min Z(-C^T)

Эта задача является двойственной к двойственной. Преобразуем ее.

mах СZ^Т

Эта задача эквивалентна задаче (20) с точностью до обозначения.

Теорема доказана.

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

Рассмотрим задачу в канонической форме. Чтобы построить задачу, двойственную к ней, преобразуем ее к стандартной форме.

Построим теперь двойственную задачу. Отметим, что число ограничений задачи возросло в два раза (каждое уравнение преобразовано в два неравенства). Вектор-строку переменных двойственной задачи разобьем на две части, в каждую из которых будет входить равное число переменных, и обозначим его (U,V) = (u₁, …, u_m, v₁, …, v_m).

При этом во всех линейных выражениях компоненты вектора В и матрицы А можно вынести за скобки, а в скобках останется разность векторов U = (u₁, …, u_m) и V = (v₁, …, v_m). Например, при перемножении строки переменных на первый столбец матрицы А будет получено:
(a₁₁u₁ + a₂₁u₂ + … + a_m1u_m - a₁₁v₁ - a₂₁v₂ - … - a_m1v_m = a₁₁(u₁ - v₁) + a₂₁(u₂ – v₂) + … + a_m1(u_m – v_m); - и т.д.

Обозначим U - V = Y. При этом переменные Y = (u₁ - v₁; …; u_m – v_m) =
= (y₁... y_m) не ограничены по знаку. Тогда двойственная задача примет вид:

min YB

YA ³ C

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

На основании проведенных рассуждений можно сделать вывод, что для построения двойственной задачи не обязательно каждый раз приводить задачу линейного программирования к стандартной форме, а именно нет необходимости преобразовывать уравнения к неравенствам, а не ограниченные по знаку переменные - к неотрицательным. Пусть в задаче в смешанной форме первые m` ограничений – уравнения, а остальные m-m` - неравенства; и первые n` переменных неотрицательны, а остальные n-n` переменных по знаку могут быть любыми. Между задачей линейного программирования в смешанной форме и двойственной ей задачей линейного программирования можно установить следующее соответствие:

max cjxj	min biyi
aijxj = bi,	(22) aijyi ³ cj,
aijxj £ bi,	aijyi = cj,
xj ³ 0,	yi ³ 0,
xj 0,	yi 0,

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

а) Переменные двойственной задачи соответствуют ограничениям исходной задачи, а ограничения - переменным.

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

в) В задаче линейного программирования на максимум в ограничениях-неравенствах должен стоять знак £, а на минимум - ³.

г) Ограничениям-неравенствам исходной задачи соответствуют неотрицательные двойственные переменные, а уравнениям – не ограниченные по знаку переменные.

д) Неотрицательным переменным исходной задачи соответствуют ограничения неравенства двойственной задачи, а не ограниченным по знаку - уравнения.

Если обе сопряженные задачи записаны в стандартной форме, их называют симметричными сопряженными задачами.

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

min 2х₁ + 3х₂ - 4х₃ + х₅

4х₁ - 3х₂ - х₃ + х₄ + х₅ £10

х₁ + 4х₂ + х₃ + х₅ = 15

2х₁ - 4х₂ - х₃ + х₄ ³ 3

х_{1-3, 5} ³ 0

Так как задача на минимум, умножим обе части первого ограничения на -1, чтобы получить знак неравенства ³: -4х₁ + 3х₂ + х₃ - х₄ - х₅ ³ -10.

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

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

Первое ограничение двойственной задачи соответствует переменной х₁ прямой задачи, поэтому коэффициенты этого ограничения берут из столбца коэффициентов при х₁, а свободный член – из целевой функции прямой задачи. Так как х₁ ³ 0, это ограничение – неравенство. Так как двойственная задача на максимум, знак неравенства £. Аналогично строятся второе, третье и пятое ограничения. Четвертое ограничение соответствует переменной х₄, знак которой может быть любым. Поэтому оно – уравнение.

Переменные y₁ и y₃ соответствуют первому и третьему ограничениям прямой задачи, которые представляют собой неравенства. Поэтому эти переменные – неотрицательные. Второе ограничение прямой задачи – уравнение, поэтому переменная y₂ не ограничена по знаку.

max -10y₁ + 15y₂ + 3y₃

-4y₁ + y₂ + 2y₃ £ 2

3y₁ + 4y₂ - 4y₃ £ 3

y₁ + y₂ - y₃ £ -4

-y₁ + y₃ = 0

-y₁ + y₂ £ 1

y_1,3 ³ 0

Дата добавления: 2015-01-18 | Просмотры: 781 | Нарушение авторских прав