На головну

сімплексні таблиці

  1.  АНАЛІЗ таблиці спряженості
  2.  Будьте готові представити і пояснити структуру своєї таблиці усно.
  3.  Ввести послідовно назву статистичних ознак з таблиці 1 як назви стовпців. Вони повинні бути введені послідовно в осередку без пропуску стовпців.
  4.  Внесення змін до таблиці.
  5.  ПИТАННЯ Прикладне ПО. Електронні таблиці.
  6.  Вставка в таблицю і видалення рядків, стовпців, таблиці
  7.  Вставка і створення таблиці

Практичні розрахунки з використанням симплекс методу - на комп'ютері. Якщо вручну, то використовуються симплекс-таблиці. Будемо вирішувати завдання на максимум.

I. Після введення додаткових змінних систему рівнянь і лин функцію записують у вигляді, який називається розширеною системою: (Слайд 2)

 А11 * Х1 + А12 * Х2 + ... + А1N * Xn + Xn + 1 = В1

а21 * Х1 + а22 * Х2 + ... + а2n * Xn + Xn +2 = В2 ............................. .........................................

аm1 * Х1 + аm2 * Х2 + ... + аmn * Xn + Xn + m = Вm

F - c1X1 - c2X2 - ... - cnXn = 0

Припускаємо, що всі додаткові змінні мають той же знак, що і вільні члени, в іншому випадку використовується М-метод (розглянемо далі).

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

III. Перевіримо виконання критерію оптимальності (при макс - наявність негативні коефіцієнтів в останньому рядку, т. К. Вони з «-»). Якщо їх немає, то досягнутий максимум (його значення - в лівому нижньому кутку таблиці), основні змінні - значення другого стовпця, неосновні = 0, т. Е. Оптимальне БР.

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

Складаємо оціночні відносини кожного рядка за правилами:

1) ?Bi / Aij?, якщо Bi і Aij одного знака і Aij НЕ = 0, Bi НЕ = 0.

2) ?, якщо Bi і Aij різного знака і Aij НЕ = 0, Bi НЕ = 0.

3) 0, якщо Bi = 0 і Aij> 0.

4) ?, якщо Bi = 0 і Aij <0.

5) ?, якщо Aij = 0.

Визначаємо min по I для {?Bi / Aij?}. Якщо кінцевого мінімуму немає, то немає кінцевого оптимуму. Якщо мінімум кінцевий, то вибирається рядок q, на якій він досягається (будь-яка, якщо їх кілька), називається роздільною рядком. На перетині дозволяє елемент Aqs.

V. Переходимо до наступної таблиці за правилами:

1) в лівому стовпчику записуємо новий базис: замість основної змінної Xq - змінну Xs;

2) в шпальтах, що відповідають основним змінним, проставляємо: 1 - проти «своєї основної змінної, 0 - проти« чужий основною змінною, 0 - в останньому рядку для всіх основних змінних;

3) новий рядок з номером q отримуємо зі старої поділом на дозволяючий елемент Aqs;

4) всі інші нові елементи Aij обчислюємо по правилом прямокутника: (Слайд 3)

Далі перейти до п. III алгоритму.

Приклад (вирішували як приклад симплекс-методу):

 F = 2x1 + 3х2 a maxпрі обмеженнях:  х1 + 3х2 <= 182х1 + х2 <= 16х2 <= 53x1 <= 21х1, х2> = 0  Розширена система має вигляд:  х1 + 3х2 + х3 = 182х1 + х2 + х4 = 16х2 + х5 = 53x1 + х6 = 21х1, х2, х3, х4, х5, х6> = 0F - 2x1 - 3х2 = 0

таблиці:

 базис  вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5  Х6
 Х3  18/3
 Х4
 Х5
 Х6 ?
F  -2  -3  

 

 базис  вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5  Х6
 Х3  -3
 Х4  -1  11/2
 Х2 ?
 Х6
F  -2  
 базис  вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5  Х6
 Х1  -3 ?
 Х4  -2  5/5
 Х2  5/1
 Х6  -3  12/9
F  -3  
 базис  вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5  Х6
 Х1  -1/5  3/5  
 Х5  -2/5  1/5  
 Х2  2/5  -1/5  
 Х6  3/5  -9/5  
F  4/5  3/5  

Метод штучного базису (М-метод)

Використовується, коли перше БР - неприпустиме.

У кожне рівняння, що дає негативну компоненту в БР, вводиться своя нова неотрицательная штучна змінна У1, У2, ..., Ук, яка має той же знак, що і вільний член в правій частині рівняння. У першій таблиці включаються в число основних (базисних) всі штучні змінні і ті звичайні додаткові змінні, які визначають невід'ємні компоненти БР. Складається нова лінійна функція Т = F - м (У1 + У2 + ... + Ук), де М - довільно велике число, і шукається її максимум. (Слайд 6)

Справедлива теорема (без доведення):

1. Якщо в оптимальному вирішенні нової функції всі штучні змінні = 0, то відповідні значення інших змінних дають оптимальне рішення вихідної завдання (тощо. Е. Тмах = Fмах, якщо У1 = У2 = ... = Ук = 0, т. Е. мінімум М-функції = 0).

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

3. Якщо Тмах = ?, то вихідна задача також нерозв'язна, причому або Fмах = ?, або умови завдання суперечливі.

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

приклад:

 F = x1 + 2х2 a max  х1 - х2 <= -1х1 - х2> = -3х1 <= 3х1, х2> = 0  Розширена система має вигляд:  х1 - х2 + х3 = -1х1 - х2 - х4 = -3х1 + х5 = 3х1, х2, х3, х4, х5, х6> = 0

Х1 = (0; 0; -1; 3; 3) - неприпустиме БР, тому в перше рівняння введемо штучну змінну У1 з тим же знаком, що і вільний член.

 х1 - х2 + х3 - в1 = -1х1 - х2 - х4 = -3х1 + х5 = 3  - Х1 + х2 - х3 + в1 = 1 х1 + х2 + х4 = 3х1 + х5 = 3

У першій симплексній таблиці останній рядок - це (-М) -функція, т. Е. (М) У1. Заповнюється множенням рядка У1 на коефіцієнт (М).

 (Слайд 7)
 базис

 вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5  У1
 У1  -1  -1
 Х4  -1
 Х5 ?
F  -1  -2  
 Мт  -М М  -М М  -М  

Замінюємо У1 на Х2.

 базис  вільний член  змінні  Оціночна ставлення
 Х1  Х2  Х3  Х4  Х5
 Х2  -1  -1  
 Х4  
 Х5  
F  -3  -2  
 Мт  

Останній рядок показує, що критерій оптимальності виконаний: мах (-М) = 0, значить хв М = 0. далі цей рядок можна не розглядати. Отримано ДБР (0; 1; 0; 2; 3), починаючи з якого вирішуємо вихідну задачу відповідно до звичайного алгоритмом.




 лінійне програмування |  Поняття економіко-математичної моделі |  Завдання про розкрої матеріалів. |  Система m лінійних рівнянь з n змінними |  Геометричний сенс рішень нерівностей, рівнянь і їх систем |  Є опуклим багатокутником (або опуклою багатокутної областю). |  Властивості задач ЛП |  Геометричний метод розв'язання задач ЛП |  симплексний метод |  Знаходження оптимуму лінійної функції |

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