додати матеріал


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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

¸ Московський кіновідео інститут (МКВІ0
ЛЕКЦІЇ
З дисципліни:
Економіко-математичні
методи і моделі
ВИКЛАДАЧ Мацнев А.П.
                                                             
                                                                           
                                             
Москва 2004
ЗМІСТ
1. Моделювання економічних систем.
Основні поняття та визначення
1.1. Виникнення і розвиток системних уявлень
1.2. Моделі та моделювання. Класифікація моделей
1.3. Види подібності моделей
1.4. Адекватність моделей
2. МАТЕМАТИЧНІ МОДЕЛІ І МЕТОДИ ЇХ РОЗРАХУНКУ
2.1. Поняття операційного дослідження
2.2. Класифікація і принципи побудови математичних моделей
3. Деякі відомості з математики
3.1. Опуклі множини
3.2. Лінійні нерівності
3.3. Значення лінійної форми на опуклому безлічі
4. ПРИКЛАДИ ЗАВДАНЬ лінійного програмування
4.1. Транспортна задача
4.2. Загальна формулювання задачі лінійного програмування
4.3. Графічна інтерпретація розв'язання задач лінійного програмування
5. МЕТОДИ РІШЕННЯ ЗАДАЧ лінійного програмування
5.1. Загальна та основна задачі лінійного програмування
5.2. Геометричний метод рішення задач лінійного програмування
5.3. Графічне рішення задачі розподілу ресурсів
5.4. Симплексного методу
5.5. Аналіз симплекс-таблиць
5.6. Рішення транспортних задач
6. МЕТОДИ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
І багатокритеріальної оптимізації
6.1. Постановка задачі нелінійного програмування
6.2. Постановка задачі динамічного програмування
Основні умови і область застосування
6.3. Багатокритерійна оптимізація
1. Моделювання економічних систем.
Основні поняття і визначення.
1.1. Виникнення і розвиток системних уявлень
Науково-технічна революція призвела до виникнення таких понять, як великі і складні економічні системи, що володіють специфічними для них проблемами. Необхідність вирішення таких проблем призвела до появи особливих підходів і методів, які поступово накопичувалися і узагальнювались, утворюючи, в кінці кінців, особливу науку - системний аналіз.
На початку 80-х років системність стала не тільки теоретичною категорією, але і усвідомленим аспектом практичної діяльності. Широко поширилося поняття того, що наші успіхи пов'язані з тим, наскільки системно ми підходимо до вирішення виникаючих проблем, а наші невдачі викликані відсутністю системності у наших діях. Сигналом про недостатню системності в нашому підході до вирішення будь-якої задачі є поява проблеми, дозвіл ж проблеми, що виникла відбувається, як правило, при переході на новий, більш високий, рівень системності нашої діяльності. Тому системність не тільки стан, а й процес.
У різних сферах людської діяльності виникли різні підходи і відповідні методи вирішення специфічних проблем, які отримали різні назви: у військових і економічних питаннях - «дослідження операцій», в політичному та адміністративному управлінні - «системний підхід», у філософії «діалектичний матеріалізм», в прикладних наукових дослідженнях - «кібернетика». Пізніше стало ясно, що всі ці теоретичні та прикладні дисципліни утворюють як би єдиний потік, «системне рух», яке поступово оформилося в науку, що отримала назву «системний аналіз». В даний час системний аналіз є самостійною дисципліною, що має свій об'єкт діяльності, свій достатньо потужний арсенал засобів і свою прикладну область. Будучи по суті прикладної діалектикою, системний аналіз використовує всі засоби сучасних наукових досліджень - математику, моделювання, обчислювальну техніку та натурні експерименти.
þ Найцікавіша і складна частина системного аналізу - це «витягування» проблеми з реальної практичної задачі, відділення важливого від несуттєвого, пошук правильного формулювання для кожної з виникаючих проблем, тобто те, що називається «постановкою завдання».
Багато досить часто недооцінюють роботу, пов'язану з формулюванням завдання. Однак багато фахівців думають, що «добре поставити завдання - значить на половину її вирішити». Хоча в більшості випадків замовнику здається, що він вже сформулював свою проблему, системний аналітик знає, що запропонована клієнтом постановка задачі є моделлю його реальної проблемної ситуації і неминуче має цільовий характер, залишаючись приблизною і спрощеною. Тому необхідно перевірити цю модель на адекватність, що призводить до розвитку та уточненню початкової моделі. Дуже часто первісна формулювання викладена в термінах не тих мов, які необхідні для побудови моделі.
1.2. Моделі та моделювання. Класифікація моделей
Спочатку моделлю називали якесь допоміжний засіб, об'єкт, який у певних ситуаціях замінював інший об'єкт. Наприклад, манекен у певному сенсі замінює людини, будучи моделлю людської фігури. Древні філософи вважали, що відобразити природу можна тільки за допомогою логіки і правильних міркувань, тобто за сучасною термінологією за допомогою мовних моделей. Через кілька століть девізом англійської Наукового товариства стало гасло: «Нічого словами!», Визнавалися тільки висновки, підкріплені експериментально або математичними викладками.
В даний час для осягнення істини існує 3 шляхи:
À теоретичне дослідження;
Á експеримент;
 моделювання.
þ Моделлю називається об'єкт-заступник, який в певних умовах може заміняти об'єкт-оригінал, відтворюючи цікавлять нас властивості і характеристики оригіналу, причому має суттєві переваги:
- Дешевизну;
- Наочність;
- Легкість оперування і т.п.
þ У теорії моделей моделюванням називається результат відображення однієї абстрактної математичної структури на іншу - теж абстрактну, або як результат інтерпретації першої моделі в термінах і образах другий.
Paзвития поняття моделі вийшло за межі математичних моделей і стало ставитися до будь-яких знань та уявлень про світ. Оскільки моделі відіграють надзвичайно важливу роль в організації будь-якої діяльності людини їх можна розділити на пізнавальні (когніцітівние) і прагматичні, що відповідає поділу цілей на теоретичні і практичні.
þ Пізнавальна модель орієнтована на наближенні моделі до реальності, яку ця модель відображає. Пізнавальні моделі є формою організації та подання знань, засобом з'єднання нових знань зі своїми. Тому при виявленні розбіжності між моделлю і реальністю постає завдання усунення цієї розбіжності за допомогою зміни моделі.
þ Прагматичні моделі є засобом управління, засобом організації практичних дій, способом представлення зразково правильних дій або їх результату, тобто є робочим поданням цілей. Поетомy при виявленні розбіжності між моделлю і реальністю треба направити зусилля на зміну реальності так, щоб наблизити реальність до моделі. Таким чином, прагматичні моделі носять нормативний характер, грають роль зразка, під який підганяється дійсність. Прикладами прагматичних моделей служать плани, кодекси законів, робочі креслення і т.д.
Іншим принципом класифікації цілей моделювання може служити поділ моделей на статичні і динамічні.
þ Для одних цілей нам може знадобитися модель конкретного стану об'єкта в певний момент часу, свого роду «моментальна фотографія» об'єкта. Такі моделі називаються статичними. Прикладом є структурні моделі систем.
þ У тих же випадках, коли виникає необходімост' у відображенні процесу зміни станів, потрібні динамічні моделі систем.
У розпорядженні людини є два типи матеріалів для побудови моделей - кошти самої свідомості та засоби окружающею матеріального світу. Відповідно до цього моделі діляться на абстрактні (ідеальні) і матеріальні.
þ Очевидно, що до абстрактних моделей відносяться мовні конструкції та математичні моделі. Математичні моделі мають найбільший точністю, але щоб дійти до їх використання в даній області, необхідно отримати достатню кількість знань. На думку Канта, будь-яка галузь знання може тим більше іменуватися наукою, чим більшою мірою в ній використовується математика.
1.3. Види подібності моделей
Щоб деяка матеріальна конструкція могла бути моделлю, тобто заміняла в якомусь відношенні оригінал, між оригіналом і моделлю має бути встановлено відношення подібності. Існують різні способи встановлення такого подібності, що надає моделям особливості, специфічні для кожного способу.
þ Перш за все, це подібність, що встановлюється в процесі створення моделі. Назвемо таке подобу прямим. Прикладом такого подібності є фотографії, масштабовані моделі літаків, кораблів, макети будівель, викрійки, ляльки і т.д.
Слід пам'ятати, що як би добре не була модель, вона все-таки лише замінник оригіналу, тільки в певному відношенні. Навіть тоді, коли модель прямого подоби виконана з того ж матеріалу, що і оригінал, тобто подібна йому субстратно, виникають проблеми перенесення результатів моделювання на оригінал. Наприклад, при випробуванні зменшеної моделі літака в аеродинамічній трубі завдання перерахунку даних модельного експерименту стає нетривіальною і виникає розгалужена, змістовна теорія подібності, що дозволяє привести у відповідність масштаби та умови експерименту, швидкість потоку, в'язкість і густина повітря. Важко досягається взаємозамінність моделі і оригіналу у фотокопіях творів мистецтва, голографічних зображеннях предметів мистецтва.
þ Другий тип подібності між моделлю та оригіналом називається непрямим. Непряме подібність між оригіналом і моделлю об'єктивно існує в природі і виявляється у вигляді достатній близькості чи збігу їх абстрактних математичних моделей і внаслідок цього широко використовується в практиці реального моделювання. Найбільш характерним прикладом може служити електромеханічна аналогія між маятником і електричним контуром.
Виявилося, що багато закономірностей електричних і механічних процесів описуються однаковими рівняннями, різниця полягає лише у різній фізичної інтерпретації змінних, що входять в це рівняння. Роль моделей, які мають непрямим подобою, дуже велика і роль аналогій (моделей непрямого подібності) в науці і практиці важко переоцінити. Аналогові обчислювальні машини дозволяють знайти рішення майже всякого диференціального рівняння, являючи собою, таким чином, модель, аналог процесу, що описується цим рівнянням. Використання електронних аналогів в практиці визначається тим, що електричні сигнали легко виміряти і зафіксувати, що дає відомі переваги моделі.
þ Третій, особливий клас моделей складають моделі, подобу яких оригіналу не є ні прямим, ні непрямим, а встановлюється в результаті угоди. Таке подобу називається умовним. З моделями умовного подоби доводиться мати справу дуже часто, оскільки вони є способом матеріального втілення абстрактних моделей. Прикладами умовного подоби служать гроші (модель вартості), посвідчення особи (модель власника), всілякі сигнали (моделі повідомлення).
Наприклад, сигналом настання кочівників у стародавніх слов'ян служили багаття на курганах. Паперові грошові знаки можуть грати роль моделі вартості лише до тих пір, поки в середовищі їх звернення існують правові норми, що підтримують їх функціонування. Керенки в даний час мають лише історичну цінність, але це не гроші, на відміну від царських золотих монет, які представляють матеріальну цінність через наявність благородного металу. Особливо наочна умовність знакових моделей: квітка у вікні явочної квартири Штірліца означав провал явки, ні сорт, ні колір не мали ніякого відношення до знакової функції квітки.
1.4. Адекватність моделей
þ Модель, за допомогою якої успішно досягається поставлена ​​мета, будемо називати адекватної цього ланцюга. Адекватність означає, що вимоги повноти, точності та правильності (істинності) моделі виконані не взагалі, а лише в тій мірі, яка достатня досягнення поставленої мети.
У ряді випадків вдається ввести міру адекватності деяких цілей, тобто вказати спосіб порівняння двох моделей за ступенем успішності досягнення цілі з їх допомогою. Якщо до того ж є спосіб кількісно виразити міру адекватності, то завдання поліпшення моделі істотно полегшується. Саме в таких випадках можна кількісно ставити, питання про ідентифікацію моделі т.e. про знаходження в заданому класі моделей найбільш адекватної, про дослідження чутливості і стійкості моделей т.e. залежно заходи адекватності моделі від її точності, про адаптацію моделей, тобто підстроюванні параметрів моделі з метою підвищення її точності.
Наближеність моделі не слід плутати з адекватністю. Наближеність моделі може бути дуже високою, але у всіх випадках модель - це інший об'єкт і відмінності неминучі (єдиною досконалою моделлю будь-якого об'єкта є сам об'єкт). Величину, міру, ступінь прийнятності відмінності можна ввести, тільки співвідносячи його з метою моделювання. Так деякі підробки творів мистецтва навіть експерти не можуть відрізнити від оригіналу, але все-таки це всього лише підробка, і з точки зору вкладення капіталу не представляє ніякої цінності, хоча для любителів мистецтва нічим не відрізняється від оригіналу. У англійського фельдмаршала Монтгомері під час війни був двійник, поява якого на різних ділянках фронту навмисно дезінформувала розвідку німців.
Спрощення є сильним засобом для виявлення головних ефектів в досліджуваному явищі: це видно на прикладі таких явищ фізики, як ідеальний газ, абсолютно пружне тіло, математичний маятник і абсолютно твердий важіль.
Є ще один, досить загадковий, аспект спрощеності моделі. Чому-то виявляється, що з двох моделей, однаково добре описують систему, та модель, яка простіше, ближче до істини. Геоцентрична модель Птоломея дозволяла розрахувати рух планет, хоча й з дуже громіздким формулами, з переплетенням складних циклів. Перехід до геліоцентричної моделі Коперника значно спростив розрахунки. Древні казали, що простота - друк істини.
2. МАТЕМАТИЧНІ МОДЕЛІ І МЕТОДИ ЇХ РОЗРАХУНКУ
2.1. Поняття операційного дослідження
Bпервие математичні моделі були використані для вирішення практичної задачі в 30-х роках у Великобританії при створенні системи протиповітряної оборони. Для розробки даної системи були залучені вчені різних спеціальностей. Система створювалася в умовах невизначеності щодо можливих дій противника, тому дослідження проводилися на адекватних математичних моделях. У цей час вперше був застосований термін: «операційне дослідження», що припускає дослідження військової операції. У наступні роки операційні дослідження або дослідження операцій розвиваються як наука, результати якої застосовуються для вибору оптимальних рішень при управлінні реальними процесами і системами.
Рішення людина брала завжди і у всіх сферах своєї діяльності. Раніше хотіли, щоб ухвалені рішення завжди були правильними. Тепер прийнято говорити, що рішення повинні бути оптимальними. Чим складніший об'єкт управління, тим важче прийняти рішення, і, отже, тим легше припуститися помилки. Питанням прийняття рішень на основі застосування ЕОМ і математичних моделей присвячена нова наука «Дослідження операцій», що набуває в останні роки все більш широке поле додатків. Ця наука порівняно молода, її межі і зміст не можна вважати чітко визначеними.
Предмет під назвою «Дослідження операцій» входить в програму елітарних вузів, але не завжди в цей термін вкладається один і той же зміст. Деякі вчені під «дослідженням операцій» розуміють, головним чином, математичні методи оптимізації, такі як лінійні, нелінійні, динамічне програмування. Інші до дослідження операцій підходять з позиції теорії ігор і статистичних рішень. Нарешті, деякі вчені вкладають у поняття «дослідження операцій» надмірно широкий зміст, вважаючи її основою системного аналізу і «наукою наук».
þ Під терміном «дослідження операцій» ми будемо розуміти застосування математичних, кількісних методів для обгрунтування рішень у всіх областях цілеспрямованої людської діяльності.
Остаточно термін «дослідження операцій» закріпився в кінці Другої світової війни, коли в збройних силах США були сформовані спеціальні групи математиків і програмістів, в завдання яких входила підготовка рішень для командувачів бойовими діями. Надалі дослідження операцій розширило область своїх застосувань на різні галузі практики: економіка, транспорт, зв'язок і навіть охорона природи.
щоб людині прийняти рішення без ЕОМ, найчастіше нічого не треба, окрім досвіду та інтуїції. Щоправда, ніякої гарантії правильності, а тим більше оптимальності при цьому немає. Підкреслимо, що ЕОМ ніяких рішень не приймає. Рішення приймає чоловік (ОПР). А ЕОМ тільки допомагає знайти варіанти рішень. Неодмінна присутність людини (як остаточний інстанції прийняття рішень) не відміняється навіть при наявності повністю автоматизованої системи управління. Не можна забувати про те, що саме створення керуючого алгоритму, вибір одного з можливих його варіантів, є також рішення. У міру автоматизації управління функції людини переміщаються з одного рівня управління на інший - вищий. Основні етапи рішення задачі прийняття оптимальних рішень за допомогою ЕОМ показані на Рис. 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 1 M 1 + a 2 M 2 + ... + A n M n,
де a i ³ 0 і a 1 + a 2 + ... + a n = 1.
þ Узагальнюючи сказане вище, можна сказати, що безліч точок називається опуклим, якщо разом з будь-якими своїми точками воно містить і опуклу довільну комбінацію цих точок. Оскільки довільна точка відрізку представляє собою опуклу комбінацію його кінців, то це і означає, що опукле безліч разом з двома даними точками містить весь з'єднує їх відрізок.
Очевидно, що будь-яка точка опуклого багатокутника, що лежить всередині його або в одній зі сторін, за винятком вершин, може бути представлена ​​як опукла лінійна комбінація інших точок цього багатокутника. Навпаки, вершини багатокутника не подаються у вигляді опуклої комбінації двох будь-яких інших точок. У цьому сенсі вершини багатокутника називають екстремальними точками.
þ пряма лінія називається опорною, якщо вона має з опуклим багатокутником, принаймні, одну спільну точку і весь багатокутник розташований по один бік від цієї прямої. Через кожну з вершин багатокутника можна провести нескінченну безліч опорних ліній. У просторі трьох вимірів, за аналогією з поняттям опорної прямої вводиться поняття опорної площини.
þ Опорною площиною називається всяка площину, що має з опуклим багатогранником, принаймні, одну спільну точку, причому таку, що весь багатогранник розташований по один бік від неї. Опорна площину може мати з опуклим багатогранником спільну точку (вершину багатогранника), пряму (ребро), і, нарешті, загальну межу.
3.2. Лінійні нерівності
розглянемо докладніше системи лінійних нерівностей і покажемо, що рішення їх тісно пов'язане з поняттями опуклого багатокутника і опуклого многогранника.

Для початку розглянемо нерівність з однією змінною величиною x 1, наприклад x 1 <4. Якщо на площині провести пряму х 1 = 4, то вона розділить всю площину на дві частини - півплощини: в одній з них, а саме зліва від прямої х 1 = 4, лежать точки, абсциси яких менше 4, а праворуч від прямої - точки , абсциси яких більше 4. Таким чином, нерівність x 1 <4 геометрично визначає полуплоскость (Рис.1). Розглянемо тепер нерівність з двома змінними типу 1 +4 х 2 <12. Побудуємо пряму лінію 1 +4 х 2 = 12. Розділимо обидві частини рівняння на 12:


з якого видно, що пряма відсікає по осях відрізки, рівні 4 і 3.
Нерівність 1 +4 х 2 < 12 визначає собою сукупність всіх точок площини, що лежать нижче прямої, тобто в заштрихованої частини (Мал. 2).

Щоб легше було зрозуміти, яку саме полуплоскость визначає те чи інше нерівність, ми в ліву частину нерівності підставимо координати початку координат, тобто х 1 = 0 і х 2 = 0. Якщо нерівність задовольняється, то воно визначає ту полуплоскость, в якій лежить початок координат, в іншому випадку - іншу полуплоскость. Користуючись геометричними міркуваннями, знайти можливі рішення системи:
ì3х 1 +4 х 2 £ 12
íx 1 <2
îх 1> 0 і х 2> 0

Кожне з нерівностей системи визначає полуплоскость, зазначену на Рис.3 штрихами.
Отриманий багатокутник є опуклим, бо разом з будь-якими двома точками містить весь з'єднує їх відрізок. таким чином, ми бачимо, що опуклий багатокутник можна задати аналітично, за допомогою системи лінійних нерівностей. Лінійне рівняння з трьома змінними: a 11 x 1 + a 12 x 2 + a 13 x 3 = b 1 визначає в просторі деяку площину, яка розсікає весь простір на два півпростору.
У зв'язку з цим нерівність a 11 x 1 + a 12 x 2 + a 13 x 3 £ b 1 визначає одне з півпросторів, до якого належить також і сама гранична площину. У загальному випадку, коли система нерівностей совместна, простір рішень утворює деякий опуклий багатогранник - багатогранник рішень. Окремим випадком його можуть бути: окрема грань, ребро або крапка. Останнє має місце, коли система нерівностей має одне єдине рішення. Подальші узагальнення приводять нас до розгляду m лінійних нерівностей з n невідомими. Кожне рівняння a i 1 x 1 + a i 2 x 2 + ... + A in x n = b i є рівнянням деякої гіперплощини в n-мірному просторі, яка як би розсікає весь простір на два півпростору.
3.3. Значення лінійної форми на опуклому безлічі
Припустимо, що задана деяка система з m-лінійних нерівностей (або рівнянь) з n змінними х 1, х 2, ..., х n. Система нерівностей у випадку спільності визначає деякий опукле безліч в n-мірному просторі, обмежений чи нескінченне (багатогранник рішень).
Припустимо далі, що нам задана деяка лінійна форма від цих змінних, що визначає функцію мети:
| = C 1 x 1 + c 2 x 2 + ... + C n x n
У кожній точці опуклого безлічі, тобто для кожного рішення нашої системи, лінійна форма | приймає певне значення. Виникає питання: у яких точках опуклого безлічі лінійна форма | сягає свого найбільшого і найменшого значення, якщо, звичайно, такі існують? Рішення загальної задачі лінійного програмування зводиться, таким чином, до знаходження точок опуклого безлічі, у яких задана лінійна форма досягає оптимального значення, і ми шукаємо такі точки 1, х 2, ..., х n), координати яких ненегативні. Сформулюємо одне важливе твердження, що полегшує вирішення завдання.
þ У тих випадках, коли безліч рішень задачі лінійного програмування утворює опуклий багатогранник, лінійна форма досягає оптимального значення в одній з його вершин, у зв'язку з чим останні й називаються екстремальними точками.
У загальному випадку, лінійна форма | = c 1 x 1 + c 2 x 2 + ... + C n x n задає гіперплощина в n-мірному просторі. При | = 0 ця гіперплощина проходить через початок координат. Потім пересуваємо цю площину паралельно самій собі в напрямку вектора P перпендикулярно до цієї площини. Перша з вершин, в якій лінійна форма (гіперплощина) зустріне опуклий багатогранник, буде точкою, в якій лінійна форма досягає найменшого значення, а остання з вершин - точкою, в якій лінійна форма досягає найбільшого значення.
Може трапитися, що гіперплощина виявиться паралельної одній з граней або ребер опуклого багатогранника, і тоді лінійна форма | сягає свого найменшого або найбільшого значення в будь-якій точці, що лежить на цьому ребрі. Але й тоді вона досягає ці значення у вершині, що лежить на цьому ребрі.
Існують різні методи розв'язання задач лінійного програмування. Одним з найбільш простих і наочних методів рішення є графічний метод. Цей метод дозволяє вирішувати завдання, які призводять до систем рівнянь з двома або трьома змінними. Більшість завдань лінійного програмування призводить до систем лінійних нерівностей з великим числом змінних. Ці завдання вирішуються симплексним методом.
4. ПРИКЛАДИ ЗАВДАНЬ лінійного програмування
4.1. Транспортна задача
вугілля, що видобувається в декількох родовищах, відправляється ряду споживачів. нам відомо, скільки вугілля видобувається в кожному з родовищ, скажімо за місяць і скільки його потрібно на той самий строк кожному із споживачів. Відомі відстані між родовищами і споживачами, а також умови сполучення між ними. Враховуючи ці дані. Можна підрахувати, у що обходиться перевезення кожної тонни вугілля з будь-якого родовища в будь-який пункт споживання. Вимагається при цих умовах спланувати перевезення вугілля таким чином, щоб витрати на них були мінімальними.
Нехай для простоти задані всього 4 родовища М 1, М 2, М 3, М 4, причому їхня щомісячна видобуток становить a 1, а 2, а 3, а 4 тонн вугілля. Припустимо далі, що це вугілля треба доставити до пунктів споживання b 1, b 2, b 3, b 4, b 5, відповідно з щомісячними потребами цих пунктів. Будемо вважати, що загальне виробництво вугілля одно сумарної потреби в ньому (збалансованість планів): a 1, а 2, а 3, а 4 = b 1, b 2, b 3, b 4, b 5. Завдання полягає у визначенні такого плану перевезень, при якому загальна вартість перевезень була б найменшою. Позначимо через x 11 кількість вугілля (в тоннах), призначене до відправлення з M 1 в П 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
Загальна кількість вугілля, привозиться в пункт П 1 з усіх родовищ, буде х 11 + х 12 + х 13 + х 14 + х 15 = b 1; в інші пункти - П 2, П 3 і т.д. і прийме вигляд рівнянь 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 11 х 11 + c 12 х 12 + c 13 х 13 + c 14 х 14 + c 15 х 15 + ... + C 41 х 41 + c 42 х 42 + c 43 х 43 + c 44 х 44 + c 45 х 45.
4.2. Загальна формулювання задачі лінійного програмування
Аналогічно транспортної задачі вирішується завдання про оптимізацію розподілу ресурсів (трудових, матеріальних, фінансових) і завдання про дієту. При всьому розмаїтті, за своїм конкретним змістом кожна з них була завданням на знаходження найбільш вигідного варіанта. З точки зору математичної, в кожній задачі шукаються значення декількох невідомих, причому потрібно, щоб:
À ці значення задовольняли деякій системі лінійних рівнянь або нерівностей;
Á при цих значеннях деяка лінійна функція (лінійна форма) від цих невідомих зверталася в мінімум (максимум);
 ці значення були невід'ємними.
Завданнями такого роду і займається лінійне програмування.
þ Говорячи точніше, лінійне програмування - це математична дисципліна, що вивчає методи знаходження найменшого (або найбільшого) значення лінійної функції декількох змінних, за умови, що останні задовольнять кінцевому числу лінійних рівнянь або нерівностей. Загальна математична формулювання задачі лінійного програмування виглядає наступним чином.
Дана система лінійних рівнянь:
ìа 11 x 1 + а 12 x 2 + ... + А 1 n x n = b 1
ïа 21 x 1 + а 22 x 2 + ... + А 2 n x n = b 2
(I) í ... ... ... ... ... ... ... ...
îа m 1 x 1 + а m 2 x 2 + ... + А mn x n = b m
і лінійна функція | = c 1 x 1 + c 2 x 2 + ... + C n x n (II).
Потрібно знайти такі невід'ємні рішення х 1 ³ 0, х 2 ³ 0 ... х n ³ 0 (III) системи (I) при яких функція | приймає найменше (найбільше) значення.
Рівняння (I) називаються обмеженнями даного завдання, рівняння (II) називається лінійної формою, а рівняння (III), строго кажучи, теж є обмеженнями, однак їх не прийнято так називати, бо вони є загальними для всіх задач лінійного програмування, а не тільки конкретного завдання. Будь-яке невід'ємне рішення системи рівнянь називається допустимим. Допустиме рішення, що дає мінімум функції |, оптимальне рішення (якщо воно існує) не обов'язково єдино; можливі випадки, коли є незліченна безліч оптимальних рішень. Нарешті, саму функцію | часто називають лінійною формою або функцією цілі.
Здавалося б, тому що задача лінійного програмування ставиться як завдання мінімізації деякої функції |, то можна застосувати класичний прийом диференціального числення. Однак приватні похідні | рівні коефіцієнтам при невідомих, які в «нуль» одночасно не звертаються.
4.3. Графічна інтерпретація
рішення задач лінійного програмування
Задачу лінійного програмування (ЛП) можна вирішувати аналітичними та графічними методами. Аналітичні методи є основою для вирішення задачі на ЕОМ. Їх єдиний недолік полягає в тому, що на відміну від графічних методів, вони недостатньо наочні. Графічні методи дуже наочні, але вони придатні лише для вирішення завдань на площині, тобто коли розмірність простору К = 2. Однак, враховуючи велику наочність графічних методів, за їх допомогою розглянемо ідею розв'язання задачі ЛП на прикладі задачі розподілу ресурсів.
Однак перш ніж зайнятися рішенням, зробимо деякі зауваження. Нехай ми маємо систему m рівняння з n невідомими (I).
Можливі такі варіанти:
À Число невідомих менше, ніж число рівнянь n < m.
н апример: ì2x 1 = 4, у цьому випадку n = 1;
îx 1 = 5, тоді m = 2 (число лінійно незалежних рівнянь). (4.4)
Очевидно, що система (4.4) рішення не має, і вона несумісна;
Á Число невідомих дорівнює числу рівнянь n = m.
У цьому випадку система має єдиний розв'язок або не має жодного. Зауважимо, що m дорівнює числу лінійно незалежних рівнянь.
Для системи: ì2x = 10, n = 1, m = 1;
î6x = 30.
 Якщо число невідомих більше числа рівнянь, то система має незліченну безліч рішень. Нехай n > m. Наприклад:
2 x 1 + x 2 = 2 (4.5)
Очевидно, що це рівняння прямої, і всі значення x 1 і x 2, що лежать на цій прямій, є рішенням рівняння (4.2). Значить рівняння (4.5) має незліченну безліч рішень.
У випадку, коли система має більше одного можливого рішення, може бути поставлена ​​задача оптимізації, суть якої в тому, що з усіх допустимих рішень, які відповідають обмеженням і граничним умовам, вибрати таке, яке надає цільової функції оптимум. Згадаймо побудова лінійних залежностей. Нехай дано рівняння:
a 1 x 1 + a 2 x 2 = b (4.6)
Перетворимо його до виду:
(4.7)
Запис (4.7) називають рівнянням прямої у відрізках, що зображено на Рис. 4.1. Розглянемо ще одну форму представлення рівняння (4.6). Запишемо це рівняння у вигляді:
a 2 x 2 = ba 1 x 1
або

або
x 2 = F - kx 1 (4.8)
Рівняння (4.8) зображено на рис. 4.2.


Згадаймо нерівності. Якщо лінійне рівняння з двома змінними може бути представлено у вигляді прямої на площині, то нерівність виду:
a 1 x 1 + a 2 x 2 £ b (4.9)
зображується як полуплоскость, показана на рис. 4.1. На цьому малюнку частина площини, що задовольняє нерівності, заштрихована. Координати всіх точок, що належать заштрихованому ділянці, мають такі значення x 1 і x 2, які задовольняють заданому нерівності. Значить, ці значення становлять область допустимих рішень (ОДР). Саму пряму вважаємо належить кожній з двох зазначених півплощини. Припустимо тепер, що задано не одне нерівність, а система:
ìа 11 x 1 + а 12 x 2 £ b 1
ïа 21 x 1 + а 22 x 2 £ b 2
(4.10)   í ... ... ... ...
îа m 1 x 1 + а m 2 x 2 £ b m,
де перша нерівність визначає деяку полуплоскость П 1, друге - полуплоскость П 2 і т.д.
якщо яка-небудь пари чисел (x 1, x 2) задовольняє всім нерівностям (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 1 P 1 + x 2 P 2 + ... + X n P n = P 0 (5.6)
Х ³ 0 (5.7)
де C = (з 1, с 2, ..., с n), Х = (х 1, х 2, ..., х n); СХ - скалярний твір; Р 1, Р 2, ..., Р n і Р 0 - m-мірні вектор-стовпчики, складені із коефіцієнтів при невідомих і вільних членах системи рівнянь задачі.
þ План X = (х 1, х 2, ..., х n) називається опорним планом основного завдання лінійного програмування, якщо система векторів P j, що входять до розкладання (5.6) з позитивними коефіцієнтами x j, лінійно незалежна.
Непорожнє безліч планів основного завдання лінійного програмування утворює опуклий багатогранник. Кожна вершина цього многогранника визначає опорний план. В одній з вершин багатогранника рішень (тобто для одного з опорних планів) значення цільової функції є максимальним (за умови, що функція обмежена зверху на безлічі планів). Якщо максимальне значення функція приймає більш ніж в одній вершині, то це ж значення вона приймає в будь-якій точці, що є опуклою лінійною комбінацією даних вершин.
Вершину багатогранника рішень, в якій цільова функція приймає максимальне значення, знайти порівняно просто, якщо завдання, записана у формі стандартної, містить не більше двох змінних або завдання, записана у формі основної, містить не більше двох вільних змінних. Haйдем рішення задачі, що полягає у визначенні максимального значення функції:
F = c 1 x 1 + з 2 х 2 (5.8)
за умов:
a i 1 x 1 + a i 2 x 2 £ 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 1 = 0 і x 2 = 0. У цьому випадку, якщо система нерівностей (5.9), (5.10) совместна, область її рішень є безліч точок, що належать всім зазначеним півплощини.
þ Так як безліч точок перетину даних півплощин опукле, то областю допустимих рішень (ОДР) завдання (5.8) - (5.10) є опукле безліч, яке називається багатокутником рішень. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з вихідної системи обмежень заміною знаків нерівностей на знаки точних рівностей.
Таким чином, вихідна задача лінійного програмування полягає в знаходженні такої точки області припустимих рішень, в якій цільова функція F приймає максимальне значення. Ця точка існує тоді, коли багатокутник рішень не порожній і на ньому цільова функція обмежена зверху. За зазначених умов в одній з вершин ОДР цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня c 1 x 1 + c 2 x 2 = h (де h - деяка постійна), що проходить через ОДР, і будемо її пересувати в напрямку вектора C = (з 1; з 2) до тих пір, поки вона не пройде через останню її загальну точку з багатокутником ОДР. Координати цієї точки і визначаю оптимальний план цієї задачі.
При знаходженні рішення задачі можуть зустрітися випадки, зображені на рис. 5.1-5.4. Рис. 5.1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. З рис. 5.2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На рис. 5.3 зображено випадок, коли цільова функція не обмежена зверху на безлічі припустимих рішень, а на рис. 5.4 - випадок, коли система обмежень задачі несумісна.
Oтметім, що знаходження мінімального значення лінійної функції при даній системі обмежень відрізняється від перебування її максимального значення при тex же обмеженнях лише тим, що лінія рівня c 1 x 1 + c 2 x 2 = h пересувається не в напрямку вектора С, а в протилежному напрямку .




Таким чином, зазначені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при визначенні її мінімального значення.
Той факт, що оптимальне рішення знаходиться в одній з вершин багатокутника ОДР, дозволяє зробити ще два важливих висновки:
À якщо оптимальним рішенням є координати вершини багатокутника ОДР, значить, скільки вершин має ОДР, стільки існує цільових функцій і стільки оптимальних рішень з цих функцій може мати завдання.
Á оскільки, чим більше обмежень має завдання, тим більше вершин, тo, отже, чим більше цільових функцій і, отже, тим більше оптимальних рішень з цих функцій.
З малюнків можна зробити висновок, що вершина, координати якої є оптимальним рішенням, визначаються кутом нахилу прямої, яка описує цільову функцію. Отже, кожна вершина буде відповідати оптимальному вирішенню для деякої цільової функції. Отже, знаходження рішення задачі лінійного програмування (5.8) - (5.10) на основі її геометричної інтерпретації включає наступні етапи.
е. тапи знаходження рішення задачі лінійного програмування:
À Будують прямі, рівняння яких виходять в результаті заміни в обмеженнях (5.9) і (5.10) знаків нерівностей на знаки точних рівностей.
Á Знаходять півплощини, зумовлені кожним з обмежень задачі.
 Знаходять багатокутник рішень (ОДР).
à Будують вектор C = (з 1; с 2).
Ä Будують пряму c 1 x 1 + c 2 x 2 = h, що проходить через багатокутник рішень.
Å пересувають пряму c 1 x 1 + c 2 x 2 = h в напрямку вектора С, в результаті чого-небудь знаходять точку (точки), в якій цільова функція приймає максимальне значення, або встановлюють необмеженість зверху функції на безлічі планів.
Æ Визначають координати точки максимуму функції і обчислюють значення цільової функції в цій точці.
5.3. Графічне рішення задачі розподілу ресурсів
Нехай для двох видів продукції П 1 і П 2 потрібні трудові, матеріальні та фінансові ресурси. Наявність ресурсів кожного виду і їх норми витрати, необхідні для випуску одиниці продукції, наведено в табл. 5.1.
Таблиця 5.1
Характеристика
Вид продукції
располаг.
П 1
П 2
ресурс
Резерви:
трудові
1
4
14
матеріальні
3
4
18
фінансові
6
2
27
випуск
1
1
---
прибуток
4
8,5
---
план
х 1
х 2
---
з залишимо математичну модель задачі.
ìx 1 +4 x 2 £ 14
ï3x 1 +4 x 2 £ 18
(5. 11)   í6x 1 +2 x 2 £ 27
îx 1 ³ 0, x 2 ³ 0.

математична модель представляє собою систему лінійних нерівностей. Значить ОДР нашого завдання опуклий багатокутник. Для зручності побудови нерівності можна записати у формі, аналогічній рівнянням у відрізках:
ìx 1 / 14 + x 2 / 7 / 2 £ 1
ïx 1 / 6 + x 2 / 9 / 2 £ 1
(5.12) íx 1 / 9 / 2 + x 2 / 27 / 2 £ 1
îx 1 ³ 0, x 2 ³ 0.
Якщо ми хочемо знайти оптимальне рішення, то повинні прийняти цільову функцію. Припустимо, ми хочемо, щоб рішення було оптимальним в сенсі максимізації сумарного випуску. Тоді цільова функція:
F = x 1 + x 2 ® max (5.13)
Цю залежність представимо у вигляді x 2 = F - x 1. З графіка даного рівняння (Мал. 5.1) випливає, що tg a = - 1, при цьому a = 135 о, а величина F дорівнює відрізку, який відсікається прямої функції цілі на осі координат. Якщо пряму переміщати паралельно самій собі в напрямку, зазначеному стрілками, то ця величина буде зростати. Очевидно, що оптимальним рішенням будуть координати точки С (x * 1; x * 2). При цьому F = F *.
На підставі розглянутого, можна зробити виключно важливий висновок: оптимальним рішенням є координати вершин ОДР. А з цього висновку слід метод розв'язання задачі лінійного програмування.
м етод рішення задачі лінійного програмування:
À Знайти вершини ОДР, як точки перетину обмежень.
Á Визначити послідовно значення цільової функції у вершинах.
 Вершина, в якій цільова функція набуває оптимальне значення, є оптимальною вершиною.
à Координати оптимальної вершини є оптимальними значеннями шуканих змінних.
Якщо напрямок цільової функції збігається з напрямком однієї зі сторін, то у завдання буде, принаймні, два рішення. У такому випадку говорять, що завдання має альтернативні рішення. А це означає, що одне і те ж оптимальне значення цільової функції може бути отримано при різних значеннях змінних.
Той факт, що оптимальне рішення знаходиться на вершині ОДР, дає ще два дуже важливих висновки:
À якщо оптимальним рішенням є координати вершин ОДР, значить, скільки вершин має ОДР, стільки оптимальних рішень може мати завдання.
Á оскільки чим більше обмежень, тим більше вершин, то, отже, чим більше обмежень, тим більше оптимальних рішень.
Як видно на Рис. 5.1, вершина, координати якої є оптимальним рішенням, визначається кутом нахилу прямої, яка описує цільову функцію. Отже, кожна вершина буде відповідати оптимальному вирішенню для деякої цільової функції. Пояснимо це на розглянутому раніше прикладі. Раніше ми знаходили оптимальне рішення по максимізації сумарного випуску F 1 = x 1 + x 2 ® max. Знайдемо оптимальні рішення ще для чотирьох цільових функцій:
F 2 = x 2 ® max (максимізація випуску продукції П 2)
F 3 = x 1 ® max (максимізація випуску продукції П 1)
F 4 = 4 x січня +8,5 x 2 ® max (максимізація прибутку)
F 5 = (1 +3 +6) x 1 + (4 +4 +2) x 2 = 10х 1 +10 х 2 ® 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 2 ... x n обмеження x 1 + x 2 + ... + X n = 1.
þ У математиці симплексом в k-мірному просторі називається сукупність k +1 вершин.
Так для площині при k = 2 симплексом буде трикутник; в просторі при k = 3 симплексом буде тетраедр, який має 4 вершини.
З урахуванням цього поняття аналітичний метод рішення задачі ЛП називають симплекс-методом. Він заснований на алгоритмі спрямованого перебору вершин. Цей алгоритм забезпечує перехід від однієї вершини до іншої в такому напрямку, при якому значення цільової функції від вершини до вершини поліпшується.
þ Визначення значення цільової функції і змінних в одній вершині вважається итерацией.
Число ітерацій в реальних задачах може вимірюватися сотнями. Вручну, за допомогою симплекс-методу, можуть бути вирішені завдання, що містять не більше 10 ітерацій. Тому в реальних задачах застосовують ЕОМ і пакети прикладних програм (ППП).
Метод вирішення завдань ЛЗ з допомогою симплексних таблиць викладено на конкретному прикладі. Нехай потрібно знайти невід'ємне рішення системи лінійних нерівностей:
ì4x 1 +9 x 2 £ 56
(5.14) í5x 1 +3 x 2 £ 37
î-x 1 +2 x 2 £ 2
звертає в максимум лінійну форму:
| = 3 x 1 +4 x 2 (5.15)
Спочатку перейдемо від системи нерівностей (5.14) до системи рівнянь, додавши до лівих частинах нерівностей невід'ємні змінні x 3, x 4, x 5. Ми отримаємо:
ì4x 1 +9 x 2 + x 3 +0. x 4 +0. x 5 = 56
(5.16) í5x 1 +3 x 2 +0. x 3 + x 4 +0. x 5 = 37
î-x 1 +2 x 2 +0. x 3 +0. x 4 + x 5 = 2
| = 3 x 1 +4 x 2 +0 . x 3 +0 . x 4 +0 . x 5 (5.17)
перепишемо тепер систему (5.16) у вигляді системи 0-рівнянь:
ì0 = 56 - (4x 1 +9 x 2 +1. x 3 +0. x 4 +0. x 5)
(5.18) í0 = 37 - (5x 1 +3 x 2 +0. x 3 +1. x 4 +0. x 5)
î0 = 2 - (-x 1 +2 x 2 +0. x 3 +0. x 4 +1. x 5)
| = 0 - (- 3 x 1 -4 x 2 -0 . x 3 -0 . x квітня -0 . x 5) (5.19)
зауважимо, що система (5.18) може бути записана у вигляді одного векторної рівності:
0 = B-(A 1 x 1 + A 2 x 2 + A 3 x 3 + A 4 x 4 + A 5 x 5),
де вектор-стовпець В має своїми компонентами вільні члени, а вектори A 1, A 2, ... , A 5 - коефіцієнти при відповідних змінних 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 1 +4 x 2 +0 . x 3 +0 . x 4 +0 . x 5.
Вектори A 3, A 4, A 5 утворюють базис. Це означає, що, присвоївши х 1 = 0, х 2 = 0, отримуємо з (5.16) перше базисне рішення: x 1 = 0; x 2 = 0; x 3 = 56; x 4 = 37; x 5 = 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 1 = 0; x 2 = 0; x 3 = 56; x 4 = 37; x 5 = 2. Значення лінійної форми, рівне нулю, ми записуємо в першій клітині індексного рядка.
Оскільки ми вирішуємо завдання на максимум, то з виразу лінійної форми видно, що має сенс збільшити x 1 або x 2. Дійсно, коефіцієнти при цих змінних в дужках негативні (а по суті позитивні), і якщо ми покладемо x 1> 0 або x 2> 0, то значення | збільшиться. Але ці ж коефіцієнти з їх знаками стоять в індексному рядку.
Отже, ми приходимо до наступного висновку: наявність в індексному рядку негативних чисел при вирішенні завдання на максимум свідчить про те, що нами оптимальне рішення не отримано, і те, що від табл. 5.3 треба перейти до наступної.
Перехід до нової таблиці, тобто до нової покращеної програмі здійснюємо наступним способом: в індексному рядку знаходимо найбільше за абсолютним значенням негативне (а при завданні на мінімум - найбільший позитивний) число. У нашому прикладі цим числом буде - 4. Знайдене число визначає провідний або ключовий стовпець. Потім ми ділимо вільні члени на позитивні елементи ведучого шпальти і вибираємо з отриманих відносин найменше. Найменша відношення визначає провідну рядок. У даному випадку маємо:
                                       
Таким чином, провідною рядком буде рядок A 5. На перетині ведучого шпальти і головною рядка стоїть дозволяє елемент. У нашому випадку - це число 2.
Тепер ми приступаємо до складання другої таблиці або другого плану. Замість одиничного вектора A 5 ми в базис вводимо вектор 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 4 виводимо з базису і вводимо замість нього вектор 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 1 = 68/13; x 2 = 47/13; x 3 = 33/13; x 4 = x 5 = 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 1 + X 2 + X 3 + x 4 £ 16
ï6x 1 + 5x 2 + 4x 3 + 3x 4 £ 110
(5. 2 0) í4x 1 + 6x 2 + 10x 3 + 13x 4 £ 100
îx j ³ 0, j ³ 1,4.
F = 60 x 1 + 70 x 2 + 120 x 3 + 130 x 4 ® max
Від системи нерівностей (5.20) перейдемо до системи рівнянь. Для цього, у кожне нерівність додамо по одній додаткової змінної: y i ³ 0, i ³ 1, m. Тоді отримаємо систему рівнянь:
ìx 1 + x 2 + x 3 + x 4 + y 1 = 16
ï6x 1 + 5x 2 + 4x 3 + 3x 4 + y 2 = 110
(5.21) í4x 1 + 6x 2 + 10x 3 + 13x 4 + y 3 = 100
îx j ³ 0, j = 1,4; y i ³ 0, i = 1,3.
F = 60 x 1 + 70 x 2 + 120 x 3 + 130 x 4 ® max
Потім перепишемо систему (5.21) в наступному вигляді:
ì y 1 = 16 - (x 1 + x 2 + x 3 + x 4)
ï y 2 = 110 - (6x 1 + 5x 2 + 4x 3 + 3x 4)
(5.22) í y 3 = 100 - (4x 1 + 6x 2 + 10x 3 + 13x 4)
î F = 0 - (-60x 1 - 70x 2 - 120x 3 - 130x 4)
Систему (5.22) можна представити у вигляді Таблиці 5В, яку складають у такий спосіб: вільні змінні, укладені в дужки, виносять у верхній рядок таблиці. В інші стовпці записують вільні члени і коефіцієнти перед вільними змінними. Ця, так звана симплекс таблиця, служить основою для вирішення завдань лінійного програмування. У цій таблиці змінні, які є вільними, у даному випадку x 1, x 2, x 3, x 4 по умові рівні 0. Оскільки вільні змінні рівні 0, то з системи (5.22) видно, що базисні змінні y 1, y 2, y 3, а також цільова функція F, яку записують знизу, рівні вільним членам. Значить y 1 = 16, y 2 = 110, y 3 = 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 змінних будуть засадничими, тобто не дорівнюють нулю. З урахуванням введених термінів можна сказати, що метою рішення завдання ЛП є знаходження базисних і вільних змінних.
Для задачі ЛП, записаної у вигляді симплекс таблиці, можна сформулювати ознаки допустимого і оптимального рішень. Рішення є допустимим, якщо в симплекс таблиці у стовпці вільних членів всі значення, пов'язані з базисним змінним будуть невід'ємними. Оптимальне значення, як ми знаємо, може або мінімізувати, або максимізувати значення цільової функції. У зв'язку з цим, для оптимальних значень є дві ознаки: один для випадку мінімізації цільової функції, інший - для випадку максимізації.
Цільова функція має мінімальне значення, якщо, по-перше, рішення є допустимим, тобто вільні члени будуть невід'ємними, а по = друге, всі елементи в рядку цільової функції (вільний член не розглядається) будуть недодатні. При цьому цільова функція дорівнює вільному члену. Таким чином можна зробити висновок, що у Табл. отримано оптимальне рішення нашої задачі для випадку мінімізації цільової функції.
Дійсно, якщо x 1 = x 2 = x 3 = x 4 = 0 ми ніякої продукції не випускаємо і при цьому прибуток F = 0. Додаткові змінні y 1, y 2, y 3, показують обсяг невикористаних ресурсів, рівні, відповідно: 16, 110,100, тобто того ресурсу, який є в наявності. Справді, ми нічого не виробляємо, але не витрачаємо ресурси. Отже, дані в Табл. відповідають такий вершині ОДР, в якій цільова функція приймає мінімальне значення.
Ознака максимізації цільової функції формується таким чином: цільова функція має максимальне значення, якщо, по-перше, рішення є допустимим, а по-друге, всі елементи в рядку цільової функції (вільний член не розглядається) будуть невід'ємними.
Оскільки Табл. не задовольняє цією ознакою, то необхідно перейти до іншої вершині ОДР. Перехід від однієї вершини до іншої, проводиться за певним алгоритмом симплекс-методу, який полягає в обміні змінних.
þ Кожний перехід від однієї вершини до іншої, який називається итерацией, полягає в тому, що одна базисна змінна прирівнюється до нуля, тобто переходить у вільну, а одна вільна змінна переводиться в базисну.
На кожній ітерації перевіряють задоволення ознак допустимого і оптимального рішень. Така процедура триває до тих пір, поки не будуть задоволені обидві ознаки. Стосовно нашого завдання переходимо до наступної симплекс-таблиці, отриманої після першої ітерації.
Перехід до нової таблиці здійснюємо наступним способом: в індексному рядку, де знаходиться цільова функція знаходимо найбільше за абсолютним значенням негативне число. Знайдене число визначає провідний стовпець. Потім ми ділимо вільні члени на позитивні елементи ведучого шпальти і вибираємо з отриманих відносин найменше. Найменша відношення визначає провідну рядок. У нашому випадку маємо:

Таким чином, провідним стовпцем буде стовпець х 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
У Табл. в індексному рядку тільки один негативний елемент, отже, провідним стовпцем буде х 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
З цієї таблиці видно, що у стовпці вільних членів всі елементи позитивні. Значить рішення є допустимим. У рядку цільової функції всі елементи теж позитивні. Отже, це рішення оптимальне і максимізує цільову функцію. При цьому оптимальним планом будуть наступні величини: х 1 * = 10, х 3 * = 6 (значить, вони - базисні) і х 2 * = х 4 * = 0 (тому що вони вільні). При цьому цільова функція F = 1320.
Ось результат рішення задачі. Проте, за допомогою симплекс-таблиці можна дізнатися ще багато корисних відомостей. Так їх цієї ж таблиці бачимо, що вільні змінні y 1 = y 3 = 0, а базисна змінна y 2 = 26. А це означає, що в оптимальному плані резерви трудових ресурсів та обладнання дорівнюють нулю. Іншими словами, ці ресурси використовуються повністю. Разом з тим резерв ресурсів сировини y 2 = 26, що свідчить про те, що є надлишки сировини. Ось які корисні відомості можна отримати з остаточної симплекс-таблиці.
5.6. Рішення транспортних задач
Як приклад наведемо рішення транспортної задачі ЛП за допомогою таблиці. Транспортна таблиця складається з m рядків і n стовпців. У правому верхньому куті кожної клітини будемо ставити вартість З ij перевезення одиниці вантажу з A i в B j, а в центр клітини помістимо перевезення X ij.
Таблиця 5.6
ПН
У 1
У 2
У 3
У 4
У 5
Запаси а i
ПЗ
A 1
13
7
14
7
5
30
A 2
11
8
12
6
8
48
A 3
6
10
10
8
11
20
A 4
14
8
10
10
15
30
Заявки b j
18
27
42
26
15
128
Таблиця 5.7
ПН
У 1
У 2
У 3
У 4
У 5
Запаси а i
ПЗ
A 1
18 13
12 липня
14
7
5
30
A 2
11
15 серпня
33 12
6
8
48
A 3
6
10
10 Вересня
11 серпня
11
20
A 4
14
8
10
15 жовтня
15 15
30
Заявки b j
18
27
42
26
15
128
Складемо опорний план. Можна застосувати метод «північно-західного вугілля». Нехай пункт В 1 подав заявки на 18 одиниць вантажу. Задовольнимо її із запасів А 1. Після цього в ньому залишається ще 30-18 = 12 одиниць вантажу. Віддамо їх пункту В 2. Але заявка цього пункту ще не задоволена. Виділимо залишок 27-12 із запасів А 2 і т.д. розмірковуючи аналогічним чином, складемо таблицю 5.8. Отриманий план перевезень є опорним, але навряд чи він є оптимальним у сенсі вартості перевезень.
þ Нагадаємо, що пряма, яка має з областю, принаймні, одну загальну точку, притім так, що вся область лежить по одну сторону від цієї прямої, називається опорною по відношенню до цієї галузі.
Таким чином, завдання ЛЗ на геометричному мовою може бути сформульована так: серед прямих рівня функції мети | знайти опорну по відношенню до ОДР і притому так, щоб вся область лежала з боку великих значень |. Наш план - не оптимальний. Відразу видно, що його можна поліпшити, якщо зробити в ньому «циклічну перестановку», зменшивши перевезення в «дорогою» клітині (2.3) з вартістю 12. але зате, збільшивши перевезення в «дешевої» клітині (2.4) з вартістю 6. щоб план залишався опорним, ми повинні при цьому зробити одну з вільних клітин базисної, а одну з базисних - вільної.
Скільки одиниць вантажу можемо ми перенести по циклу наступного циклу: (2.4) ® (3.4) ® (3.3) ® (2.3), збільшуючи перевезення у непарних вершинах циклу і зменшуючи у парних? Очевидно, не більше 11 одиниць (інакше перевезення в клітці (3.4) стали б негативними). Також очевидно, що в результаті циклічного перенесення допустимий план залишається допустимим - баланс заявок і запасів не порушується. Зробимо перенесення і запишемо покращений план в таблицю 5.8.
таблиця 5.8
ПН
У 1
У 2
У 3
У 4
У 5
Запаси а i
ПЗ
A 1
18 13
12 липня
14
7
5
30
A 2
11
15 серпня
33 12
11 6
8
48
A 3
6
10
20 10
8
11
20
A 4
14
8
10
15 10
15 15
30
Заявки b j
18
27
42
26
15
128
Таблиця 5.9
ПН
У 1
У 2
У 3
У 4
У 5
Запаси а i
ПЗ
A 1
- 13 березня
12 липня
14
7
+ 15 5
30
A 2
11
15 серпня
22 12
11 6
8
48
A 3
6
10
20 10
8
11
20
A 4
+ 15 14
8
10
15 10
- 15
30
Заявки b j
18
27
42
26
15
128
подивимося, що ми зекономили. Загальна вартість плану в табл. 5.7 дорівнює:
1 = 18 '13 +12' 7 +15 '8 +33' 12 +9 '10 +11' 8 +15 '10 +15' 15 = 1287.
Загальна вартість плану табл. 5.6 дорівнює:
2 = 18 '13 +12' 7 +15 '8 +22' 12 +11 '6 +20' 10 +15 '10 +15' 15 = 1243.
Таким чином, нам вдалося зменшити вартість перевезень на 44 одиниці.
Дійсно алгебраїчна сума вартостей, які стоять у вершинах циклу зі знаком «+», якщо перевезення у цій вершині збільшуються, і зі знаком «-», якщо зменшуються (так звана «ціна циклу»). в даному випадку дорівнює 6-8 +10-12 =- 4. Значить, при перенесенні однієї величини вантажу по цьому циклу вартість зменшується на 4. А ми перенесемо 11 одиниць. Отже, ціна циклу 4. 11 = 44.
Спробуємо ще раз покращити план табл. 5.8 за допомогою циклу (табл. 5.9) з ціною: 5-15 +14-13 = 9. Перекидаючи 15 одиниць вантажу, скорочуємо вартість на: 9. 15 = 135.
6. МЕТОДИ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
І багатокритеріальної оптимізації
6.1. Постановка задачі нелінійного програмування
У загальному вигляді завдання нелінійного програмування (ЗНП) формується таким чином:
f (x 1, x 2, ..., x n) ® max (min) (6.1)
ì g i (x 1, x 2 ..., x n £ b i, i = 1, m 1
ï g i (x 1, x 2 ..., x n ³ b i, i = m 1 +1, m 2
(6.2) í ... ... ... ... ... ... ... ... ... ... ...
î g i (x 1, x 2 ..., x n = b i, i = m 2 +1, m 2
де x j - керуючі змінні або рішення ЗНП, j = 1, n;
b i - Фіксовані параметри, i = 1, m;
f, g i, i = 1, n - задані функції від n змінних.
Якщо f і g i лінійні, то (6.1), (6.2) проходить у завдання лінійного програмування.
þ Вирішити задачу нелінійного програмування - це означає знайти такі значення керуючих змінних x j, j = 1, n, які задовольняють систему обмежень (6.2) і доставляють максимум або мінімум функції f.
Для задачі нелінійного програмування, на відміну від лінійних задач, немає єдиного рішення. Залежно від виду цільової функції (6.1) і обмежень (6.2) розроблено кілька спеціальних методів рішення, до яких відносяться методи множників Лагранжа, квадратичне і опукле програмування, градієнтні методи, ряд наближених методів рішення, графічний метод. Зауважимо, що нелінійне моделювання економічних завдань часто буває досить штучним. Велика частина економічних проблем зводиться до лінійних моделями.
6.2. Постановка задачі динамічного програмування.
Основні умови і область застосування.
У ряді реальних економічних і виробничих завдань необхідно враховувати зміну модельованого процесу в часі і вплив часу на критерій оптимальності. Для вирішення зазначених завдань використовується метод динамічного планування (програмування). Цей метод більш складний у порівнянні з методами розрахунку статичних оптимізаційних завдань. Також не простою справою є процес побудови для реальної задачі математичної моделі динамічного програмування.
Нехай розглядається задача, що розпадається на m кроків або етапів, наприклад планування діяльності підприємства на декілька років, поетапне планування інвестицій, управління виробничими потужностями протягом тривалого терміну. Показник ефективності завдання в цілому позначимо через W, а показники ефективності на окремих кроках - через j i, i = 1, m. Якщо W володіє властивістю адитивності, тобто:
(6.3)
можна знайти оптимальне рішення задачі методом динамічного програмування.
þ Таким чином, динамічне програмування - це метод оптимізації багатокрокових або багатоетапних процесів, критерій ефективності яких має властивість (6.3).
þ У завданнях динамічного програмування критерій ефективності називається виграшем. Дані процеси керовані, і від правильного вибору управління залежить величина виграшу.
þ Змінна х i, від якої залежать виграш на i-му кроці і, отже, виграш в цілому, називаються кроковим управлінням i = 1, m.
þ Управлінням процесу в цілому (х) називається послідовність крокових управлінь х = (х 1, х 2, ..., х i, ..., х m).
þ Оптимальне управління х * - це значення управління х, при якому значення W (x *) є максимальним (або мінімальним, якщо потрібно зменшити програш)
W * = W (x *) = max {W (x)}
                    xÎX, (6.4)
де X - область допустимих управлінь.
Oптімальное управління x * визначається послідовністю оптимальних крокових управлінь: x * = (x 1 *, x 2 *, ..., x i *, ..., x m *).
þ В основі методу динамічного програмування лежить принцип оптимальності Белмана, формулюються так: управління на кожному кроці треба вибирати так, щоб оптимальною була сума виграшів на всіх залишилися до кінця процесу кроки, включаючи виграш на даному кроці.
Пояснимо це правило. При вирішенні завдань динамічного програмування на кожному кроці вибирається управління, яке повинно привести до оптимального виграшу. якщо вважати всі кроки незалежними один від одного, то оптимальним кроковим управлінням буде то управління, яке приносить максимальний виграш саме на цьому кроці. Але, наприклад, при покупці нової техніки замість застарілої, на її придбання затрачуються певні кошти. Тому прибуток від її експлуатації спочатку може бути невеликою. Однак у наступні роки нова техніка буде приносити більший прибуток. І навпаки, якщо керівник прийме рішення залишити стару техніку для отримання прибутку в поточному році, то в подальшому це призведе до значних збитків. Даний приклад демонструє наступний факт: у багатокрокових процесах всі кроки залежать один від одного, і, отже, управління на кожному конкретному кроці треба вибирати, з урахуванням його майбутніх впливів на весь процес.
Інший момент, який слід враховувати при виборі управління на даному кроці, - це можливі варіанти закінчення попереднього кроку. Ці варіанти визначають стан процесу. Наприклад, при визначенні кількості коштів у i-му році, необхідно знати, скільки коштів залишилося в наявності до цього року, і який прибуток отримана в попередньому (i-1)-му році.
Таким чином, при виборі крокового управління необхідно враховувати:
À можливі результати попереднього кроку.
Á вплив управління на всі залишилися до кінця процесу кроки.
У задачі динамічного програмування перший пункт враховують, роблячи на кожному кроці умовні припущення про можливі варіанти закінчення попереднього кроку, і проводячи для кожного з варіантів умовну оптимізацію. Виконання другого пункту забезпечується тим, що в задачах динамічного програмування умовна оптимізація проводиться від кінця процесу до початку. Спершу оптимізується останній m-й крок, на якому не треба враховувати можливі дії обраного управління х m, на всі наступні кроки, тому що ці кроки просто відсутні. Роблячи припущення про умови закінчення (m-1)-го кроку, для кожного з них проводять умовну оптимізацію m-го кроку і визначають умовне оптимальне керування х m. Аналогічно поступають для (m -1)-го кроку, роблячи припущення про випадки закінчення (m -2)-го кроку, і, визначаючи умовне оптимальне керування на (m -1)-му кроці, що приносить оптимальний виграш на двох останніх кроках - (m-1)-му і m-му. Так само діють на всіх інших кроках до першого. На першому кроці, як правило, не треба робити умовних припущень, тому що стан системи перед першим кроком зазвичай відомо. Для цього стану вибирають оптимальний шаговое управління, що забезпечує оптимальний виграш на першому і всіх подальших кроків. Це управління є, безумовно, оптимальним керуванням на першому кроці і, знаючи його, визначаються оптимальне значення виграшу і безумовні оптимальні управління на всіх її кроках.
6.3. Багатокритеріальна оптимізація
þ завдання, в яких оптимізацію проводять за кількома параметрами, називають завданнями багатокритеріальної або векторної оптимізації.
Як і при лінійному програмуванні задачі багатокритеріальної оптимізації включають в себе три основні частини.
т ри основні частини задачі багатокритеріальної оптимізації:
À цільову функцію,
Á обмеження,
 граничні умови.
Найбільш часто цільова функція представляється узагальненими показниками ефективності, які представляють собою зважену суму приватних показників, в яку кожен з них входить з певною вагою, що відображає його важливість:
W = a 1. W 1 + a 2. W 2 + ... + A n . W n
Для тex показників, які бажано збільшити, ваги беруться позитивні, а для тex, які бажано зменшити - негативні.
Призначення коефіцієнтів ваг проводять за допомогою експертних оцінок. Методи експертних оцінок досить широко поширені. Математичних методів визначення експертних оцінок досить багато. Розглянемо деякі з них.
Математичні методи визначення експертних оцінок:
À Безпосереднє призначення коефіцієнтів ваг.
Згідно з цим методом кожен i-й експерт для кожного k-ого параметра повинен призначити коефіцієнт ваги a ik таким чином, щоб сума коефіцієнтів ваги, призначена одним експертом для різних параметрів, дорівнювала 1.

i = 1, n, де n - число експертів.
В якості коефіцієнта ваги k-ого параметра a k приймають середнє значення за результатами експертизи всіх експертів:

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

Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Лекція | 417.8кб. | скачати

Схожі роботи:
Економіко математичні методи і моделі
Економіко математичні методи і моделі 3
Економіко математичні методи і прикладні моделі 2
Економіко математичні методи і прикладні моделі
Детерміновані економіко математичні моделі та методи факторного аналізу
Багатофакторні економіко-математичні моделі прогнозування інфляції
Економіко математичні моделі управління інвестиційним портфелем
Економіко математичні методи
Економіко математичні методи 3
© Усі права захищені
написати до нас
Рейтинг@Mail.ru