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

Загальна лінійна економіко-математична модель економічних процесів та явищ – так звана загальна задача лінійного програмування подається у вигляді:

(3.1)

за умов:

(3.2)

(3.3)

Отже, потрібно знайти значення змінних x ₁, x ₂, …, x_n, які задовольняють умови (3.2) і (3.3), і цільова функція (3.1) набуває екстремального (максимального чи мінімального) значення.

Для довільної задачі математичного програмування у п.2.1 були введені поняття допустимого та оптимального планів.

Для загальної задачі лінійного програмування використовуються такі поняття.

Вектор Х = (х ₁, х ₂, …, х_n), координати якого задовольняють систему обмежень (3.2) та умови невід’ємності змінних (3.3), називається допустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х = (х ₁, х ₂, …, х_n) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (3.2) у вигляді рівностей, а також обмеження (3.3) щодо невід’ємності змінних.

Опорний план Х = (х ₁, х ₂, …, х_n), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

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

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

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

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

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

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

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

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

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

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

Перехід від загальної ЗЛП до стандартної

Задачу (3.1)—(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі b_i (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_i від’ємне, то, помноживши i -те обмеження на
(– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i -те обмеження має вигляд нерівності а_{i 1} х ₁+ а_{i 2} х ₂+…+ а_inx_n ≤ b_i, то останню завжди можна звести до рівності, увівши додатковузмінну x_{n +1}:

a_{i 1} x ₁+ a_{i 2} x ₂+…+ a_inx_n + x_{n + 1} = b_i.

Аналогічно обмеження виду а_{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n ≥ b_k зводять до рівності, віднімаючи від лівої частини додаткову змінну х_{n +2}, тобто:

a_{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n – x_{n + 2} = b_k (х_{n +1} ≥ 0, х_{n +2} ≥ 0).

АЛГОРИТМ СИМПЛЕКС МЕТОДУ

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

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

5. Повторення дій, починаючи з пункту (3).

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

1. Якщо в оцінковому рядку останньої симплекс таблиці =0 відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язувальний елемент у зазначеному стовпці таблиці та здійснивши 1 крок симплекс методу.

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

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

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: