загрузка...
загрузка...
На головну

Друга теорема подвійності

  1. Аксіома Больцано-Вейєрштрасса і теорема про стягують системі відрізків
  2. В) Теорема про зміну моментів кількості руху для матеріальної системи (теорема моментів)
  3. Вектор прискорення в даний момент часу визначається як перша похідна від вектора швидкості за часом або друга похідна від радіуса-вектора за часом.
  4. друга аксіома
  5. Друга аналітична група катіонів
  6. ДРУГА ГРУПА
  7. ДРУГА ЛЕКЦІЯ

Тісний зв'язок між двома взаємно подвійними завданнями проявляється не тільки в рівність оптимальних значень їх лінійних функцій, про що стверджувалося в першій (основний) теоремі подвійності.

Нехай дано дві взаємно двоїсті завдання I - (6.1) - (6.3) і II - (6.4) - (6.6). Якщо кожну з цих задач вирішувати симплексним методом, то необхідно їх привести до канонічного виду, для чого в систему обмежень (6.2) завдання I (в короткій записи  ) Слід ввести m невід'ємних змінних  , А у систему обмежень (6.5) завдання II ( ) n невід'ємних змінних  , де i(j) - Номер нерівності, в яке введена додаткова змінна .

Системи обмежень кожної з взаємно двоїстих задач приймуть вид:

 . (6.12)

 . (6.13)

Встановимо наступне відповідність між початковими змінними однієї з двоїстих задач і додатковими змінними іншої задачі:

 Змінні вихідної завдання I
 початкові  додаткові
 додаткові  початкові
 Змінні вихідної задачі II

Теорема 6.1.Позитивним (ненульовим) компонентам оптимального вирішення однієї з взаємно двоїстих задач відповідають нульові компоненти оптимального вирішення іншої задачі, тобто для будь-яких i = 1, 2, ..., т и у = 1, 2, ..., п:

якщо  , то  ; якщо  , то  і аналогічно,

якщо  , то  ; якщо  , то .

З теореми випливає важливий висновок про те, що введене раніше відповідність (6.14) між змінними взаємно двоїстих задач при досягненні оптимуму (тобто на останньому кроці вирішення кожного завдання симплексним методом) представляє відповідність між основними (Як правило, не рівними нулю) змінними однієї з двоїстих задач і неосновними (Рівними нулю) змінними іншої задачі, коли вони утворюють допустимі базисні рішення.

Розглянута теорема є наслідком наступної теореми.

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

Приклад 6.5.Переконатися в справедливості другої теореми подвійності для взаємно двоїстих задач I і II, наведених в прикладі 6.2.

Рішення.На підставі виразу (6.14) встановимо наступне відповідність між змінними. У гл. 5 обидва завдання були вирішені симплексним методом. На останньому кроці вирішення кожного завдання (див. С. 54 і с. 57) отримано:

 у вихідній задачі I в двоїстої завданню II

 (6.20)  (6.21)

 при  при

оптимальному базисному оптимальному базисному

рішенні  рішенні

Компоненти оптимального рішення двоїстої завдання

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

Зауваження.Якщо в одній з взаємно двоїстих задач порушується єдиність оптимального рішення, то оптимальне рішення двоїстої завдання вироджене. Це пов'язано з тим, що при порушенні єдиності оптимального рішення вихідної завдання в вираженні лінійної функції її оптимального рішення через неосновні змінні відсутня хоча б одна з неосновних змінних.

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

Приклад 6.6.Вирішити симплексним методом задачу

 при обмеженнях

.

і знайти оптимум і оптимальне рішення двоїстої завдання, використовуючи теореми подвійності.

Рішення.Вирішуючи задачу симплексним методом, отримаємо на останньому кроці рішення (рекомендуємо читачеві переконатися в самостійно):  , тобто  при оптимальному базисному рішенні  = (4; 7; 0; 0; 6; 6).

У цьому завданню відповідність (6.14) між змінними набуде вигляду:

На підставі першої теореми подвійності  . На підставі другої теореми подвійності оптимальне рішення двоїстої завдання  = (2/7; 3/7; 0; 0; 0; 0), так як , тобто коефіцієнту при відповідній змінній х3в вираженні лінійної функції F(x),  , Тобто коефіцієнту при змінної  через відсутність відповідних змінних х5, х6, x1, х2в вираженні F(x) Їх коефіцієнти дорівнюють нулю. Отже, в двоїстої завданню Zmin = 10 при  = (2/7; 3/7; 0; 0; 0; 0).

Метод, при якому спочатку симплексним методом вирішується двоїста задача, а потім оптимум і оптимальне рішення вихідної завдання знаходяться за допомогою теорем подвійності, називається двоїстим симплексним методом. Цей метод буває вигідно застосовувати, коли перше базисне рішення вихідної завдання неприпустиме або, наприклад, коли число її обмежень m більше числа змінних n.



Попередня   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   Наступна

Геометрична інтерпретація симплексного методу | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці | Поняття про М-методі (методі штучного базису) | Економічна інтерпретація завдання, двоїстої задачі про використання ресурсів | Взаємно двоїсті задачі лінійного програмування і їх властивості |

загрузка...
© um.co.ua - учбові матеріали та реферати