На головну

Загальна задача лінійного програмування

  1. CLIPS як багатофункціональне середовище програмування (інженерії знань)
  2. I. Загальна характеристика міжнародних відносин в Новий час.
  3. I.5.3) Складові частини Зводу Юстиніана (загальна характеристика).
  4. II.7.1. Загальна характеристика уваги
  5. III. 12.1. Загальна характеристика мислення
  6. Quot; Аналітична професіограма "та загальна схема профвідбору
  7. V. 16.1. Загальна характеристика темпераменту

Розглянуті вище приклади завдань лінійного програмування дозволяють сформулювати загальну задачу лінійного програмування.

Дана система m лінійних рівнянь і нерівностей з n змінними

 (1.20)

 . (1.22)

і лінійна функція  . (1.21)

Необхідно знайти таке рішення Х= (х1, х2, ..., xj, ..., Xn), При якому лінійна функція (1.21) приймає оптимальне (тобто максимальне або мінімальне) значення.

Система (1.20) називається системою обмежень, а функція F - лінійною функцією, лінійної формою, цільовою функцією або функцією мети.

Більш коротко загальну задачу лінійного програмування можна представити у вигляді:

при обмеженнях

.

Оптимальним рішенням (або оптимальним планом) задачі лінійного програмування називається рішення Х= (х1, х2, ... , xn) Системи обмежень (1.20), що задовольняє умові (1.22), при якому лінійна функція (1.21) приймає оптимальне (максимальне або мінімальне) значення.

Терміни "рішення" та "план" - синоніми, проте перший частіше використовується, коли мова йде про формальну сторону завдання (її математичному рішенні), а другий - про змістовний бік (економічної інтерпретації).

За умови, що всі змінні невід'ємні  система обмежень (1.20) складається лише з одних нерівностей, таке завдання лінійного програмування називається стандартної, Якщо система обмежень складається з одних рівнянь, то завдання називається канонічної (В ряді робіт з математичного програмування стандартне завдання називають симетричною, а канонічну завдання - основний). Так, в наведених вище прикладах задач лінійного програмування завдання 1 і 2 - стандартні, завдання 4 - канонічна, а завдання 3 - загальна.

Будь-яке завдання лінійного програмування може бути зведена до канонічної, стандартної або загальної задачі. Розглянемо спочатку допоміжну теорему.

Теорема 1.1. Всякому рішенням (a1, a2, ... , an) нерівності  (1.23) відповідає певне рішення (a1, a2, ... , an; аn+1) рівняння  (1.24) в якому  (1.25) і навпаки, кожному рішенню (a1, a2, ... , an; аn+1) Рівняння (1.24) і нерівності (1.25) відповідає певне рішення (a1, a2, ... , an) Нерівності (1.23).

Використовуючи цю теорему, уявімо, як приклад, стандартне завдання (1.4) - (1.6), в канонічному вигляді. З цією метою в кожне з m нерівностей системи обмежень (1.4) введемо додаткові невід'ємні змінні  і система обмежень (1.4) набуде вигляду:

 (1.26)

Таким чином, стандартна задача (1.4) - (1.6) в канонічної формі набуде вигляду: знайти таке рішення Х= (х1, х2, ... , xn), Яке задовольняє системі (1.26) і умові (1.5), при якому функція (1.6) приймає максимальне значення.

Зауваження. У розглянутій задачі все нерівності виду "  ", Тому додаткові невід'ємні змінні вводилися зі знаком" + ". У разі нерівностей виду"  "Відповідні додаткові змінні варто було б ввести зі знаком" - ".

 



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

ЗАГАЛЬНА ПОСТАНОВКА ЗАВДАННЯ лінійного програмування | Економіко-математична модель | ГЛАВА 4. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗАВДАНЬ лінійного програмування | Геометрична інтерпретація симплексного методу | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці |

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