Приклад 1. За початковий базис можна вибрати Р1, Р4, Р5 або Р2, Р4, Р5, тоді початковий опорний план Х=(0,0,0,1,1) є

За початковий базис можна вибрати Р₁, Р₄, Р₅ або Р₂, Р₄, Р₅, тоді початковий опорний план Х=(0,0,0,1,1) є виродженим, так як базисна змінна х₁=0 або х₂=0. Для обох початкових планів z=0, тобто у випадку виродженності значення цільової функції може повторюватись навідь при зміні базису.

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

для декількохзначень k, де s – номер вектора, який вводять до базису. У цьому випадку також при зміні складу базисних змінних значення цільової функції буде залишатись незмінним.

Оскільки число наборів векторів скінченне, то після деякого числа ітерацій дійдемо до одного з висновків:

1. розв’язок оптимальний;

2. задача не розв’язувана;

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

Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язування

Лекція 6

Тема лекції: Розв’язання задач ЛП симплекс-методом (продовження)

Мета: ознайомити студентів з методами розв’язання задач ЛП симплекс – методов із стандартним базисом, симплекс-методом зі штучним базисом.

План лекції

4. Правило уникнення зациклювання при застосуванні симплекс-методу.

5. Метод штучної базиси розв’язування задач ЛП.

6. Приклад вирішення задачі ЛП методом штучної бази.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

4. Правило уникнення зациклювання при застосуванні симплекс-методу.

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

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

Приклад 2. Вирішити задачу ЛП

за умов

5. Метод штучної базиси розв’язування задач ЛП.

Застосовується у тих випадках, коли в вихідній задачі ЛП, яка записана у канонічному вигляді, в системі обмежень немає необхідної кількості одиничних ортогональних незалежних векторів P_j, тобто важко вказати початковий опорний план.

М-метод полягає у використанні правил симплекс – методу до так званої задачі ЛП. Вона отримується із початкової додованням до лівої частини системи рівнянь таких штучних одиничних векторів з відповідними невід’ємними штучними змінними, щоб знову отримати m одиничних ортогональних лінійно незалежних векторів.

У цільовій функції задачі ЛП штучні змінні мають коефіцієнт - М (f(x)→max) або +М (f(x)→min), де під М ми розуміємо досить велике додатне число.

При розв’язанні цієї задачі симплекс-методом оцінки Δ_j будуть залежити від М. Для порівняння оцінок, треба пам’ятати, що М – достатньо велике додатне число, тому із базису будуть виключатися у першу чергу штучні вектори.

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

Якщо оптимальний розв’язок М – задачі містить штучні змінні або М – задача нерозв’язна, то початкова задача також нерозв’язна.

6. Приклад вирішення задачі ЛП методом штучної бази.

Інвестиційна компанія має на своєму рахунку 5 млн. грн. Розглядаються чотири види інвестицій – державні цінні папери, цінні папери корпорацій, акції сфери обслуговуння та акції виробничої сфери. Державні цінні папери належать до без ризикових, решта інвестицій – до ризикових. Метою інвестиційної компенії є максимізація прибутку. Прибуток від інвестицій становить відповідно – 5%, 8%, 10% та 12%. Гроші які не інвестуються, залишаються на банківському рахунку і дають прибуток 1%. Менеджер з інвестицій ухвалив рішення, що не менше ніж 2 млн. грн. слід розмістити у цінні папери корпорацій, а в інвестиційні проект из елементами ризику потрібно вкласти не більше ніж 4 млн. грн.

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

Питання для самоконтролю.

· В чому полягає симплекс-метод із стандартним базисом?

· Поясніть основну ідею симплекс-методу.

· Як визначити початковий опорний план задачі ЛП?

· Дайте економічну інтерпретацію критерію оптимальності опорного плану та правила переходу до нового базису.

· Як визначається вектор для введення у базис, якщо опорний план неоптимальний?

· Як визначається вектор, що виводиться із базису?

· Сформулюйте ознаку нерозв’язності задачі ЛП у симплекс-методі.

· Коли використовують симплекс-метод зі штучним базисом?

· Принципи заповнення симплекс-таблиці.

· Що таке розв’язувальний елемент симплекс-таблиці?

· Як перевірити опорний план на оптимальність?

· Поясніть метод Жордана-Гауса.

· Що таке штучні змінні?