Лінійні моделі для ухвалення бізнес-рішень. Моделі лінійного програмування у розв'язках задач керування транспортними процесами Загальний вигляд моделі лінійного програмування

Лекція 2

В канонічної форми

допустимим рішенням ЗЛП(допустимим планом).

оптимальним рішенням ЗЛП.

Необхідність

Приклад.

Запишемо завдання в канонічної форми

Особливі ситуації графічного рішення ЗЛП

Крім випадку, коли завдання має єдине оптимальне рішеннядля і , можуть бути особливі ситуації:

1. завдання має безліч оптимальних рішень - Екстремум функції досягається на відрізку ( альтернативний оптимум)- Рисунок 2;

2. завдання не можна розв'язати через необмеженість ОДР, або – рисунок 3;

3. ОДР - єдина точка А, тоді;

4. завдання не можна розв'язати якщо ОДР є порожня область.

А

Малюнок 2 Малюнок 3

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

де параметр. За будь-якого значення від 0 до 1можна отримати всі точки відрізка , для кожної з яких функція набуває однакового значення. Звідси назва – альтернативний оптимум.

Приклад. Розв'язати графічно завдання лінійного програмування ( альтернативний оптимум):

Запитання для самоконтролю

1. Запишіть задачу лінійного програмування у загальній формі.

2. Запишіть завдання лінійного програмування у канонічній та стандартній формах.

3. За допомогою яких перетворень можна перейти від загальної чи стандартної форми задачі лінійного програмування до канонічної?

4. Дайте визначення допустимого та оптимального розв'язання задачі лінійного програмування.

5. Яке з рішень і є «кращим» для завдання мінімізації функції, якщо ?

6. Яке з рішень і є «кращим» для завдання максимізації функції, якщо ?

7. Запишіть стандартну форму математичної моделі задачі лінійного програмування із двома змінними.

8. Як побудувати напівплощину, задану лінійною нерівністю з двома змінними ?

9. Що називається розв'язанням системи лінійних нерівностей із двома змінними? Побудуйте на площині область допустимих розв'язків такої системи лінійних нерівностей, яка:

1) має єдине рішення;

2) має безліч рішень;

3) немає жодного рішення.

10. Запишіть для лінійної функції градієнт вектор, назвіть вигляд ліній рівня. Як розташовані відносно один одного градієнт та лінії рівня?

11. Сформулюйте алгоритм графічного методу розв'язання стандартної ЗЛП із двома змінними.

12. Як знайти координати рішення та значення ?

13. Побудуйте область допустимих рішень, градієнт та лінії рівня для завдань лінійного програмування, в яких:

1) досягається в єдиній точці, а - на відрізку ОДР;

2) досягається в єдиній точці ОДР, а .

14. Дайте геометричну ілюстрацію ЗЛП, якщо вона:

1) має єдині оптимальні рішення для і;

2) має безліч оптимальних рішень для .

Лекція 2

графічний метод знаходження оптимального рішення

1. Форми лінійних математичних моделей та їх перетворення

2. Графічний метод вирішення задачі лінійного програмування

3. Особливі ситуації графічного рішення ЗЛП

4. Графічне вирішення економічних завдань лінійного програмування

Форми лінійних математичних моделей та їх перетворення

Математична модель задачі лінійного програмування (ЗЛП) може бути записана однією з трьох форм.

В загальної форми математичної моделіпотрібно знайти максимум або мінімум цільової функції; система обмежень містить нерівності та рівняння; в повному обсязі змінні може бути неотрицательными.

В канонічної формиматематичної моделі потрібно знайти максимум цільової функції; система обмежень складається лише з рівнянь; всі змінні невід'ємні.

У стандартній формі математичної моделі потрібно знайти максимум або мінімум функції; всі обмеження є нерівністю; всі змінні невід'ємні.

Рішення системи обмежень, що задовольняє умовам невід'ємності змінних, називають допустимим рішенням ЗЛП(допустимим планом).

Багато допустимих рішень називають областю допустимих рішень ЗЛП.

Допустиме рішення , при якому цільова функція досягає екстремального значення, називають оптимальним рішенням ЗЛП.

Три форми запису ЗЛП еквівалентні тому, кожна з них з допомогою математичних перетворень може бути зведена до інший формі.

Необхідність переходу від однієї форми математичної моделі до іншоїпов'язана з методами вирішення завдань: наприклад, симплексний метод, що широко використовується в лінійному програмуванні, застосовується до завдання, записаного в канонічній формі, а графічний метод – до стандартної форми математичної моделі.

Перехід до канонічної форми запису ЗЛП.

Приклад.

Запишемо завдання в канонічної форми, Вводячи в ліву частину першої нерівності системи обмежень додаткову (балансову) змінну зі знаком «+», а в ліву частину другої нерівності додаткову змінну зі знаком «мінус».

Економічний сенс різних додаткових змінних може бути не однаковий: він залежить від економічного сенсу обмежень, до яких ці змінні входять.

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

Т10. Постановка задачі лінійного програмування

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

Для складання математичної моделі необхідно:

1. вибрати змінні завдання;

2. скласти систему обмежень;

3. поставити цільову функцію.

Змінними завданняназиваються величини х 1 , х 2, ..., х n, які повністю характеризують економічний процес. Їх зазвичай записують як вектора Х = (х 1 , х 2 ,…, х n).

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

Цільовий функцією називаєтьсяфункція F(X) = f(х 1 , х 2 ,…, х n) змінних задачі, що характеризує якість виконання завдання та екстремум якої потрібно знайти.

Загальне завдання математичного програмуванняформулюється наступним чином: знайти змінні завдання х 1, х 2, ..., х n, які забезпечують екстремум цільової функції

F(X) = f(х 1 , х 2 ,…, х n) ® max (min) (2)

та задовольняють системі обмежень (1).

Якщо цільова функція (2) та система обмежень (1) лінійні, то завдання математичного програмування називається завданням лінійного програмування (ЗЛП).

Вектор Х (набір змінних задач) називається допустимим рішенням, або планом ЗЛП, якщо він відповідає системі обмежень (1). Допустимий план Х, який забезпечує екстремум цільової функції, називається оптимальним рішеннямЗЛП.

2. Приклади складання математичних моделей економічних завдань

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

1.Завдання про оптимальний виробничий план

Для виробництва двох типів виробів Т1 і Т2 використовуються три види ресурсів S1, S2, S3. Запаси ресурсів, кількість одиниць ресурсів, що витрачаються на виготовлення одиниці продукції, а також прибуток від одиниці продукції наведені в таблиці:

Потрібно знайти такий план виробництва, у якому прибуток від її реалізації буде максимальною.

Рішення.

Позначимо х 1 , х 2 – число одиниць продукції відповідно до Т 1 і Т 2 , запланованих до виробництва. Для їх виготовлення потрібно (х 1 + х 2) одиниць ресурсу S 1, (х 1 + 4х 2) одиниць ресурсу S 2, (х 1) одиниць ресурсу S 3 . Споживання ресурсів S 1 , S 2 , S 3 не повинно перевищувати їх запасів відповідно 8, 20 і 5 одиниць.

Тоді економіко-математичну модель завдання можна сформулювати так:

Знайти план випуску продукції Х = (х 1, х 2), що задовольняє системі обмежень:

та умовою ,

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

Завдання можна легко узагальнити у разі випуску n типів продукції з використанням m видів ресурсів.

2.Завдання про оптимальний раціон

Є два види корму К1 і К2, що містять поживні речовини S1, S2 і S3. Зміст кількості одиниць поживних речовин в 1 кг кожного виду корму, необхідний мінімум поживних речовин, а також вартість 1 кг корму наведено в таблиці:

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

Рішення.

Позначимо х 1 , х 2 – кількість кормів До 1 і До 2 , які входять у денний раціон. Тоді цей раціон включатиме (3х 1 + х 2) одиниць поживної речовини S 1 , (х 1 +2х 2) одиниць речовини S 2 , (х 1 +6х 2) одиниць поживної речовини S 3 . Оскільки вміст поживних речовин S 1 , S 2 і S 3 у раціоні має бути відповідно 9, 8 та 12 одиниць, то економіко-математичну модель завдання можна сформулювати так:

Скласти денний раціон Х = (х 1 , х 2), що задовольняє системі обмежень:

та умовою ,

при якому функція приймає мінімальне значення.

Форми запису ЗЛП

У ЗЛП потрібно знайти екстремум лінійної цільової функції:

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

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

де а ij, b i, c j (,,) - Задані постійні величини.

Так записується ЗЛП у спільноїформі. Якщо система обмежень містить лише нерівності, то ЗЛП представлена ​​в стандартноюформі. Канонічної (основний)Формою запису ЗЛП називається запис, коли система обмежень містить лише рівність. Отже, наведені вище ЗЛП записані у стандартній формі.

Загальна, стандартна і канонічна форми ЗЛП еквівалентні тому, кожна з них з допомогою нескладних перетворень може бути переписана у інший формі. Це означає, що й є спосіб вирішення однієї із зазначених завдань, може бути визначено оптимальний план будь-який із завдань.

Щоб перейти від однієї форми запису ЗЛП до іншої треба вміти переходити від обмежень-нерівностей до обмежень-рівностей і навпаки.

Обмеження – нерівність (£) можна перетворити до обмеження-рівності додаванням до його лівої частини додаткової невід'ємної змінної, а обмеження-нерівність (³) – в обмеження рівності відніманням з його лівої частини додаткової невід'ємної змінної. Кількість додаткових неотрицательных змінних, що вводяться, дорівнює числу перетворюваних обмежень-нерівностей.

Введені додаткові змінні мають певний економічний сенс. Так, якщо в обмеженнях вихідної ЗЛП відображаються витрати і наявність ресурсів, то значення додаткової змінної ЗЛП у канонічній формі дорівнює обсягу відповідного ресурсу, що не використовується.

Приклад 1. Записати в канонічній формі ЗЛП:

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

Рішення.

Цільова функція залишається без змін:

Система нерівностей перетворюється на систему рівностей:

При вирішенні ЗЛП графічним методом потрібен перехід від канонічної форми до стандартної форми.

Для приведення ЗЛП до стандартної форми використовується метод Жордана – Гаусарішення СЛАУ. На відміну від методу Гауса, у якому розширена матриця системи наводиться до ступінчастого вигляду, метод Жордана – Гауса у складі розширеної матриці формується одинична матриця. Тому зворотний хід тут не потрібний.

Для перетворення вихідної канонічної ЗЛП на еквівалентну стандартну ЗЛП:

а) у розширеній матриці системи обмежень вибирається відмінний від нуля елемент aqp. Цей елемент називається дозвільним, а q - я рядок і р-й стовпець називаються роздільною здатністю і стовпцем.

б) рядок, що дозволяє, переписується без зміни, а всі елементи роздільного стовпця, крім роздільного, замінюються нулями. Інші елементи розширеної матриці визначаються за допомогою «правила прямокутника»:

Розглянемо чотири елементи розширеної матриці: елемент а ij , що підлягає перетворенню, що дозволяє елемент a qp і елементи а i р та a qj . Для знаходження елемента а ij слід від елемента а ij відняти добуток елементів а i р і a qj , розташованих у протилежних вершинах прямокутника, поділений на роздільну здатність елемент a qp:

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

Приклад 2. Привести до стандартного вигляду:

Рішення.

Методом Жордана – Гауса наведемо систему рівнянь-обмежень ЗЛП до рівносильної системи нерівностей. Виберемо в якості роздільної здатності елемент третій елемент першого рядка:

Число -9, отримане в останньому стовпці останнього рядка, необхідно записати на цільову функцію з протилежним знаком. В результаті перетворень ЗЛП набуває вигляду:

Т.к. змінні х 2 і х 3 невід'ємні, то відкинувши їх, можна записати ЗЛП у симетричному вигляді:

У канонічній формі ЗЛП цільова функція може мінімізуватися, так і максимізуватися. Щоб перейти від знаходження максимуму до знаходження мінімуму чи навпаки, Досить змінити знаки коефіцієнтів цільової функції: F 1 = - F. Отримана в результаті цього завдання і вихідна ЗЛП мають одне і те ж оптимальне рішення, а значення цільових функцій на цьому рішенні відрізняються лише знаком.

Властивості ЗЛП

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

Безліч точок називається опуклимякщо воно містить весь відрізок, що з'єднує дві будь-які точки цієї множини.

Відповідно до цього визначення багатокутник на рис.1 є опуклим безліччю, а багатокутник на рис.1б таким не є, т.к. відрізок MN між двома його точками M та N не повністю належить цьому багатокутнику.

Випуклими множинами можуть бути не тільки багатокутники. Прикладами опуклих множин є коло, сектор, відрізок, куб, піраміда тощо.

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

Крапка Х називається опуклою лінійною комбінацієюточок Х 1 , Х 2 , ..., Х n якщо виконуються умови:

Х = α 1 Х 1 +α 2 Х 2 +…+ α n Х n ,

j ≥ 0, j j = 1.

Очевидно, що в окремому випадку при n = 2 опуклою лінійною комбінацією двох точок є з'єднувальний їх відрізок.

3. Кожному допустимому базисному рішенню системи обмежень канонічної ЗЛП відповідає кутова точка багатогранника рішень, і навпаки, кожній кутовій точці багатогранника рішень відповідає допустиме базисне рішення.

З двох останніх властивостей випливає: якщо ЗЛП має оптимальне рішення, воно збігається, по крайнього заходу, з однією з її допустимих базисних рішень.

Таким чином, екстремум лінійної функції ЗЛП слід шукати серед кінцевого числа її допустимих базисних рішень.

Основою вирішення економічних завдань є математичні моделі.

Математичною моделлюЗавдання називається сукупність математичних співвідношень, що описують суть задачі.

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

Змінними завданняназиваються величини Х1, Х2, Хn, що повністю характеризують економічний процес. Зазвичай їх записують як вектора: X=(X 1 , X 2 ,...,X n).

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

Цільовою функцієюЗавдання називають функцію змінних задач, яка характеризує якість виконання завдання та екстремум якої потрібно знайти.

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

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

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

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

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

Приклад складання математичної моделі

Завдання використання ресурсів (сировини)

Умова:Для виготовлення n видів продукції використовується m видів ресурсів. Скласти математичну модель.

Відомі:

• b i (i = 1,2,3,..., m) - запаси кожного i-го виду ресурсу;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - витрати кожного i-го виду ресурсу на виробництво одиниці обсягу j-го виду продукції;
• c j (j = 1,2,3,..., n) - прибуток від одиниці обсягу j-го виду продукції.

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

Рішення:

Введемо вектор змінних X = (X 1, X 2, ..., X n), де x j (j = 1,2, ..., n) - Обсяг виробництва j-го виду продукції.

Витрати i-го виду ресурсу виготовлення даного обсягу x j продукції рівні a ij x j , тому обмеження використання ресурсів виробництва всіх видів продукції має вид:
Прибуток від j-го виду продукції дорівнює c j x j , тому цільова функція дорівнює:

Відповідь- Математична модель має вигляд:

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

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

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

Вона може бути представлена ​​в координатному, векторному та матричному записі.

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

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

• А - матриця коефіцієнтів системи рівнянь
• Х - матриця-стовпець змінних завдання
• Ао - матриця-стовпець правих частин системи обмежень

Нерідко використовуються задачі лінійного програмування, які називаються симетричними, які в матричному записі мають вигляд:

Приведення загального завдання лінійного програмування до канонічної форми

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

Візьмемо лінійну нерівність a 1 x 1 +a 2 x 2 +...+anxn ≤b і додамо до її лівої частини деяку величину x n+1 , таку, що нерівність перетворилася на рівність a 1 x 1 +a 2 x 2 + ...+anxn +x n+1 =b. У цьому дана величина x n+1 є неотрицательной.

Розглянемо все на прикладі.

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

Рішення:
Перейдемо до завдання знайти максимуму цільової функції.
Для цього змінимо знаки коефіцієнтів цільової функції.
Для перетворення другої та третьої нерівностей системи обмежень у рівняння введемо невід'ємні додаткові змінні x 4 x 5 (на математичній моделі ця операція відзначена буквою Д).
Змінна х 4 вводиться в ліву частину другої нерівності зі знаком "+", оскільки нерівність має вигляд "≤".
Змінна x 5 вводиться в ліву частину третьої нерівності зі знаком "-", оскільки нерівність має вигляд "≥".
У цільову функцію змінні х 4 х 5 вводяться з коефіцієнтом. рівним нулю.
Записуємо завдання у канонічному вигляді.

МОДЕЛЬ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1 Математичне опис моделі лінійного програмування

2 Методи реалізації моделей лінійного програмування

3 Подвійне завдання лінійного програмування

Модель лінійного програмування(ЛП) має місце, якщо в досліджуваній системі (об'єкті) обмеження на змінні та цільова функція лінійні.

Моделі ЛП використовуються для вирішення двох основних типів прикладних задач:

1) оптимального планування у будь-яких сферах людської діяльності – соціальної, економічної, науково-технічної та військової. Наприклад, при оптимальному плануванні виробництва: розподілі фінансових, трудових та інших ресурсів, постачання сировини, управління запасами і т.д.

2) транспортної задачі (знаходження оптимального плану різноманітних перевезень, оптимального плану розподілу різних засобів по об'єктах різного призначення тощо)

МАТЕМАТИЧНИЙ ОПИС МОДЕЛІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Потрібно знайти невід'ємні значення змінних

що задовольняють лінійним обмеженням у вигляді рівностей та нерівностей

,

де - Задані числа,

та забезпечують екстремум лінійної цільової функції

,

де – задані числа, що записується як

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

Область допустимих рішень- Багато всіх допустимих рішень.

Оптимальне рішення
, для якого .

Зауваження

1. Наведена модель ЛП є спільної. Розрізняють також стандартніі канонічніформи моделей ЛП.

2. Умови існуванняреалізації моделі ЛП:

– безліч допустимих рішень – не пусте;

- цільова функція обмежена на (хоча б зверху при пошуку максимуму та знизу при пошуку мінімуму).

3.ЛП ґрунтується на двох теоремах

Теорема 1. Безліч G, Яке визначається системою обмежень виду, є опукле замкнуте безліч ( опуклий багатогранникз кутовими точками - вершинами.)

Теорема 2. Лінійна форма , визначена на опуклому багатограннику

j=1,2,…,s

i=s+1,s+2,…, m,

досягає екстремуму в одній із вершин цього багатогранника.

Ця теорема отримала назву теореми про екстремум лінійної форми.

Відповідно до теорії Вейерштрасса оптимальне рішення єдине і є глобальним екстремумом.

Існує загальний аналітичний підхіддля реалізації моделі ЛП – симплекс-метод. При розв'язанні задач лінійного програмування досить часто вирішення немає. Це відбувається з таких причин.

Першу причину проілюструємо прикладом

Про таку причину кажуть, що обмеження є несумісними. Область допустимих рішень – пусте безліч.

Друга причина коментується наступним прикладом:

В даному випадку область допустимих рішень не обмежена зверху. Область допустимих рішень обмежена.

Наслідуючи традиції лінійного програмування, дамо задачі ЛП економічну інтерпретацію. Нехай у нашому розпорядженні є mтипів ресурсів Кількість ресурсу типу jі . Ці ресурси необхідні для виробництва nтипів товарів. Позначимо кількість цих товарів символами відповідно. Одиниця товару типу iстоїть. Виробництво товарів типу iмає бути обмежено величинами відповідно. Виробництво одиниці товару типу iвитрачається ресурсу типу j. Необхідно визначити такий план виробництва товарів ( ), щоб їхня сумарна вартість була мінімальною.

Завдання лінійного програмування, що використовуються для оптимізації функціонування реальних об'єктів, містять значну кількість змінних та обмежень. Це зумовлює неможливість вирішення їх графічними методами. При великому числі змінних та обмежень застосовуються методи алгебри, в основі яких лежать ітераційні обчислювальні процедури. У лінійному програмуванні розроблено безліч алгебраїчних методів, що різняться між собою способами побудови початкового допустимого рішення та умовами переходу від однієї ітерації до іншої. Однак ці методи базуються на загальних теоретичних положеннях.

Спільність основних теоретичних положень призводить до того, що методи алгебри вирішення завдань лінійного програмування багато в чому подібні між собою. Зокрема, практично будь-який вимагає попереднього приведення завдання лінійного програмування до стандартної (канонічної) формі.

Алгебраїчні методи вирішення задачі ЛП починаються з приведення її до стандартній (канонічній) формі:

,

,

i=1,..,n;j=1,..,m.

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

Перехід до рівностей здійснюється додаванням до лівої частини обмежень неотрицательной залишкової змінної для нерівностей типу, і відніманням з лівої частини неотрицательной надлишкової змінної для нерівностей типу. Наприклад, нерівність при переході до стандартної форми перетворюється на рівність , a нерівність - у рівність . У цьому, як залишкова змінна , і надлишкова змінна є неотрицательными.

Передбачається, що права частина нерівностей невід'ємна. Інакше цього можна домогтися множенням обох частин нерівності на «-1» і зміною його знака на протилежний.

Якщо у вихідному завданні лінійного програмування змінна не обмежена у знаку, її можна у вигляді різниці двох невід'ємних змінних , де .

Важливою особливістю змінних є те, що за будь-якого допустиме рішеннялише одна з них може набувати позитивного значення. Це означає, що якщо , то і навпаки. Отже, може розглядатися як залишкова, а як надмірна змінні.

ПрикладНехай дане завдання лінійного програмування:

,

.

Потрібно привести її до стандартної форми. Зауважимо, що перша нерівність вихідного завдання має знак , отже, до нього необхідно ввести залишкову змінну . В результаті отримаємо.

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

Крім того, змінна не обмежена у знаку. Отже, як у цільовій функції, так і в обох обмеженнях вона повинна бути замінена на різницю . Виконавши підстановку, отримаємо завдання лінійного програмування у стандартній формі, еквівалентній вихідному завданню:

.

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Насправді обмеження завдання лінійного програмування часто задаються не рівняннями, а нерівностями.

Покажемо, як можна перейти від завдання з обмеженнями-нерівністю до основного завдання лінійного програмування.

Нехай є завдання лінійного програмування зі змінними, в якій обмеження, накладені на змінні, мають вигляд лінійних нерівностей. У деяких із них знак нерівності може бути в інших (другий вид зводиться до першого простою зміною знака обох частин). Тому поставимо всі обмеження-нерівності у стандартній формі:

Потрібно знайти таку сукупність невід'ємних значень, яка б задовольняла нерівностям (4.1), і, крім того, звертала б у мінімум лінійну функцію:

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

де - деякі нові змінні, які ми називатимемо «додатковими». Відповідно до умов (4.1), ці додаткові змінні так само, як і мають бути невід'ємними.

Таким чином, перед нами виникає завдання лінійного програмування в наступній постановці: знайти такі невід'ємні значення змінних, щоб вони задовольняли системі рівнянь (4.3) і одночасно звертали в мінімум лінійну функцію цих змінних:

Як видно, перед нами у чистому вигляді основне завдання лінійного програмування (ОЗЛП). Рівняння (4.3) задані у формі, вже дозволеній щодо базисних змінних, які виражені через вільні змінні Загальна кількість змінних дорівнює , з них «початкових» та «додаткових». Функція L виражена лише через «первісні» змінні (коефіцієнти при «додаткових» змінних у ній дорівнюють нулю).

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

Приклад 1 Є задача лінійного програмування з обмеженнями-нерівностями: ійти невід'ємні значення змінних, що задовольняють умовам

та звертають у мінімум лінійну функцію

Потрібно привести це завдання до виду ОЗЛП.

Рішення. Наводимо нерівності (4.4) до стандартної форми;

Вводимо додаткові змінні:

Завдання зводиться до того, щоб знайти невід'ємні значення змінних

що задовольняють рівнянням (4.6) та обертають у мінімум лінійну функцію (4.5).

Ми показали, як від задачі лінійного програмування з обмеженнями-нерівностями можна перейти до задачі з обмеженнями-рівністю (ОЗЛП). Завжди можливий і зворотний перехід - від ОЗЛП до завдання з обмеженнями-нерівністю. Якщо у першому випадку ми збільшували число змінних, то у другому випадку будемо його зменшувати, усуваючи базисні змінні та залишаючи лише вільні.

Приклад 2. Є завдання лінійного програмування з обмеженнями-рівністю (ОЗЛП):

та мінімізованою функцією

Потрібно записати її як завдання лінійного програмування з обмеженнями-нерівністю.

Рішення. Оскільки , то виберемо якісь дві зі змінних як вільні. Зауважимо, що змінні як вільні вибирати не можна, оскільки вони пов'язані першим із рівнянь (4 7): значення однієї з них повністю визначається значенням іншої, а вільні змінні мають бути незалежними

З такої ж причини не можна як вільні вибрати змінні (їх пов'язує друге рівняння). Виберемо як вільні змінні і висловимо через них решту:

Оскільки умови (4 9) можуть бути замінені нерівностями:

Перейдемо у вираженні лінійної функції L до вільних змінних Підставляючи L замість і їх вирази (4.9). отримаємо.