Правила составления двойственной задачи ЛП

В задачке 1 имеется n-переменных и m- ограничений типа (4). В задачке 1* имеется m –переменных и n-ограничений типа (8). Это означает, что каждой переменной в задачке 1 соответствует ограничение в задачке 1* и каждому ограничению в задачке 1 соответствует переменная в задачке 1*.

В задачке 1 требуется максимизировать мотивированную функцию на огромном количестве данных ограничений больше 0. В задачке 1* требуется Правила составления двойственной задачи ЛП минимизировать мотивированную функцию на огромном количестве данных ограничений меньше 0.

Коэффициенты сj линейной функции (1) в задачке 1 являются свободными членами ограничений (8) задачки 1*, свободные члены bi ограничений (4) в задачке 1 являются коэффициентами линейной функции (5) задачки 1*.

Коэффициенты при неведомых аij в задачках 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы Правила составления двойственной задачи ЛП по отношению друг к другу.

В задачке 1 все неравенства типа ³ , а в задачке 1* все неравенства типа £.

Если на переменную задачки 1 налагается условие неотрицательности, то соответственное ограничение в двоякой задачке является неравенством, а если условия неотрицательности на переменную нет, то соответственное ограничение в задачке 1* является уравнением. И напротив.

Пример Правила составления двойственной задачи ЛП составления двоякой задачки ЛП

Пример 1.Записать двоякую задачку к последующей задачке линейного программирования. Задачка1. Отыскать х = (х1, х2, х3, х4), удовлетворяющий условиям: Решение. Заметим, что т.е все переменные связаны условием неотрицательности, и все ограничения производятся как неравенства. Двоякая задачка имеет вид: Задачка 1* Отыскать удовлетворяющие условиям:

Пример составления двоякой Правила составления двойственной задачи ЛП задачки ЛП

Пример 2. Задачка 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на огромном количестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 7 0, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0. Решение. Задачка 1* Требует­ся минимизировать линейную функцию на огромном количестве трехмерных векторов, удовлетворяющих условиям Правила составления двойственной задачи ЛП , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь меж задачками 1 и 1*

Связь меж парой двояких задач устанавливает последующая лемма 1:

Для всех допустимых векторов х и у в задачках 1 и 1* производятся неравенства

µ(x) £ (у), (9)

при этом (9) производится как равенство в том и исключительно в том случае Правила составления двойственной задачи ЛП, если справедливы последующие соотношения:

(10)

(11)

Связь меж задачками 1 и 1*

Подтверждение. Имеем:

хj ³0 для jÎJ2

(12)

Суммируя приобретенные соотношения, получим с учетом того, что (13)

Связь меж задачками 1 и 1*

Подтверждение (продолжение). Имеем:

yi ≥ 0 для iÎI2

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются только порядком суммирова­ния и, как следует, равны Правила составления двойственной задачи ЛП меж собой, т.е. производится µ(x) £ (у) (9). Для заслуги равенства в (9), разумеется, не­обходимо и довольно, чтоб достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄

Признак оптимальности в короткой форме

Для оптимальности допустимого вектора х=( х1,х2, …хn,) в задачке 1 довольно существования допустимого вектора y=(y1,y2,…..yn Правила составления двойственной задачи ЛП) в задачке 1*, удовлетворяющего условию

m(х)= n(у)(16)

Тогда допустимый вектор y=(y1,y2,…..yn) также является хорошим в задачке 1*.

Подтверждение.

Пусть вектор х допустимый и существует допустимый вектор у таковой, что справедливо (16). Покажем, вектор х лучший.

Разглядим некий другой лучший вектор х′ в задачке 1 (х′≠х), тогда Правила составления двойственной задачи ЛП имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m(х′)≤ n(у) =m(х)и m(х′)≤m(х). Отсюда следует что х – лучший вектор.

Покажем сейчас, что вектор у также является хорошим.

Разглядим некий другой лучший вектор у′ в задачке 1 (у Правила составления двойственной задачи ЛП′≠у), тогда имеем пару векторов х и у′ . Для этой пары допустимых векторов справедливо лемма 1, т. е. n( у′)≥m(х)= n(у) и n(у)≤ n( у′). Отсюда следует что у – лучший вектор.▄


pravila-registracii-obektov-v-gosudarstvennom-reestre-opasnih-proizvodstvennih-obektov-pravitelstvo-rossijskoj-federacii-postanovlenie.html
pravila-reklamnoj-akcii-poluchi-sertifikat-il-patio-v-lente-organizator-oao-pivovarennaya-kompaniya-baltika.html
pravila-russkoj-orfografii-i-punktuacii-polnij-akademicheskij-spravochnik-pod-red-vv-lopatina-m-ast-2009-432-s.html