Восток Маркетинг


Статьи

НОУ ІНТУЇТ | лекція | Метод повного виключення. Табличний симплекс - метод. Геометрична інтерпретація задач лінійного програмування

2. Табличний симплекс - метод

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

Припустимо, що обмеження задачі зведено до такого виду, що в матриці А є одинична подматріца і всі вільні члени позитивні. Іншими словами, нехай матриця обмежень має вигляд

A1x1 + ... + Anxn + e1xn + e1xn + 1 + ... + emxn + m = A0 = [ai0],

де

для всіх i = 1, 2,., n.

Застосуємо одну ітерацію методу повного виключення до розширеної матриці обмежень Ap = [A1, ..., An, e1, ..., em, A0].

Нехай aij - направляючий елемент перетворення на даній ітерації. Тоді в результаті перетворень відповідно до (1.10) отримаємо нові значення вільних членів:

Досліджуємо вираження (2.1) і з'ясуємо умови, при яких Досліджуємо вираження (2 для всіх l, тобто нове базисне рішення буде також допустимим.

за припущенням за припущенням   , тоді , тоді

якщо якщо   , тоді   , оскільки , тоді , оскільки .

якщо якщо   , то , то

буде більше нуля при всіх l = 1, 2, ..., m тоді і тільки тоді, коли

Перетворення Гауса називають симплексним перетворенням, коли направляючий елемент визначають за такими правилами:

a) спрямовує стовпець j вибирають з умови, що в ньому є хоча б один позитивний елемент;

б) направляє рядок i вибирають так, щоб відношення б) направляє рядок i вибирають так, щоб відношення   було мінімально за умови, що aij> 0 було мінімально за умови, що aij> 0.

При такому перетворенні в базис вводиться вектор Aj і виводиться вектор Аi. Тепер треба визначити, як вибрати вектор, що вводиться в базис, щоб при цьому значення цільової функції збільшилася.

Для цього використовують так звані оцінки векторів Для цього використовують так звані оцінки векторів   : :

де де   - безліч індексів базисних векторів;  xij - визначають з умови - безліч індексів базисних векторів; xij - визначають з умови

величини величини   рівні симплекс -разніцам для змінних {xj} з протилежним знаком рівні симплекс -разніцам для змінних {xj} з протилежним знаком. Отже, для того щоб значення цільової функції збільшилася, необхідно вибрати направляючий стовпчик Аj з найбільшою за модулем негативною оцінкою, тобто

Для вирішення завдання симплекс-методом на кожній ітерації заповнюють симплекс-таблицю 2.1 .

Останній рядок таблиці - індексна - служить для визначення направляючого стовпця. її елементи Останній рядок таблиці - індексна - служить для визначення направляючого стовпця визначають за формулою (2.3). Очевидно, для всіх базисних векторів {Ai} i = 1,., M оцінки .

Значення цільової функції a00 визначається зі співвідношення

У стовпці Bx записуємо базисні змінні {xi} i = 1, ..., m. Їх значення визначаються стовпчиком вільних членів ai0, тобто

Напрямні рядок Ai і стовпець Aj вказуються стрілками. Якщо в якості направляючого елемента обраний aij, то перехід від даної симплекс-таблиці до наступної визначається співвідношеннями (1.8) - (1.10).

Отже, алгоритм вирішення задачі ЛП табличним симплекс-методом складається з етапів.

1. Розраховують і заповнюють початкову симплекс-таблицю з допустимим одиничним базисом, включаючи індексний рядок.

2. В якості направляючого стовпця вибирають Aj, для якого

3. Напрямна рядок Aі вибирають з умови

4. Роблять один крок (ітерацію) методу повного виключення Гаусса з напрямних елементом aij, для чого використовують співвідношення (1.8) - (1.10). Зокрема, елементи індексного рядка нової таблиці обчислюють відповідно до формули

Правильність обчислень контролюють за формулами безпосереднього рахунку: В стовпці Bx нової таблиці замінюють xi на xj, а в стовпці С ci на cj.

5. Якщо все 5 , То нове базисне рішення - оптимально. В іншому випадку переходять до етапу 2 і виконують чергову ітерацію.

6. Другий, третій і четвертий етапи повторюють до тих пір, поки одна з ітерацій не закінчиться одним з двох випадків:

а все а все . Це ознака (критерій) оптимальності базисного рішення останньої симплекс-таблиці;

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

Назвемо деякі особливості застосування табличного симплекс-методу.

Якщо в якості початкового базису вибирають базис з вільних змінних, для яких ci = 0, то оцінки для всіх небазисних змінних рівні Якщо в якості початкового базису вибирають базис з вільних змінних, для яких ci = 0, то оцінки для всіх небазисних змінних рівні   , А відповідне значення цільової функції , А відповідне значення цільової функції

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

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

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

также можем предложить:
печать бланков и прайс-листов | печать визитных карточек (визиток)
изготовление папок и меню | изготовление блокнотов
печать листовок

Связаться с менеджером для оформления заказа:
тел.: +38 (062) 349-56-15, 348-62-20
моб.: +38 (095) 811-22-62, +38 (093) 665-38-06,
+38 (067) 17 44 103
факс: +38 (062) 332-28-98
e-mail: [email protected]
г. Донецк, ул. Артема, 41

   2010 © Восток Маркетинг Яндекс.Метрика