Автор работы: Пользователь скрыл имя, 23 Февраля 2012 в 20:05, реферат
Різновидом подвійних задач лінійного, програмування є подвійні симетричні задачі, в яких система обмежень як вихідної, так і подвійної задач задається нерівностями, причому на подвійні змінні накладається умова позитивності.
На підставі розглянутих несиметричних і симетричних подвійних задач можна укласти, що математичні моделі пари подвійних задач можуть мати один з наступних видів.
Різновидом подвійних задач лінійного, програмування є подвійні симетричні задачі, в яких система обмежень як вихідної, так і подвійної задач задається нерівностями, причому на подвійні змінні накладається умова позитивності.
На підставі розглянутих несиметричних і симетричних подвійних задач можна укласти, що математичні моделі пари подвійних задач можуть мати один з наступних видів.
Несиметричні задачі
(1) Вихідна задача Подвійна задача
Zmin = CX; fmax = YA0;
AX = A0; YA £ С.
X ³ 0.
(2) Вихідна задача Подвійна задача
Zmax = CX; fmin = YA0;
AX = A0; YA ³ С.
X ³ 0.
Симетричні задачі
(3) Вихідна задача
Zmin = CX; fmax = YA0;
AX ³ A0; YA £ С.
X ³ 0.
(4) Вихідна задача
Zmax = CX; fmin = YA0;
AX £ A0; YA ³ С.
X ³ 0.
Таким чином, перш ніж записати подвійну задачу для даної вихідної, систему обмежень вихідної задачі необхідно привести до відповідного вигляду. Запишемо, наприклад, математичну модель подвійної задачі для наступної вихідної.
Приведемо без доказу наступну теорему.
Теорема 1.1. Якщо
при підстановці компонент
Якщо i-я компоненту оптимального плану подвійної задачі позитивна, то i-e обмеження вихідної задачі задовольняється її оптимальним рішенням як строга рівність.
Перехід до подвійної задачі не обов'язковий, оскільки якщо розглянути першу симплексну таблицю з одиничним додатковим базисом, то легко відмітити, що в стовпцях записана вихідна задача, а в рядках - подвійна. Причому оцінками плану вихідної задачі є Сj а оцінками плану подвійної задачі – bi. Вирішимо "подвійну задачу по симплексній таблиці, в якій записана вихідна задача; знайдемо оптимальний план подвійної задачі, а разом з ним і оптимальний план вихідної задачі. Цей метод носить назву подвійного симплексного методу.
Хай необхідно вирішити вихідну задачу лінійного програмування, поставлену в загальному вигляді: мінімізувати функцію Z = СХ при АХ = A0, Х ³ 0. Тоді в подвійної задачі необхідно максимізувати функцію f = YA0 при YA £ С.
Допустимо, що вибраний такий базис D = (A1, А2 ..., Аi ..., Аm), при якому хоч би одна з компонент вектора Х = D-1 A0 = (x1, x2 ..., xi ..., xm) негативна (наприклад, xi < 0), але для всіх векторів Aj виконується співвідношення Zj – Cj £ 0 (i = 1,2 ..., n). Тоді на підставі теореми подвійності Y = Сбаз D-1 - план подвійної задачі. Цей план не оптимальний, оскільки, з одного боку, при вибраному базисі X містить негативну компоненту і не є планом вихідної задачі, а з іншого боку, оцінки оптимального плану подвійної задачі повинні бути ненегативними.
Таким чином, вектор Аi, відповідний компоненті xi < 0, слід виключити з базису вихідної задачі, а вектор, відповідний негативній оцінці, - включити в базис подвійної задачі.
Для вибору вектора, що включається в базис вихідної задачі, проглядаємо i-й рядок: якщо в ньому не містяться xij < 0, то лінійна функція подвійної задачі не обмежена на многограннику рішень, а вихідна задача не має рішень. Якщо ж деякі xij < 0, то для стовпців, що містять ці негативні значення, обчислюваний 0j= min (xi/xij) ³ 0 і визначаємо вектор, відповідний max 0j(Zj — Cj) при рішенні вихідної задачі на мінімум і min 0j(Zj — Cj) при рішенні вихідної задачі на максимум. Цей вектор і включаємо в базис вихідної задачі. Вектор, який необхідно виключити з базису вихідної задачі, визначається направляючим рядком.
Якщо 0j = min (xi/xij) = 0, тобто xi = 0, то xij береться за розв’язуючий елемент тільки в тому випадку, якщо xij > 0. Такий вибір розв’язуючого елементу на даному етапі не приводить до збільшення кількості негативних компонент вектора X. Процес продовжуємо до отримання Х ³ 0; при цьому знаходимо оптимальний план подвійної задачі, отже, і оптимальний план вихідної задачі. В процесі обчислень по алгоритму двоїстого симплексного методу умова Zj – Cj £ 0 можна не враховувати до виключення всіх хi < 0, потім оптимальний план знаходиться звичайним симплексним методом. Це зручно використовувати, якщо все хi < 0; тоді для переходу до плану вихідної задачі за одну ітерацію необхідне 0j визначити не по мінімуму, а по максимуму відносин, тобто 0j = max (xi/xij) > 0.
Двоїстим симплексним методом можна вирішувати задачі лінійного програмування, системи обмежень яких при позитивному базисі містять вільні члени будь-якого знаку. Цей метод дозволяє зменшити кількість перетворень системи обмежень, а також розміри симплексної таблиці.
Вирішити задачі подвійним симплекс методом
Задача 1
за умови
Приводимо систему обмежень до канонічного вигляду
|
Базис |
С |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
3 |
2 |
0 |
0 |
0 | |||
x3 |
0 |
21 |
3 |
1 |
1 |
0 |
0 |
x4 |
0 |
30 |
2 |
3 |
0 |
1 |
0 |
x5 |
0 |
-16 |
-2 |
0 |
0 |
0 |
1 |
z-c |
0 |
-3 |
-2 |
0 |
0 |
0 | |
x1 |
3 |
7 |
1 |
1/3 |
1/3 |
0 |
0 |
x4 |
0 |
16 |
0 |
7/3 |
-2/3 |
1 |
0 |
x5 |
0 |
-2 |
0 |
2/3 |
2/3 |
0 |
1 |
z-c |
21 |
0 |
-1 |
1 |
0 |
0 | |
x1 |
3 |
33/7 |
1 |
0 |
3/7 |
-1/7 |
0 |
x2 |
2 |
48/7 |
0 |
1 |
-2/7 |
3/7 |
0 |
x5 |
0 |
-46/7 |
0 |
0 |
6/7 |
-2/7 |
1 |
z-c |
195/7 |
0 |
0 |
5/7 |
3/7 |
0 |
Відповідь: Fmax=27,857 Xопт=(4,714;6,857;0;0;0)