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

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

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

Вибравши = 1 ключовим елементом, переходимо до нової таблиці.

Виписуючи окремо 1-й рядок (виразивши з нього, ) і замінивши , дістаємо першу стандартну форму задачі

де

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

(25)

(26)

(27)

Або у короткому запису

(25а)

(26а)

Скалярно-векторна форма:

(25б)

(26б)

(27б)

Матрична форма:

(25в)

(26в)

(27в)

Векторна форма:

(25г)

(26г)

(27г)

Лема 2. Перша стандартна форма основної задачі лінійного програмування завжди може бути зведена до другої стандартної форми.

Доведення. Припустимо, що невідомі є вільними;

- базисними; ранг матриці системи обмежень (22) дорівнює

Розв'яжемо систему рівнянь (22) відносно базисних невідомих і нехай розв'язок має вигляд

(28)

Всі невідомі невід'ємні, тому

Враховуючи це, поставимо у відповідність отриманому розв'язку (28) еквівалентну систему нерівностей:

Введемо позначенняі помноживши всі нерівності на -1 отримуємо систему обмежень:

Очевидно, що остання система обмежень збігається з (26) і рівносильна системі обмежень (3-9) У тому розумінні, що будь-якому розв'язку системи нерівностей відповідає певний розв'язок системи рівнянь (22) Для завершення доведення леми підставимо у цільову функцію (21) замість базисних невідомих їхні вирази (28). Якщо згрупувати подібні члени, то цільова функція набуде вигляду (25). Приклад 2. Звести до другої стандартної форми задачу

Розв'язання. Виписуємо матрицю системи обмежень

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

Отже, ранг . Базисні невідомі: ; вільні невідомі:

Розв'язуємо систему відносно базисних невідомих:

Так як, то

Запишемо цільову функцію z через вільні невідомі

Отже, задача, рівносильна вихідній, має вигляд:

Із лем 1, 2 випливає така теорема.

Теорема 1. Основна задача лінійного програмування у першій стандартній формі і основна задача лінійного програмування у другій стандартній формі еквівалентні між собою

3. Економічна модель задачі

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

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

Таблиця 1 Інформація, необхідна для складання виробничої програми

Побудуємо економіко-математичну модель даної задачі.

Позначимо черезкількість вироблених морозильних камер, а через, — електроплит. Виразимо математично умови, що обмежують використання ресурсів.

Виходячи з нормативів використання кожного з ресурсів на одиницю продукції, що наведені в табл. 1, запишемо сумарні витрати робочого часу:

.

За умовою задачі ця величина

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

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

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

Отже, умови задачі, описані в прикладі 1.1, можна подати такою економіко-математичною моделлю:

5

за умов:

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

Перевіримо виконання умов задачі:

9,2-50 + 4·15 = 520;

3-50 + 6·15 = 240;

2·15 = 30<40.

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

Виручка становитиме: F = 300-50 + 200-15 = 18000 ум. од.

Отриманий оптимальний план у порівнянні з першим варіантом виробничої програми уможливлює збільшення виручки на

18000-16 800 = 1200 ум. од., тобто на100% = 7,1%

4. Математична модель задачі

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

знайти максимум (мінімум) функції

(29)

або

за умов

(30)

(31)

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

Задачу (29)—(2.3) легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (30) всі (і =1,2, ...... n) невід'ємні, а всі обмеження є рівностями.

Якщо якесьвід'ємне, то, помноживши -те обмеження на (—1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності , , то останню завжди можна звести до рівності, увівши допоміжну змінну

Аналогічно обмеження виду зводимо до рівності, віднімаючи від лівої частини допоміжну змінну ,тобто І

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

за умов

Розв'язування. Помножимо другу нерівність на (-1) і введемо відповідно допоміжні змінніідля другого та третього обмеження:

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

Отже, будь-яку задачу ЛП можна записати в такій канонічній формі:

знайти максимум функції (32)

за умов

(33)

(34)

Задачу (32)—(34) можна розв'язувати на мінімум, якщо цільову функцію помножити на (-1), тобто

5. Геометрична інтерпретація стандартної задачі

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

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

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

Розглянемо розв'язування нерівностей.

Лема 3. Множина розв'язків нерівності з двома змінними

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

Доведення. Гранична пряма перпендикулярна до вектора нормалі . (рис 3.1). Вектор нормалі (його ще називають напрямним вектором ) є градієнтом лінійної функції і показує напрям зростання її значень — одиничні вектори вздовж осейі відповідно; таким чином, . Справді, нехай ,. Візьмемо на прямій, яка визначається вектором точку , причому нехай , тобто точка лежить далі від початку координат, ніж точка. Очевидно також, що . У точці числове значення лінійної функції дорівнює . Аналогічно в точці значення . Ураховуючи, що , дістанемо