Коротка теорія
Лінійне програмування - розділ математичного програмування, застосовуваний розробки методів відшукання екстремуму лінійних функцій кількох змінних при лінійних додаткові обмеження, що накладаються на змінні. За типом розв'язуваних завдань його методи поділяються на універсальні та спеціальні. За допомогою універсальних методівможуть вирішуватись будь-які завдання лінійного програмування(ЗЛП). Спеціальні методи враховують особливості моделі завдання, її цільової функції та системи обмежень. Особливістю завдань лінійного програмування і те, що екстремуму цільова функція досягає межі області допустимих рішень.
Графічний методВирішення завдань лінійного програмування дає можливість наочно уявити їх структуру, виявити особливості та відкриває шляхи дослідження більш складних властивостей. Завдання лінійного програмування з двома змінними можна вирішити графічно. Однак уже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більша за три, графічне рішення, взагалі кажучи, неможливе. Випадок двох змінних не має особливого практичного значенняПроте його розгляд прояснює властивості обмежень ЗЛП, призводить до ідеї її вирішення, робить геометрично наочними способи рішення та шляхи їх практичної реалізації.
Якщо обмеження та цільова функція містить більше двох змінних, тоді необхідно (або методом послідовного поліпшення рішення) - він універсальний і можна вирішити будь-яку ЗЛП. Для деяких прикладних завдань лінійного програмування, таких як розроблені спеціальні методи рішення.
Приклад розв'язання задачі
Умова задачі
Підприємство випускає два види продукції: Виріб 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 ден.
Метод графічного рішення, якщо завдання з двома змінними має лінійні обмеження, а цільова функція – квадратична, детально розглянуто тут
На сторінці детально розібрано рішення задачі лінійного програмування симплексним методом, крім того, показано побудову двоїстої задачілінійного програмування та знаходження її рішення щодо вирішення прямої задачі.
Транспортне завдання та метод потенціалів
Докладно розглянуто транспортне завдання, її математична модель та методи вирішення – знаходження опорного плану методом мінімального елемента та пошук оптимального розв'язання методом потенціалів.
Випукло програмування – графічний метод
Наведено зразок розв'язання задачі опуклого квадратичного програмування графічним методом.
Графічні методи пов'язані перш за все з геометричним зображеннямфункціональної залежності за допомогою ліній на площині. Графіки використовуються для швидкого знаходження значення функцій за відповідним значенням аргументу, для наочного зображення функціональних залежностей.
В економічному аналізі використовуються майже всі види графіків: діаграми порівняння, діаграми часових рядів, криві розподіли, графіки кореляційного поля, статистичні картограми. Особливо поширені в аналізі діаграми порівняння - порівняння звітних показників з плановими, попередніх періодів і передових підприємств вітчизняних чи зарубіжних. Для наочного зображення динаміки економічних явищ (а в аналізі з динамічними рядамидоводиться мати справу дуже часто) використовуються діаграми часових рядів.
За допомогою координатної сітки будуються графіки залежності, наприклад, рівня витрат від обсягу виробленої та реалізованої продукції, а також. графіки, на яких можна зображати кореляційні зв'язки між показниками. У системі осей координат зображення показує вплив різних чинників той чи інший показник.
Широко застосовується графічний метод на дослідження виробничих процесів, організаційних структур, процесів програмування тощо. буд. Наприклад, для аналізу ефективності використання виробничого устаткування будуються розрахункові графіки, зокрема графіки множинних чинників.
Позначення: кожне коло вважається однією з вершин графіка; цифра у верхньому секторі кожної вершини означає її порядковий номер; нз номерів двох сусідніх вершин складається шифр роботи; цифра в нижньому секторі кожної вершини є порядковим номеромпопередньої вершини, а лінія, що з'єднує ці дві вершини, означає певну роботу. Внизу під лінією записана планова тривалість цієї роботи; цифра у лівому секторі кожної вершини означає загальну тривалість усіх попередніх робіт, цифра у правому секторі відрізняється від цифри у лівому на величину резерву (запасу часу). Таким чином, для вершин, що лежать на критичному шляху, цифри в лівому та правому секторах вершини збігаються, оскільки запас часу дорівнює 0.
У математично формалізованій системі аналізу, планування та управління особливе місце посідають мережеві графіки. Вони дають великий економічний ефект при будівництві та монтажі промислових та інших підприємств.
Мережевий графік (рис. 6.1) дозволяє виділити з усього комплексу робіт найважливіші, що лежать на критичному шляху, і зосередити на них основні ресурси будівельно-монтажних організацій, встановлювати взаємозв'язок між різними спеціалізованими організаціями та координувати їхню роботу. Роботи, що лежать на критичному шляху, потребують найтривалішого очікування надходження чергової події. На стадії оперативного аналізута управління мережевим графіком дає можливість здійснювати дієвий контроль за ходом будівництва, своєчасно вживати заходів щодо усунення можливих затримокв роботі.
Застосування мережевих графіківаналізу, планування та управління забезпечує, як показують багато прикладів, скорочення термінів будівництва на 20-30%, підвищення продуктивності праці на 15-20%.
При аналізі, що здійснюється безпосередньо на будівництві, використання матеріалів мережевого плануваннята управління сприяє правильному визначеннюпричин, які впливають перебіг будівництва, і виявлення підприємств, які забезпечують виконання доручених їм робіт чи постачання устаткування терміни, встановлені графиком.
Розробка мережного графіка у будівництві здійснюється за наявності: норм тривалості будівництва та строку введення в дію об'єкта або комплексу об'єктів, проектно-кошторисної документації, проекту організації будівництва та виконання робіт, типових технологічних карт, діючих норм витрат праці, матеріалів та роботи машин Крім того, при складанні графіка використовуються досвід виконання окремих робіт, а також дані про виробничу базу будівельних та монтажних організацій.
На основі всіх цих даних складається таблиця робіт і ресурсів, де в технологічній послідовності виконання робіт вказуються їх характеристика, обсяг, трудомісткість у людино-днях, виконавець (організація та бригада), чисельність робітників, змінність, потреба в механізмах та матеріалах, джерела їх надходження , загальна тривалість виконання роботи у днях, а також попереднє завдання, після закінчення якого можна починати цю роботу. Виходячи з показників такої таблиці, готують мережевий графік, який може мати різний ступінь деталізації в залежності від прийнятої схеми виробництва.
ведення робіт та рівня керівництва; крім загального графікавиконавці розробляють графік виконуваних ними робіт.
Основні елементи мережного графіка: подія, робота, очікування, залежність.
При аналізі ходу будівництва об'єкта слід встановлювати, чи правильно складено мережевий графік, чи не допущено при цьому завищення критичного шляху, чи враховані при оптимізації графіка всі можливості його скорочення, чи не можна якісь роботи виконувати паралельно або скоротити час, що витрачається на них шляхом збільшення коштів механізації та інших. Це особливо важливо у випадках, коли тривалість робіт за графіком не забезпечує закінчення будівництва вчасно.
Основним матеріалом мережевого планування, що використовується при аналізі, є інформація про хід робіт за графіком, який зазвичай складається не рідше одного разу на декаду. Як приклад наводиться карта завдання та інформації про хід роботи з об'єкта будівництва, який здійснюється за мережевим графіком (табл. 6.1). За даними карти, критичні роботи виконувались на початку місяця з випередженням графіка, проте потім було допущено відставання монтажу балок підкранових по ряду Б, а подальша робота - монтаж балок підкранових по ряду А - закінчена з відставанням на один день.
Оптимізація мережевих графіків складає стадії планування у вигляді скорочення критичного шляху, т. е. мінімізації термінів виконання будівельних робіт при заданих рівнях ресурсів, мінімізації рівня споживання матеріальних, трудових і фінансових ресурсів при фіксованих термінах виконання будівельних робіт. Можливий і змішаний підхід: для однієї частини робіт (дорожчих) - мінімізувати рівень споживання ресурсів за фіксованих термінів виконання робіт, для іншої - мінімізувати терміни при фіксованому рівні ресурсів.
Вирішення оптимізаційних завдань суттєво полегшується наявністю пакетів прикладних програм(ППП), пристосованих до упорядкування оптимальних мережевих графіків на ЕОМ.
У зарубіжній практиці системного аналізупоширений графо-математичний метод, який одержав назву «дерево рішень». Суть цього методу полягає у наступному.
Шляхом попередньої оцінкипотреб, попереднього аналізу можливих організаційних, технічних чи технологічних умов намічаються всі передбачувані варіанти вирішення цього завдання. Спочатку розробляються
| | Завдання | | Інформація | Резерв часу по роботам | Чис ти |
|||||||
| Найменування робіт | шифр | дата початку | дата закінчити | планова продов | Ре зерв брехня | % тих- | необхідний час для | при чину | фактична дата | знаходячи щимся | не перебувають | резерв часу з |
| | робіт | робіт (план) | ня робіт (план) | житель ність, днів | мені | кой готовий ності | закінчити ня робіт, днів | задер жки | закінчити ня робіт | на критичному шляху | аа критичному шляху | початку місяця, днів |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Розробка ґрунту | 1-2 | 1/IV | 6/IV | 5 | 0 | 100 | - | - | 6/IV | ¦- | - | - |
| Бетонування фундаментів під котли | 2-3 | 7/IV | 17/1V | 9 | 0 | 100 | 14/IV | 2 | 2 |
|||
| Бетонування фундаментів по ряду А | 2-4 | 7/IV | 14/1V | 7 | 2 | 100 | 14/IV | | | |
||
| Те саме по ряду Б | 2-5 | 7/IV | 14/IV | 7 | 2 | 100 | - | - | 14/IV | | | |
| Влаштування трубної розводки | 6-18 | 18/IV | 21/IV | 4 | 19 | 100 | - | - | 29/IV | -7 |
||
| Пристрій зворотного засипання | 6-7 | 18/IV | 19/IV | 2 | 0 | 100 | 17/IV | 2 | 2 |
|||
| Монтаж збірних залізобетонних ко | | | | | | | | | | | | |
| лонн: по ряду Б | 7-8 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | _ | - | - |
| по ряду А | 7-9 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | - | - | - |
Влаштування підкранових шляхів та монтаж баштового крана 7-10
Установка опорних рам на фундамент під обладнання 7-16 Монтаж підкранових балок:
по ряду Б 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2
по ряду А 10-12 25/IV 26/IV
Монтаж першої частини балок та плит покриття 12-13 27/IV 4/V
Монтаж підкранових колій мостового lt;3 крана 12-14 27/IV 3/V
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 0 | 100 | - | - | 22/IV | 1 | - | 1 |
| 14 | 100. | - | - | 29/IV | - | -5 | - |
| 1 | 100 | за- | 27/IV | -2 |
27/IV -1
тримка з поставкою з/б конструкцій
- 100 -
укрупнені варіанти. Потім у міру введення додаткових умовкожен із новачків розчленовується ряд варіантів. Графічне зображення цих варіантів дозволяє виключити менш вигідні їх і вибрати найбільш прийнятний.
Цей метод може знайти у нас застосування щодо порядку обробки тих чи інших деталей на кількох верстатах з метою мінімізації загального часу обробки; при встановленні обсягів ресурсів для мінімізації загальних виробничих витрат; при розподілі капіталовкладень та інших ресурсів по промисловим об'єктам; при вирішенні транспортних та інших завдань.
Розв'язання задачі лінійного програмування (ЗЛП) графічним методом
Загальна постановка злп
Знайти значення n змінних x 1 , x 2 , …, x n , що доставляють екстремум (мінімум або максимум) лінійної функції Z = C 1 x 1 + C 2 x 2 + ... + C n x n
і одночасно задовольняють m обмежень виду
a 1,1 x 1 +a 1,2 x 2 +…+a 1,n x n£ =≥b 1 ,
a 2,1 x 1 +a 2,2 x 2 +…+a 2,n x n£ = ≥b 2 ,
. . . . . . . . . . . . . . . . . . . . . . .,
a m,1 x 1 +a m,2 x 2 +…+a m,n x n£ = ≥b m ,
при заданих a i, j, b i, C j (i=1,2,…,m; j=1,2,…,n). Знак відношення може набувати будь-якого з трьох наведених значень.
Приклад задачі лінійного програмування
Розглянемо таке завдання. Менеджер підприємства, що виготовляє два види фарб, описав досліднику операцій ситуацію, що склалася на виробництві та ринку збуту фарб. Виявилося, що фабрика виготовляє два види фарб: для внутрішніх та зовнішніх робіт. Обидві фарби надходять до оптового продажу. Для виробництва фарб використовуються два вихідні продукти - А і В. Максимально можливі добові запаси цих продуктів 6 і 8 тонн відповідно. Досвід показав, що добовий попит на зовнішню фарбу ніколи не перевищує попит на внутрішню більш ніж 1 тонну. Крім того, встановлено, що попит на зовнішню фарбу ніколи не перевищує 2 тонни на добу. Оптові ціни однієї тонни фарб склалися так: 3 тисячі рублів на зовнішню фарбу та 2 тисячі рублів – на внутрішню. Яку кількість фарби кожного виду має виробляти фабрика, щоб дохід від реалізації був максимальним?
Щоб розв'язати поставлене перед дослідником завдання, спочатку необхідно розробити математичну модель описаної ситуації.
При побудові математичної моделі фахівець із дослідження операцій ставить собі три питання.
- Для яких величин має бути побудована модель? Інакше висловлюючись, потрібно ідентифікувати змінні завдання.
- Які обмеження повинні бути накладені на змінні, щоб виконувались умови, характерні для системи, що моделюється?
- У чому полягає мета, для досягнення якої з усіх можливих (допустимих) значень змінних потрібно вибрати ті, які відповідатимуть оптимальному (найкращому) розв'язанню задачі?
Введемо змінні:
x 1 – добовий обсяг виробництва зовнішньої фарби (у тоннах),
x 2 – добовий обсяги виробництва внутрішньої фарби (в тоннах).
Враховуючи оптові цінина тонну кожного виду фарби, добовий дохід від продажу виробленої продукції визначається лінійною цільовою функцією Z = 3x 1 + 2x 2 .
Метою виробництва є отримання максимального прибутку, отже необхідно знайти значення x 1 і x 2 , які максимізують цільову функцію Z.
Оскільки виробник фарб неспроможна розпорядитися значеннями змінних довільним чином, остільки необхідно виділити безліч можливих значень цих змінних, що визначається конкретними умовами виробництва та збуту. Це безліч називається областю допустимих значень.
Перший тип обмежень визначається запасами продуктів А та В, з яких виробляються фарби. З технології виробництва відомо, що виробництво тонни зовнішньої фарби йдуть дві частини продукту А, але в тонну внутрішньої – одна частина. Для продукту співвідношення зворотне. Ці технологічні умовиописуються нерівностями
2x 1 + x 2 £ 6 (на складі 6 тонн продукту А),
x 1 + 2x 2 £ 8 (на складі 8 тонн продукту).
Останні два обмеження означають очевидну обставину: не можна використовувати для фарб більше товарів А і В, ніж їх є практично на складі.
Ситуація з реалізацією фарб на ринку призводить до наступних обмежень: x 1 – x 2 £ 1 (зовнішньої фарби реалізується не більше ніж на одну тонну більше внутрішньої), x 1 £ 2 (зовнішньої фарби продається не більше двох тонн на день).
Підсумовуючи все сказане, можна математичну модель, що описує виробничу ситуацію, що склалася, задати в наступній формі:
знайти® max( Z=2× x 1 + 3× x 2 ) при наступних обмеженнях на значення змінних x 1 та x 2
2 × x 1 + x 2 £ 6 обмеження (1),
X 1 + 2 × x 2 £ 8 обмеження (2),
X 1 - x 2 £ 1 обмеження (3),
X 1 £ 2 обмеження (4)
та вимога невід'ємності змінних x 1 ³ 0 (5), x 2 ³ 0 (6).
Отримана математична модельє завданням лінійного програмування.
Графічний метод розв'язання злп
Графічний метод рішення злп може бути реалізований лише у двовимірному випадку.
Математична модель, отримана для сформульованої типового завдання, вимагає дослідження, оскільки заздалегідь не відомо, чи має вона (як математична задача) Рішення. Дослідження проведемо з використанням графічних побудов. Одночасно з таким дослідженням знайдемо (якщо воно є) та рішення.
1 етап. Побудова області допустимих рішень
Ціль – побудувати область, кожна точка якої задовольняє всім обмеженням.
Кожне з шести обмежень геометрично задає напівплощину. Для того, щоб її збудувати, потрібно:
- · Замінити в обмеженні знак нерівності на рівність (отримаємо рівняння прямої);
- · Побудувати пряму по двох точках;
- · Визначити, яку напівплощину задає знак нерівності. Для цього підставити в нерівність якусь точку (наприклад, початок координат). Якщо вона задовольняє нерівності – зафарбовуємо напівплощину, що її містить.
Такі дії виконуємо всім обмежень. Кожну з прямих позначимо номерами, прийнятими під час нумерації обмежень (див. рис).
Областю допустимих рішень (задовольняє всім обмеженням) є безліч точок першого квадранта координатної площини (x 1 , x 2), що являє собою перетин всіх напівплощин, що визначаються нерівностями обмежень.
Безліч точок, що задовольняють усім шести обмежень завдання – багатокутник AFEDCB.
2 етап Побудова ліній рівня цільової функції та визначення точки максимуму
Ціль - знайти в побудованому багатокутнику AFEDCB точку, в якій функція мети Z = 2x1 + 3x2 приймає максимальне значення.
Проведемо пряму 2x1+3x2=Сonst (лінію рівня) так, щоб вона перетинала багатокутник AFEDCB (наприклад, Const=10). Ця лінія рівня малюнку зображена пунктирною лінією.
Якщо розглядати значення лінійної цільової функції Z на множині точок (x 1, x 2), що належать відрізку пунктирної прямої, розташованому всередині шестикутника, всі вони рівні одному й тому ж значенню (Const = 10).
Визначимо напрямок зростання функції. Для цього побудуємо лінію рівня з більшим значенням. Це буде пряма, паралельна з побудованою, але розташована правіше. Значить, у заданому напрямку значення цільової функції зростає, і в наших інтересах зрушити її якнайдалі в цьому напрямку.
Зсув можна продовжувати доти, поки пряма, що переміщається, перетинає багатокутник допустимих рішень. Останнє положення пряме, коли вона має одну загальну точку з багатокутником AFEDCB (точка С), відповідає максимальному значеннюцільової функції Z і досягається в точці З координатами x 1 = 4/3 (» 1.333), x 2 = 10/3 (» 3.333). При цьому Z = 38/3 (12.667).
Поставлене завдання повністю вирішено. З проведених геометричних міркувань видно, що рішення єдине. Зробимо деякі узагальнення, які з геометричної інтерпретації завдання.
Перше. Область допустимих рішень – опуклий багатокутник ( Чому опуклий? Чи може область допустимих рішень бути порожньою безліччю? Крапку? Відрізок? Промінь? Пряму? Якщо так, наведіть приклад системи обмежень).
Друге. Максимум цільової функції досягається у вершині багатокутника допустимих рішень ( а чи може бути не єдине рішення? Чи може рішення не бути?)
Завдання 1 (виконати на занятті, показати викладачеві)
Вирішити графічним методом
|
А) F = 2 x 1 +3 x 2 è max При обмеженнях x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x 2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0 |
B ) F = 4 x 1 +6 x 2 è min При обмеженнях 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x 1 +6x 2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0 |
|
C ) F =3 x 1 +3 x 2 è max При обмеженнях x 1 +x 2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0 |
D ) F =2 x 1 -3 x 2 è min При обмеженнях x 1 +x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0 |
A) x1 = 6 x2 = 4 F = 24
B) x1 = 2 x2 = 3 F = 26
C) x1Î x2=8-x1 F=24
Завдання 2 (виконати на занятті, показати викладачеві)
Відповісти на питання, виділені курсивом.
Завдання 3 (домашнє)
Написати програму.
Дан текстовий файлвиду
2 3 (коефіцієнти цільової функції)
4 (кількість обмежень)
2 2 12 (обмеження)
1 2 8
4 0 16
0 4 12
Побудувати прямі так, щоб багатокутник допустимих рішень був цілком на екрані (визначення масштабу див. в кн. Онегова). Прямі можуть бути паралельні до осей!
Побудувати кілька ліній рівня цільової функції (натискаємо клавішу – пряма переміщується, відображається значення цільової функції). Відобразити масштаб.
Найбільш простим та наочним методом вирішення задачі лінійного програмування (ЗЛП) є графічний метод. Він заснований на геометричній інтерпретації задачі лінійного програмування та застосовується при вирішенні ЗЛП із двома невідомими:
Розглянемо розв'язання цього завдання на площині. Кожна нерівність системи функціональних обмежень геометрично визначає напівплощину з граничною прямою а пх, + + a j2 х 2 = b n i = 1, т.Умови невід'ємності визначають напівплощини з граничними прямими х (= 0, х 2= 0 відповідно. Якщо система спільна, то напівплощини, перетинаючи, утворюють загальну частину, яка є опуклим безліччю і є сукупністю точок; координати кожної з цих точок є рішенням системи. Сукупність цих точок називають багатокутник рішень.Він може бути точкою, відрізком, променем, обмеженим та необмеженим багатокутником.
Геометрично ЗЛП є відшукання такої кутової точки багатокутника рішень, координати якої доставляють максимальне (мінімальне) значення лінійної цільової функції,причому допустимими рішеннями є всі точки багатокутника розв'язків.
Лінійне рівняння описує безліч точок, що лежать на одній прямій. Лінійна нерівністьвизначає деяку область на площині.
Визначимо, яку частину площини визначає нерівність 2х (+ Зх 2 12.
По-перше, побудуємо пряму 2х, + Зх 2 = 12. Вона проходить через точки (6; 0) та (0; 4). По-друге, визначимо, яка напівплощина задовольняє нерівність. Для цього вибираємо будь-яку точку на графіку, що не належить прямої, і підставляємо її координати в нерівність. Якщо нерівність виконуватиметься, то дана точкає допустимим рішенням і напівплощина, що містить точку, задовольняє нерівності. Для підстановки у нерівність зручно використовувати початок координат. Підставимо х ( = х 2 = 0 у нерівність 2х, + Зх 2 12. Отримаємо 20 + 30 
Аналогічно графічно можна зобразити всі обмеження задачі лінійного програмування.
Рішенням кожної нерівності системи обмежень ЗЛП є напівплощина, що містить граничну пряму і розташована по одну сторону від неї. Перетин напівплощин, кожна з яких визначається відповідною нерівністю системи, називається областю допустимих рішень(ОДР) або областю визначення.
Необхідно пам'ятати, що область допустимих рішень задовольняє умови невід'ємності (Xj > 0j = 1, д).Координати будь-якої точки, що належить області визначення, є допустимим розв'язанням задачі.
Для знаходження екстремального значення цільової функції при графічному рішенні ЗЛП використовують вектор-градієнт,координати якого є приватними похідними цільової функції:
Цей вектор показує напрямок якнайшвидшої зміни цільової функції. Пряма c [x l + з 2 х 2 = f(x 0),перпендикулярна вектору-градієнту, є лінією рівняцільової функції (рис. 2.2.2). У будь-якій точці лінії рівня цільова функція приймає те саме значення. Прирівняємо цільову функцію постійній величині а.Змінюючи значення а,отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня цільової функції.
Мал. 2.2.2.
Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зміщенні лінії в один бік рівень лише зростає,а при зміщенні в інший бік - тільки зменшується.
Графічний метод рішення ЗЛПскладається з чотирьох етапів:
- 1. Будується область допустимих рішень (ОДР) ЗЛП.
- 2. Будується вектор-градієнт цільової функції (ЦФ) з початком у точці х 0(0; 0): V = (с, з 2).
- 3. Лінія рівня CjXj+ з 2 х 2 = а (а -постійна величина) - пряма, перпендикулярна вектору-градієнту V, - пересувається у напрямку вектора-градієнта у разі максимізації цільової функції f(x v x 2)доти, доки залишить меж ОДР. При мінімізації /(*, х 2)лінія рівня переміщається у напрямку, протилежному вектору-градієнту. Крайня точка (або точки) ОДР при цьому русі є точкою максимуму (мінімуму) f(x p jc 2).
Якщо пряма, відповідна лінії рівня при своєму русі не залишає ОДР, то мінімуму (максимуму) функції f(xр х 2) немає.
Якщо лінія рівня цільової функції паралельна до функціонального обмеження завдання, на якому досягається оптимальне значенняЦФ, то оптимальне значення ЦФ буде досягатися в будь-якій точці цього обмеження, що лежить між двома оптимальними кутовими точками, і, відповідно, кожна з цих точок є оптимальним рішеннямЗЛП.
4. Визначаються координати точки максимуму (мінімуму). Для цього достатньо вирішити систему рівнянь прямих, що дають у перетині точку максимуму (мінімуму). Значення f(x ( , х 2),знайдене в отриманій точці є максимальним (мінімальним) значенням цільової функції.
Можливі ситуації графічного рішення ЗЛП представлені у табл. 2.2.1.
Таблиця 2.2.1
|
Вид ОДР |
Вид оптимального рішення |
|
Обмежена |
Єдине рішення |
|
Безліч рішень |
|
|
Необмежена |
ЦФ не обмежена знизу |
|
ЦФ не обмежена зверху |
|
|
Єдине рішення |
|
|
Безліч рішень |
|
|
Єдине рішення |
|
|
Безліч рішень |
Приклад 2.2.1. Планування випуску продукції пошивального підприємства (завдання про костюми).
Намічається випуск двох видів костюмів - чоловічих та жіночих. На жіночий костюм потрібно 1 м вовни, 2 м лавсану і 1 людина день трудовитрат; на чоловічий - 3,5 м вовни, 0,5 м лавсану і 1 людина день трудовитрат. Усього є 350 м вовни, 240 м лавсану і 150 человекодней трудовитрат.
Потрібно визначити, скільки костюмів кожного виду необхідно пошити, щоб забезпечити максимальний прибуток, якщо прибуток від жіночого костюма становить 10 ден. од., як від чоловічого - 20 ден. од. При цьому слід мати на увазі, що необхідно пошити щонайменше 60 чоловічих костюмів.
Економіко-математична модель задачі
Змінні: х, - кількість жіночих костюмів; х 2 -кількість чоловічих костюмів.
Цільова функція:
Обмеження:
Перше обмеження (вовна) має вигляд х (+ 3,5 х 2 х ( + 3,5 х 2 = 350 проходить через точки (350; 0) і (0; 100). Друге обмеження (по лавсану) має вигляд 2х (+ 0,5 х 2 2х х + 0,5 х 2 = 240 проходить через точки (120; 0) та (0; 480). Третє обмеження (по праці) має вигляд х у +х 2150. Пряма х (+ х 2 = 150 проходить через точки (150; 0) та (0; 150). Четверте обмеження (за кількістю чоловічих костюмів) має вигляд х 2> 60. Розв'язанням цієї нерівності є напівплощина, що лежить вище за пряму х 2 = 60.
В результаті перетину побудованих чотирьох напівплощин отримуємо багатокутник, який і є областю допустимих рішень нашого завдання. Будь-яка точка цього багатокутника задовольняє всі чотири функціональні нерівності, а для будь-якої точки поза цим багатокутником хоча б одна нерівність буде порушена.
На рис. 2.2.3 затінена область допустимих рішень (ОДР). Для визначення напрямку руху до оптимуму збудуємо вектор-градієнт V, координати якого є приватними похідними цільової функції:
Щоб збудувати такий вектор, потрібно з'єднати точку (10; 20) з початком координат. Для зручності можна будувати вектор, пропорційний вектору V. Так, на рис. 2.2.3 зображено вектор (30; 60).
Потім побудуємо лінію рівня 10xj + 20х2 = а.Прирівняємо цільову функцію постійній величині а.Змінюючи значення а, Отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня цільової функції.
Важливим методом наукового аналізу статистичного матеріалу є графічні зображення. Перші спроби використання графічних методів у економічних дослідженнях розпочалися ще 1780-х роках. Однак більш широкого застосування графічний метод отримав пізніше - у середині XVIII ст., особливо після вперше в історії зробленої статистики доповіді представника Берлінського статистичного бюро Швабе "Теорія" графічних зображень"На 8-му Міжнародному статистичному конгресі (Петербург, 1872 р.). За відомим висловом німецького фізика Ф. Ауербаха, XX ст. ознаменувалося "тріумфальною ходою графічного методу в науці".
Що таке графік? Графік – це форма наочного уявленнястатистичних даних про соціально-економічні явища та процеси через геометричні образи, малюнки або схематичні географічні карти та пояснення до них.
Графік має п'ять основних елементів загальної конструкції: поле, координатну сітку, графічні знаки та їх розміщення у полі графіка, масштаб та експлікація (рис. 10.3).
Мал. 10.3. Основні елементи графіка
Кожен із цих елементів має своє призначення та виконує відповідну роль у побудові та інтерпретації. Поле графіка - це простір, де розміщуються геометричні та інші знаки, складові графічне зображення.
Графічний образ - це сукупність різних символічних знаків, з допомогою яких відбиваються статистичні дані. Ці знаки можуть зображуватись у формах: ліній, точок, геометричних, графічних, а іноді негеометричних фігур.
Координатна сітка – це прямокутна системакоординат, у якій осі абсцис відкладається час, але в осі ординат - кількісні показники за масштабом.
Масштаб - умовна міра переведення числової величини статистичного явища в графічну та навпаки. Він служить для встановлення числових значеньявищ, виражених на графіку.
Експлікація графіка – словесне пояснення його конкретного змісту, яке зазвичай включає:
1) заголовок із необхідними додатковими поясненнями;
2) точне пояснення сутності, умовно надається в даному графікуйого графічним знакам (геометричним, образотворчим, фоновим, суто умовним)
3) інші пояснення, примітки тощо.
Крім того, на полі графіка можна наносити деякі додаткові відомостінаприклад числові дані, які позначаються у деяких графічних знаків і повторюють у цифровій формі їх точні значення, виражені графічно.
Графіки грають особливо важливу рольу вивченні складних взаємозв'язків соціально-економічних явищ і процесів, виявленні тенденцій, закономірностей та зміни показників динаміки, а також у поточному аналізі. Основними відмінностями та перевагами графічного методу порівняно з іншими є: найкраща наочність; можливість загалом охопити дані досліджуваних; можливість вираження деяких аналітичних залежностей, які не дуже чіткі та важкі для виявлення за інших способів подання даних.
За допомогою графіків можна здійснювати оперативний контроль за виробництвом, реалізацією продукції, виконанням договірних зобов'язань та поставлених завдань. Таким чином, графіки призначені:
Для узагальнення та аналізу даних;
Зображення розподілу даних;
Виявлення закономірностей розвитку досліджуваних явищ та процесів у динаміці;
Відображення взаємозв'язків показників;
Здійснення контролю за виробництвом, виконанням договорів щодо збуту продукції тощо.
Існують різні класифікації графіків - за формою графічних образів, за змістом, характером поставлених завдань.
За формою графічних образів розрізняють наступні типиграфіків:
1) точкові;
2) лінійні;
3) площинні;
4) об'ємні;
5) художні (образотворчі, умовні).
У точкових графіках обсяг сукупності виражається або однією точкою, або накопиченням точок. Одна точка може означати один випадок чи кілька (наприклад, один завод, 500 працівників).
Лінійні графіки складаються з одних ліній: відрізків прямих, ламаних, ступінчастих, плавних кривих (переважно передачі динаміки сукупності). Часто відрізки прямої замінюють смужками однакової ширини, які виступають також як графічні знаки та одним виміром (довжиною). У разі графіки називають стовпчикової, якщо смужки розміщені вертикально, або стрічковими, коли смужки лежать горизонтально.
У свою чергу колонці графіки діляться на колонці діаграми: прості і суцільні, з груп стовпчиків і т.д., а стрічкові - на стрічкові діаграми: прості та ступінчасті, компонентні парні, ковзаючі, двосторонньо спрямовані (наприклад, "вікова піраміда" складу населення) .
До спеціальним видамлінійних графіків відносяться спіральні (для явищ, які необмежено розвиваються в часі і за наростаючою величиною), радіальні діаграми (для відображення закономірностей явищ, що періодично повторюються, їх ритмічності, сезонності).
Площинні графіки – це графіки двох вимірів у вигляді площин різних геометричних форм. Залежно від цього можуть бути квадратними, круговими, секторними. Ці графіки доцільно використовуватиме порівняння явищ, представлених абсолютними і відносними величинами.
Важливими особливостями площинних графіків є двовимірний знак Варзара, стрічкова або поточна діаграма і балансова діаграма.
Двовимірний "знак Варзара" (на ім'я його винахідника російського статистика В.Є. Варзара) - це прямокутник з основою а висотою Ь і площею Sab, який є корисним для графічного вираження досить частих подібних співвідношень трьох величин a, by S.
Стрічкова, або поточна, діаграма застосовується для схематичного вираження обсягу та складу вантажопотоків між двома пунктами в одному та другому напрямках.
Балансова діаграма - це двостороння стрічкова діаграма, стрічки якої розгалужуються у дві сторони на вужчі смужки, своєю шириною виражають відповідні величини статей доходів та витрат, статей активу та пасиву тощо.
Об'ємні - тривимірні графіки, які використовуються рідко, оскільки вони менш виразні в порівнянні з лінійними та площинними.
Художні (образотворчі, умовні) - графіки з умовними графічними знаками, що відбивають сукупності чи її окремі значення як фігур людей, контурів тварин, схематичних малюнків предметів тощо.
Велике значення має класифікація графіків за змістом. З огляду на це графіки поділяються на два класи - діаграми та статистичні карти.
Діаграма - це графічне вираження обсягів та особливостей однієї чи кількох сукупностей з допомогою кількісних графічних знаків (геометричних, художніх, фонових, суто умовних).
Однак діаграма не дає графічного уявленнятериторіальне розміщення зображуваних сукупностей або територіальну зміну їх ознак. Для цього використовуються статистичні карти, які призначені для зображення територіального розміщення сукупностей або територіальної зміни їх ознак. Вони поділяються на два класи - картограми та картодіаграми.
Картограми - контурні географічні карти, у яких з допомогою графічних знаків представлена кількісна територіальна характеристика сукупності.
Картодіаграми - контурні географічні карти, де окремі райони (області, пункти) території нанесені однакового виду діаграми (одна чи кілька), що зображують обсяг та територіальні особливості однотипних сукупностей у цих районах. Так, наприклад, зображуються потоки вантажів, пасажирів, що перевозяться, населення, мігрує тощо.
Діаграми та статистичні карти виконують такі важливі завданняз дослідження сукупності:
Загальне порівняння;
Вивчення структури;
Вивчення динаміки;
Вивчення взаємозв'язків їх ознак;
Вимірювання ступеня виконання господарських планів, договірних зобов'язань у планово-економічній практиці.
У свою чергу і діаграми, і картограми залежно від їхнього призначення діляться на підкласи, групи та форми (табл. 10.27).
При побудові графіків слід дотримуватися таких вимог:
1) спиратися на достовірні числові дані;
2) графіки повинні бути значущими за задумом та цікавими за змістом;
3) повинні бути побудованими відповідно до поставлених завдань та їх практичного призначення;
4) бути гранично економними - містити максимум відомостей, ідей при мінімумі засобів їхнього графічного вираження, простими, чіткими, зрозумілими;
5) технічно добре виконаними.
Розглянемо докладніше основні види та форми діаграм та статистичних карт, які найчастіше використовуються у практиці аналітичної роботи.
Лінійна діаграма - один із найпоширеніших видів графіків, який служить для зображення динаміки досліджуваних явищ. Для його побудови використається прямокутна система координат. На осі абсцис відкладають рівні відрізки - періоди часу (дні, місяці, роки тощо. п.), але в осі ординат - прийнято масштаб, характеризує одиниці виміру. На координатному полі наносять точки, що дорівнює величині показника на певний період. Потім всі точки з'єднуються прямими лініями, внаслідок чого отримують ламану лінію, яка характеризує зміну явища, що вивчається, за певний період часу (табл. 10.28, рис. 10.4).
|
Підклас |
Різновиди та графічна форма, найчастіше зустрічається |
||
|
Діаграми |
І. Діаграми загального порівняннясукупностей |
1. однорідних сукупностей |
Колонки, стрічкові, художні |
|
2. Різнорідних сукупностей |
Колонці, стрічкові, площинні |
||
|
ІІ. Діаграми структури |
1. Діаграми розподілу чисельності |
Полігон, гістограма, кумулята, огива, крива розподілу, графік Лоренца, кореляційне поле |
|
|
2. Діаграми груп |
Діаграми зі стовпчиків, стрічок, поділених на абсолютні або відсоткові частини, секторні, балансові діаграми, «вікова піраміда» та ін. |
||
|
ІІІ. Діаграми динаміки |
1. Діаграми динаміки обсягів |
Колонці, лінійні, кумулятивні, спіральні, художні діаграми |
|
|
2. Діаграми динаміки структури |
Діаграми зі стовпчиків з відсотковим розподілом, по колах з розподілом на сектори та ін. |
||
|
3. Діаграми сезонних коливань |
Лінійні, стовпчикові, радіальні діаграми |
||
|
IV. Діаграми взаємозв'язків ознак |
1. Діаграми зміни сукупності |
Точкові, фонові |
|
|
2. Діаграми форми зв'язку |
Діаграми з ламаних або з плавних кривих |
||
|
3. Діаграми ступеня тісноти зв'язку |
Замкнуті контури кореляційного поля у вигляді ступінчастих ламаних або еліпсоподібних кривих і т.д. |
||
|
V. Діаграми виконання планів |
1. Діаграми поточного виконання |
Лінійні діаграми, графіки Ганта |
|
|
2. Діаграми виконання від початку періоду |
Кумуляти, кумулятивні графіки Ганта, графіки Лоренца |
||
|
Статистичні карти |
VI. Картограми |
1. Картограми розміщення одиниць сукупності |
Крапкові картограми |
|
2. Картограми розміщення сукупного обсягу ознаки |
Крапкові картограми |
||
|
3. Картограми зміни зведених ознак |
Крапкові, фонові картограми |
||
|
4. Ізолінійні картограми |
Лінійні картограми |
||
|
5. Центрограми |
Крапкові картограми |
Таблиця 10.28. Інвестиції в основний капітал у житлове будівництво України у 2000-2005 pp., у фактичних цінах, млн грн
Дані графіка свідчать, що обсяги інвестицій в основний капітал у житлове будівництво України у фактичних цінах зростали з 2000 до 2005 року.
Мал. 10.4. Динаміка обсягу інвестицій в основний капітал у житлове будівництво України у 2000-2005 рр., у фактичних цінах, млн грн
Планово-лінійні графіки будують на спеціально розробленій сітці, де по горизонталі відкладають одиниці часу, а по вертикалі розміщують об'єкти дослідження. Причому, кожен відрізок по горизонталі відповідає 100% виконання планового завдання. Ці відрізки поділяються на 5 рівних частин, Кожна з яких відповідає 20% планового завдання.
Ступінь виконання плану на графіці зображується двома лініями: тонкою переривчастою - за одиницю часу (день, декаду) та суцільною жирною - за звітний період загалом.
Розглянемо порядок побудови планово-лінійного графіка з прикладу.
приклад. Побудувати лінійний графіквиконання планового завдання бригадою робітників із будівельно-монтажних робіт, використовуючи дані табл. 10.29.
Таблиця 10.29. Виконання планового завдання бригадою робітників із будівельно-монтажних робіт
Графік виконання планового завдання бригадою будівельників з будівельно-монтажних робіт представлений на рис. 10.5.
Тонка безперервна лінія першого дня відповідає 90% виконання плану і займає чотири з половиною комірки, а лінія другого дня - 80% і займає чотири клітини, лінія третій день простяглася рівно на п'ять, а четвертого - на п'ять осередків (100%) плюс ще додатковий. нижчий відрізок, який займає 20% і т.п.
Зображення рівня виконання плану наростаючим підсумком потребує деяких додаткових розрахунків. Так, за перший день суцільна жирна лінія буде такою довжиною, як і тонка безперервна - 90% і займе чотири з половиною клітини. Далі слід зробити такі розрахунки: протягом двох днів фактично виконано 513 м 2 (225 + 288). З цієї суми 250 м 2 відносять до виконання плану протягом першого дня. Тоді в рахунок другого дня залишиться 263 м2, що згідно з планом у цей день становить 91% (263 288).
Відповідно до жирної лінії займає п'ять осередків першого дня і 91% другого. За три дні фактично було виконано 923 м2 (225+288+410). У рахунок виконання плану перших двох днів записується 610 м 2 , а рахунок третього дня - 313 м 2 , що згідно з планом на цей день становить 76% (313: 410). Жирна лінія займе по 5 осередків першого та другого днів та 76% третього. Аналогічно проводяться подальші розрахунки. Ступінь виконання плану щодня на жирної лінії позначається точками.
Колонці діаграми- дуже поширений вид графіків в одному вимірі завдяки їхній наочності та простоті. Статистичні дані в них зображуються у вигляді прямокутників однакової ширини, що розташовані вертикально по горизонтальній прямій (рис. 10.6).
Висота стовпчиків має відповідати величині зображених явищ. Якщо ж стовпчики розміщують горизонтально, такий графік називається стрічковим (рис. 10.7).
Колонці та стрічкові діаграми дозволяють порівнювати величини різного значення, характеризувати те саме явище в динаміці; характеризувати сукупність.
Секторні діаграми (або кругові) – діаграми, призначені для відображення структури досліджуваних явищ та процесів. Вони зображуються у вигляді кола, розділеного на сектори, величини яких відповідають розмірам явищ, що зображаються (рис. 10.8).
Як свідчать дані графіка (рис. 10.8), основним джерелом фінансування лізингових операцій в Україні є банківські кредити(80,9%), потім – власні кошти (16,1%). Позикові кошти юридичних осібстановлять лише 3,6%.
Мал. 10.6. Динаміка обсягу інвестицій в основний капітал у житлове будівництво України у 2000-2005 pp., у фактичних цінах, млн грн
Мал. 10.7. Динаміка обсягу інвестицій в основний капітал у житлове будівництво України у 2000-2005 pp., у фактичних цінах, млн грн
У сучасних умовахрозвитку інформаційно-комп'ютерних систем з'явилася можливість будувати графіки за допомогою пакетів комп'ютерних програм, у тому числі електронних таблиць EXCEL, "Statistica-6" та ін. Вони зручні у використанні та значно спрощують цю роботу.
Мал. 10.8. Структура джерел фінансування лізингових операцій в Україні на початок 2005 p., %
