Розглянемо кілька методів розв'язання задач лінійного програмування.
Графічний метод досить простий і наочний вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному поданні допустимих рішень та ЦФ завдання.
Кожна з нерівностей задачі лінійного програмування визначає на координатній площині деяку напівплощину, а система нерівностей загалом - перетин відповідних площин. Безліч точок перетину даних напівплощин називається областю допустимих рішень (ОДР). ОДР завжди є опуклою фігуру, тобто. що має наступну властивість: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена опуклим багатокутником, необмеженою опуклою багатокутною областю, відрізком, променем, однією точкою. У разі несумісності системи обмежень задачі (1) ОДР є пустою множиною.
Все вищесказане стосується і випадку, коли система обмежень (1) включає рівності, оскільки будь-яка рівність
можна уявити як системи двох нерівностей
ЦФ при фіксованому значенні визначає на площині пряму лінію. Змінюючи значення L, ми отримаємо сімейство паралельних прямих, званих лініями рівня.
Це з тим, зміна значення L спричинить зміна лише довжини відрізка, отсекаемого лінією рівня осі (початкова ордината), а кутовий коефіцієнт прямий залишиться постійним. Тому для вирішення достатньо побудувати одну з ліній рівня, довільно вибравши значення L.
Вектор з координатами з коефіцієнтів ЦФ при перпендикулярний до кожної з ліній рівня. Напрямок вектора збігається з напрямком зростання ЦФ, що є важливим моментом для вирішення задач. Напрям зменшення ЦФ протилежно напрямку вектора.
Суть графічного методу ось у чому. У напрямку (проти напрямку) вектора в ОДР проводиться пошук оптимальної точки. Оптимальною вважається точка, якою проходить лінія рівня, що відповідає найбільшому (найменшому) значенню функції. Оптимальне рішення завжди знаходиться на межі ОДР, наприклад, в останній вершині багатокутника ОДР, якою пройде цільова пряма, або на всій його стороні.
При пошуку оптимального розв'язання задач лінійного програмування можливі такі: існує єдине рішення задачі; існує безліч рішень (альтернативний оптиум); ЦФ не обмежена; область допустимих рішень – єдина точка; Завдання немає рішень.
Малюнок 1 Геометрична інтерпретація обмежень та ЦФ задачі
Розглянемо методику розв'язання задач ЛП графічним методом.
- 1) в обмеженнях завдання (1) замінити знаки нерівностей знаками точних рівностей та побудувати відповідні прямі;
- 2) знайти та заштрихувати напівплощини, дозволені кожним з обмежень-нерівностей задачі (1). Для цього потрібно підставити в конкретну нерівність координати будь-якої точки [наприклад, (0; 0)] і перевірити істинність отриманої нерівності.
Якщо нерівність істинна, то треба заштрихувати напівплощину, що містить дану точку; інакше (нерівність хибне) треба заштрихувати напівплощину, що не містить дану точку.
Оскільки і повинні бути невід'ємними, то їх допустимі значення завжди будуть перебувати вище осі та правіше за осі, тобто. у першому квадранті.
Обмеження-рівності дозволяють лише ті точки, які лежать на відповідній прямій. Тому необхідно виділити на графіку такі прямі;
- 3) визначити ОДР як частину площини, що належить одночасно всім дозволеним областям, та виділити її. За відсутності ОДР завдання немає рішень;
- 4) якщо ОДР - не порожня безліч, потрібно побудувати цільову пряму, тобто. будь-яку з ліній рівня (де L - довільне число, наприклад, кратне і, тобто. зручне щодо розрахунків). Спосіб побудови аналогічний до побудови прямих обмежень;
- 5) побудувати вектор, який починається у точці (0; 0) і закінчується у точці. Якщо цільова пряма та вектор побудовані правильно, то вони будуть перпендикулярні;
- 6) при пошуку максимуму ЦФ необхідно пересувати цільову пряму в напрямку вектора, при пошуку мінімуму ЦФ - проти напрямки вектор. Остання під час руху вершина ОДР буде точкою максимуму чи мінімуму ЦФ. Якщо такої точки (точок) не існує, то можна зробити висновок про необмеженість ЦФна безлічі планів зверху (при пошуку максимуму) або знизу (при пошуку мінімум);
- 7) визначити координати точки max (min) ЦФ та обчислити значення ЦФ. Для обчислення координат оптимальної точки необхідно вирішити систему рівнянь прямих на перетині яких знаходиться.
Симплекс-метод - це один із перших спеціалізованих методів оптимізації, націлений на вирішення завдань лінійного програмування, у той час як методи простого та спрямованого перебору можуть бути застосовані для вирішення практично будь-якої задачі оптимізації. Він був запропонований американцем Г. Данцигом у 1951 р. Симплекс-метод полягає у просуванні по опуклому багатограннику обмежень від вершини до вершини, при якому на кожному кроці значення цільової функції покращується доти, доки не буде досягнуто оптимуму.
Симплекс метод - це характерний приклад ітераційних обчислень, що використовуються під час вирішення більшості оптимізаційних завдань. У обчислювальній схемі симплекс-метода реалізується впорядкований процес, при якому, починаючи з деякої вихідної допустимої кутової точки (зазвичай початок координат), здійснюються послідовні переходи від однієї допустимої екстремальної точки до іншої доти, доки не буде знайдена точка, що відповідає оптимальному рішенню ( 2).
Малюнок 2 Перехід від однієї вершини до іншої
Симплекс-метод, відомий також у нашій літературі під назвою методу послідовного поліпшення плану, вперше розробив Г. Данциг у 1947 р. Цей метод дозволяє переходити від одного допустимого базисного рішення до іншого, причому так, що цільові функції безперервно зростають. В результаті оптимальне рішення знаходять за кінцеве число кроків.
Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь чи нерівностей та лінійного функціоналу.
Алгоритм рішення ЗЛП є симплексним методом.
Симплекс-метод має на увазі послідовний перебір всіх вершин області допустимих значень з метою знаходження тієї вершини, де функція набуває екстремального значення. На першому етапі знаходиться якесь рішення, яке покращується на кожному наступному кроці. Таке рішення називається базисним.
Розглянемо кроки симлекс-методу.
- 1) у складеній таблиці спочатку необхідно переглянути стовпець із вільними членами. Якщо в ньому є негативні елементи, необхідно здійснити перехід до другого кроку, якщо ж ні, то до п'ятого;
- 2) на другому кроці необхідно визначитися, яку змінну виключити з базису, а яку включити, для того, щоб зробити перерахунок симплекс-таблиці. Для цього переглядаємо стовпець із вільними членами та знаходимо в ньому негативний елемент. Рядок з негативним елементом буде називатися ведучою. У ній знаходимо максимальний за модулем негативний елемент, відповідний стовпець - ведений. Якщо ж серед вільних членів є негативні значення, а у відповідному рядку немає, то така таблиця не матиме рішень. Змінна у провідній рядку, що у стовпці вільних членів виключається з базису, а змінна, відповідна провідному стовпцю входить у базис. У таблиці 1 наведено приклад симплекс-таблиці.
Таблиця 1
Приклад симплекс-таблиці
|
Базисні змінні |
Вільні члени в обмеженнях |
Небазисні змінні |
|||||
- 3) на третьому кроці перераховуємо всю симплекс-таблицю за спеціальними формулами;
- 4) якщо після перерахунку у стовпці вільних членів залишилися негативні елементи, то переходимо до першого кроку, якщо таких немає, то до п'ятого;
- 5) якщо Ви дійшли до п'ятого кроку, то знайшли рішення, яке допустиме. Однак це не означає, що воно оптимальне. Оптимальним воно буде лише в тому випадку, якщо позитивні усі елементи у F-рядку. Якщо це не так, то необхідно поліпшити рішення, для чого знаходимо для наступного перерахунку провідні рядок і стовпець за наступним алгоритмом. Спочатку знаходимо мінімальне негативне число в рядку F, виключаючи значення функції. Стовпець із цим числом і будемо ведучим. Для того, щоб знайти провідний рядок, знаходимо відношення відповідного вільного члена та елемента з провідного стовпця, за умови, що вони позитивні. Мінімальне відношення дозволить визначити провідний рядок. Знову перераховуємо таблицю за формулами, тобто. переходимо до кроку 3;
- 6) якщо неможливо знайти провідний рядок, тому що немає позитивних елементів у провідному стовпці, то функція в області допустимих розв'язків задачі не обмежена зверху і Fmax ->?. Якщо рядку F і стовпці вільних членів всі елементи позитивні, то знайдено оптимальне рішення.
Коротка теорія
Лінійне програмування - розділ математичного програмування, застосовуваний розробки методів відшукання екстремуму лінійних функцій кількох змінних при лінійних додаткових обмеженнях, накладених на змінні. За типом розв'язуваних завдань його методи поділяються на універсальні та спеціальні. За допомогою універсальних методів можуть вирішуватись будь-які завдання лінійного програмування (ЗЛП). Спеціальні методи враховують особливості моделі завдання, її цільової функції та системи обмежень. Особливістю є те, що екстремума цільова функція досягає межі області допустимих рішень.
Графічний метод розв'язання задач лінійного програмування дає можливість наочно уявити їх структуру, виявити особливості та відкриває шляхи дослідження складніших властивостей. Завдання лінійного програмування з двома змінними можна вирішити графічно. Однак уже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більша за три, графічне рішення, взагалі кажучи, неможливе. Випадок двох змінних немає особливого практичного значення, проте його розгляд прояснює властивості обмежень ЗЛП, призводить до ідеї її вирішення, робить геометрично наочними способи рішення та шляхи їх практичної реалізації.
Якщо обмеження та цільова функція містить більше двох змінних, тоді необхідно (або методом послідовного поліпшення рішення) - він універсальний і можна вирішити будь-яку ЗЛП. Для деяких прикладних завдань лінійного програмування, таких як розроблені спеціальні методи рішення.
Приклад розв'язання задачі
Умова завдання
Підприємство випускає два види продукції: Виріб 1 та Виріб 2. На виготовлення одиниці Виробу 1 потрібно витратити кг сировини першого типу, кг сировини другого типу, кг сировини третього типу. На виготовлення одиниці Виробу 2 потрібно витратити кг першого типу, сировини другого типу, сировини третього типу. Виробництво забезпечене сировиною кожного типу у кількості кг, кг, кг відповідно. Ринкова ціна одиниці Виробу 1 становить тис. крб., а одиниці Виробу 2 - тис. руб.
Потрібно:
- Побудувати математичну модель завдання.
- Скласти план виробництва виробів, що забезпечує максимальну виручку від реалізації за допомогою графічного методу вирішення завдання лінійного програмування.
Розв'язання задачі
Побудова моделі
Через і позначимо кількість виробів, що випускаються 1-го і 2-го типу.
Тоді обмеження на ресурси:
Крім того, за змістом завдання
Цільова функція економіко-математичної моделі, що виражає виручку, що отримується від реалізації:
Отримуємо наступну економіко-математичну модель:
Побудова області допустимих рішень
Розв'яжемо отриману задачу лінійного програмування графічним способом:
Для побудови області допустимих рішень будуємо в системі координат відповідні даним обмеженням-нерівностей граничні прямі:
Знайдемо точки, якими проходять прямі:
Рішенням кожної нерівності системи обмежень ЗЛП є напівплощина, що містить граничну пряму і розташована по одну сторону від неї.
Для визначення напівплощини візьмемо будь-яку точку, наприклад, що не належить прямої (1), підставимо координати (0; 0) у відповідну нерівність. Т.к. нерівність вірна:
Області розв'язків відповідної 1-ї нерівності відповідає ліва напівплощина
Візьмемо будь-яку точку, наприклад, яка не належить прямої (2), підставимо координати (0;0) у відповідну нерівність. Т.к. нерівність вірна:
Візьмемо будь-яку точку, наприклад, яка не належить прямої (3), підставимо координати (0;0) у відповідну нерівність. Т.к. нерівність вірна:
Області розв'язків відповідної 2-ї нерівності відповідає ліва напівплощина
Областю допустимих рішень є фігура.
Знаходження рішення задачі ЛП
Будуємо вектор координати якого пропорційні коефіцієнтам цільової функції. Тут – коефіцієнт пропорційності.
Перпендикулярно до побудованого вектора проводимо лінію рівня.
Переміщуємо лінію рівня у напрямку вектора так, щоб вона стосувалася області допустимих рішень у крайній точці. Рішенням на максимум є точка , координати якої знаходимо як точку перетину прямих (2) та (1).
Відповідь
Таким чином необхідно випускати 56 виробів 1-го виду та 64 вироби 2-го виду. При цьому виторг від реалізації виробів буде максимальним і складе 5104 ден.
Метод графічного рішення, якщо завдання з двома змінними має лінійні обмеження, а цільова функція – квадратична, детально розглянуто .
На ціну сильно впливає терміновість рішення (від доби до кількох годин). Онлайн-допомога на іспиті/заліку здійснюється за попереднім записом.
Заявку можна залишити прямо в чаті, попередньо скинувши умову завдань та повідомивши необхідні вам терміни вирішення. Час відповіді – кілька хвилин.
Математичне моделювання в дослідженні операцій є, з одного боку, дуже важливим і складним, а з іншого - практично не піддається наукової формалізації процесом. Зауважимо, що спроби виділити загальні принципи створення математичних моделей, які неодноразово робилися, призводили або до декларування рекомендацій найзагальнішого характеру, що важко докласти для вирішення конкретних проблем, або, навпаки, до появи рецептів, що застосовуються насправді тільки до вузького кола завдань. Тому найкориснішим є знайомство з технікою математичного моделювання на конкретних прикладах.
Завдання лінійного програмування можна вирішити такими методами:
алгоритмом Флойда;
алгоритм дейкстри на графах;
графічний метод;
метод симплекс-таблиць та ін.
Алгоритм розв'язання задач лінійного програмування методом Дейкстри на графах.
У найпростішій реалізації для зберігання чисел d[i] можна використовувати масив чисел, а для зберігання приналежності елемента множині U - масив булевих змінних.
На початку алгоритму відстань для початкової вершини належить рівним нулю, проте інші відстані заповнюються великим позитивним числом (більшим максимального можливого шляху графі). Масив прапорів заповнюється нулями. Потім запускається основний цикл.
На кожному кроці циклу необхідно знайти вершину U з мінімальною відстанню та прапором рівним нулю. Потім потрібно встановити прапор в 1 і перевіряємо всі сусідні з нею вершини U. Якщо відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то необхідно зменшити його. Цикл завершується, коли прапори всіх вершин стають рівними 1, або коли у всіх вершин c прапором 0. Останній випадок можливий тоді і тільки тоді, коли граф G не пов'язаний.
Спосіб вирішення завдань лінійного програмування графічним методом.
Графічний метод розв'язання задачі лінійного програмування заснований на геометричній інтерпретації задачі лінійного програмування і застосовується в основному при розв'язанні задач двовимірного простору і лише деяких завдань тривимірного простору, так як досить важко побудувати багатогранник рішень, що утворюється в результаті перетину напівпросторів. Завдання простору розмірності більше трьох зобразити графічно взагалі неможливо.
Нехай завдання лінійного програмування задане у двовимірному просторі, тобто обмеження містять дві змінні.
Мінімальне значення функції визначено формулою (1).
(1)
Обмеження представлені формулами (2) та (3).
(2)
(3)
Нехай система (2) за умови (3) є спільною. Кожна з нерівностей із систем (2) і (3) визначає напівплощину з граничними прямими представлено формулою(4):
Лінійна функція (1) при фіксованих значеннях Z є рівнянням прямої лінії: 
Необхідно побудувати багатокутник рішень системи обмежень (2) та графік лінійної функції (1) при Z = 0. Тоді поставленої задачі лінійного програмування можна дати таку інтерпретацію:
Знайти точку багатокутника рішень, у якій пряма 
опорна та функція Z при цьому досягає мінімуму.
Значення 
зменшуються в напрямку вектора 
тому пряму Z=0 необхідно пересувати паралельно самої собі в напрямку вектора N.
Якщо багатокутник рішень обмежений, то пряма двічі стає опорною по відношенню до багатокутника рішень (у точках B і E), причому мінімальне значення набуває в точці E. Координати точки 
необхідно знайти, вирішуючи систему рівнянь прямих DE та EF.
Якщо ж багатокутник рішень є необмежену багатокутну область, то можливі два випадки.
Випадок 1. Пряма 
, Пересуваючись у напрямку вектораN або протилежно йому, постійно перетинає багатокутник рішень і в жодній точці не є опорною до нього. У цьому випадку лінійна функція не обмежена на багатокутнику рішень як зверху, так і знизу.
Випадок 2. Пряма, пересуваючись, все ж таки стає опорною щодо багатокутника рішень. Тоді в залежності від виду області лінійна функція може бути обмеженою зверху та необмеженою знизу, обмеженою знизу та необмеженою зверху, або обмеженою як знизу, так і зверху.
Для вирішення цієї задачі був обраний найбільш відомий і широко застосовується на практиці для вирішення задач лінійного програмування є симплекс-метод. Незважаючи на те, що симплекс-метод є досить ефективним алгоритмом, що показав хороші результати при вирішенні прикладних задач лінійного програмування, він є алгоритмом складної секспоненціальної.
Симплексний метод завдань лінійного програмування ґрунтується на переході від одного опорного плану до іншого, при якому значення цільової функції зростає або зменшується.
Перед складанням симплекс-таблиці завдання має бути перетворена, система обмежень приведена до допустимого базисного вигляду, за допомогою якого з цільової функції повинні бути виключені базові змінні, як показано на малюнку 1.
Рисунок 1 – Початкове перетворення системи обмежень
Тут для визначеності запису вважається, що як базові змінні можна взяти змінні X1, X2, ..., Xr і що при цьому b1, b2, ..., br ≥ 0 (відповідне базисне рішення є опорним).
Для складання симплекс-таблиці у всіх рівностях за умови завдання члени, містять перемінні, переносяться у ліву частину, вільні залишаються праворуч, тобто. Завдання записується у вигляді системи рівності як показано на малюнку 2.
Рисунок 2 – Перетворення системи нерівностей
Алгоритм переходу до наступної таблиці такий:
проглядається останній рядок (індексна) таблиці та серед коефіцієнтів цього рядка (виключаючи стовпець вільних членів) вибирається найменше від'ємне число при знайденні max, або найбільше позитивне при задачі на min. Якщо такого немає, то вихідне базисне рішення є раціональним і дана таблиця є останньою;
проглядається стовпець таблиці, що відповідає обраному негативному (позитивному) коефіцієнту в останньому рядку- ключовий стовпець, і в цьому стовпці вибираються позитивні коефіцієнти. Якщо таких немає, то цільова функція необмежена області допустимих значень змінних і завдання рішень немає;
серед обраних коефіцієнтів стовпця вибирається той, котрій абсолютна величина відношення відповідного вільного члена (що у стовпці вільних членів) до цього елемента мінімальна. Цей коефіцієнт називається вирішальним, а рядок у якому він знаходиться ключовий;
надалі базисна змінна, що відповідає рядку роздільної здатності елемента, повинна бути переведена в розряд вільних, а вільна змінна, що відповідає стовпцю роздільного елемента, вводиться в число базисних. Будується нова таблиця, що містить нові назви базисних змінних:
розділимо кожен елемент ключового рядка (виключаючи стовпець вільних членів) на роздільну здатність елемент і отримані значення запишемо в рядок зі зміненою базисною змінною нової симплекс таблиці.
Рядок роздільної здатності елемента ділиться на цей елемент і отриманий рядок записується в нову таблицю на те ж місце.
у новій таблиці всі елементи ключового стовпця = 0, крім розрізає, він завжди дорівнює 1.
стовпець, у якого в ключовому рядку є 0, у новій таблиці буде таким самим.
рядок, у якій у ключовому стовпці є 0, у новій таблиці буде такий самий.
інші клітини нової таблиці записується результат перетворення елементів старої таблиці, як показано малюнку 3.
Рисунок 3 – Складання нового елемента у симплекс-таблиці
В результаті одержують нову симплекс-таблицю, що відповідає новому базисному рішенню.
Тепер слід переглянути рядок цільової функції (індексний), якщо в ньому немає негативних значень (у задачі на знаходження максимального значення), або позитивних (у задачі на знаходження мінімального значення) крім того, що стоїть на місці (вільного стовпця), то означає, що оптимальне рішення отримано. В іншому випадку, переходимо до нової симплекс таблиці за описаним вище алгоритмом.
Для розв'язання задачі даної курсової роботи було обрано напрямок завдання щодо оптимального розподілу коштів на підприємстві. Оптимальним планом чи оптимальним рішенням завдання лінійного програмування є план, у якому значення цільової зростатиме (зменшуватися).
Після аналізу зібраної інформації, було складено завдання лінійного програмування по цеху №8 у ВАТ «НефАЗ». На фарбувальному конвеєрі, на якому фарбуються деталі. Необхідно пофарбувати оптимальну кількість деталей за одну робочу зміну, щоб прибуток був максимальним.
Для подальшого розв'язання задачі необхідно скласти постановку задачі та математичну модель задачі.
Завдання. Розв'язати графічно завдання лінійного програмування, визначивши екстремальне значення цільової функції:
при обмеженнях
Побудуємо область допустимих рішень, тобто. розв'яжемо графічно систему нерівностей. Для цього побудуємо кожну пряму та визначимо напівплощини, задані нерівностями (напівплощини позначені штрихом).
Побудуємо рівняння 3x1+x2=9 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 9. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 3. З'єднуємо точку (0; 9) з (3; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 3 . 0+1. 0 - 9 ≤ 0, тобто. 3x 1 +x 2 - 9≥ 0 у напівплощині вище прямої.
Побудуємо рівняння x1+2x2=8 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 4. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 8. З'єднуємо точку (0; 4) з (8; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 1 . 0+2. 0 - 8 ≤ 0, тобто. x 1 +2x 2 - 8≥ 0 у напівплощині вище прямої.
Побудуємо рівняння x 1 + x 2 = 8 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 8. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 8. З'єднуємо точку (0; 8) з (8; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 1 . 0+1. 0 - 8 ≤ 0, тобто. x 1 +x 2 - 8≤ 0 у напівплощині нижче прямої.
Перетином напівплощин буде область, координати точок якого задовольняють умові нерівностей системи обмежень задачі.
Позначимо межі області багатокутника розв'язків.
Перевірити правильність побудови графіків функцій можна за допомогою калькулятора
Розглянемо цільову функцію задачі F = 4x1+6x2 → min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 4x1 +6x2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок мінімізації F(X). Початок вектора – точка (0; 0), кінець – точка (4; 6). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, то рухаємо пряму до першого торкання зазначеної області. На графіці ця пряма позначена пунктирною лінією.
Пряма F(x) = 4x 1 +6x 2 перетинає область у точці B. Оскільки точка B отримана в результаті перетину прямих (1)
і (2)
, її координати задовольняють рівнянням цих прямих:
3x 1 +x 2 =9
x 1 +2x 2 =8
Розв'язавши систему рівнянь, отримаємо: x 1 = 2, x 2 = 3
Звідки знайдемо мінімальне значення цільової функції:
F(X) = 4*2 + 6*3 = 26
Найбільш простим та наочним методом лінійного програмування (ЛП) є графічний метод. Він застосовується для розв'язання задач ЛП із двома змінними. Розглянемо завдання ЛП у стандартній формі:
max f(x 1 , x 2 ..., x n) = ,
, i = 1, 2, …, m,
x j 0, j = 1, 2, …, n.
Покладемо n=2і розглядатимемо завдання на площині. Нехай система нерівностей спільна (має хоча б одне рішення).
Кожна нерівність цієї системи геометрично визначає напівплощину з граничною прямою а i 1 х 1 + а i 2 х 2 = b i , i = 1, 2, …, m. Умови невід'ємності визначають напівплощини з граничними прямими х 1 = 0, х 2 = 0 відповідно. Система спільна, тому напівплощини, як опуклі множини, перетинаючи, утворюють загальну частину, яка є опуклим множиною і є сукупністю точок, де координати кожної точки є рішенням даної системи. Сукупність цих точок називають багатокутником розв'язків. Він може бути точкою, відрізком, променем, обмеженим та необмеженим багатокутником.
Таким чином, геометрично ЗЛП є відшуканням такої точки багатокутника рішень, координати якої доставляють лінійній функції мети максимальне (мінімальне) значення, причому допустимими рішеннями є всі точки багатокутника рішень.
Лінійне рівняння описує безліч точок, що лежать на одній прямій. Лінійна нерівність визначає деяку область на площині. Визначимо, яку частину поверхні визначає нерівність 2х 1 + Зх 2 12.
По-перше, побудуємо пряму 2х1+ Зх 2= 12. Вона проходить через точки (6; 0) та (0; 4). Для того щоб визначити, яка напівплощина задовольняє нерівності, необхідно вибрати будь-яку точку на графіці, що не належить прямої, і підставити її координати в нерівність. Якщо нерівність виконуватиметься, то дана точка є допустимим рішенням, і напівплощина, що містить точку, задовольняє нерівності. Для підстановки в нерівність зручно використовувати точку початку координат. Підставимо х 1 = х 2 = 0 у нерівність 2х 1 + Зх 2 12. Отримаємо 2х0 + 3х0 12. Дане твердження є вірним, отже, нерівності 2х 1 + Зх 2 12 відповідає нижня напівплощина, що містить точку (0; 0). Це відбито на графіку, зображеному на рис. 1.1.
Аналогічно графічно можна зобразити всі обмеження завдання ЛП.
Рішенням кожної нерівності системи обмежень ЗЛП є напівплощина, що містить граничну пряму і розташована по одну сторону від неї. Перетин напівплощин, кожна з яких визначається відповідною нерівністю системи, називається областю допустимих рішень, або областю визначення. Необхідно пам'ятати, що область допустимих рішень задовольняє умови невід'ємності ( х j 0, j = 1, 2, …, n). Координати будь-якої точки, що належить області визначення, є допустимим розв'язанням задачі.
Для знаходження екстремального значення цільової функції при графічному розв'язанні задач ЛП використовують вектор-градієнт, координати якого є похідними приватними цільової функції, тобто.
Цей вектор показує напрямок якнайшвидшої зміни цільової функції. Пряма з 1 х 1 + з 2 х 2 = f(х 0), перпендикулярна вектор-градієнт, є лінією рівня цільової функції. У будь-якій точці лінії рівня цільова функція приймає те саме значення. Прирівняємо цільову функцію постійній величині «а». Змінюючи значення "а", отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня цільової функції.
Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зміщенні лінії в один бік рівень тільки зростає, а при зміщенні в інший бік лише убуває.
З геометричної погляду завдання лінійного програмування шукається така кутова точка чи набір точок з допустимого безлічі рішень, у якому досягається найвища (нижня) лінія рівня, розташована далі (ближче) інших у напрямі якнайшвидшого зростання.
Графічний метод розв'язання ЗЛП складається з наступних етапів.
1. Будується багатокутна область допустимих рішень (ОДР) ЗЛП.
2. Будується вектор-градієнт цільової функції (ЦФ) у якійсь точці х 0 , що належить ОДР:
3. Лінія рівня з 1 х 1 + з 2 х 2 = а (а - постійна величина) - пряма, перпендикулярна вектору-градієнту - пересувається в напрямку цього вектора у разі максимізації f(x 1 , х 2) до тих пір, поки не залишить меж ОДР. Гранична точка (або точки) області при цьому русі є точкою максимуму f(x 1 , х 2).
4. Для знаходження координат точки максимуму достатньо вирішити два рівняння прямих, що одержуються з відповідних обмежень і дають у перетині точку максимуму. Значення f(x 1 , х 2), знайдене в точці, що отримується, є максимальним.
При мінімізації (максимізації) функції f(x 1 , х 2) лінія рівня переміщається у напрямку, протилежному вектору-градієнту. Якщо пряма, відповідна лінії рівня при своєму русі не залишає ОДР, то мінімум (максимум) функції f(x 1 , х 2) не існує.
Якщо лінія рівня паралельна якомусь функціональному обмеження завдання, то оптимальне значення ЦФ буде досягатися в будь-якій точці цього обмеження, що лежить між двома оптимальними кутовими точками, і, відповідно, будь-яка з цих точок є оптимальним рішенням ЗЛП. Можливі ситуації графічного розв'язання задач ЛП представлені у табл. 1.3.
Таблиця 1.3
| № | Вид ОДР | Вид оптимального рішення | Примітки |
| Багатокутна замкнута | Єдине рішення | ||
| Єдине рішення | |||
| Багатокутна | ЦФ не обмежена знизу | ||
| ЦФ не обмежена зверху | |||
| Багатокутна незамкнена | Єдине рішення | ||
| Безліч рішень | |||
| Відрізок | Єдине рішення |
Розглянемо графічне рішення задач лінійного програмування на прикладі.
приклад 1.1. Планування випуску продукції пошивального підприємства (завдання про костюми).
Намічається випуск двох видів костюмів – чоловічих та жіночих. На жіночий костюм потрібно 1м вовни, 2м лавсану та 1 чол./день трудовитрат. На чоловічий костюм - 3,5 м вовни, 0,5 м лавсану і 1 чол./День трудовитрат. Усього є 350м вовни, 240м лавсану і 150 чол. / Днів трудовитрат. Потрібно визначити, скільки костюмів кожного виду необхідно пошити, щоб забезпечити максимальний прибуток, якщо прибуток від жіночого костюма становить 10 грошових одиниць, як від чоловічого – 20 грошових одиниць. При цьому слід мати на увазі, що необхідно пошити щонайменше 60 чоловічих костюмів.
Введемо такі позначення: х 1 – число жіночих костюмів; х 2 – кількість чоловічих костюмів. Прибуток від жіночих костюмів становить 10х 1 , як від реалізації чоловічих - 20х 2 , тобто. необхідно максимізувати цільову функцію:
10х1 + 20х2
Обмеження завдання мають вигляд:
х 1 + х 2 150,
2 х 1 + 0,5 х 2 240,
х 1 + 3,5 х 2 350,
х 2 60,
х 1 0.
Перше обмеження праці х 1 + х 2 150. Пряма х 1 + х 2 = 150 проходить через точки (150; 0) і (0; 150) (рис. 1.2).
Друге обмеження по лавсану 2 х 1 + 0,5 х 2 240. Пряма 2 х 1 + 0,5 х 2 = 240 проходить через точки (120; 0) та (0; 480). Третє обмеження по шерсті х 1 + 3,5 х 2 350. Додамо четверте обмеження за кількістю чоловічих костюмів х 2 60. Розв'язанням цієї нерівності є напівплощина, що лежить вище за пряму х 2 = 60. На рис. 1.3 заштрихована область допустимих рішень. Для визначення напрямку руху до оптимуму побудуємо вектор-градієнт, координати якого є похідними приватними цільової функції, тобто.
Щоб збудувати такий вектор, потрібно з'єднати точку (10; 20) з початком координат. При максимізації цільової функції необхідно рухатись у напрямку вектора-градієнта, а при мінімізації – у протилежному напрямку. Для зручності можна будувати вектор, пропорційний вектору. Так, на рис. 1.4 зображено вектор-градієнт (30; 60).
Для визначення напрямку руху до оптимуму побудуємо вектор-градієнт, координати якого є похідними приватними цільової функції, тобто.
У нашому випадку рух лінії рівня здійснюватимемо до її виходу з області допустимих рішень. У крайній, кутовий, точці досягається максимум цільової функції. Для знаходження координат цієї точки достатньо вирішити два рівняння прямих, що одержуються з відповідних обмежень і дають у перетині точку максимуму:
х 1 + 3,5 х 2 = 350,
х 1 + х 2 = 150.
Звідси легко записати рішення вихідної ЗЛП: max f(x)= 2300 і досягається при х 1 = 70 та х 2 = 80 (див. рис. 1.4).
1.3.ТЕХНОЛОГІЯ РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ЗА ДОПОМОГОЮ НАДБУДОВКИ ПОШУК РІШЕННЯ У СЕРЕДОВИЩІ EXCEL
1.3.1. Загальні відомості про роботу з табличним процесором Excel
Розглянемо деякі аспекти роботи з табличним процесором Excel, які дозволять спростити розрахунки, необхідні рішення оптимізаційних завдань. Табличний процесор – це програмний продукт, призначений для автоматизації обробки даних табличної форми.
Елементи екрану Excel. Після запуску Excel з'являється на екрані таблиця, вид якої показаний на рис 1.5.
Це зображення називають робочим листом. Воно є сіткою рядків і стовпців, перетину яких утворюють прямокутники, звані осередками. Робочі листи призначені для введення даних, розрахунків, організації інформаційної бази тощо. Вікно Excel відображає основні програмні елементи: рядок заголовка, рядок меню, рядок стану, кнопки керування вікнами.
Робота із формулами.У програмах електронних таблиць формули служать до виконання безлічі різноманітних розрахунків. За допомогою Excel можна швидко створити формулу. Формула складається з трьох основних частин:
1) знаку рівності;
2) сукупності значень чи посилань на осередках, з якими виконуються розрахунки;
3) операторів.
4) Якщо знак рівності відсутня, то Excel інтерпретує дані не як формулу, бо як введення даних у комірку. Формули можна вводити безпосередньо в комірку або рядок формул - як текст, так і число. При цьому слід виконати такі дії:
· Виділити комірку, яка повинна містити формулу і ввести знак (=);
· Ввести оператор або знак дії;
· Виділити іншу комірку, що включається у формулу;
· Натиснути на клавішу Enter.
У рядку формул з'явиться введена формула, у комірці – результат розрахунку.
Використання у формулах функцій. Для полегшення введення формул можна скористатися функціями Excel. Функції - це вбудовані в Excel формули. Excel містить множину формул. Вони згруповані за різними типами: логічні, математичні, інженерні, статистичні та ін.
Для активізації тієї чи іншої формули слід натиснути кнопку Вставка, Опції. У вікні Майстер функцій зліва міститься перелік типів функцій. Після вибору типу праворуч буде розміщено список самих функцій. Вибір функції здійснюється натисканням клавіші миші на відповідній назві.
Різні функції виконують різні типи обчислень за певними правилами. Коли функція є одиничним об'єктом у комірці робочого аркуша, вона починається зі знака (=), далі слідує назва функції, а потім - аргументи функції, укладені в дужки.
Пошук рішення – це надбудова Excel, яка дозволяє вирішувати оптимізаційні завдання. Якщо в меню Сервіс відсутня команда Пошук рішення, необхідно завантажити цю надбудову. Виберіть команду Сервіс => Надбудови та активізуйте надбудову Пошук рішення. Якщо ж цієї надбудови немає в діалоговому вікні Надбудови, вам необхідно звернутися до панелі керування Windows, клацнути на піктограмі Встановлення та видалення програм і за допомогою програми інсталяції Excel (або Office) встановити надбудову Пошук рішення.
Після вибору команд Сервіс => Пошук рішення з'явиться діалогове вікно Пошук рішення.
У діалоговому вікні Пошук рішення є три основні параметри;
Встановити цільову комірку.
Змінюючи комірки.
Обмеження.
Спочатку потрібно заповнити поле Встановити цільову комірку. У всіх завданнях для засобу Пошук рішення оптимізується результат в одному з осередків робочого листа. Цільова осередок пов'язана з іншими осередками цього робочого листа за допомогою формул. Засіб Пошук рішення використовує формули, які дають результат у цільовому осередку, для перевірки можливих рішень. Можна вибрати пошук найменшого або найбільшого значення для цільового осередку або встановити конкретне значення.
Другий важливий параметр засобу Пошук рішення - це параметр Змінюючи комірки. Тут вказуються осередки, значення яких змінюватимуться у тому, щоб оптимізувати результат у цільової осередку. Для пошуку рішення можна вказати до 200 осередків, що змінюються. До цих осередків пред'являється дві основні вимоги: вони повинні містити формул і зміна їх значень має відбиватися зміні результату цільової осередку. Іншими словами, цільовий осередок залежить від змінних осередків.
Третій параметр, який потрібно вводити на вкладці Пошук рішення, – це обмеження.
Для вирішення завдання необхідно:
1) вказати адреси осередків, в які буде вміщено результат рішення (змінні осередки);
2) запровадити вихідні дані;
3) запровадити залежність для цільової функції;
4) ввести залежність для обмеження,
5) запустити команду Пошук рішень;
6) призначити комірку для цільової функції (установити цільову комірку);
7) запровадити обмеження;
8) запровадити параметри на вирішення ЗЛП.
Розглянемо технологію рішення, використовуючи умови прикладу 1.1 (завдання про костюми).
Економіко-математична модель задачі
Нехай х 1 – число жіночих костюмів; х 2 - кількість чоловічих костюмів,
10 х х 1 + 20 х х 2 max
Обмеження завдання мають вигляд:
х 1 + х 2 150 - обмеження праці;
2 x х 1 + 0,5 х х 2240 - обмеження по лавсану;
х 1 + 3,5 х х 2 350 - обмеження вовни;
х 2 60 - обмеження з чоловічих костюмів;
х 1 0 – обмеження по жіночих костюмах.
1. Вказати адреси осередків, в які буде поміщено результат рішення (змінні осередки).
Позначте через x 1, х 2 кількість костюмів кожного типу. У нашому завданні оптимальні значення вектора = (х 1, х 2) будуть поміщені в осередках А2: В2, оптимальне значення цільової функції - в осередку СЗ.
2. Ввести вихідні дані.
Введіть вихідні завдання, як показано на рис. 1.6.
3. Ввести залежність для цільової функції.
· Помістити курсор у комірку «СЗ», відбудеться виділення комірки.
· Помістити курсор на кнопку Майстер функцій на панелі інструментів.
· Ввести Enter. На екрані з'являється діалогове вікно Майстер функцій крок 1 із 2.
· У вікні Функції вибрати рядок СУММПРОИЗВ (рис. 1.7). На екрані
· З'являється діалогове вікно СУММПРОИЗВ (рис. 1.8).
· У рядок Масив 1 ввести А2:В2.
· У рядок Масив 2 ввести АЗ:ВЗ.
Масив 1 буде використовуватися при введенні залежностей для обмежень, тому цей масив треба зробити абсолютну посилання. На рис. 1.9 показано, що в комірку СЗ введено функцію.
5. Ввести залежності для обмежень (рис. 1.10).
· Помістити курсор у комірку СЗ.
· На панелі інструментів кнопка Копіювати в буфер.
· Помістити курсор у комірку С4.
· Помістити курсор у комірку С5.
· На панелі інструментів кнопка Вставити з буфера.
· Помістити курсор в комірку Сб.
· На панелі інструментів кнопка Вставити з буфера.
· Помістити курсор у комірку С7.
· Натисніть кнопку Вставити з буфера на панелі інструментів. (Вміст комірок С4-С7 необхідно перевірити. Вони обов'язково повинні містити інформацію, як це показано для прикладу на рис. 1.11; як приклад представлено вміст комірки С5.)
· У рядку Меню вказівник мишки помістити на Сервіс. У розгорнутому меню виберіть команду Пошук рішення. З'являється діалогове вікно Пошук рішення (рис. 1.12).
5. Запустити команду Пошук рішення.
6. Призначити комірку для цільової функції (установити цільову комірку), вказати адреси комірок, що змінюються.
· Помістити курсор у рядок Встановити цільову комірку.
· Ввести адресу осередку $С$3.
· Ввести тип цільової функції залежно від умови вашого завдання. Для цього відзначте, чому дорівнює цільова функція - Максимальне значення або Мінімальне значення.
· Помістити курсор у рядок Змінюючи комірки.
· Ввести адреси змінних змінних А$2:В$2 (рис. 1.13).
7. Ввести обмеження.
· Помістити вказівник миші на кнопку Додати. З'являється діалогове вікно Додавання обмеження.
· Ввести знак обмеження.
· У рядку Обмеження ввести адресу $D$4 (рис. 1.14).
· Помістити вказівник миші на кнопку Додати. На екрані знову з'явиться діалогове вікно Додавання обмеження.
· Ввести інші обмеження задачі за вищеописаним алгоритмом.
· Після введення останнього обмеження натиснути кнопку ОК. На екрані з'явиться діалогове вікно Пошук рішення із введеними умовами (рис. 1.15).
8. Ввести параметри для розв'язання задачі лінійного програмування.
· У діалоговому вікні помістити вказівник мишки на кнопку Параметри. На екрані з'явиться діалогове вікно Параметри пошуку рішення (мал. 1.16).
· Встановити прапорці у вікнах Лінійна модель (це забезпечить застосування симплекс-метода) та невід'ємні значення.
· Помістити вказівник миші на кнопку ОК. На екрані з'явиться діалогове вікно Пошук рішення.
· Помістити вказівник Миші на кнопку Виконати.
Через нетривалий час з'являться діалогове вікно Результати пошуку рішення та вихідна таблиця із заповненими осередками АЗ:ВЗ для значень х i та осередок СЗ з максимальним значенням цільової функції (рис. 1.17).
Якщо вказати тип звіту Стійкість, можна отримати додаткову інформацію про оптимальне рішення (рис. 1.18).
В результаті розв'язання задачі було отримано відповідь: необхідно пошити 70 шт. жіночих костюмів та 80 шт. чоловічих костюмів, щоб отримати максимальний прибуток 2300 у.о.
1.4. ПОДВІЙНІСТЬ У ЗАВДАННЯХ ЛІНІЙНОГО ПРОГРАМУВАННЯ. АНАЛІЗ ОТРИМАНИХ ОПТИМАЛЬНИХ РІШЕНЬ
У 1975 р. наш співвітчизник Л.В. Канторович отримав Нобелівську премію з економіки (спільно з американським економістом Т. Купмансом) за розробку теорії оптимального використання ресурсів (див. Додаток 1).
З кожним завданням лінійного програмування тісно пов'язана інша лінійна задача, яка називається двоїстою; первісне завдання називається вихідним, чи прямий. Зв'язок вихідної і двоїстої завдань полягає, зокрема, у цьому, що рішення однієї з них можна отримати безпосередньо з рішення інший.
Змінні двоїстої задачі y i називаються об'єктивно обумовленими оцінками, чи двоїстими оцінками, чи «цінами» ресурсів, чи тіньовими цінами.
Кожна із завдань двоїстої пари фактично є самостійним завданням лінійного програмування і може бути вирішена незалежно від іншої.
Подвійне завдання стосовно вихідної складається відповідно до таких правил:
1) цільова функція вихідної задачі формулюється на максимум, а цільова функція двоїстої задачі - на мінімум, при цьому в задачі на максимум всі нерівності у функціональних обмеженнях мають вигляд (), у задачі на мінімум - вид ( );
2) матриця А, складена з коефіцієнтів при невідомих у системі обмежень вихідної задачі, і аналогічна матриця А Т у двоїстої задачі виходять один з одного транспонуванням;
3) число змінних у двоїстої задачі дорівнює числу функціональних обмежень вихідної задачі, а кількість обмежень у системі двоїстої задачі - числу змінних у вихідній задачі;
4) коефіцієнтами при невідомих у цільовій функції двоїстої задачі є вільні члени в системі обмежень вихідного завдання, а правими частинами в обмеженнях двоїстого завдання - коефіцієнти при невідомих цільовій функції вихідної задачі; j 0.
Дві наведені завдання утворюють пару симетричних подвійних завдань. Основні твердження про взаємно двоїсті завдання містяться у двох наступних теоремах.
Перша теорема двоїстості. Для взаємно двоїстих завдань має місце одне із взаємовиключних випадків.
1. У прямій та двоїстій задачах є оптимальні рішення,
при цьому значення цільових функцій на оптимальних рішеннях
збігаються
2. У прямій задачі допустима множина не порожня, а цільова функція на цій множині не обмежена зверху. При цьому у двоїстої задачі буде порожня допустима множина.
3. У двоїстої задачі допустима множина не порожня, а цільова функція на цій множині не обмежена знизу. При цьому у прямої задачі допустима множина виявляється порожньою.
4. Обидві з цих завдань мають порожні допустимі множини.
Друга теорема двоїстості (теорема про доповнювальну нежорсткість). Нехай = ( x 1 ,х 2,..., х п) - допустиме рішення прямої задачі, a = (у 1, у 2, ..., у т) - допустиме рішення двоїстої задачі. Для того щоб вони були оптимальними рішеннями відповідно до прямої та двоїстої задач, необхідно і достатньо, щоб виконувались наступні співвідношення:
Умови (1.4) і (1.5) дозволяють, знаючи оптимальне рішення однієї із взаємно двоїстих завдань, знайти оптимальне рішення іншого завдання.
Розглянемо ще одну теорему, висновки якої будуть використані надалі.
Теорема про оцінки. Значення змінних y i в оптимальному розв'язанні двоїстої задачі є оцінкою впливу вільних членів b i системи обмежень (нерівностей) прямої задачі на величину
Вирішуючи ЗЛП симплекс-методом, ми одночасно вирішуємо подвійну ЗЛП. Змінні двоїстої задачі y i називають об'єктивно зумовленими оцінками.
Розглянемо економічну інтерпретацію двоїстої задачі з прикладу завдання про килимах.
Приклад 1 .2. Використовуючи постановку завдання про килими, виконати такі завдання.
1. Сформулювати економіко-математичну модель завдання про килимах на максимум загальної вартості продукції, використовуючи дані табл. 1.1.
2. Використовуючи Пошук рішення, знайти такий план випуску продукції, за якого загальна вартість продукції буде максимальною.
3. Сформулювати економіко-математичну модель двоїстої задачі до задачі про килими.
4. Знайти оптимальний план двоїстої задачі, використовуючи теореми двоїстості, пояснити рівність нулю Х1 і Х4.
5. Використовуючи протоколи пошуку рішення, виконати аналіз отриманого оптимального рішення вихідного завдання.
6. Визначити, як зміниться загальна вартість та план випуску продукції зі збільшенням запасу ресурсу труб на 12 од.
1. Сформулюємо економіко-математичну модель завдання.
Позначимо через Х1, Х2, Х3, Х4 число килимів кожного типу. Цільова функція має вигляд
F(X) = ЗХ 1 + 4Х 2 + ЗХ 3 + Х 4 max,
а обмеження щодо ресурсів
7Х 1 + 2Х 2 + 2Х 3 + 6Х 4 80,
5Х 1 + 8Х 2 + 4 Х 3 + ЗХ 4 480,
2Х 1 + 4 Х 2 + Х 3 + 8X 4130,
Х 1, X 2, X 3, Х 4 0.
2. Пошук оптимального плану випуску.
Вирішення задачі виконаємо за допомогою надбудови Excel Пошук рішення. Технологія розв'язання задачі була детально розглянута у задачі про костюми. У нашому завданні оптимальні значення вектора Х=(Х 1 , X 2 , X 3 , Х 4) будуть поміщені в осередках ВЗ:ЕЗ, оптимальне значення цільової функції - в осередку F4.
Введемо вихідні дані. Спочатку опишемо цільову функцію за допомогою функції – СУММПРОИЗВ (рис. 1.19). А потім введемо дані для лівих частин обмежень. У пошуку рішення введемо напрямок цільової функції, адреси змінних, додамо обмеження. На екрані з'явиться діалогове вікно Пошук рішення із введеними умовами (рис. 1.20).
Після введення параметрів для вирішення ЗЛП слід натиснути кнопку Виконати. На екрані з'явиться повідомлення про те, що рішення знайдено (рис. 1.21).
Отримане рішення означає, що максимальний прибуток 150 тис. руб. фабрика може отримати при випуску 30 килимів другого виду та 10 килимів третього виду. При цьому ресурси «праця» та «обладнання» будуть використані повністю, а із 480 кг пряжі (ресурс «сировина») буде використано 280 кг.
Створення звіту за результатами пошуку рішення. Excel дозволяє надати результати пошуку рішення у формі звіту (табл. 1.4). Існує три типи таких звітів:
· Результати (Answer). До звіту включаються вихідні та кінцеві значення цільової та змінних осередків, додаткові відомості про обмеження.
· Стійкість (Sensitivity). Звіт, що містить відомості про чутливість рішення до малих змін у комірках, що змінюються, або у формулах обмежень.
· Межі (Limits). Крім вихідних і кінцевих значень змінюваних та цільових осередків, до звіту включаються верхні та нижні межі значень, які можуть приймати впливові комірки при дотриманні обмежень.