Економіко математичні методи і моделі 4

þ Під терміном «дослідження операцій» ми будемо розуміти застосування математичних, кількісних методів для обгрунтування рішень у всіх областях цілеспрямованої людської діяльності.
Остаточно термін «дослідження операцій» закріпився в кінці Другої світової війни, коли в збройних силах США були сформовані спеціальні групи математиків і програмістів, в завдання яких входила підготовка рішень для командувачів бойовими діями. Надалі дослідження операцій розширило область своїх застосувань на різні галузі практики: економіка, транспорт, зв'язок і навіть охорона природи.
щоб людині прийняти рішення без ЕОМ, найчастіше нічого не треба, окрім досвіду та інтуїції. Щоправда, ніякої гарантії правильності, а тим більше оптимальності при цьому немає. Підкреслимо, що ЕОМ ніяких рішень не приймає. Рішення приймає чоловік (ОПР). А ЕОМ тільки допомагає знайти варіанти рішень. Неодмінна присутність людини (як остаточний інстанції прийняття рішень) не відміняється навіть при наявності повністю автоматизованої системи управління. Не можна забувати про те, що саме створення керуючого алгоритму, вибір одного з можливих його варіантів, є також рішення. У міру автоматизації управління функції людини переміщаються з одного рівня управління на інший - вищий. Основні етапи рішення задачі прийняття оптимальних рішень за допомогою ЕОМ показані на Рис. 2.1.

Вихідні дані

H

Об'єкт

F

Завдання

F

Модель

F

Алгоритм

F

Програма

F

ЕОМ :

Пакет прикладних програм (ППП)

H

Рішення

'
Рис. 2.1. Основні етапи рішення завдання прийняття рішення за допомогою ЕОМ.
в ибгр завдання - найважливіше питання. Які основні вимоги має задовольняти завдання? Таких вимог два:
À повинно існувати, як мінімум, два варіанти її рішення (адже якщо варіант один, значить і вибирати нема з чого);
Á треба чітко знати в якому сенсі шукане рішення має бути найкращим (хто не знає, куди йому плисти - тому немає і попутного вітру).
Вибір завдання завершується її змістовної постановкою. Коли виставляються змістовна постановка задачі, до неї залучаються фахівці в предметної області. Вони прекрасно знають свій конкретний предмет, але не завжди уявляють, що потрібно для формалізації задачі і представлення її у вигляді математичної моделі.
Хорошу модель скласти не просто. Відомий математик Р. Беллмана сказав так: «Якщо ми спробуємо включити в нашу модель занадто багато рис дійсності, то захлинемося в складних рівняннях; якщо занадто спростимо її, то вона перестане відповідати нашим вимогам». Таким чином, дослідник повинен пройти між пастками Переупрощенія і болотом переускладненою. Для виконання успіху моделювання треба виконати три правила, які, на думку древніх, є ознаками мудрості. Ці правила стосовно завдань математичного моделювання і формулюються так: врахувати головні властивості об'єкта моделювання; нехтувати його другорядними властивостями; вміти відокремити головні властивості від другорядних.
Складання моделі - це мистецтво, творчість. Древні казали: «Якщо двоє дивляться на одне і те ж, це не означає, що обидва бачать одне й те саме». І слова древніх греків: «Якщо двоє роблять одне і те ж, це не означає, що вийде одне і те ж». Ці слова повною мірою ставляться до складання математичних моделей. Якщо математична модель - це діагноз захворювання, то алгоритм - це метод лікування.
Можна виділити наступні основні етапи операційного дослідження:
À спостереження явища та збір вихідних даних;
Á постановка задачі;
 побудова математичної моделі;
à розрахунок моделі;
Ä тестування моделі та аналіз вихідних даних. Якщо отримані результати не задовольняють дослідника, то слід або повернутися на етап 3, т.e. запропонувати для вирішення завдання іншу математичну модель; або повернутися на етап 2, т.e. поставити завдання більш коректно;
Å застосування результатів досліджень.
Таким чином, операційне дослідження є ітераційним процесом, кожний наступний крок якого наближає дослідника до вирішення що стоїть перед ним проблеми. У центрі операційного дослідження знаходяться побудова і розрахунок математичної моделі.
þ Математична модель - це система математичних співвідношень, приблизно, в абстрактній формі описують досліджуваний процес або систему.
þ Економіко-математична модель - це математична модель, призначена для дослідження економічної проблеми.
Проведення операційного дослідження, побудова та розрахунок математичної моделі дозволяють проаналізувати ситуацію і вибрати оптимальні рішення з управління нею або обгрунтувати запропоновані рішення. Застосування математичних моделей необхідно в тих випадках, коли проблема складна, залежить від великої кількості факторів, по-різному впливають на її рішення.
Використання математичних моделей дозволяє здійснити попередній вибір оптимальних або близьких до них варіантів рішень за певними критеріями. Вони науково обгрунтовані, і особа, яка приймає рішення, може керуватися ними при виборі остаточного рішення. Слід розуміти, що не існує рішень, оптимальних «взагалі». Будь-яке рішення, отримане при розрахунку математичної моделі, оптимально за одним або кількома критеріями, запропонованими постановником завдання і дослідником.
В даний час математичні моделі застосовуються для аналізу, прогнозування і вибору оптимальних рішень в різних галузях економіки. Це планування і оперативне управління виробництвом, управління трудовими ресурсами, управління запасами, розподіл ресурсів, планування і розміщення об'єктів, керівництво проектом, розподіл інвестицій і т.п.
2.2. Класифікація і принципи побудови
математичних моделей
Можна виділити наступні основні етапи побудови математичної моделі:
À Визначення мети, тобто, чого хочуть домогтися, вирішуючи поставлене завдання.
Á Визначення пapaметров моделі, тобто заздалегідь відомих фіксованих факторів, на значення яких дослідник не впливає.
 Формування керуючих змінних, змінюючи значення яких можна наближатися до поставленої мети. Значення керуючих змінних є розв'язками задачі.
à Визначення області допустимих рішень, тобто тих обмежень, яким повинні задовольняти керуючі змінні.
Ä Виявлення невідомих факторів, тобто величин, які можуть змінюватися випадковим або невизначеним чином.
Å Вираз мети через управляючі змінні, параметри і невідомі чинники, т.e. формування цільової функції, званої також критерієм ефективності чи критерієм оптимальності задачі.
Введемо наступні умовні позначення:
a - параметри моделі;
x - керуючі змінні або рішення;
X - область допустимих рішень;
x - Випадкові або невизначені фактори;
W - цільова функція або критерій ефективності (критерій оптимальності).
W = W (x, a, x)
Відповідно до введених термінами, математична модель задачі має наступний вигляд:
W = W (x, a, x) ® max (min) (2.1)
x Î X
þ Вирішити завдання - це означає знайти таке оптимальне рішення x ^* Î X, щоб при даних фіксованих параметрах a і з урахуванням невідомих x факторів значення критерію ефективності W було по можливості максимальним (мінімальним).
W ^* = W (x ^*, a, x) = max (min) W (x, a, x)
x Î X
þ Таким чином, оптимальне рішення - це рішення, переважне перед іншими за певним критерієм ефективності (одному або декільком).
Перерахуємо деякі основні принципи побудови математичної моделі:
À Необхідно порівнювати точність і докладність моделі, по-перше, з точністю тex вихідних даних, якими володіє дослідник, і, по-друге, з тими результатами, які потрібно отримати.
Á Математична модель повинна відображати суттєві риси досліджуваного явища і при цьому не повинна його сильно спрощувати.
 Математична модель не може бути повністю адекватна реальному явищу, тому для його дослідження краще використовувати кілька моделей, для побудови яких застосовані різні математичні методи. Якщо при цьому виходять подібні результати, то дослідження закінчується. Якщо результати суттєво відрізняються, то слід переглянути постановку задачі.
à Будь-яка складна система завжди піддається малим зовнішніх і внутрішніх дій, отже, математична модель повинна бути стійкою (зберігати властивості і структуру при цих впливах).
За кількістю критеріїв ефективності математичні моделі діляться на однокритерійним та багатокритеріальні. Багатокритеріальні математичні моделі містять два і більше критерію.
По обліку невідомих факторів математичні моделі діляться на детерміновані, стохастичні та моделі з елементами невизначеності.
þ У стохастичних моделях невідомі чинники - це випадкові величини, для яких відомі функції розподілу і різні статистичні характеристики (математичне сподівання, дисперсія, середньоквадратичне відхилення і т.п.). Серед стохастичних характеристик можна виділити:
- Моделі стохастичного програмування, в яких або в цільову функцію (2.1), або в обмеження (2.2) входять випадкові величини;
- моделі теорії випадкових процесів, призначені для вивчення процесів, стан яких у кожен момент часу є випадковою величиною;
- Моделі теорії масового обслуговування, в якій вивчаються багатоканальні системи, зайняті обслуговуванням вимог. Також - до стохастичним моделей можна віднести моделі теорії корисності, пошуку і прийняття рішень.
þ Для моделювання ситуацій, що залежать від факторів, для яких неможливо зібрати статистичні дані і значення яких не визначено, використовуються моделі з елементами невизначеності.
þ У моделях теорії ігор завдання видається у вигляді гри, в якій беруть участь кілька гравців, які переслідують різні цілі, наприклад, організацію підприємства в умовах конкуренції.
þ В імітаційних моделях реальний процес розгортається в машинному часу, і простежуються результати випадкових впливі на нього, наприклад, організація виробничого процесу.
þ У детермінованих моделях невідомі фактори не враховуються. Незважаючи на уявну простоту цих моделей, до них зводяться багато які практичні задачі, в тому числі більшість економічних завдань. По виду цільової функції і обмежень детерміновані моделі діляться на: лінійні, нелінійні, динамічні та графічні.
þ У лінійних моделях цільова функція та обмеження лінійні по керуючим змінним. Побудова і розрахунок лінійних моделей є найбільш розвиненим розділом математичного моделювання, тому часто до них намагаються звести й інші завдання або на етапі постановки, або в процесі вирішення. Для лінійних моделей будь-якого виду і досить великий розмірності відомі стандартні методи рішення.
þ Hелінейние моделі - це моделі, в яких або цільова функція, або яке-небудь з обмежень (або усі обмеження) нелінійні по керуючим змінним. Для нелінійних моделей немає єдиного методу розрахунку. Залежно від виду нелінійності, властивостей функції і обмежень можна запропонувати різні способи рішення. Однак може трапиться і так, що для поставленої нелінійної задачі взагалі не існує методу розрахунку. У цьому випадку завдання слід спростити, або звівши її до відомих лінійним моделям, або просто лінеаризована модель.
þ У динамічних моделях, на відміну від статичних лінійних і нелінійних моделей, враховується фактор часу. Критерій оптимальності в динамічних моделях може бути самого загального вигляду (і навіть узагалі не бути функцією), однак для нього повинні виконуватися певні властивості. Розрахунок динамічних моделей складний, і для кожної конкретної задачі необхідно розробляти спеціальний алгоритм рішення.
þ Графічні моделі - Використовуються тоді, коли завдання зручно представити у вигляді графічної структури.
3. Деякі відомості з математики
3.1. Опуклі множини
Попередньо дамо деякі поняття, дуже важливі для лінійного програмування.
þ м ножество точок називається опуклими, якщо воно разом з будь-якими двома точками містить відрізок, що з'єднує ці точки. Найпростішими прикладами опуклих множин можуть служити: відрізок, трикутник, квадрат, деякі геометричні тіла, наприклад, піраміда, куб і т.д.
зауважимо, що опуклий багатокутник володіє тим властивістю, що весь розташований за одну сторону кожної з прямих, які беруть участь у її освіті.
þ в ипуклой лінійної комбінацією точок М _1, М _2, ... М _n називається будь-яка точка М така, що:
М = a ₁ M ₁ + a ₂ M ₂ + ... + A _n M _n,
де a _i ³ 0 і a ₁ + a ₂ + ... + a _n = 1.
þ Узагальнюючи сказане вище, можна сказати, що безліч точок називається опуклим, якщо разом з будь-якими своїми точками воно містить і опуклу довільну комбінацію цих точок. Оскільки довільна точка відрізку представляє собою опуклу комбінацію його кінців, то це і означає, що опукле безліч разом з двома даними точками містить весь з'єднує їх відрізок.
Очевидно, що будь-яка точка опуклого багатокутника, що лежить всередині його або в одній зі сторін, за винятком вершин, може бути представлена ​​як опукла лінійна комбінація інших точок цього багатокутника. Навпаки, вершини багатокутника не подаються у вигляді опуклої комбінації двох будь-яких інших точок. У цьому сенсі вершини багатокутника називають екстремальними точками.
þ пряма лінія називається опорною, якщо вона має з опуклим багатокутником, принаймні, одну спільну точку і весь багатокутник розташований по один бік від цієї прямої. Через кожну з вершин багатокутника можна провести нескінченну безліч опорних ліній. У просторі трьох вимірів, за аналогією з поняттям опорної прямої вводиться поняття опорної площини.
þ Опорною площиною називається всяка площину, що має з опуклим багатогранником, принаймні, одну спільну точку, причому таку, що весь багатогранник розташований по один бік від неї. Опорна площину може мати з опуклим багатогранником спільну точку (вершину багатогранника), пряму (ребро), і, нарешті, загальну межу.
3.2. Лінійні нерівності
розглянемо докладніше системи лінійних нерівностей і покажемо, що рішення їх тісно пов'язане з поняттями опуклого багатокутника і опуклого многогранника.
Для початку розглянемо нерівність з однією змінною величиною x _1, наприклад x ₁ <4. Якщо на площині провести пряму х ₁ = 4, то вона розділить всю площину на дві частини - півплощини: в одній з них, а саме зліва від прямої х ₁ = 4, лежать точки, абсциси яких менше 4, а праворуч від прямої - точки , абсциси яких більше 4. Таким чином, нерівність x ₁ <4 геометрично визначає полуплоскость (Рис.1). Розглянемо тепер нерівність з двома змінними типу 3х ₁ +4 х ₂ <12. Побудуємо пряму лінію 3х ₁ +4 х ₂ = 12. Розділимо обидві частини рівняння на 12:


з якого видно, що пряма відсікає по осях відрізки, рівні 4 і 3.
Нерівність 3х ₁ +4 х ₂ < 12 визначає собою сукупність всіх точок площини, що лежать нижче прямої, тобто в заштрихованої частини (Мал. 2).
Щоб легше було зрозуміти, яку саме полуплоскость визначає те чи інше нерівність, ми в ліву частину нерівності підставимо координати початку координат, тобто х ₁ = 0 і х ₂ = 0. Якщо нерівність задовольняється, то воно визначає ту полуплоскость, в якій лежить початок координат, в іншому випадку - іншу полуплоскость. Користуючись геометричними міркуваннями, знайти можливі рішення системи:
ì3х ₁ +4 х ₂ £ 12
íx ₁ <2
îх _1> 0 і х _2> 0
Кожне з нерівностей системи визначає полуплоскость, зазначену на Рис.3 штрихами.
Отриманий багатокутник є опуклим, бо разом з будь-якими двома точками містить весь з'єднує їх відрізок. таким чином, ми бачимо, що опуклий багатокутник можна задати аналітично, за допомогою системи лінійних нерівностей. Лінійне рівняння з трьома змінними: a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ = b ₁ визначає в просторі деяку площину, яка розсікає весь простір на два півпростору.
У зв'язку з цим нерівність a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ £ b ₁ визначає одне з півпросторів, до якого належить також і сама гранична площину. У загальному випадку, коли система нерівностей совместна, простір рішень утворює деякий опуклий багатогранник - багатогранник рішень. Окремим випадком його можуть бути: окрема грань, ребро або крапка. Останнє має місце, коли система нерівностей має одне єдине рішення. Подальші узагальнення приводять нас до розгляду m лінійних нерівностей з n невідомими. Кожне рівняння a _{i 1} x ₁ + a _{i 2} x ₂ + ... + A _in x _n = b _i є рівнянням деякої гіперплощини в n-мірному просторі, яка як би розсікає весь простір на два півпростору.
3.3. Значення лінійної форми на опуклому безлічі
Припустимо, що задана деяка система з m-лінійних нерівностей (або рівнянь) з n змінними х _1, х _2, ..., х _n. Система нерівностей у випадку спільності визначає деякий опукле безліч в n-мірному просторі, обмежений чи нескінченне (багатогранник рішень).
Припустимо далі, що нам задана деяка лінійна форма від цих змінних, що визначає функцію мети:
| = C ₁ x ₁ + c ₂ x ₂ + ... + C _n x _n
У кожній точці опуклого безлічі, тобто для кожного рішення нашої системи, лінійна форма | приймає певне значення. Виникає питання: у яких точках опуклого безлічі лінійна форма | сягає свого найбільшого і найменшого значення, якщо, звичайно, такі існують? Рішення загальної задачі лінійного програмування зводиться, таким чином, до знаходження точок опуклого безлічі, у яких задана лінійна форма досягає оптимального значення, і ми шукаємо такі точки (х _1, х _2, ..., х _n), координати яких ненегативні. Сформулюємо одне важливе твердження, що полегшує вирішення завдання.
þ У тих випадках, коли безліч рішень задачі лінійного програмування утворює опуклий багатогранник, лінійна форма досягає оптимального значення в одній з його вершин, у зв'язку з чим останні й називаються екстремальними точками.
У загальному випадку, лінійна форма | = c ₁ x ₁ + c ₂ x ₂ + ... + C _n x _n задає гіперплощина в n-мірному просторі. При | = 0 ця гіперплощина проходить через початок координат. Потім пересуваємо цю площину паралельно самій собі в напрямку вектора P перпендикулярно до цієї площини. Перша з вершин, в якій лінійна форма (гіперплощина) зустріне опуклий багатогранник, буде точкою, в якій лінійна форма досягає найменшого значення, а остання з вершин - точкою, в якій лінійна форма досягає найбільшого значення.
Може трапитися, що гіперплощина виявиться паралельної одній з граней або ребер опуклого багатогранника, і тоді лінійна форма | сягає свого найменшого або найбільшого значення в будь-якій точці, що лежить на цьому ребрі. Але й тоді вона досягає ці значення у вершині, що лежить на цьому ребрі.
Існують різні методи розв'язання задач лінійного програмування. Одним з найбільш простих і наочних методів рішення є графічний метод. Цей метод дозволяє вирішувати завдання, які призводять до систем рівнянь з двома або трьома змінними. Більшість завдань лінійного програмування призводить до систем лінійних нерівностей з великим числом змінних. Ці завдання вирішуються симплексним методом.
4. ПРИКЛАДИ ЗАВДАНЬ лінійного програмування
4.1. Транспортна задача
вугілля, що видобувається в декількох родовищах, відправляється ряду споживачів. нам відомо, скільки вугілля видобувається в кожному з родовищ, скажімо за місяць і скільки його потрібно на той самий строк кожному із споживачів. Відомі відстані між родовищами і споживачами, а також умови сполучення між ними. Враховуючи ці дані. Можна підрахувати, у що обходиться перевезення кожної тонни вугілля з будь-якого родовища в будь-який пункт споживання. Вимагається при цих умовах спланувати перевезення вугілля таким чином, щоб витрати на них були мінімальними.
Нехай для простоти задані всього 4 родовища М _1, М _2, М _3, М _4, причому їхня щомісячна видобуток становить a _1, а _2, а _3, а ₄ тонн вугілля. Припустимо далі, що це вугілля треба доставити до пунктів споживання b _1, b _2, b _3, b _4, b _5, відповідно з щомісячними потребами цих пунктів. Будемо вважати, що загальне виробництво вугілля одно сумарної потреби в ньому (збалансованість планів): a _1, а _2, а _3, а ₄ = b _1, b _2, b _3, b _4, b _5. Завдання полягає у визначенні такого плану перевезень, при якому загальна вартість перевезень була б найменшою. Позначимо через x ₁₁ кількість вугілля (в тоннах), призначене до відправлення з M ₁ в П _1; взагалі через x _ij позначимо кількість вугілля, що відправляється з родовища M _i в пункт споживання П _j. Схема перевезень прийме вигляд, зображений у таблиці 4.1.
Схема перевезень                                       таблиця 4.1

	ПН	в П 1	в П 2	в П 3	в П 4	в П 5	Всього
ПЗ							відправлено
з М 1		х 11	х 12	х 13	х 14	х 15	a 1
з М 2		х 21	х 22	х 23	х 24	х 25	а 2
з М 3		х 31	х 32	х 33	х 34	х 35	а 3
з М 4		х 41	х 42	х 43	х 44	х 45	а 4
Всього привезено		b 1	b 2	b 3	b 4	b 5

4.1

ìх 11 + х 12 + х 13 + х 14 + х 15 = b 1 ïх 21 + х 22 + х 23 + х 24 + х 25 = b 2 íх 31 + х 32 + х 33 + х 34 + х 35 = b 3 îх 41 + х 42 + х 43 + х 44 + х 45 = b 4

4.2

ìх 11 + х 12 + х 13 + х 14 + х 15 = a 1 ïх 21 + х 22 + х 23 + х 24 + х 25 = a 2 íх 31 + х 32 + х 33 + х 34 + х 35 = a 3 îх 41 + х 42 + х 43 + х 44 + х 45 = a 4

Загальна кількість вугілля, привозиться в пункт П ₁ з усіх родовищ, буде х _{11 +} х _{12 +} х _{13 +} х _{14 +} х _{15 =} b _1; в інші пункти - П _2, П ₃ і т.д. і прийме вигляд рівнянь 4.1. загальна кількість вугілля, що вивозиться з М _1, буде: х _{11 +} х _{12 +} х _{13 +} х _{14 +} х _{15 =} a _1, набуде вигляду 4.2. припускаємо, що вартість перевезення прямо пропорційна кількості перевезеного вугілля, тобто вартість перевезення x _ij тонн вугілля дорівнює:
x _{i j} = C _{i j} ^. X _{i j}
Загальна вартість S всіх перевезень буде дорівнює: (4.3)
S = c ₁₁ х ₁₁ + c ₁₂ х ₁₂ + c ₁₃ х ₁₃ + c ₁₄ х ₁₄ + c ₁₅ х ₁₅ + ... + C ₄₁ х ₄₁ + c ₄₂ х ₄₂ + c ₄₃ х ₄₃ + c ₄₄ х ₄₄ + c ₄₅ х _45.
4.2. Загальна формулювання задачі лінійного програмування
Аналогічно транспортної задачі вирішується завдання про оптимізацію розподілу ресурсів (трудових, матеріальних, фінансових) і завдання про дієту. При всьому розмаїтті, за своїм конкретним змістом кожна з них була завданням на знаходження найбільш вигідного варіанта. З точки зору математичної, в кожній задачі шукаються значення декількох невідомих, причому потрібно, щоб:
À ці значення задовольняли деякій системі лінійних рівнянь або нерівностей;
Á при цих значеннях деяка лінійна функція (лінійна форма) від цих невідомих зверталася в мінімум (максимум);
 ці значення були невід'ємними.
Завданнями такого роду і займається лінійне програмування.
þ Говорячи точніше, лінійне програмування - це математична дисципліна, що вивчає методи знаходження найменшого (або найбільшого) значення лінійної функції декількох змінних, за умови, що останні задовольнять кінцевому числу лінійних рівнянь або нерівностей. Загальна математична формулювання задачі лінійного програмування виглядає наступним чином.
Дана система лінійних рівнянь:
ìа ₁₁ x ₁ + а ₁₂ x ₂ + ... + А _{1 n} x _{n =} b ₁
ïа ₂₁ x ₁ + а ₂₂ x ₂ + ... + А _{2 n} x _{n =} b ₂
(I) í ... ... ... ... ... ... ... ...
îа _{m 1} x ₁ + а _{m 2} x ₂ + ... + А _mn x _{n =} b _m
і лінійна функція | = c ₁ x ₁ + c ₂ x ₂ + ... + C _n x _n (II).
Потрібно знайти такі невід'ємні рішення х ₁ ³ 0, х ₂ ³ 0 ... х _n ³ 0 (III) системи (I) при яких функція | приймає найменше (найбільше) значення.
Рівняння (I) називаються обмеженнями даного завдання, рівняння (II) називається лінійної формою, а рівняння (III), строго кажучи, теж є обмеженнями, однак їх не прийнято так називати, бо вони є загальними для всіх задач лінійного програмування, а не тільки конкретного завдання. Будь-яке невід'ємне рішення системи рівнянь називається допустимим. Допустиме рішення, що дає мінімум функції |, оптимальне рішення (якщо воно існує) не обов'язково єдино; можливі випадки, коли є незліченна безліч оптимальних рішень. Нарешті, саму функцію | часто називають лінійною формою або функцією цілі.
Здавалося б, тому що задача лінійного програмування ставиться як завдання мінімізації деякої функції |, то можна застосувати класичний прийом диференціального числення. Однак приватні похідні | рівні коефіцієнтам при невідомих, які в «нуль» одночасно не звертаються.
4.3. Графічна інтерпретація
рішення задач лінійного програмування
Задачу лінійного програмування (ЛП) можна вирішувати аналітичними та графічними методами. Аналітичні методи є основою для вирішення задачі на ЕОМ. Їх єдиний недолік полягає в тому, що на відміну від графічних методів, вони недостатньо наочні. Графічні методи дуже наочні, але вони придатні лише для вирішення завдань на площині, тобто коли розмірність простору К = 2. Однак, враховуючи велику наочність графічних методів, за їх допомогою розглянемо ідею розв'язання задачі ЛП на прикладі задачі розподілу ресурсів.
Однак перш ніж зайнятися рішенням, зробимо деякі зауваження. Нехай ми маємо систему m рівняння з n невідомими (I).
Можливі такі варіанти:
À Число невідомих менше, ніж число рівнянь n < m.
н апример: ì2x ₁ = 4, у цьому випадку n = 1;
îx ₁ = 5, тоді m = 2 (число лінійно незалежних рівнянь). (4.4)
Очевидно, що система (4.4) рішення не має, і вона несумісна;
Á Число невідомих дорівнює числу рівнянь n = m.
У цьому випадку система має єдиний розв'язок або не має жодного. Зауважимо, що m дорівнює числу лінійно незалежних рівнянь.
Для системи: ì2x = 10, n = 1, m = 1;
î6x = 30.
 Якщо число невідомих більше числа рівнянь, то система має незліченну безліч рішень. Нехай n > m. Наприклад:
2 x ₁ + x ₂ = 2 (4.5)
Очевидно, що це рівняння прямої, і всі значення x ₁ і x _2, що лежать на цій прямій, є рішенням рівняння (4.2). Значить рівняння (4.5) має незліченну безліч рішень.
У випадку, коли система має більше одного можливого рішення, може бути поставлена ​​задача оптимізації, суть якої в тому, що з усіх допустимих рішень, які відповідають обмеженням і граничним умовам, вибрати таке, яке надає цільової функції оптимум. Згадаймо побудова лінійних залежностей. Нехай дано рівняння:
a ₁ x ₁ + a ₂ x ₂ = b (4.6)
Перетворимо його до виду:
(4.7)
Запис (4.7) називають рівнянням прямої у відрізках, що зображено на Рис. 4.1. Розглянемо ще одну форму представлення рівняння (4.6). Запишемо це рівняння у вигляді:
a ₂ x ₂ = ba ₁ x ₁
або

або
x ₂ = F - kx ₁ (4.8)
Рівняння (4.8) зображено на рис. 4.2.
Згадаймо нерівності. Якщо лінійне рівняння з двома змінними може бути представлено у вигляді прямої на площині, то нерівність виду:
a ₁ x ₁ + a ₂ x ₂ £ b (4.9)
зображується як полуплоскость, показана на рис. 4.1. На цьому малюнку частина площини, що задовольняє нерівності, заштрихована. Координати всіх точок, що належать заштрихованому ділянці, мають такі значення x ₁ і x _2, які задовольняють заданому нерівності. Значить, ці значення становлять область допустимих рішень (ОДР). Саму пряму вважаємо належить кожній з двох зазначених півплощини. Припустимо тепер, що задано не одне нерівність, а система:
ìа ₁₁ x ₁ + а ₁₂ x ₂ £ b ₁
ïа ₂₁ x ₁ + а ₂₂ x ₂ £ b ₂
(4.10)   í ... ... ... ...
îа _{m 1} x ₁ + а _{m 2} x ₂ £ b _m,
де перша нерівність визначає деяку полуплоскость П _1, друге - полуплоскость П ₂ і т.д.
якщо яка-небудь пари чисел (x _1, x ₂₎ задовольняє всім нерівностям (4.10), то, відповідна точка Р (x _1, x _2), належить усім півплощини П _1, П _2, ... П _m одночасно. Іншими словами, точка Р належить перетину (загальної частини) півплощин П _1, П _2, ... П _m, тобто деякої багатокутної області М (Мал. 4.3), яка є ОДР. Уздовж контуру області зображені штрихи, що йдуть всередину області. Вони одночасно вказують, з якого боку від даної прямої лежить відповідна полуплоскость, те ж саме зазначено і за допомогою стрілок на кожній лінії. Відразу ж відзначимо, що ОДР не завжди буває, обмежена: в результаті перетину декількох півплощин може виникнути і необмежена область (Мал. 4.4). Можливий і випадок, коли область допустимих рішень (ОДР) порожня. Це означає, що система (5.7) суперечлива (Мал. 4.5). Багатокутник ОДР має досить важливою властивістю: він є опуклим.
þ ф Ігурей називається опуклою, якщо разом з будь-якими двома своїми точками А і В, вона містить і весь відрізок АВ.
У випадку трьох невідомих, кожне рівняння являє собою площину в просторі. Кожна площина розбиває весь простір на два півпростору. Система нерівностей визначає в просторі опуклий об'ємний багатогранник, який представляє ОДР.
5. МЕТОДИ РІШЕННЯ
ЗАВДАНЬ лінійного програмування
5.1. Загальна та основна задачі лінійного програмування
До математичним завданням лінійного програмування приводять дослідження конкретних виробничо-господарських ситуацій, які в тому чи іншому вигляді інтерпретуються як завдання про оптимальне використання обмежених ресурсів (задача про розкрої, сумішах і т.д.).
У всіх цих завданнях потрібно знайти максимум або мінімум лінійної функції за умови, що її змінні приймають невід'ємні значення і задовольняють деякій системі лінійних рівнянь або лінійних нерівностей якій системі, що містить як лінійні нерівності, так і лінійні рівняння. Кожна з етіx завдань є окремим випадком загальної задачі лінійного програмування.
þ Oбщей задачею лінійного програмування називається задача, яка coстоіт у визначенні максимального (мінімального) значення функції:
  (5.1)
за умови:
(5.2)
(5.3)
X _j ³ 0 (j = 1, 1, 1 £ n) (5.4)
де a _{i j,} b _i, з _j - задані постійні величини і k £ m.
þ Функція (5.1) називається цільовою функцією (або лінійною формою) завдання (5.1) - (5.4), а умови (5.2) - (5.4) - обмеженнями даного завдання.
þ Стандартної (або симетричною) задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (5.1) при виконанні умов (5.2) і (5.4), де k = m і 1 = n.
þ Канонічної (або основний) задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (5.1) при виконанні умов (5.3) і (5.4), де k = 0 і 1 = n.
þ Сукупність чисел Х ^* = (x _1, x _2, ..., x _n), що задовольняють обмеженням завдання (5.2) - (5.4), називається допустимим рішенням (або планом).
þ План Х ^* = (x _1, x _2, ..., x _n), при якому цільова функція задачі (5.1) приймає своє максимальне (мінімальне) значення, називається оптимальним.
значення цільової функції (5.1) при плані X будемо позначати через F (X). Отже, Х ^* - оптимальний план задачі, якщо для будь-якого X виконується нерівність F (X) £ F (Х ^*) (відповідно F (X) ³ F (Х ^*)).
5.2. Геометричний метод рішення
задач лінійного програмування
Перепишемо основну задачу лінійного програмування у векторній формі: знайти максимум функції
F = CX (5.5)
за умов:
x ₁ P ₁ + x ₂ P ₂ + ... + X _n P _n = P ₀ (5.6)
Х ³ 0 (5.7)
де C = (з _1, с _2, ..., с _n), Х = (х _1, х _2, ..., х _n); СХ - скалярний твір; Р _1, Р _2, ..., Р _n і Р ₀ - m-мірні вектор-стовпчики, складені із коефіцієнтів при невідомих і вільних членах системи рівнянь задачі.
þ План X = (х _1, х _2, ..., х _n) називається опорним планом основного завдання лінійного програмування, якщо система векторів P _j, що входять до розкладання (5.6) з позитивними коефіцієнтами x _j, лінійно незалежна.
Непорожнє безліч планів основного завдання лінійного програмування утворює опуклий багатогранник. Кожна вершина цього многогранника визначає опорний план. В одній з вершин багатогранника рішень (тобто для одного з опорних планів) значення цільової функції є максимальним (за умови, що функція обмежена зверху на безлічі планів). Якщо максимальне значення функція приймає більш ніж в одній вершині, то це ж значення вона приймає в будь-якій точці, що є опуклою лінійною комбінацією даних вершин.
Вершину багатогранника рішень, в якій цільова функція приймає максимальне значення, знайти порівняно просто, якщо завдання, записана у формі стандартної, містить не більше двох змінних або завдання, записана у формі основної, містить не більше двох вільних змінних. Haйдем рішення задачі, що полягає у визначенні максимального значення функції:
F = c ₁ x ₁ + з ₂ х ₂ (5.8)
за умов:
a _{i 1} x ₁ + a _{i 2} x ₂ £ b _i (i = 1, k) (5.9)
x _j ³ 0 (i = 1,2) (5.10)
Кожне з нерівностей (5.9), (5.10) системи обмежень задачі геометрично визначає полуплоскость відповідно з граничними прямими a _{i 1} + a _{i 2} = b _i (i = 1, k), x ₁ = 0 і x ₂ = 0. У цьому випадку, якщо система нерівностей (5.9), (5.10) совместна, область її рішень є безліч точок, що належать всім зазначеним півплощини.
þ Так як безліч точок перетину даних півплощин опукле, то областю допустимих рішень (ОДР) завдання (5.8) - (5.10) є опукле безліч, яке називається багатокутником рішень. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з вихідної системи обмежень заміною знаків нерівностей на знаки точних рівностей.
Таким чином, вихідна задача лінійного програмування полягає в знаходженні такої точки області припустимих рішень, в якій цільова функція F приймає максимальне значення. Ця точка існує тоді, коли багатокутник рішень не порожній і на ньому цільова функція обмежена зверху. За зазначених умов в одній з вершин ОДР цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня c ₁ x ₁ + c ₂ x ₂ = h (де h - деяка постійна), що проходить через ОДР, і будемо її пересувати в напрямку вектора C = (з _1; з ₂₎ до тих пір, поки вона не пройде через останню її загальну точку з багатокутником ОДР. Координати цієї точки і визначаю оптимальний план цієї задачі.
При знаходженні рішення задачі можуть зустрітися випадки, зображені на рис. 5.1-5.4. Рис. 5.1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. З рис. 5.2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На рис. 5.3 зображено випадок, коли цільова функція не обмежена зверху на безлічі припустимих рішень, а на рис. 5.4 - випадок, коли система обмежень задачі несумісна.
Oтметім, що знаходження мінімального значення лінійної функції при даній системі обмежень відрізняється від перебування її максимального значення при тex же обмеженнях лише тим, що лінія рівня c ₁ x ₁ + c ₂ x ₂ = h пересувається не в напрямку вектора С, а в протилежному напрямку .

Таким чином, зазначені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при визначенні її мінімального значення.
Той факт, що оптимальне рішення знаходиться в одній з вершин багатокутника ОДР, дозволяє зробити ще два важливих висновки:
À якщо оптимальним рішенням є координати вершини багатокутника ОДР, значить, скільки вершин має ОДР, стільки існує цільових функцій і стільки оптимальних рішень з цих функцій може мати завдання.
Á оскільки, чим більше обмежень має завдання, тим більше вершин, тo, отже, чим більше цільових функцій і, отже, тим більше оптимальних рішень з цих функцій.
З малюнків можна зробити висновок, що вершина, координати якої є оптимальним рішенням, визначаються кутом нахилу прямої, яка описує цільову функцію. Отже, кожна вершина буде відповідати оптимальному вирішенню для деякої цільової функції. Отже, знаходження рішення задачі лінійного програмування (5.8) - (5.10) на основі її геометричної інтерпретації включає наступні етапи.
е. тапи знаходження рішення задачі лінійного програмування:
À Будують прямі, рівняння яких виходять в результаті заміни в обмеженнях (5.9) і (5.10) знаків нерівностей на знаки точних рівностей.
Á Знаходять півплощини, зумовлені кожним з обмежень задачі.
 Знаходять багатокутник рішень (ОДР).
à Будують вектор C = (з _1; с _2).
Ä Будують пряму c ₁ x ₁ + c ₂ x ₂ = h, що проходить через багатокутник рішень.
Å пересувають пряму c ₁ x ₁ + c ₂ x ₂ = h в напрямку вектора С, в результаті чого-небудь знаходять точку (точки), в якій цільова функція приймає максимальне значення, або встановлюють необмеженість зверху функції на безлічі планів.
Æ Визначають координати точки максимуму функції і обчислюють значення цільової функції в цій точці.
5.3. Графічне рішення задачі розподілу ресурсів
Нехай для двох видів продукції П ₁ і П ₂ потрібні трудові, матеріальні та фінансові ресурси. Наявність ресурсів кожного виду і їх норми витрати, необхідні для випуску одиниці продукції, наведено в табл. 5.1.
Таблиця 5.1

Характеристика	Вид продукції		располаг.
	П 1	П 2	ресурс
Резерви:
трудові	1	4	14
матеріальні	3	4	18
фінансові	6	2	27
випуск	1	1	---
прибуток	4	8,5	---
план	х 1	х 2	---

з залишимо математичну модель задачі.
ìx ₁ +4 x ₂ £ 14
ï3x ₁ +4 x ₂ £ 18
(5. 11)   í6x ₁ +2 x ₂ £ 27
îx ₁ ³ 0, x ₂ ³ 0.
математична модель представляє собою систему лінійних нерівностей. Значить ОДР нашого завдання опуклий багатокутник. Для зручності побудови нерівності можна записати у формі, аналогічній рівнянням у відрізках:
ìx ₁ / 14 + x ₂ / 7 / 2 £ 1
ïx ₁ / 6 + x ₂ / 9 / 2 £ 1
(5.12) íx ₁ / 9 / 2 + x ₂ / 27 / 2 £ 1
îx ₁ ³ 0, x ₂ ³ 0.
Якщо ми хочемо знайти оптимальне рішення, то повинні прийняти цільову функцію. Припустимо, ми хочемо, щоб рішення було оптимальним в сенсі максимізації сумарного випуску. Тоді цільова функція:
F = x ₁ + x ₂ ® max (5.13)
Цю залежність представимо у вигляді x ₂ = F - x _1. З графіка даного рівняння (Мал. 5.1) випливає, що tg a = - 1, при цьому a = 135 ^о, а величина F дорівнює відрізку, який відсікається прямої функції цілі на осі координат. Якщо пряму переміщати паралельно самій собі в напрямку, зазначеному стрілками, то ця величина буде зростати. Очевидно, що оптимальним рішенням будуть координати точки С (x ^* _1; x ^* _2). При цьому F = F ^*.
На підставі розглянутого, можна зробити виключно важливий висновок: оптимальним рішенням є координати вершин ОДР. А з цього висновку слід метод розв'язання задачі лінійного програмування.
м етод рішення задачі лінійного програмування:
À Знайти вершини ОДР, як точки перетину обмежень.
Á Визначити послідовно значення цільової функції у вершинах.
 Вершина, в якій цільова функція набуває оптимальне значення, є оптимальною вершиною.
à Координати оптимальної вершини є оптимальними значеннями шуканих змінних.
Якщо напрямок цільової функції збігається з напрямком однієї зі сторін, то у завдання буде, принаймні, два рішення. У такому випадку говорять, що завдання має альтернативні рішення. А це означає, що одне і те ж оптимальне значення цільової функції може бути отримано при різних значеннях змінних.
Той факт, що оптимальне рішення знаходиться на вершині ОДР, дає ще два дуже важливих висновки:
À якщо оптимальним рішенням є координати вершин ОДР, значить, скільки вершин має ОДР, стільки оптимальних рішень може мати завдання.
Á оскільки чим більше обмежень, тим більше вершин, то, отже, чим більше обмежень, тим більше оптимальних рішень.
Як видно на Рис. 5.1, вершина, координати якої є оптимальним рішенням, визначається кутом нахилу прямої, яка описує цільову функцію. Отже, кожна вершина буде відповідати оптимальному вирішенню для деякої цільової функції. Пояснимо це на розглянутому раніше прикладі. Раніше ми знаходили оптимальне рішення по максимізації сумарного випуску F ₁ = x ₁ + x ₂ ® max. Знайдемо оптимальні рішення ще для чотирьох цільових функцій:
F ₂ = x ₂ ® max (максимізація випуску продукції П ₂₎
F ₃ = x ₁ ® max (максимізація випуску продукції П ₁₎
F ₄ = ₄ x _січня +8,5 x ₂ ® max (максимізація прибутку)
F ₅ = (1 +3 +6) x ₁ + (4 +4 +2) x ₂ = 10х ₁ +10 х ₂ ® max (мінімізація використовуваних ресурсів).
Для кожної цільової функції, так само як і для F _1, можна побудувати лінію цільової функції і визначити вершину, в якій цільова функція буде мати оптимальне значення. Результати розв'язання задачі з п'яти цільових функцій зведемо в таблицю 5.2, з аналізу якої можна зробити висновок: координати кожної вершини можуть бути оптимальним рішенням у деякому сенсі.
Таблиця 5.2

Цільова функція	Вершина	x 1	x 2	x 1 + x 2	Прибуток	Використовуваний ресурс
F 1 = x 1 + x 2 ® max	C	4	1,5	5,5	28,75	55
F 2 = x 2 ® max	A	0	3,5	3,5	29,75	35
F 3 = x 1 ® max	D	4,5	0	4,5	18	45
F 4 = 4x 1 +8,5 x 2 ® max	B	2	3	5	33,5	50
F 5 = 10х 1 +10 х 2	0	0	0	0	0	0

5 .4. Симплексний метод
Симплексний метод або метод послідовного поліпшення плану є одним з основних методів вирішення завдань ЛЗ. назва симплексний метод бере від слова «симплекс», яким творець методу Р. Данциг позначив накладене на змінні x _1, x ₂ ... x _n обмеження x ₁ + x ₂ + ... + X _n = 1.
þ У математиці симплексом в k-мірному просторі називається сукупність k +1 вершин.
Так для площині при k = 2 симплексом буде трикутник; в просторі при k = 3 симплексом буде тетраедр, який має 4 вершини.
З урахуванням цього поняття аналітичний метод рішення задачі ЛП називають симплекс-методом. Він заснований на алгоритмі спрямованого перебору вершин. Цей алгоритм забезпечує перехід від однієї вершини до іншої в такому напрямку, при якому значення цільової функції від вершини до вершини поліпшується.
þ Визначення значення цільової функції і змінних в одній вершині вважається итерацией.
Число ітерацій в реальних задачах може вимірюватися сотнями. Вручну, за допомогою симплекс-методу, можуть бути вирішені завдання, що містять не більше 10 ітерацій. Тому в реальних задачах застосовують ЕОМ і пакети прикладних програм (ППП).
Метод вирішення завдань ЛЗ з допомогою симплексних таблиць викладено на конкретному прикладі. Нехай потрібно знайти невід'ємне рішення системи лінійних нерівностей:
ì4x ₁ +9 x ₂ £ 56
(5.14) í5x ₁ +3 x ₂ £ 37
î-x ₁ +2 x ₂ £ 2
звертає в максимум лінійну форму:
| = 3 x ₁ +4 x ₂ (5.15)
Спочатку перейдемо від системи нерівностей (5.14) до системи рівнянь, додавши до лівих частинах нерівностей невід'ємні змінні x _3, x _4, x _5. Ми отримаємо:
ì4x ₁ +9 x ₂ + x ₃ ^+0. x ₄ ^+0. x ₅ = 56
(5.16) í5x ₁ +3 x ₂ ^+0. x ₃ + x ₄ ^+0. x ₅ = 37
î-x ₁ +2 x ₂ ^+0. x ₃ ^+0. x ₄ + x ₅ = 2
| = 3 x ₁ +4 x ₂ +0 ^. x ₃ +0 ^. x ₄ +0 ^. x ₅ (5.17)
перепишемо тепер систему (5.16) у вигляді системи 0-рівнянь:
ì0 = 56 - (4x ₁ +9 x ₂ ^+1. x ₃ ^+0. x ₄ ^+0. x ₅₎
(5.18) í0 = 37 - (5x ₁ +3 x ₂ ^+0. x ₃ ^+1. x ₄ ^+0. x ₅₎
î0 = 2 - (-x ₁ +2 x ₂ ^+0. x ₃ ^+0. x ₄ ^+1. x ₅₎
| = 0 - (- 3 x ₁ -4 x ₂ -0 ^. x ₃ -0 ^. x _квітня -0 ^. x ₅₎ (5.19)
зауважимо, що система (5.18) може бути записана у вигляді одного векторної рівності:
0 = B-(A ₁ x ₁ + A ₂ x ₂ + A ₃ x ₃ + A ₄ x ₄ + A ₅ x _5),
де вектор-стовпець В має своїми компонентами вільні члени, а вектори A _1, A _2, ... , A ₅ - коефіцієнти при відповідних змінних x _1, x _2, x _3, x _4, x _5. Іншими словами:

	56			4			9			1			0			0
В =	37		A 1 =	5		A 2 =	3		A 3 =	0		A 4 =	1		A 5 =	0
	2			-1			2			0			0			1

Лінійна форма має вигляд: | = 3 x ₁ +4 x ₂ +0 ^. x ₃ +0 ^. x ₄ +0 ^. x _5.
Вектори A _3, A _4, A ₅ утворюють базис. Це означає, що, присвоївши х ₁ = 0, х ₂ = 0, отримуємо з (5.16) перше базисне рішення: x ₁ = 0; x ₂ = 0; x ₃ = 56; x ₄ = 37; x ₅ = 2.
При цьому значення лінійної форми | = 0. На підставі (5.18) будуємо першу сімплексною таблицю.
Симплексний таблиця будується наступним чином:
У заголовній рядку пишемо послідовно вектори B, A _1, A _2, A _3, A _4, A _5. Зліва додаємо колонку «Базисні вектори», поруч з нею колонку «С», в якій поставлені коефіцієнти при базисних змінних в лінійній формі, в даному випадку величини З _3, З _4, С _5. В останньому рядку, званої індексного, і позначається через | j-С _j, проставляються числа, рівні значенням лінійної форми, у відповідністю з рівнянням (j = 1, 2, 3, 4, 5). У результаті ми маємо таблицю 5.3.
Таблиця 5.3.

Базисні	Коефіцієнти	Вектор вільних	3	4	0	0	0
вектори	лінійної форми З	членів У	A 1	A 2	A 3	A 4	A 5
A 3	0	56	4	9	1	0	0
A 4	0	37	5	3	0	1	0
A 5	0	2	-1	2	0	0	1
Індексна рядок | j-С j		0	-3	-4	0	0	0

Це перша симплексна таблиця, відповідна перший базисного рішення: x ₁ = 0; x ₂ = 0; x ₃ = 56; x ₄ = 37; x ₅ = 2. Значення лінійної форми, рівне нулю, ми записуємо в першій клітині індексного рядка.
Оскільки ми вирішуємо завдання на максимум, то з виразу лінійної форми видно, що має сенс збільшити x ₁ або x _2. Дійсно, коефіцієнти при цих змінних в дужках негативні (а по суті позитивні), і якщо ми покладемо x _1> 0 або x _2> 0, то значення | збільшиться. Але ці ж коефіцієнти з їх знаками стоять в індексному рядку.
Отже, ми приходимо до наступного висновку: наявність в індексному рядку негативних чисел при вирішенні завдання на максимум свідчить про те, що нами оптимальне рішення не отримано, і те, що від табл. 5.3 треба перейти до наступної.
Перехід до нової таблиці, тобто до нової покращеної програмі здійснюємо наступним способом: в індексному рядку знаходимо найбільше за абсолютним значенням негативне (а при завданні на мінімум - найбільший позитивний) число. У нашому прикладі цим числом буде - 4. Знайдене число визначає провідний або ключовий стовпець. Потім ми ділимо вільні члени на позитивні елементи ведучого шпальти і вибираємо з отриманих відносин найменше. Найменша відношення визначає провідну рядок. У даному випадку маємо:
                                       
Таким чином, провідною рядком буде рядок A _5. На перетині ведучого шпальти і головною рядка стоїть дозволяє елемент. У нашому випадку - це число 2.
Тепер ми приступаємо до складання другої таблиці або другого плану. Замість одиничного вектора A ₅ ми в базис вводимо вектор A _2. Перехід до нового базису, як це відомо, еквівалентний елементарного перетворення матриці, елементами якої служать числа табл. 5.3. А саме: у новій таблиці елемент рядка, який відповідає елементу провідною рядки колишньої таблиці, дорівнює цьому елементу головною рядки, розділеному на дозволяючий елемент. щоб отримати будь-який інший елемент нової симплексного таблиці, потрібно від відповідного елемента колишньої таблиці відняти твір елемента провідною рядки на елемент ведучого шпальти, розділене на дозволяючий елемент. Наприклад, елементу 4 (табл. 5.3) буде відповідати елемент табл. 5.4:

Таким чином, ми переходимо до другої таблиці (таблиця 5.4). Зазначені вище перетворення відносяться до стовпцях B, A _1, A _2, A _3, A _4, A _5.
Таблиця 5.4.

Базисні	Коефіцієнти	Вектор вільних	3	4	0	0	0
вектори	лінійної форми З	членів У	A 1	A 2	A 3	A 4	A 5
A 3	0	47	17 / 2	0	1	0	-9 / 2
A 4	0	34	13 / 2	0	0	1	-3 / 2
A 5	4	1	-1 / 2	1	0	0	1 / 2
Індексна рядок   | j-С j		4	-5	0	0	0	2

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

Отже, що дозволяє елементом буде 13 / 2. Вектор A ₄ виводимо з базису і вводимо замість нього вектор A _1. Перерахунок коефіцієнтів здійснюємо за вказаними вище правилами і отримуємо таблицю 5.5.
Таблиця 5.5

Базисні	Коефіцієнти	Вектор вільних	3	4	0	0	0
вектори	лінійної форми З	членів У	A 1	A 2	A 3	A 4	A 5
A 3	0	33/13	0	0	1	-17/13	-33/13
A 1	3	68/13	1	0	0	2 / 13	-3/13
A 2	4	47/13	0	1	0	1 / 13	5 / 13
Індексна рядок | j-С j		392/13	0	0	0	10/13	11/13

У індексному рядку немає негативних елементів. Отже, ми отримаємо оптимальну програму. Оптимальне рішення:
x ₁ = 68/13; x ₂ = 47/13; x ₃ = 33/13; x ₄ = x ₅ = 0.
5.5. Аналіз симплекс-таблиць
Математична модель є прекрасним засобом отримання відповідей на широке коло питань, що виникають при плануванні, проектуванні і в ході управління виробництвом. Так на етапі планування доцільно знаходити варіанти плану при різних варіантах номенклатури, ресурсів, цільових функцій і т.д.
При оперативному управлінні вирішується досить широкий і важливий коло питань, які виникають при щоденному забезпеченні виробничого процесу. Ми розглянемо лише ті питання оперативного управління, які можуть бути вирішені за допомогою моделей, вже складених при плануванні. «Що буде, якщо п'ять чоловік з числа трудових ресурсів відвернуть на інші роботи? Що буде, якщо сировини поставлять на 20% менше? Яку продукцію слід випускати, якщо змінилися ціни? »Розглянемо, як знаходити відповіді на ці питання на конкретному прикладі.
Припустимо, підприємство повинно випускати продукцію чотирьох видів: П _1, П _2, П _3, П _4, використовуючи для цього три види ресурсів. Наявні ресурси, норми витрат матеріалів і прибуток наведено в Таблиці 5А.
ТАБЛИЦЯ 5А

Елемент	Вид продукції				Наявний
моделі	П 1	П 2	П 3	П 4	ресурс
Ресурси:
трудові	1	1	1	1	16
сировину	6	5	4	3	110
обладнання	4	6	10	13	100
Прибуток з одиниці продукту	60	70	120	130	---
План	х 1	х 2	х 3	х 4	---

ìx ₁ + X ₂ + X ₃ + x ₄ £ 16
ï6x ₁ + 5x ₂ + 4x ₃ + 3x ₄ £ 110
(5. 2 0) í4x ₁ + 6x ₂ + 10x ₃ + 13x ₄ £ 100
îx _j ³ 0, j ³ 1,4.
F = 60 x ₁ + 70 x ₂ + 120 x ₃ + 130 x ₄ ® max
Від системи нерівностей (5.20) перейдемо до системи рівнянь. Для цього, у кожне нерівність додамо по одній додаткової змінної: y _i ³ 0, i ³ 1, m. Тоді отримаємо систему рівнянь:
ìx ₁ + x ₂ + x ₃ + x ₄ + y ₁ = 16
ï6x ₁ + 5x ₂ + 4x ₃ + 3x ₄ + y ₂ = 110
(5.21) í4x ₁ + 6x ₂ + 10x ₃ + 13x ₄ + y ₃ = 100
îx _j ³ 0, j = 1,4; y _i ³ 0, i = 1,3.
F = 60 x ₁ + 70 x ₂ + 120 x ₃ + 130 x ₄ ® max
Потім перепишемо систему (5.21) в наступному вигляді:
ì y ₁ = 16 - (x ₁ + x ₂ + x ₃ + x ₄₎
ï y ₂ = 110 - (6x ₁ + 5x ₂ + 4x ₃ + 3x ₄₎
(5.22) í y ₃ = 100 - (4x ₁ + 6x ₂ + 10x ₃ + 13x ₄₎
î F = 0 - (-60x ₁ - 70x ₂ - 120x ₃ - 130x ₄₎
Систему (5.22) можна представити у вигляді Таблиці 5В, яку складають у такий спосіб: вільні змінні, укладені в дужки, виносять у верхній рядок таблиці. В інші стовпці записують вільні члени і коефіцієнти перед вільними змінними. Ця, так звана симплекс таблиця, служить основою для вирішення завдань лінійного програмування. У цій таблиці змінні, які є вільними, у даному випадку x _1, x _2, x _3, x ₄ по умові рівні 0. Оскільки вільні змінні рівні 0, то з системи (5.22) видно, що базисні змінні y _1, y _2, y _3, а також цільова функція F, яку записують знизу, рівні вільним членам. Значить y ₁ = 16, y ₂ = 110, y ₃ = 100, F = 0.
ТАБЛИЦЯ 5В

Величина	Вільний	Вільні змінні
	член	х 1	х 2	х 3	х 4
Базисні змінні:
y 1	16	1	1	1	1
y 2	110	6	5	4	3
y 3	100	4	6	10	13
Індексна рядок (F)	0	- 60	- 70	- 120	- 130

Нагадаємо, що в системі (5.21) загальне число змінних N = n + m, де n - число основних змінних, m - число додаткових змінних. Всі змінні можна підрозділити з одного боку на основні та додаткові, а з іншого - на базисні і вільні.
þ Вільними змінними будемо називати такі, які дорівнюють 0.
З теорії відомо, що n змінних в допустимому ухвалі повинні бути рівні 0, тобто стільки ж змінних, скільки і основних. Однак, з цього ні в якій мірі не випливає, що нулю рівні всі основні змінні. Якщо із загального числа змінних N = n + m будуть вільними n змінних, то очевидно, що m змінних будуть засадничими, тобто не дорівнюють нулю. З урахуванням введених термінів можна сказати, що метою рішення завдання ЛП є знаходження базисних і вільних змінних.
Для задачі ЛП, записаної у вигляді симплекс таблиці, можна сформулювати ознаки допустимого і оптимального рішень. Рішення є допустимим, якщо в симплекс таблиці у стовпці вільних членів всі значення, пов'язані з базисним змінним будуть невід'ємними. Оптимальне значення, як ми знаємо, може або мінімізувати, або максимізувати значення цільової функції. У зв'язку з цим, для оптимальних значень є дві ознаки: один для випадку мінімізації цільової функції, інший - для випадку максимізації.
Цільова функція має мінімальне значення, якщо, по-перше, рішення є допустимим, тобто вільні члени будуть невід'ємними, а по = друге, всі елементи в рядку цільової функції (вільний член не розглядається) будуть недодатні. При цьому цільова функція дорівнює вільному члену. Таким чином можна зробити висновок, що у Табл. 5В отримано оптимальне рішення нашої задачі для випадку мінімізації цільової функції.
Дійсно, якщо x ₁ = x ₂ = x ₃ = x ₄ = 0 ми ніякої продукції не випускаємо і при цьому прибуток F = 0. Додаткові змінні y _1, y _2, y _3, показують обсяг невикористаних ресурсів, рівні, відповідно: 16, 110,100, тобто того ресурсу, який є в наявності. Справді, ми нічого не виробляємо, але не витрачаємо ресурси. Отже, дані в Табл. 5В відповідають такий вершині ОДР, в якій цільова функція приймає мінімальне значення.
Ознака максимізації цільової функції формується таким чином: цільова функція має максимальне значення, якщо, по-перше, рішення є допустимим, а по-друге, всі елементи в рядку цільової функції (вільний член не розглядається) будуть невід'ємними.
Оскільки Табл. 5В не задовольняє цією ознакою, то необхідно перейти до іншої вершині ОДР. Перехід від однієї вершини до іншої, проводиться за певним алгоритмом симплекс-методу, який полягає в обміні змінних.
þ Кожний перехід від однієї вершини до іншої, який називається итерацией, полягає в тому, що одна базисна змінна прирівнюється до нуля, тобто переходить у вільну, а одна вільна змінна переводиться в базисну.
На кожній ітерації перевіряють задоволення ознак допустимого і оптимального рішень. Така процедура триває до тих пір, поки не будуть задоволені обидві ознаки. Стосовно нашого завдання переходимо до наступної симплекс-таблиці, отриманої після першої ітерації.
Перехід до нової таблиці здійснюємо наступним способом: в індексному рядку, де знаходиться цільова функція знаходимо найбільше за абсолютним значенням негативне число. Знайдене число визначає провідний стовпець. Потім ми ділимо вільні члени на позитивні елементи ведучого шпальти і вибираємо з отриманих відносин найменше. Найменша відношення визначає провідну рядок. У нашому випадку маємо:

Таким чином, провідним стовпцем буде стовпець х _3, а провідною рядком буде рядок y _3. На перетині ведучого шпальти і головною рядки буде дозволяє елемент. У нашому випадку це число 10. Таким чином, провідною рядком буде рядок y _3, позначимо її через A _r. Провідним стовпцем буде стовпець х _4, позначимо його через A _k, і, отже, дозволяє елемент A _rk = 10.
Тепер приступаємо до складання другої таблиці. У цій таблиці елементи направляючої рядки рівні цьому елементу головною рядки, поділеному на дозволяючий елемент, і знаходяться в співвідношенні:

Елементи будь-який інший рядка j знаходять із співвідношення:

Тобто щоб отримати будь-який інший елемент нової симплексного таблиці, потрібно від відповідного елемента колишньої таблиці відняти твір елемента провідною рядки на елемент ведучого шпальти, розділене на дозволяючий елемент.
Після цих перетворень нова симплексна таблиця після першої ітерації набуде вигляду Таблиці 5С.
ТАБЛИЦЯ 5С

Величина	Вільний	Вільні змінні
	член	х 1	х 2	х 3	х 4
Базисні змінні:
¬ y 1	6	0,6	0,4	0	- 0,3
y 2	70	4,4	2,6	0	- 2,2
¬ y 3	10	0,4	0,6	1	1,3
Індексна рядок (F)	1200	- 12	2	0	26

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

Т. о. Провідною рядком буде y _1, а вирішує елементом число 0,6.
Стосовно нашого завдання остання симплекс-таблиця, отримана після другої ітерації, буде мати вигляд:
ТАБЛИЦЯ 5 D

Величина	Вільний	Вільні змінні
	член	х 1	х 2	х 3	х 4
Базисні змінні:
х 1	10	5 / 3	2 / 3	- 1 / 6	- 1 / 2
y 2	26	-22 / 3	- 1 / 3	1 / 3	0
х 3	6	- 2 / 3	1 / 3	1 / 6	3 / 2
Індексна рядок (F)	1320	2 0	10	1 0	20

З цієї таблиці видно, що у стовпці вільних членів всі елементи позитивні. Значить рішення є допустимим. У рядку цільової функції всі елементи теж позитивні. Отже, це рішення оптимальне і максимізує цільову функцію. При цьому оптимальним планом будуть наступні величини: х ₁ ^* = 10, х ₃ ^* = 6 (значить, вони - базисні) і х ₂ ^* = х ₄ ^* = 0 (тому що вони вільні). При цьому цільова функція F = 1320.
Ось результат рішення задачі. Проте, за допомогою симплекс-таблиці можна дізнатися ще багато корисних відомостей. Так їх цієї ж таблиці бачимо, що вільні змінні y ₁ = y ₃ = 0, а базисна змінна y ₂ = 26. А це означає, що в оптимальному плані резерви трудових ресурсів та обладнання дорівнюють нулю. Іншими словами, ці ресурси використовуються повністю. Разом з тим резерв ресурсів сировини y ₂ = 26, що свідчить про те, що є надлишки сировини. Ось які корисні відомості можна отримати з остаточної симплекс-таблиці.