Системи лінійних нерівностей і лінійне програмування

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Системи лінійних нерівностей і лінійне програмування

Будь-яке значення вигляду f(x)<g(x) або f(x) ?g(x), де f(x) і g(x) Ї деякі функції, називається нерівністю з одним невідомим x.

Функція f(x) називається лівою, а g(x) правою частиною нерівності.

Нерівності вигляду f(x)<g(x) називаються строгими, а нерівності f(x) ?g(x) нестрогими.

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

Вимога «розв'язати дану нерівність» означає знайти всі розв'язки цієї нерівності або показати, що вона взагалі немає розв'язків

Нерівності можуть бути таких видів

- нерівність вигляду ax+b>px+g, або ax+b ?px+g, де a, b, p, g Ї деякі числа, називаються лінійними.

- нерівності вигляду axІ+bx+c>0, або axІ+bx+c<0, де a, b, c Ї деякі числа, причому а?0, називається квадратичними

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

- нерівність виду >b або <b де а і b деякі дійсні числа (a>0, a?1) називаються показниковими.

- нерівності виду logax>b або logax<b де a і b деякі числа (a>0, a?1) називаються логарифмічними.

Нерівності можуть входити і в системи.

Дві нерівності виду:

ax+b>0 ax+b>0

a1x+b1<0 a1x+b1>0

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

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

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

Однією з них була теорія, створена швейцарським економістом XIXст. Леоном Вальрасом (1834-1910 р.р.), який заклав основи загальної економічної рівноваги. Згідно з цією теорією між відповідними величинами, в економіці існує багатосторонній взаємозв'язок, який можна описати системою взаємовідносин між ними. У сучасній літературі з економіки математичні моделі називають моделями конкурентної рівноваги за Вальрасом. І най простіші розрахунки математичні розрахунки в економіці використовують за допомогою мікрокалькуляторів, або усних підрахунків, при складних розрахунках використовуються комп'ютери. В основі таких дій лежить або виражені формулами співвідношення між об'єктами, або логічні висновки. За аналогією фізичними моделями, що відображають зв'язок між природничими об'єктами, формули, за допомогою яких здійснюються розрахунки в теорії економіки, називають економіко-математичними моделями (ЕММ).

Наприклад: витрати виробництва k(x) однорідної продукції є функцією кількості продукції х. Якщо витрати виробництва і кількість продукції змінюються пропорційно, то відношення S=, де ?КЇ приріст витрат, а ?ХЇ приріст кількісної продукції, є величиною сталою, і її можна трактувати як витрати на одиницю продукції.

Відношення S= залишається незмінним незалежно від кількості виробленої продукції.

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

Послідовність використання економіко-матеметичної моделі при розв'язуванні задачі з економіки така:

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

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

- за допомогою математики проводиться аналіз моделі, внаслідок чого одержується розв'язок;

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

У 20-30 роках ХХст. американський економіст Василь Леонтьєв поклав початок систематизованому дослідженню структури економіки в її частково розукрупненому вигляді. При такому підході виробничі процеси в економіці розукрупнюються до рівня N секторів(галузей) виробництва, хоча й не до рівня окремих підприємств або фірм, та аналізуються переміщенням продуктів, товару, послуг між усіма галузями. Зазначимо, що «чиста галузь» є ділянкою економічною абстракцією. Вона не обов'язково існує у вигляді деякого міністерства чи об'єднання.

Основні припущення теорії Леонтьєва такі:

- В економічній системі виробляється, купляється, споживається та інвестується n видів продукції, які позначаються індексами 1,2,… n;

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

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

У моделі Леонтьєва такий характер перетворень можна описати так: якщо для виробництва одиниці продукції в у-й треба витратити Aiy одиниць і-ї продукції, то випуск л одиниць у-ї потребує витрат лАіу одиниць і-ї продукції (і=1,2,… n). Ці n2 величин Aiy називають витратними коефіцієнтами. Припускається, що вони сталі.

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

Позначимо кінцеву продукцію через Ху тобто частину, що була спожита у невиробничій сфері для створення запасів, інвестицій, експорту тощо, то систему рівнянь n

Xi- = Ху (і=1,2,… n), яку

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

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

Тобто норми витрат Аіу, валовий випуск Xi, та обсяги кінцевої продукції Ху задовольняють умову Аіу ?0, Xi?0, Ху?0 (і, у=1,2,… n)

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

З економічної точки зору наявність системи розв'язку рівнянь означає, що вона «працює» тобто модель Леонтьєва продуктивна.

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

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

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

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

- лінійного та нелінійного програмування (залежить від вигляду невідомих математичної задачі);

- динамічного і статистичного програмування (з урахуванням чи без урахування часу)

- детермінованого та стохастичного програмування (залежить від характеру параметрів моделі)

Математична модель будь-якої оптимізаційної моделі залежить від двох складових:

-1. опису економічних технологічних зв'язків, що випливають зі змісту задачі

-2. завдання критерію ефективності її розв'язку

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

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

- задачі про складання кормового раціону

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

Дані задачі занесемо в таблицю

Складемо математичну модель, ввівши такі дані:

Х1 - кількість одиниць корму В1

Х2 - кількість одиниць корму В2

Х3 - кількість одиниць корму В3

У цих позначеннях разом із кормом тварини споживають одиниці поживної речовини відповідно: а11х1, а12х2, а13х3. Загальна кількість спожитої речовини А1 становить а11х1+а12х2+а13х3. Ця сума за умовою задачі не може бути від її мінімальної добової потреби в1. Ураховуючи це, маємо нерівність

а11х1+а12х2+а13х3?в1

Аналогічні нерівності дістанемо і для А2; А3; А4; А5.

Утворені нерівності складуть систему:

а11х1+а12х2+а13х3?в1

а21х1+а22х2+а23х3?в2

а31х1+а32х2+а33х3?в3

а41х1+а42х2+а43х3?в4

а51х1+а52х2+а53х3?в5

Вартість всіх кормів позначимо через Z=P1X1+P2X2+P3X3 (min)

До системи слід додати нерівності, що характеризують невід'ємність невідомих (оскільки від'ємна кількість спожитого корму не має змісту): х1?0, х2?0, х3?0,

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

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

- задача про використання і оцінку ресурсів;

- задача оптимального завантаження устаткування;

- задача про складання сумішей;

- задача про раціональний розкрій матеріалів.

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

Серед спеціальних задач на практиці найчастіше трапляється транспортна задача (Т.З) з різними її модифікаціями та узагальненнями.

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

Нехай на m пунктах відправлення А1, А2,… Аm зосередимо а1, а2,…, аm одиниць деякого однорідного вантажу. Цей вантаж необхідно перевезти в n пунктів призначення В1, В2,… Вn, причому в кожній з них потрібно завезти відповідно в1, в2,… вn, одиниць цього вантажу. Вартість Сіу перевезення одиниці вантажу з пункту Аі у пункт bу вважається заданою.

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

Таку задачу називають Т.З з правильним балансом (або закритою Т.З). Якщо умова порушуються, то таку задачу називають Т.З з неправильним балансом (або відкритою Т.З)

Заради простоти викладок і наочності всі дані Т.З (вартості Сіу, запаси Аі, потреби bу) заносять у спеціальну таблицю, яку називають матрицею перевезень.

Оскільки наперед невідомо, скільки вантажу потрібно перевезти з пункту Аі до пункту Вj, щоб план перевезень був оптимальним, назначимо його через Х іj. Усі невідомі занесемо в таблицю 2.

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

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

З кожного пункту відправлення до пунктів призначення відправляється така кількість вантажу:

Разом системи і складають систему обмежень ТЗ. В розгорнутому вигляді вона має вигляд

Х11+Х12+ … + Х1n= а1

Х21+Х22+ … + Х2n= а2

…. …. …. ….

Хm1+Хm2+ … + Хmn= аm

Х11+Х21+ … + Хm1= b1

Х12+Х22+ … + Хm2= b2

Х1 n +Х2 n + … + Хmn= bn

Система обмежень легко скласти, якщо скористатись таблицею. Для цього слід пам'ятати, що сума всіх Х іj розміщених в і-му рядку, дорівнює запасу аі у пункті відправлення Аі, а сума Х іj з j-го стовпця - потребі bj пункту призначення Вj.

Вартість перевезення вантажу з пункту Аі до пункту Вj дорівнює СіуХіу. Щоб знайти загальну вартість перевезення, треба взяти суму вартостей перевезення. отже, загальна вартість перевезення буде:

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

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

Слід пам'ятати, що ранг матриці системи обмежень Т.З

визначається формулою r =m +n-1, де m - кількість пунктів відправлення, а n - споживання.

Транспортні задачі можна розв'язувати різними методами:

- симплекс-метод

- діагональний метод

- метод осереднених коефіцієнтів

Размещено на Allbest.ru