Пряма та двоїста задачі ЛП

Тема 1 Лінійне програмування

(8 г. – 4 лекції)

Лекція 3 (2 г.)

2.3 Двоїста(спряжена) задача ЛП

2.3.1Пряма та двоїста задачі ЛП

2.3.2 Зв’язок між розв’язками прямої та двоїстої задач

2.3.3Пошук розв’язку двоїстої задачі

2.3.4 Економічне тлумачення двоїстих задач*

2.3.5 Аналіз робастності двоїстих оцінок*

2.3.6 Двоїстий симплекс-метод*

2.3 Двоїста задача ЛП

Будь-якій задачі ЛП можна певним чином зіставити так звану двоїсту задачу по відношенню до даної.

Запишемо умову прямої задачі ЛП:

, за умов (26)

, (27)

(). (28)

Визначення 14. Задача, яка полягає в находженні мінімального значення функції

, за умов (29)

, (30)

(), (31)

називається двоїстою по відношенню до задачі (26)-(28).

Алгоритм побудови двоїстої задачі:

1. Цільова функція прямої задачі (26)-(28) задається на максимум, а цільова функція двоїстої задачі (29)-(31) задається на мінімум.

2. Матриця коефіцієнтів двоїстої задачі – це транспонована матриця коефіцієнтів прямої задачі.

3. Кількість змінних двоїстої задачі (29)-(31) дорівнює кількості співвідношень (27) прямої, тобто . Кількість обмежень у системі (30) – кількості змінних у прямій задачі, тобто .

4. Вектор коефіцієнтів цільової функції і вектор правих частин у двоїстій задачі міняються містами по відношенню до прямої, тобто .

5. Якщо змінна прямої задачі може приймати тільки позитивні значення, то та умова у системі (30) двоїстої задачі буде нерівністю виду «». Якщо змінна може приймати як позитивні, так і відмінні значення, то та умова у системі (30) двоїстої задачі буде рівнянням. Якщо те співвідношення у системі (30) є нерівністю, то та змінна двоїстої задачі . У протилежному випадку змінна може набувати як позитивних, так і від’ємних значень.

Існують два види моделей двоїстих задач: симетричні і несиметричні:

Симетричні:

Вихідна 1. , ,	Двоїста , ,
2. , ,	, ,

Несиметричні:

Вихідна 1. , ,	Двоїста , , – будь-які
2. , ,	, , – будь-які

Приклад 4 [3]. Скласти двоїсту задачу по відношенню до наступної задачі:

(32)

за умов

(33)

. (34)

Двоїста задача має вигляд:

,

- будь-які.

Приклад 5. Скласти двоїсту задачу по відношенню до наступної задачі:

(35)

за умов

(36)

. (37)

.

Двоїста задача має вигляд:

(38)

за умов

(39)

.

Приклад 6. Скласти двоїсту задачу по відношенню до наступної задачі:

(40)

за умов

(41)

. (42)

Двоїста задача має вигляд:

(43)

за умов

(44)

– будь-яке. (45)

Дата добавления: 2014-01-13