Лекция 8 чисельне диференціювання та інтегрування. Основна задача лінійного програмування. Дослідження її окремих випадків. Модифікований варіант жордановых винятків
8.1. Постановка основної задачі лінійного програмування (озлп)
Основною задачею лінійного програмування - скорочено ОЗЛП - називається задача відшукання максимуму функції
при обмеженнях
.
Тут
- змінні (аргументи), а
,
- константи. Функцію
в цій ситуації називають цільовий.
8.2. Екстремальні задачі, що зводяться до озлп заміною змінних
Найпростіший випадок екстремальної задачі, що зводиться до ОЗЛП, виглядає точно так само, як задача з п.1, але тільки замість максимуму потрібно знайти мінімум. Очевидно, у цьому випадку досить у цільової функції поміняти знак, знайти, вирішуючи ОЗЛП, максимум цієї зміненої функції, а потім поміняти знак у знайденого максимуму - отримане число буде шуканим мінімумом.
Не менш простим є випадок екстремальної задачі, що виглядає так само, як ОЗЛП із п.1, але одне або кілька обмежень виглядають так:
для
деяких
.
У цьому випадку такі обмеження множаться
на -1 і, природно, знак «більше або
дорівнює» заміняється на знак «менше
або дорівнює».
Нарешті, третім випадком екстремальної задачі, що зводиться до ОЗЛП, є випадок, коли деякі обмеження виглядають як точні рівності:
при
деяких
.
У такій ситуації кожна така рівність
заміняється на парі нерівностей:
і
,
одночасне виконання яких і є заданою рівністю.
8.3. Лінійна заміна змінних і її використання в дослідженні основної
задачі лінійного програмування
Ідея
методу, яким традиційно вирішується
ОЗЛП, полягає в тому, щоб змінні
,
через які виражена вся вихідна інформація
в задачі, виразити через інші змінні
за допомогою спеціально підібраних
рівностей
так,
щоб у результаті формулювання ОЗЛП
стала дуже простій і відповідь виявилася
очевидним (використовувані тут символи
ніяк не пов'язані із символами з
формулювання ОЗЛП). Ми вже розглядали
в Лекції 1 один варіант роботи з рівностями
типу (8.3.1), які в математику називаються
лінійною
заміною змінних
- це жордановы
виключення;
у п.4 нижче розглядається ще один варіант
роботи з рівностями типу (8.3.1).
8.4. Модифікований варіант жордановых виключень як спосіб організації лінійної заміни змінних
З
Лекції 1 відомий дуже зручний спосіб
організації обчислень, які виробляються
при вираженні змінних
через змінні
на основі рівностей (8.3.1): він називається
жордановыми
виключеннями.
А зараз ми введемо ще один тип жордановых винятків, які називаються модифікованими жордановыми винятками. Розглянемо систему рівностей, аналогічну системі (8.3.1), але зі зміненими знаками:
(8.4.1)
.
Зашифруємо цю систему рівностей за допомогою таблиці:
|
- |
- |
... |
- |
... |
- |
|
|
|
... |
|
... |
|
|
|
|
... |
|
... |
|
... |
... |
... |
... |
... |
... |
... |
|
|
|
... |
|
... |
|
... |
... |
... |
... |
... |
... |
... |
|
|
|
... |
|
... |
|
Знову
припустимо, що
й виразимо з рівності
змінну
через змінні
:
.
Якщо тепер підставити (8.4.2) в усі рівності (8.4.1), крім i-го, а i-е рівність замінити на (8.4.2), то вийде нова система рівностей, у якій змінні й помінялися ролями. Запишемо відповідну таблицю:
|
- |
- |
... |
- |
... |
- |
|
|
|
... |
|
... |
|
|
|
|
... |
|
... |
|
... |
... |
... |
... |
... |
... |
... |
|
|
|
... |
|
... |
|
... |
... |
... |
... |
... |
... |
... |
|
|
|
... |
|
... |
|
і
виразимо коефіцієнти
через коефіцієнти
.
Описана
дія й називається модифікованим
жордановым виключенням з розв'язним
елементом
.
Ми надалі для цього виключення будемо
використовувати скорочений запис МЖИ,
а для простого виключення, описаного
раніш, - запис ПЖИ.