Головна

й випадок. ЗЛП представлена ??в симетричної формі запису.

  1. C - матриця (за формою нагадує куб) застосовується для визначення взаємозв'язку елементів трьох списків одночасно.
  2. Погодження прикметників у формі порівняльної ступеня з іменниками
  3. Exercise II. Розкрийте дужки і вживайте дієслова у відповідній формі.
  4. II тур - «практичне втілення», проводітсяв очно-заочній формі
  5. III. Визначення рівняння нелінійної регресії у формі користувача
  6. Аграрні проблеми пореформеної Росії
  7. Активна медитація повинна народжуватися щомиті як спроба зупинити роботу розуму, спрямовану на реалізацію (в будь-якій формі) думок і бажань.

Тоді система обмежень має вигляд

Зведемо задачу до канонічної формі запису, додавши до лівих частинах

системи обмежень додаткові змінні (  ). тоді

система обмежень прийме кращий вигляд:

Звідси отримуємо початковий опорний план:

.

У цільову функцію додаткові змінні вводяться з коефіцієнтами, рівними нулю: (  ).

Приклад 4. Знайти початковий опорний план

Рішення. Наведемо завдання до канонічного вигляду:

Система обмежень має кращий вигляд. Початковий опорний план .

3-й випадок. Нехай система обмежень має вигляд

Зведемо задачу до канонічного вигляду, додавши до лівих частинах

системи обмежень додаткові змінні (  ):

Тепер система обмежень, взагалі кажучи, не має переважного виду. У цьому випадку вводять штучний базис шляхом переходу до М-задачі:

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

 Z (  ) = 0.

Між оптимальними планами вихідної задачі і M-завдання є такий зв'язок: якщо в оптимальному плані M-завдання все штучні змінні  дорівнюють нулю, то значення решти координат плану  дадуть оптимальний план вихідної завдання.

Знаходження оптимального опорного плану. Початковий опорний план 0 досліджується на оптимальність:

1) якщо в Z-строке немає негативних елементів (не рахуючи вільного члена) - план оптимальний. Якщо в Z -строке немає також і нульових елементів, то оптимальний план єдиний; якщо ж серед елементів є хоча б один нульовий, то оптимальних планів безліч.

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

3) якщо в Z -строке є хоча один негативний елемент, а в кожному стовпці з таким елементом є хоча б один позитивний, то можна перейти до нового опорного плану, ближчого до оптимального. Для цього стовпець з негативним елементом в f-рядку беруть за розв'язний (якщо в f-рядку негативних елементів декілька, що дозволяє вибирають стовпець з найбільшим за абсолютною величиною негативним елементом), визначають по мінімальному сімплексному відношенню роздільну рядок і роблять крок жорданова виключення. Отриманий опорний план знову досліджують на оптимальність.

Описаний процес повторюється до тих пір, поки не буде знайдений оптимальний опорний план або встановлена ??нерозв'язність завдання.

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

Рішення: Завдання записана в канонічній формі, але два вільних члена негативні, тому перед тим як записати задачу в формі таблиці, помножимо перше і друге рівняння на (-1).

А тепер будемо перекидати нулі з лівого стовпчика на верх таблиці. Для першого кроку жорданова виключення візьмемо що дозволяє, наприклад, четвертий стовпець (в ньому є позитивні елементи!). Роздільна рядок визначиться щодо мінімального з відносин: 4/1 і 7/1. В даному випадку min (4/1; 7/1) = 4/1 і відповідає першому рядку, вона і буде роздільної.

таб.1

 
 0 = 0 = 0 = 4 7 1  1 1 1 0  1 2 1 0 12  1 0 1 1
Z =  3 1 0 0 0

таб.2

 
 = 0 = 0 = 1  1 1 0  1 2 1 13 0  1 + 1
Z =  3 1 0 0

таб.3

 
 = 0 = = 1  1 + 1  4 2 23 0 1
Z =  3 1 0

таб.4

 
= = = 1 2  2 11 1
Z =  3 1

Зробивши ще два кроки Жорданових винятків (таб.2  таб.3) приходимо до таб.4, в лівому стовпчику якої вже немає нулів: базис виділено. Йому відповідає початковий опорний план:  = (0; 0; 2; 2; 5). Знайдений нами опорний план неоптимальний, тому що в Z -строке присутній негативний елемент (  3). У відповідному йому стовпці є позитивні елементи, тому є можливість поліпшити план (таб.5).

таб.5

 
= = = 1  22 3  1 3
Z = 3 5

Однак і цей план неоптимальний, тому що в Z -строке присутній негативний елемент (  5). Зробивши ще один крок, отримуємо таб.6., В Z -строке якої немає негативних елементів.

таб.6

 
= = =  
f =  4/3 5/3

Значить, що міститься в таб.6 опорний план є оптимальним. Отже,  = (4; 1; 9; 0; 0), fmax= 16. Завдання вирішена.

зауваження: якщо ЗЛП задана в симетричної формі запису, то ввівши додаткові змінні, її можна привести до канонічної формі, і вирішувати за запропонованим алгоритмом.

Список літератури

1 Кузнецов, А. В. Керівництво вирішення задач з математичного програмування: навч. посібник / А. В. Кузнєцов, Н. І. Холод, Л. С. Костевич. - 2-е изд., Перераб і доп. - Мінськ: Виш. шк., 2001. - 448 с.

2 Унсовіч, А. Н. Короткий курс вищої математики для економістів / А. Н. Унсовіч - Барановичі: БНДП, 2000. - 531 с.

 



Й випадок. Система обмежень має кращий вигляд. | Значення коефіцієнтів у формулах (1) при ухилах річки

Денної та заочної форм навчання | Звичайні і модифіковані жорданову виключення | Рішення систем лінійних рівнянь | Базисні та опорні рішення системи лінійних рівнянь | Основна ідея і алгоритм симплексного методу |

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