79.Запишіть загальну математичну модель задачі лінійного програмування. Які є форми запису задач лінійного програмування?

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

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

Або:

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

на деякі невідомі можуть бути накладені умови невід'ємності:

Даний запис означає наступне: знайти екстремум цільової функції (1) і відповідні йому змінні X = (X1, X2, ..., Xn) за умови, що ці змінні задовольняють системі обмежень (2) та умовам невід'ємності (3).

Допустимим рішенням (планом) задачі лінійного програмування називається будь-який n-мірний вектор X = (X1, X2, ..., Xn), що задовольняє системі обмежень і умов невід'ємності.

Безліч допустимих рішень (планів) завдання утворює область допустимих рішень (ОДР).

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

Канонічна форма задачі лінійного програмування.

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

Канонічна задача лінійного програмування в координатному записі має вигляд:

Або:

на деякі невідомі можуть бути накладені умови невід'ємності:

Канонічна задача лінійного програмування в матричному записі має вигляд:

тут:

А - матриця коефіцієнтів системи рівнянь

Х - матриця-стовпець змінних задачі

Ао - матриця-стовпець правих частин системи обмежень.

Симетрична форма записи завдання лінійного програмування. Тут прийнято виділяти дві стандартні завдання - задачу максимізації і задачу мінімізації.

Стандартна задача максимізації: необхідно знайти максимальне значення цільової функції (4.1) при обмеженнях

і умовах невід'ємності

Стандартна задача мінімізації: необхідно знайти мінімальне значення цільової функції (4.1) при обмеженнях

і умовах невід'ємності

80.Сформулюйте основні аналітичні властивості розв’язання задачі лінійного програмування.

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

Властивість 1. (Теорема 3.1) Множина всіх планів задачі лінійного програмування опукла.

Властивість 2. (Теорема 3.2) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’яз­ків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 3.3) Якщо відомо, що система векторів A₁, A₂, …, A_k (k≤n) у розкладі A₁x₁ +A₂x₂ + … + A_nx_n = A₀, X≥0 лінійно незалежна і така, що

A₁x₁ + A₂x₂ + … + A_kx_k = A₀,

де всі x_j ≥ 0, то точка X = (x₁, x₂, …, x_k, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 3.4) Якщо X = (x₁, x₂, …, x_n) – кутова точка багатогранника розв’язків, то вектори в розкладі A₁x₁ + + A₂x₂ + … + A_nx_n = A₀, X ≥ 0, що відповідають додатним x_j, є лінійно незалежними.

Наслідок 1. Оскільки вектори мають розмірністьm, то кутова точка багатокутника розв’язків має не більше, ніж m додатних компонентів .

Наслідок 2. Кожній кутовій точці багатокутника розв’язків відповідає лінійно незалежних векторів системи.

З наведених властивостей можна зробити висновок, що якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:

1. існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;

2. кожний опорний план відповідає кутовій точці багатогранника розв’язків.

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

14