На головну

Алгоритм симплекс методу

  1. D. Симплекс-метод
  2. I. Внесення відомостей в форму ДМВ-1 при використанні методу визначення митної вартості за ціною угоди із ввезених товарів
  3. II. Вимоги до методів вимірювання і контролю показників мікроклімату
  4. III. Внесення відомостей у форму ДТС-2 при застосуванні резервного методу визначення митної вартості
  5. N Вибір методу пайки залежить від програми випуску виробів, особливостей конструкції, вимог до якості.
  6. N Необхідна точність досягається методами автоматичного отримання розмірів на налаштованих верстатах при забезпеченні взаємозамінності оброблюваних заготовок і що збираються вузлів.
  7. А) негативно ставилися до особи І. В. Сталіна і його методам будівництва соціалізму

При вирішенні ЗЛП симплекс-метод реалізується у вигляді так званої симплекс таблиці. Алгоритм симплекс методу складається з наступних етапів:

1. Заготовлюється вихідна симплекс таблиця в першому стовпці якої розташовуються позначення векторів входять в базис, у другому стовпці коефіцієнти Ci ЦФ відповідні векторах, що входять в базис, а в третьому стовпці пишеться величина Z0, де Z0= ?mi = 1CiXi. Далі йдуть стовпці відповідні всіма векторами Aj, В цих стовпцях записуються координати цих векторів в розглянутому базисі, при етоі для векторів входять в базис ці координати мають вигляд (0,0,0, ..., 0,1,0, ..., 0). Тут: одиниця стоїть в тому рядку, де знаходиться сам базисний вектор. У додатковому рядку зверху виписують коефіцієнти Ci відповідні цим векторах. У додатковому рядку знизу пишуться величини Zj-Cj= ?mi = 1CiXij-Cj. Далі йдуть етапи які пов'язані з перетворенням заготовленої таблиці.

2. розглядається додатковий рядок знизу:

· Якщо все різниці Zj-Cj<= 0,то отриманий план є оптимальним (теор. 2)

· якщо Zj-Cj> 0для деякого j , То вибирається стовпець з максимальним значенням цієї різниці. індекс jвизначається завдан вектор вводиться в базис. нехай max (Zj-Cj) = Zi-Ci значітвекторAi необхідно ввести в базис. Цей вектор називається напрямних , Йому відповідає направляючий стовпець, який позначають символом «^»

3. переглядаємо направляючий стовпчик якщо в ньому все xil<0, То значить ЦФ не обмежена знизу, якщо є xil> 0, То знаходимо величину ?0= mini xi/ xil проглядаються тільки ті дроби для яких xil> 0.Нехай цей мінімум досягається для вектора Ak, Тоді саме цей вектор підлягає виведенню з базису. Рядок відповідає цьому вектору називається направляючої і позначається «a».

4. Після визначення напрямних шпальти і рядки заповнюють нову симплекс таблицю. У такій таблиці на місці направляючої рядка буде стояти Ai .Заповнення нової таблиці починається з направляючої рядка. Як компоненти опорного плану туди пишеться величина ?0 X'l= ?0= Xk/ Xkl, інші елементи цього рядка визначаються за формулою X'lj X'lj= Xkj/ Xklде Xkl елемент знаходиться на перетині напрямних рядка і стовпчика, саме на нього діляться всі колишні елементи направляючої рядки, а на місці колишнього елемента Xkl автоматично з'являється одиниця. Загальне правило для перерахунку направляючої рядки можна записати так: Ak (Новий ел-т направляючої рядка) = (старий Ел-т направл. Рядки) / (ел-т стоїть на перетині направл. Шпальти і рядки)

5. перераховуються всі елементи інших рядків таблиці, включаючи додаткову нижню рядок. Перерахунок проводиться за формулами

· для компонент опорного плану X'i= Xi-?0Xil= Xi- (Xk/ Xkl) * Xil

· для компонент розкладених по базису X'ij= Xij- (Xkj/ Xkl) * Xil

· Для додаткового рядкаZ'j-Cj= (Zj-Cj) - (Xkj/ Xkl) * (Zl-Cl)

Всі ці формули будуються по одному правилу:

(Новий ел-т) = (старий ел-т) - (ел-т нової направл. Рядки) * (ел-т направл. Стовпця стоїть в соотв. Рядку)

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

Методи природного і штучного базису. Основні поняття, алгоритми методів.

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

метод штучного базису заснований на штучному введенні в математичну модель задачі таких векторів.

Нехай задана ЗЛП канонічної форми

F: C1X1= C2X2+ ... + CnXnamin

a11x1+ a21x2+ ... + An1xn= b1

a12x1+ a22x2+ ... + An2xn= b2

..............................

a1mx1+ a2mx2+ ... + Anmxn= bm

xi> = 0 Vi= 1, n

Тоді її перетворюють до вигляду

F: C1X1+ C2X2+ ... + CnXn+ MXn = 1+ MXn + 2+ ... + MXn + mamin

a11x1+ a21x2+ ... + An1xn+ xn + 1= b1

a12x1+ a22x2+ ... + An2xn+ xn + 2= b2

.....................................

a1mx1+ a2mx2+ ... + Anmxn+ xn + m= bm

Xi> = 0 Vi= 1, n + m

Де М - нескінченно великі числа. В отриманій задачі відразу видно вихідний базис, як нього слід взяти вектора при штучно введених змінних xn + 1, xn + 2, ..., Xn + m. Оскільки саме ці вектора матимуть вигляд: (1,0,0, ..., 0), (0,1,0, ..., 0), (0,0, ..., 1). Потім перетворену завдання вирішують, використовуючи алгоритм симплекс методу. Вихідний опорний план перетвореної завдання має вигляд (0,0, ..., 0, xn + 1, xn + 2, ..., Xn + m) = (0,0, ..., 0, b1, b2, ..., Bm). Вихідна симплекс таблиця виглядає наступним чином

 БазісAi  коеф. ЦФCi  ПланXi  C1  C2  ...  Cn M M  ... M
 A1  A2  ...  An An + 1 An + 2  ... An + m
An + 1 M b1 a11 a21  ... an1  ...
An + 2 M b2 a12 a22  ... an2  ...
 ...  ...  ...  ...  ...  ...  ...  ...  ...  ...  ...
An + m M bm a1m a2m  ... anm  ...
  Z0              

Визначаємо ел-ти додаткового рядка за формулами Z0= Mb1+ Mb2+ ... + Mbm= ?mi = 1Mbi= M?ni = 1bi

 Для визначення різниць Zj= a11M + Ma12+ ... + Ma1m= M?mj = 1aij V i = 1, n

Zj-Cj= M?mj = 1aij-Cj

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

Оскільки М дуже велике число, то серед різниць Zj-Cj буде багато позитивних чисел. Т. е. Буде безліч претендентів на введення в базис серед векторів A1, A2, ..., An

Якщо якийсь вектор відповідає штучно введеним змінним xn + 1, xn + 2, ..., Xn + m, То відповідний вектор виводиться з базису, а стовпець симплекс таблиці при цьому векторі викреслюється і більше до нього не повертаються. В кінці перетворення симплекс таблиці можливі два варіанти:

· Всі вектори відповідні штучним змінним були виведені з базису, в цьому випадку всі стовпці симплекс таблиці відповідні додатковим змінним зникнуть, і буде вирішуватися вихідна задача

· Отриманий оптимальний план все ж буде містити будь-яку додаткову змінну, це означає, що ОДР вихідної задачі порожня, т. Е. Її обмеження суперечливі, тому вихідна задача взагалі не має рішень.

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

Симетричні двоїсті задачі:



наближені методи | Друга стандартна форма

Математичне формулювання завдань дискретного програмування | Метод відсікань. Формулювання вірного відсікання. алгоритм методу | Переваги та недоліки алгоритму. | Формування нижніх і верхніх оцінок цільової функції | алгоритм методу | комбінаторні методи | Метод лексикографічного перебору | Метод неявного перебору по векторної решітці | Вихідна задача в канонічній формі | Xi |

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