§ 1.4. Основні властивості злп. Симплексні перетворення

У § 1.2 зазначалося, що ЗЗЛП можна звести до СЗЛП і за розв’язком останньої легко побудувати розв’язок початкової задачі. Зрозуміло, що і загальні властивості ЗЗЛП аналогічні загальним властивостям відповідної СЗЛП. Тому в цьому параграфі ми будемо говорити про властивості СЗЛП.

, (1.4.1)

, (1.4.2)

. (1.4.3)

Ці властивості будуть сформулюємо у вигляді тверджень. Не всі твердження будуть формально обґрунтовуватись. Відповідні доведення поміщені в багатьох підручниках, зокрема [2], [11].

У попередньому параграфі уже стверджувалось, що множина допустимих планів є опуклою. Легко переконатисяу правильності такого твердження:

Твердження 1.4.1. Множина оптимальних планів задачі (1.4.1) – (1.4.3) опукла.

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

,

, ,

, .

Нехай і . Тоді згідно із властивостями скалярного добутку

.

.

.

Отже, план є допустимим і оптимальним. Твердження доведено.

Сформулюємо без доведення.

Твердження 1.4.2. Точка є вершиною многогранної множини допустимих точок задачі (1.4.1) – (1.4.3) тоді і тільки тоді, коли вектор є базисним планом цієї задачі.

Оскільки кількість обмежень (1.4.2) і (1.4.3) скінчена, то кількість вершин множини допустимих точок, а отже, кількість базисних (опорних) планів задачі (1.4.1) –(1.4.3) скінченна.

Міркування про досяжність оптимального значення цільової функції в кутовій точці допустимої множини і Твердження 1.4.2 дають можливість формулювати

Твердження 1.4.3. Якщо існують базисні плани задачі (1.4.1) – (1.4.3) і цільова функція задачі обмежена знизу, то вона досягає мінімального значення хоча б на одному базисному плані.

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

Визначення всіх базисних планів задачі – дуже громіздка задача. Кількість таких планів може бути дуже великою. Тому “сліпий” перебір базисних планів неефективний. Запропонований Данцігом (Dantzig Gb.) так званий симплексний метод розв’язування є, по суті, впорядкованим методом перебору цих планів. Він передбачає знаходження одного базисного плану, тестування його на оптимальність і, у випадку його не оптимальності, переходу за певними правилами до нового базисного плану, на якому цільова функція досягає меншого значення. У зв’язку зі скінченною кількістю базисних (опорних) планів задачі процес визначення оптимального плану буде скінченним. При цьому не всі базисні плани аналізуються.

Зі сказаного вище випливає, що основними процедурами симплексного методу є:

• одноразова процедура визначення так званого початкового базисного плану;

• процедура тестування базисного плану на оптимальність;

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

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

Помноживши (1.4.3) на обернену матрицю до відповідної базисної матриці, отримуємо канонічну форму задачі (1.4.1) – (1.4.3)

, (1.4.4)

(1.4.5)

, ; (1.4.6)

, . (1.4.7)

Базисний (опорний) план, згідно із (1.4.5) – (1.4.7), має вигляд .

Якщо використати відому процедуру Жордана-Гаусса зведення системи лінійних рівнянь до діагональної форми, то систему (1.4.5) можна записати в іншому рівносильному вигляді.

Наприклад, якщо , то з усіх рівнянь, крім другого, можна виключити . Для цього друге рівняння ділимо на і результат записуємо замість другого рівняння. Отримане друге рівняння множимо на і віднімаємо від рівняння з номером . Результатом віднімання замінюємо рівняння за номером в системі (1.4.5).

Замість системи (1.4.5) ми отримали еквівалентну їй систему

(1.4.8)

Якщо були б невід’ємними, то (1.4.8) відповідала б новій КЗЛП з базисними змінними і небазисними змінними .

Зрозуміло, що

, , ,

, , ,

, .

Взагалі, якщо , (), то з множини базисних змінних можна вивести та ввести в множину базисних змінну . Відповідні формули мають вигляд

(1.4.9)

(1.4.10)

Якщо при всіх виявиться , то отримуємо новий базисний (опорний) план задачі

.

На базисному плані цільова функція має значення

,

а на базисному плані , з урахуванням того, що можна представити у вигляді

,

набуває значення

.

Числа , , називаються відносними оцінками змінних відповідно.

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

Позначимо . Маємо

. (1.4.11)

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

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

Якщо розглядати лише невироджені базисні плани, то і відповідно .

Тому найчастіше для спрощення розрахунків спочатку вибирають номер (змінну , яку треба ввести в множину базисних змінних) так, що і

. (1.4.12)

Якщо номер уже вибрано, залишається вибрати (визначити змінну ) так, щоб план був допустимим, тобто щоб

або

, якщо ,

(для умови виконуються автоматично).

Отже, номер вибирають так, щоб

. (1.4.13)

Елемент матриці називають провідним елементом перетворення.

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

Із (1.4.11) випливає, що, коли всі , значення цільової функції зменшити не вдається. Неважко також показати, що у випадку існування і виконання умов для всіх , цільова функція необмежена знизу і в цьому розумінні розв’язку задачі (1.4.1) – (1.4.3) не існує.

Наведені міркування дозволяють сформулювати ще кілька тверджень.

Твердження 1.4.4. (умови оптимальності). Якщо для деякого базисного плану КЗЛП (1.4.4) – (1.4.7) справедливі нерівності для всіх , то – розв’язок цієї задачі (оптимальний план).

Твердження 1.4.5. (умова необмеженості знизу цільової функції). Якщо для деякого базисного плану задачі (1.4.4) – (1.4.7) існує оцінка , а всі , то цільова функція задачі необмежена знизу ().

Викладені вище властивості і робочі формули (1.4.9), (1.4.10) дають можливість побудувати обчислювальну схему так званого симплексного методу розв’язання ЗЛП.

Етапи поліпшення базисного плану КЗЛП проілюструємо наступним прикладом.

,

, , , , .

Тут

,

,

.

Базисні змінні та , небазисні – , , . Початковим базисним планом є .

.

Підрахуємо .

, ,

, .

Визначимо номер небазисної змінної, яку треба ввести в множину базисних з умови

.

Отже, і треба ввести в множину базисних змінних.

Визначимо номер базисної змінної, яку треба вивести із множини базисних змінних з умови

,

що відповідає другому рядку, в якому знаходиться базисна змінна . Отже, з множини базисних змінних треба вивести і . Згідно із формулами (1.4.9), (1.4.10),

, , , , ,

, , , , ,

, що відповідає базисній змінній ,

, що відповідає базисній змінній .

Новий базисний план задачі

і

.

Задачу можна записати в новій канонічній формі

,

, , , , .

Зауважимо, що цільова функція задачі зменшилась, як і вказувалось формулою (1.4.11), на

.