Главная | Обратная связь | Поможем написать вашу работу!

Двоїсті задачі лінійного програмування

1. Пряма і двоїста задачі. Кожній задачі лінійного програмування можна певним чином зіставити деяку співставити задачу (лінійного програмування), що називається двоїстою або сполученою стосовно вихідного або прямої. Дамо визначення двоїстої задачі стосовно загальної задачі лінійного програмування, що полягає в знаходженні максимального значення функції

F = c₁x₁ + c₂x₂+... + c_nx_n (50)

при умовах

x_j ≥ 0 (j = , l ≤ n) (52)

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

F* = b₁y₁ + b₂y₂+... + b_my_m (53)

при умовах

x_j ≥ 0 (j = , k ≤ m) (55)

називається двоїстою стосовно задачі (50)-(52). Задачі (50)-(52) і (53)-(55) утворять пари задач, що називаються в лінійному програмуванні двоїстою парою. Порівнюючи дві сформульовані задачі, бачимо, що двоїста задача стосовно вихідної складається відповідно до наступних правил:

1. Цільова функція вихідної задачі (50)-(52) задається на максимум, а цільова функція двоїстої (53)-(55) – на мінімум.

2. Матриця

складена з коефіцієнтів при невідомих у системі обмежень (51) вихідної задачі (50)-(52), і аналогічна матриця

у двоїстій задачі (53)-(55) отримуються одна з одної транспонуванням (тобто заміною рядків стовпцями, а стовпців – рядками).

3. Число змінних у двоїстій задачі (53)-(55) дорівнює числу співвідношень у системі (51) вихідної задачі (50)-(52), а число обмежень у системі (54) двоїстої задачі – числу змінних у вихідній задачі.

4. Коефіцієнтами при невідомих у цільовій функції (53) двоїстої задачі (53)-(55) є вільні члени в системі (51) вихідної задачі (50)-(52), а правими частинами в співвідношеннях системи (54) двоїстої задачі – коефіцієнти при невідомих у цільовій функції (50) вихідної задачі.

5.Якщо змінна х_j вихідної задачі (50)-(52) може приймати лише додатні значення, то j -а умова в системі (54) двоїстої задачі (53)-(55) є нерівністю виду «≥». Якщо ж змінна х_j може приймати як додатні, так і від’ємні значення, то j -е співвідношення в системі (54) являє собою рівняння. Аналогічні зв’язки мають місце між обмеженнями (51) вихідної задачі (50)-(52) і змінними двоїстої задачі (53)-(55). Якщо i -е співвідношення в системі (51) вихідної задачі є нерівністю, то i -а змінна двоїстої задачі y_i ≥ 0. В іншому випадку змінна y_i може приймати як додатні, так і від’ємні значення.

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

1.77. Скласти двоїсту задачу стосовно задачі, що полягає в максимізації функції

F= 2 x₁ + x₂ +3 x₃ (58)

при умовах

х₁, х₂, х₃, х₄ ≥ 0 (60)

Розв’язок. Для даної задачі

Число змінних у двоїстій задачі дорівнює числу рівнянь у системі (59), тобто дорівнює трьом. Коефіцієнтами в цільовій функції двоїстої задачі є вільні члени системи рівнянь (59), тобто числа 12, 24, 18.

Цільова функція вихідної задачі (58)-(60) досліджується на максимум, а система умов (59) містить тільки рівняння. Тому у двоїстій задачі цільова функція досліджується на мінімум, а її змінні можуть приймати будь-які значення (у тому числі і від’ємні). Так як всі три змінні вихідної задачі (58)-(60) приймають тільки лише невід’ємні значення, то в системі умов двоїстої задачі повинні бути три нерівності виду «≥». Отже, для задачі (58)—(60) двоїста задача така: знайти мінімум функції F*= 12 y₁ +24 y₂ +18 y₃ при умовах

. F= 2 x₁ + x₂ +3 x₃

х₁, х₂, х₃ ≥ 0 2. Зв’язок між розв’язками прямої і двоїстої задач.

Розглянемо пари двоїстих задач, утворені основною задачею лінійного програмування і двоїстою до неї.

Вихідна задача: знайти максимум функції

при умовах

x_j ≥ 0 (j = ) (63)

Двоїста задача: знайти мінімум функції

при умовах

Кожна із задач двоїстої пари (61)-(63) і (64), (65) фактично є самостійною задачею лінійного програмування і може бути вирішена незалежно одна від іншої. Однак при визначенні симплексним методом оптимального плану однієї із задач тим самим отримує розв’язок і інша задача.

Існуючі залежності між розв’язками прямої і двоїстої задач характеризуються сформульованими нижче лемами і теоремами двоїстості.

Лема 1.1. Якщо X – деякий план вихідної задачі (61)-(63), а В – довільний план двоїстої задачі (64), (65), то значення цільової функції вихідної задачі при плані X завжди не перевищує значення цільової функції двоїстої задачі при плані Y, тобто F(Х)≤ F*(Y).

Лема 1.2. Якщо F(Х*) = F*(Y*) для деяких планів X* і Y* задач (61)-(63) і (64), (65), то X* – оптимальний план вихідної задачі, а Y* – оптимальний план двоїстої задачі.

Теорема 1.9 (перша теорема двоїстості). Якщо одна з пари двоїстих задач (61)-(63) або (64), (65) має оптимальний план, то й інша має оптимальний план і значення цільових функцій задач при їхніх оптимальних планах рівні між собою, тобто F_max=F*_min.

Якщо ж цільова функція однієї з пари двоїстих задач не обмежена [для вихідної (61)-(63) – зверху, для двоїстої (64), (65) – знизу], то інша задача взагалі не має планів.

Теорема 1.10 (друга теорема двоїстості).

План Х*= (х₁ *, х₂ *, …, х_n *) задачі (61)-(63) і план Y *=(y₁ *, y₂ *, …, y_m *) задачі (64), (65) є оптимальними планами цих задач тоді і тільки тоді, коли для будь-якого j (j= ) виконується рівність

Геометрична інтерпретація двоїстих задач. Якщо число змінних у прямій і двоїстій задачах, що утворять дану пару, дорівнює двом, то, використовуючи геометричну інтерпретацію задачі лінійного програмування, можна легко знайти розв’язок даної пари задач. При цьому має місце один з наступних трьох випадків, що взаємно виключають один одного: 1) обидві задачі мають плани; 2) плани має тільки одна задача; 3) для кожної задачі двоїстої пари множина планів є порожньою.

1.87. Для задачі, що полягає у визначенні максимального значення функції F= 2 x₁ +7 x₂ при умовах

x₁, x₂ ≥ 0

скласти двоїсту задачу і знайти розв’язок обох задач.

Розв’язок. Двоїстою задачею стосовно вихідного є задача, що полягає у визначенні мінімального значення функції F*= 14 y₁ +8 y₂ при умовах

y₁, y₂ ≥ 0

Як у вихідній, так і у двоїстій задачі число невідомих дорівнює двом. Отже, їхнє розв’язок можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (рис. 1.14 і 1.15).

Як видно з рис. 1.14, максимальне значення цільова функція вихідної задачі приймає в точці В. Отже, Х*= (2;6) є оптимальним планом, при якому F_max =46.

Мінімальне значення цільова функція двоїстої задачі приймає в точці Е (рис. 1.17). Виходить, Y *=(1; 4) є оптимальним планом двоїстої задачі, при якому F * _min =46. Таким чином, значення цільових функцій вихідної і двоїстої задач при їх оптимальних планах рівні між собою.

Рис. 1.14 Рис. 1.15

З рис. 1.14 видно, що при всякому плані вихідної задачі значення цільової функції не більше 46. Одночасно, як видно з рис. 1.15, значення цільової функції двоїстої задачі при будь-якому її плані не менше 46. Таким чином, при будь-якому плані вихідної задачі значення цільової функції не перевершує значення цільової функції двоїстої задачі при її довільному плані.

Знаходження розв’язку двоїстих задач. Розглянемо пари двоїстих задач – основну задачу лінійного програмування (61)-(63) і двоїсту до неї задачу (64), (65).

Припустимо, що за допомогою симплексного методу знайдений оптимальний план X* задачі (61) - (63) і цей план визначається базисом, утвореним векторами .

Позначимо через С_б= () вектор-рядок, складений з коефіцієнтів при невідомих у цільовій функції (61) задачі (61)-(63), а через Р ^-1 – матрицю, зворотну матриці Р, що складена з компонент векторів базису. Тоді має місце наступне твердження.

Теорема 1.11. Якщо основна задача лінійного програмування має оптимальний план X*, то Y*=С_бР ^-1 є оптимальним планом двоїстої задачі.

Таким чином, якщо знайти симплексним методом оптимальний план задачі (61)-(63), то, використовуючи останню симплекс-таблицю, можна визначити С_б і Р ^-1і за допомогою співвідношення Y*=С_бР ^-1знайти оптимальний план двоїстої задачі (64), (65).

У тому випадку, коли серед векторів P₁, P₂,...; P_n,складених з коефіцієнтів при невідомих у системі рівнянь (62), є т одиничних, зазначену матрицю Р ^-1утворять числа перших т рядків останньої симплекс-таблиці, що стоять у стовпцях даних векторів. Тоді немає необхідності визначати оптимальний план двоїстої задачі множенням C_б на Р ^-1оскільки компоненти цього плану збігаються з відповідними елементами (т +1)-го рядка стовпців одиничних векторів, якщо даний коефіцієнт c_j =0, і дорівнюють сумі відповідного елемента цього рядка і c_j,якщо c_j ≠0.

Сказане вище має місце і для симетричної пари двоїстих задач. При цьому так як система обмежень вихідної задачі містить нерівності виду «≤», то компоненти оптимального плану двоїстої задачі збігаються з відповідними числами (т +1)-го рядка останньої симплекс-таблиці розв’язок вихідної задачі. Зазначені числа стоять у стовпцях векторів, що відповідають додатковим змінним.

1.89. Для задачі, що полягає у визначенні максимального значення функції F=x₁ +2 x₂ –2 x₃ при умовах

х₁, х₂, х₃ ≥ 0

скласти двоїсту задачу і знайти її розв’язок.

Розв’язок. Двоїста задача стосовно вихідного полягає в знаходженні мінімуму функції F*= 12 y₁ +17 y₂ +4 y₃ при умовах

y₁, y₂, y₃ ≥ 0

Щоб знайти розв’язок двоїстої задачі, спочатку знаходимо розв’язок вихідної задачі методом штучного базису. Воно наведено в табл. 1.42.

З останньої симплекс-таблиці видно, що двоїста задача має розв’язок y₁ ^*=5/7; y₂ ^*=0; y₃ ^*=6/7.

Оптимальні двоїсті оцінки задовольняють всім умовам двоїстої задачі. При цьому мінімальне значення цільової функції двоїстої задачі, рівне F*_т_in= = 12·(5/7)+17·0+4·(6/7)=12, збігається з максимальним значенням цільової функції F_тах вихідної задачі.

Таблиця 1.42

i	Базис	C_б	P₀			–1		– M
P₁	P₂	P₃	P₄	P₅	P₆
	P₄ P₅ P₆	– М	–4	–1 –1 –2	–1 –2	–2 –2
	P₄ P₅ P₁				7/2 3/2 –1/2 –5/2	–1		1/2 –1/2 1/2 1/2
	P₂ P₅ P₁					–2/7 13/7 6/7 9/7	2/7 –3/7 1/7 5/7	1/7 –5/7 4/7 6/7

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒