Варіант 4 Методи оптимальних рішень Частина 1. Методи прийняття оптимальних рішень. Структура моделі

Кафедра «Фінанси та менеджмент»

Н.Є. Гучек

доцент, кандидат технічних наук

КОНСПЕКТ ЛЕКЦІЙ

з дисципліни

методи оптимальних рішень

Напрямок підготовки: 080100 «Економіка»

Профілі підготовки: «Фінанси та кредит», «Бухгалтерський облік, аналіз та

аудит», «Податки та оподаткування», «Світова економіка»
Форма навчання: очна

Тула 2012 р.

Конспект лекцій підготовлено доцентом Н.Є. Гучек та обговорено на засіданні кафедри «Фінанси та менеджмент» факультету ЕІМ,

Конспект лекцій переглянуто та затверджено на засіданні кафедри «Фінанси та менеджмент» факультету економіки та менеджменту

Зав. кафедрою __________________________ Є.А. Федорова

1.1. Основні поняття теорії прийняття рішень 4

1.2. Математична формалізація 7

1.3. Сучасний етапрозвитку теорії прийняття рішень 12

Лекція 2. Математичне моделювання 15

2.1. Етапи побудови математичної моделі 15

2.2. Поняття стійкості, оптимізації та адекватності моделі 18

2.3. Постановка та технологія вирішення оптимізаційних завдань управління 21

Лекція 3. Лінійне програмування 25

3.1. Лінійне програмування як інструмент математичного моделювання економіки 25

3.2. Приклади моделей лінійного програмування 29

Лекція 4. Завдання лінійне програмування 33

4.1. Форми завдань лінійного програмування та їх еквівалентні перетворення 33

4.2. Геометрична інтерпретація задачі лінійного програмування 37

Лекція 5. Симплексний метод розв'язання задачі лінійного програмування 41

5.1. Симплекс-метод 41

5.2. Симплексні таблиці та алгоритм розв'язання задач 42

5.3. Застосування симплексного методув економічних завданнях 44

Лекція 6. Метод штучного базисурозв'язання задачі лінійного програмування 48

6.1. Метод штучного базису 48

6.2. Застосування методу штучного базису 49

Лекція 7. Подвійні завдання лінійного програмування 52

7.1. Подвійне завдання для стандартного завдання 52

7.2. Основні теореми двоїстості 57

7.3. Метод одночасного вирішення пари двоїстих завдань 62

Лекція 1. Введення у теорію прийняття рішень

План.

1.1. Основні поняття теорії ухвалення рішень.

1.2. Математична формалізація.

1.3. Сучасний етап розвитку теорії ухвалення рішень.

1.1. Основні поняття теорії прийняття рішень

Математичні моделі та методи – необхідний елемент економічної теоріїна мікро- та макрорівні. Використання математики в економіці дозволяє:

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

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

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

по-четверте, використання мови математики дозволяє точно та компактно викладати положення економічної теорії, формулювати її поняття та висновки.

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

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

Методи оптимізації;

Імовірнісно-статистичні методи;

Методи побудови та аналізу імітаційних моделей;

Методи аналізу конфліктних ситуацій(Теорії ігор).

У всіх цих групах можна виділити статичну та динамічну постановки. За наявності фактору часу використовують диференційне рівняннята різницеві схеми.

Методи оптимальних рішень спираються теорію оптимальних рішень. Розглянемо основні поняття теорії ухвалення рішень 1 .

Хто ухвалює рішення? Теоретично прийняття рішень є спеціальний термін- Особа, яка приймає рішення, скорочено ЛПР. Це той, на кому лежить відповідальність за ухвалене рішення, той, хто підписує наказ чи інший документ, у якому висловлено рішення. Зазвичай це генеральний директор чи голова правління, командир військової частини, мер міста тощо. Але іноді діє колективний ЛПР, наприклад, рада директорів, Державна ДумаРосійської Федерації.

Проект рішення готують фахівці або, як то кажуть, «апарат ЛПР». Проте відповідальність лежить на ЛПР, а не тих, хто брав участь у підготовці рішення.

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

порядок підготовки рішення (регламент). Регламенти, що визначають порядок роботи, є дуже важливими. Від них залежить ухвалене рішення.

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

Наприклад, часто зустрічається формулювання «максимум прибутку при мінімумі витрат» внутрішньо суперечлива. Мінімум витрат дорівнює 0, коли робота не проводиться, то й прибуток тоді теж дорівнює 0. якщо ж прибуток великий, то й витрати великі, оскільки і те, й інше пов'язане з обсягом виробництва. Можна або максимізувати прибуток при фіксованих витратах, або мінімізувати витрати при заданому прибутку, але неможливо досягти "максимуму прибутку при мінімумі витрат".

Часто однієї і тієї ж мети можна досягти у різний спосіб.

Ресурси.Кожне рішення передбачає використання тих чи інших ресурсів. У практичній роботі над проектом рішення важливо відповідати на запитання: Чого ми хочемо досягти? Які ресурси ми готові використати для цього?

Ризики та невизначеності. Чимало рішень приймаються за умов ризику, тобто. при можливій небезпеці втрат. Пов'язано це з різноманітними невизначеностями, що оточують нас. Невизначеність – це недостатність інформації про ті чи інші фактори. Крім негативних несподіванок, бувають позитивні удачі. При ухваленні рішень слід застрахуватися від втрат і не пропустити успіх.

Формулювання «Максимум прибутку та мінімум ризику» - внутрішньо суперечлива. Зазвичай при зростанні прибутку зростає і ризик - можливість багато чи все втратити. Невизначеність значень показників, на основі яких приймаються рішення, описується інтервальними значеннями цих показників, наприклад (60  3) % або 1000  200 руб. Тому необхідно вивчити стійкість висновків щодо допустимих відхилень вихідних даних, а також щодо малих змін передумов математичної моделі, що використовується. Будь-який вимір проводиться з деякою похибкою, і цю похибку необхідно вказувати.

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

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

МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ

Короткий курс лекцій

Саратов 2012

МІНІСТЕРСТВО СІЛЬСЬКОГО ГОСПОДАРСТВА

РОСІЙСЬКОЇ ФЕДЕРАЦІЇ

ФЕДЕРАЛЬНА ДЕРЖАВНА БЮДЖЕТНА

ОСВІТНА УСТАНОВА ВИЩОГО

ПРОФЕСІЙНОЇ ОСВІТИ

«САРАТІВСЬКИЙ ДЕРЖАВНИЙ АГРАРНИЙ

УНІВЕРСИТЕТ імені М. І.ВАВІЛОВА»

_____________________________________________________

МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ

Короткий курс лекцій

Саратов 2012

УДК 517(075.8)

ББК 22.161.

Видання здійснено за підтримки

програми TEMPUS JP, грант Європейської

Комісії 159188-TEMPUSPL-TEMPUS-JPCR

Терехова оптимальних рішень. ( короткий курслекцій): Навчальний посібник/сост.: , - Саратов: Вид - у ФДБОУ ВПО «Саратовський ГАУ»., 201с.

Короткий курс лекцій підготовлений відповідно до положень та вимог Державного освітнього стандарту вищої професійної освіти, включає основні теоретичні питання, літературу з вивчення курсу

Призначено для студентів напряму підготовки 110100.62 Агрохімія та агроґрунтознавство (профіль Агроекологія), 280100.68 «Природооблаштування та водокористування», для бакалаврів напряму “Економіка підприємств та організацій” профіль“ Економіка підприємств та організацій (агропромисловий комплекс а)”, Бухгалтерський облікта аудит”, “Харчова промисловість”, “Фінанси та кредит”, а також для магістрів, аспірантів, викладачів, наукових співробітників.

ISBN, 2012

ВСТУП

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

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

лекція 1

Дослідження операцій. Економіко-математичні моделі.

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

Оргсистемиє об'єктом вивчення теорії дослідження операцій.

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

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

Її мета – кількісне обґрунтування прийнятих управлінських рішень та прогнозних планів розвитку.

Дослідження операцій складає математичних моделях досліджуваних об'єктів.

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

Отже модель є інструментом наукового пізнання. Вона будується суб'єктом дослідження так, щоб відобразити характеристики об'єкта-оригіналу (властивості, взаємозв'язки, структурні та функціональні параметри тощо), суттєві для мети дослідження. Тому питання адекватності моделі объекту-оригиналу правомірно вирішувати лише щодо певної мети.

Процес побудови, вивчення та застосування моделей називається моделюванням. Його сутність схематично представлена на рис. 1.

https://pandia.ru/text/78/095/images/image004_15.gif" width="529" height="371">

Моделювання економіки – це відтворення економічних об'єктів та процесів у обмежених, малих, експериментальних формах, у штучно створених умовах.

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

Наведемо таку загальну класифікацію ЕММ.

за цільового призначення ЕММ поділяються на теоретико-аналітичні та прикладні. Теоретико-аналітичні ЕММ призначені для дослідження загальних властивостейта закономірностей економічних процесів. Прикладні ЕММ використовуються при вирішенні конкретних економічних завдань.

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

за способів відображення фактора часу ЕММ діляться на статичні та динамічні. У статичних ЕММ всі залежності відносяться до одного моменту чи періоду часу. Динамічні ЕММ характеризують зміни економічних процесів у часі.

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

Існують інші ознаки класифікації ЕММ. Причому з розвитком економіко-математичних досліджень класифікація досліджуваних ЕММ розширюється.

Зазначимо також, що характером використовуваного математичного апарату при побудові ЕММ розрізняють методи класичної і прикладної математики.

Методи класичної математики включають математичний аналіз, лінійну алгебру, теорію ймовірностей та ін.

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

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

Критерій оптимальності, як правило, має кількісний характер. Наприклад, у ролі можуть виступити максимум прибутку чи мінімум витрат.

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

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

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

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

Компромісне рішення – рішення, оптимальне за всіма критеріями, зазвичай, немає. І тому остаточний вибір прийнятногоза цими критеріями рішення залишається за особою, яка приймає рішення.

ЛЕКЦІЯ 2

Балансові моделі. Модель Леонтьєва багатогалузевої економіки.

Продуктивні моделі.

У економіці існує баланс між окремими галузями. Розглянемо найпростіший варіант моделі міжгалузевого балансу – модель «витрати-випуск».

Нехай є nрізних галузей, кожна з яких виробляє свій продукт і потребує продукції інших галузей (виробниче споживання). Введемо такі позначення:

xi ‑загальний обсяг продукції галузі iза плановий рік - так званий валовий випускгалузі i;

xij ‑обсяг продукції галузі i,витрачається галуззю jу процесі виробництва;

yi‑ обсяг продукції галузі i,призначений до споживання у невиробничій сфері - обсяг кінцевого споживання.До нього входять створювані у господарстві запаси, особисте споживання громадян, забезпечення суспільних потреб (освіта, наука, охорона здоров'я, розвиток інфраструктури тощо), постачання експорту.

Зазначені величини зведемо до таблиці.

Виробниче

споживання

Кінцеве

Споживання

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

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

Зробимо таке припущення: для випуску будь-якого обсягу xjпродукції галузі jнеобхідно витратити продукцію галузі iу кількості , т. е. матеріальні витрати пропорційні обсягу виробленої продукції:

https://pandia.ru/text/78/095/images/image014_8.gif" width="23" height="28 src="> називають коефіцієнтами прямих матеріальних витрат або коефіцієнтами матеріаломісткості . Вони показують скільки необхідно одиниць продукції галузі iдля виробництва одиниці продукції галузі j, якщо враховувати лише прямі витрати .

https://pandia.ru/text/78/095/images/image016_7.gif" width="85" height="24 src=">, (3)

https://pandia.ru/text/78/095/images/image018_6.gif" width="15" height="17"> називається вектор валового випуску, вектор ‑ вектор кінцевого споживання, а матриця А ‑матрицею прямих витрат.Співвідношення (3) називається рівнянням лінійногоміжгалузевого балансуРазом із викладеною інтерпретацією матриці Аі векторів це співвідношення називають також моделлю Леонтьєва.

Рівняння міжгалузевого балансу можна використовуватиме планових розрахунків:

Задаючи для кожної галузі iваловий випуск продукції можна визначити обсяги кінцевого споживання кожної галузі, width="101"

де Е- одинична матриця;

Задаючи величини кінцевого споживання кожної галузі :

де - матриця, зворотна до матриці і невід'ємні (це витікає з економічного сенсу А, https://pandia.ru/text/78/095/images/image019_9.gif" width="16" height="23 src="> ). Для стислості будемо записувати це так: .

Таким чином, планові розрахунки за моделлю Леонтьєва можна виконувати за дотримання наступної умови продуктивності:

матриця називається продуктивноюякщо для будь-якого вектора існує рішення рівняння(3).

В цьому випадку і модель Леонтьєва, яка визначається матрицею А, теж називається продуктивною.

Сформулюємо критерії продуктивності матриці продуктивна тоді і тільки тоді, коли матриця існує і невід'ємна.

КритерійII. Матриця в матричний ряд в матричний ряд

У співвідношенні (4) матриці називаються матрицями коефіцієнтів непрямих витрат 2-го, 3-го і т. д. порядків. Їхня сума утворює матрицю коефіцієнтів непрямих витрат

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

Таким чином, із співвідношень (4) та (5) маємо

тобто матриця коефіцієнтів повних матеріальних витрат включає матриці коефіцієнтів прямих і непрямих витрат.

Розглянемо приклади.

приклад 1. Дослідити на продуктивність матрицю

https://pandia.ru/text/78/095/images/image037_4.gif" width="48 height=19" height="19">:

https://pandia.ru/text/78/095/images/image039_4.gif" width="577" height="143 src=">

Додатки алгебри для елементів матриці

https://pandia.ru/text/78/095/images/image041_4.gif" width="189 height=55" height="55">;

https://pandia.ru/text/78/095/images/image043_3.gif" width="220 height=55" height="55">;

https://pandia.ru/text/78/095/images/image045_3.gif" width="221 height=55" height="55">;

https://pandia.ru/text/78/095/images/image047_5.gif" width="209" height="55 src=">;

https://pandia.ru/text/78/095/images/image049_3.gif" width="468" height="84 src=">

Отримана матриця невід'ємна і за критерієм I вихідна матриця Апродуктивна.

приклад 2. Для матриці коефіцієнтів прямих витрат з прикладу 1 і вектора кінцевого споживання

https://pandia.ru/text/78/095/images/image051_3.gif" width="80" height="84 src=">

а) Вектор валового випуску обчислимо за формулою

https://pandia.ru/text/78/095/images/image053_3.gif" width="483" height="84 src=">

б) Матрицю непрямих витрат Узнайдемо із співвідношення (2.6):

https://pandia.ru/text/78/095/images/image055_3.gif" width="409" height="84 src=">

Таким чином, при збільшенні вектора кінцевого споживання на https://pandia.ru/text/78/095/images/image056_3.gif".

лекція 3,4,5

Завдання математичного та лінійного програмування.

Моделі лінійного програмування.

Нерідко економічні завдання мають єдине рішення і потрібно вибрати найкраще – оптимальне їх. Моделювання таких завдань зводиться до математичного програмування (ЗМП).

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

Сформулюємо в загальному виглядіЗМП:

https://pandia.ru/text/78/095/images/image058_3.gif" width="296" height="79"> (8)

https://pandia.ru/text/78/095/images/image060_3.gif" width="123" height="25"> – цільова функція, умови (8) – спеціальні обмеження, умови (9) – загальні обмеження ЗМП.

Крапку , координати якої задовольняють обмеженням (8) та (9), називають допустимим рішеннямЗМП.

Безліч всіх допустимих рішень ЗМП називають допустимою безліччю.

Допустиме рішення , що задовольняє співвідношенню (7), називають оптимальним рішеннямЗМП.

Якщо ЗМП цільова функція і функції , – лінійні, маємо загальне завдання лінійного програмування (ЗЛП):

https://pandia.ru/text/78/095/images/image065_3.gif" width="356" height="79 src="> (11)

https://pandia.ru/text/78/095/images/image066_3.gif" width="336" height="25 src=">;

- стандартнаЗЛП, що включає як обмеження (11) тільки нерівності, тобто.

https://pandia.ru/text/78/095/images/image068_3.gif" width="20" height="25">, і , з якого можна налагодити виробництво двох видів товарів: https://pandia.ru /text/78/095/images/image072_2.gif" width="20" height="25 src=">. Запаси сировини, норма витрати на виробництво одиниці товарів, і навіть прибуток від одиниці кожного товару наведено у таблиці 1 (цифри умовні).

Таблиця 1

Методи оптимальних рішень

ЗМІСТ

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

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

Таблиця 1. Графік самостійної роботи з дисципліни «Методи оптимальних рішень»

Зміст	Терміни здачі	Критерії оцінки
1. Вивчення теоретичного матеріалу
2. Розв'язання завдань контрольної роботи	За 1,5 місяці до сесії	Кожне завдання оцінюється за десятибальною системою
3. Підготовка до підсумкової аттестації	Під час сесії

1. ВВЕДЕННЯ. ЗАГАЛЬНА ПОСТАНОВКА ЗАВДАННЯ

p align="justify"> Процеси прийняття рішень лежать в основі будь-якої цілеспрямованої діяльності. В економіці вони передують створенню виробничих та господарських організацій, забезпечують їх оптимальне функціонування та взаємодію. У наукових дослідженнях – дозволяють виділити найважливіші наукові проблеми, Визначити способи їх вивчення, визначають розвиток експериментальної бази і теоретичного апарату. При створенні нової техніки– складають важливий етапу проектуванні машин, пристроїв, приладів, комплексів, будівель, у розробці технології їх побудови та експлуатації; в соціальній сфері- використовуються для організації функціонування та розвитку соціальних процесів, їх координації з господарськими та економічними процесами Оптимальні (ефективні) рішення дозволяють досягати мети при мінімальних витратахтрудових, матеріальних та сировинних ресурсів.

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

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

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

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

Під прийняттям рішень у курсі «Методи оптимальних рішень» розуміють складний процес, у якому можна виділити такі основні етапи:

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

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

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

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

Широкий клас завдань управління складають такі екстремальні завдання, у математичних моделях яких умови на змінні задаються рівностями та нерівностями. Теорія та методи вирішення цих завдань якраз і складають зміст математичного програмування. На третьому етапі, користуючись математичним апаратом, знаходять розв'язання відповідних екстремальних завдань. Звернімо увагу на те, що завдання математичного програмування, пов'язані з вирішенням практичних питань, як правило, мають велике числозмінних та обмежень. Обсяг обчислювальних робіт для знаходження відповідних рішень настільки великий, що весь процес не мислиться без застосування сучасних електронних обчислювальних машин (ЕОМ), а значить, вимагає створення програм для ЕОМ, що реалізують ті чи інші алгоритми, або використання вже наявних стандартних програм.

4-й етап. Зіставлення результатів обчислень, отриманих на 3-му етапі, з об'єктом, що моделюється, тобто експертна перевірка результатів (критерій практики). Таким чином, на цьому етапі встановлюється ступінь адекватності моделі та об'єкта, що моделюється, в межах точності вихідної інформації. Тут можливі два випадки:

1-й випадок. Якщо результати зіставлення незадовільні ( звичайна ситуаціяна початковій стадії процесу моделювання), то переходять до другого циклу процесу. При цьому уточнюється вхідна інформація про об'єкт, що моделюється, і, у разі необхідності, уточнюється постановка завдання (1-й етап); уточнюється чи будується наново математична модель (2-й етап); вирішується відповідне математичне завдання (3 етап) і, нарешті, знову проводиться зіставлення (4 етап).

2-й випадок. Якщо результати зіставлення задовільні, модель приймається. Коли мова йдепро неодноразове використання практично результатів обчислень, виникає завдання підготовки моделі до експлуатації. Припустимо, наприклад, що метою моделювання є створення календарних планів виробничої діяльностіпідприємства. Тоді експлуатація моделі включає збирання та обробку інформації, введення обробленої інформації в ЕОМ, розрахунки на основі розроблених програм календарних планів і, нарешті, видачу результатів обчислень (у зручному для користувачів вигляді) для їх використання у сфері виробничої діяльності.

У математичному програмуванні можна назвати два напрями.

До першого, вже цілком сформованого напряму – власне математичного програмування – ставляться детерміновані завдання, які передбачають, що вся вихідна інформація цілком певною.

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

Традиційно в математичному програмуванні виділяють такі основні розділи:

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

Нелінійне програмування – цільова функція та обмеження нелінійні. Нелінійне програмування прийнято поділяти так:

Випукло програмування – цільова функція опукла (якщо розглядається завдання її мінімізації) і опукло безліч, де вирішується екстремальна задача.

Квадратичне програмування – цільова функція квадратична, а обмеженнями є лінійні рівності та нерівності.

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

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

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

Нарешті, зауважимо, що найменування предмета – " методи оптимальних рішень " – пов'язані з тим, що метою вирішення завдань вибір програми дій. Розглянемо докладніше завдання лінійного програмування

2. ГЕОМЕТРИЧНЕ ВИТОРКУВАННЯ ЗАВДАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Завдання лінійного програмування (ЗЛП):

знайти вектор X = (x 1 ,x 2 ,...,x n) максимізуючий лінійну форму

F = Σ c j x j → max (2.1)

J=1

і задовольняє умовам:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

Лінійна функція F називається цільовою функцією завдання.

Перепишемо це завдання у векторній формі:

Знайдемо такі функції:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 (2.5)

x j ≥0 , j = 1,…,n (2.6)

де P 1 , …, P n і P 0 - m-мірні вектори стовпці, з коефіцієнтів при невідомих і вільних членів системи рівнянь задачі:

B 1 a 11 a 12 a 1n

P 0 = (b 2); P 1 = (a 21); P 2 = (a 22); ……. P n = (a 2n); (2.7)

… … … …

B n a m1 a m2 a mn

План X = (x 1 x 2 ... x n) називається опорним планом основної ЗЛП, якщо позитивні коефіцієнти х j стоять при лінійно незалежних векторах Р j .

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

Теорема

Якщо основна ЗЛП має оптимальний планмаксимальне значення цільова функція завдання приймає в одній з вершин багатогранника рішень.

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

Висновки:

Непорожня безліч планів основної ЗЛП утворює опуклий багатогранник;

Кожна вершина цього багатогранника визначає опорний план;

В одній із вершин багатогранника значення цільової функції є максимальним.

Двовимірний випадок ЗЛП

Знайдемо рішення задачі, що полягає у визначенні максимального значенняфункції

F = c 1 x 1 + c 2 x 2 (2.8)

за умов

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1,2) (2.10)

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

Для визначення даної вершини побудуємо лінію рівня c 1 x 1 +c 2 x 2 =h, (де h - деяка постійна), що проходить через багатокутник рішень, і пересуватимемо її в напрямку вектора С = (з 1, з 2) до тих доки вона не пройде через останню її загальну точку з багатокутником рішень. Координати зазначеної точки визначають оптимальний план даної задачі.

Етапи розв'язання ЗЛП геометричним методом:

1. Побудувати прямі за рівняннями (2.9), (2.10).

2. Знайти напівплощини, що визначаються кожним із обмежень задачі.

3. Знайти багатокутник рішень.

4. Побудувати вектор.

5. Побудувати пряму c 1 x 1 +c 2 x 2 =h, що проходить через багатокутник розв'язків.

6. Пересунути пряму c 1 x 1 +c 2 x 2 =h у напрямку вектора.

7. Визначити координати точки максимуму функції та обчислити значення цільової функції у цій точці.

приклад 1.

Для виробництва двох видів виробів А та В підприємство використовує три види сировини. Норми витрати сировини кожного виду на виготовлення одиниці виробленої продукції даного виду наведені в Таблиці 2.1. У ній же зазначено прибуток від одного виробу кожного виду та загальна кількість сировини цього виду, яка може бути використана підприємством.

Таблиця 2.1

Уіди сировини	Норми витрати сировини (кг) на один виріб		Загальна кількість сировини (кг)
Уіди сировини	А	У	Загальна кількість сировини (кг)
1	12	4	300
2	4	4	120
3	3	12	252
Прибуток одного виробу від (руб.)	30	40

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

Рішення:

х1 - випуск виробів виду А

х2 – випуск виробів виду

Тоді обмеження завдання:

Загальний прибуток від виробів виду і В складе: F = 30х 1 + 40x 2

Знайдемо розв'язання задачі, використовуючи її геометричну інтерпретацію.

Для цього в нерівностях системи обмежень перейдемо до рівностей і збудуємо відповідні прямі:

Знайдемо координати точки В – перетину прямих:

Розв'язавши цю систему рівнянь, отримаємо: x 1 = 12; x 2 = 18

Отже, якщо підприємство виготовить 12 виробів виду А та 18 виробів виду В, то воно отримає максимальний прибуток, що дорівнює

F max = 30 · 12 +40 · 18 = 1080 руб.

приклад 2.

Вирішити ЗЛП

max(min)F = 2x1 +3x2;

Рішення. Для побудови області допустимих рішень будуємо в системі x 1 Ox 2 граничні прямі, що відповідають даним обмеженням-нерівностям:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

Знаходимо напівплощини, у яких виконуються дані нерівності. Для цього внаслідок опуклості будь-якої напівплощини достатньо взяти довільну точку, через яку не проходить відповідна гранична пряма, і перевірити, чи ця пробна точка задовольняє обмеження-нерівності. Якщо задовольняє, то дана нерівність виконується в напівплощині, що містить пробну точку. В іншому випадку береться напівплощина, що не містить пробної точки. Як пробна точка часто зручно брати початок координат О(0; 0). Для нашого прикладу область допустимих рішень - безліч точок чотирикутника АВСD (рис. 6).

Будуємо вектор з = (з 1; з 2) = (2; 3). Так як він необхідний лише для з'ясування напрямку зростання цільової функції, іноді для більшої наочності зручно будувати λс (λ> 0). Перпендикулярно вектору з проводимо лінію рівня F=0. Паралельним переміщенням прямий F = 0 знаходимо крайню точку В. в якій цільова функція приймає максимальне значення і точку А, в якій досягається мінімальне значення.

Координати точки визначаються системою

Звідки Fmax = F(A) = 32/9

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО РІШЕННЯ

Завдання 1.1-1.10 вирішити графічно.

Завдання з багатьма змінними

Розглянемо наступне завдання лінійного програмування

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

Зробити це можна, послідовно, виключаючи змінні або методом Жордана-Гаусса. Розглянемо спосіб Жордана-Гаусса.

Таблиця 1

x 1

x 2

x 3

x 4

x 5

-1

(-3) 1 , (-1) 3,4

Таблиця 2

x 2

-2

-1

-3

-4

-2

-1

-3

(2) 1 , (-1) 2 ,(1) 3

Таблиця 3

x 2

x 4

-4

-1

-2

-1

-4

(-1) 2 , (1) 3 ,(2) 4

Таблиця 4

x 5

x 2

x 4

-2

(-1) 2 , (1) 3 ,(2) 4

Відкинемо в рівняннях-обмеженнях невід'ємні дозволені невідомі

x 2 , x 4 , x 5 і замінимо знак рівності знаками нерівності, отримаємо допоміжне завдання лінійного програмування з двома змінними:

F(x) = 2 x 3 +2 → max

F (x) = 0: 2 x 3 +2 -0 (0; -1); (5; -1)

F max = 2 при х 1 = 0; x 3 = 0

3. СИМПЛЕКСНИЙ МЕТОД РІШЕННЯ ЗАВДАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ

3.1. Геометрична інтерпретація симплексного методу

Якщо завдання лінійного програмування оптимізується, то оптимум відповідає кутовий точці (хоча б однієї) О.Д.Р. і збігається з хоча б одним із невід'ємних базисних рішень. Таким чином, перебираючи кінцеве число невід'ємних базисних рішень системи, вибираємо їх те, що відповідає екстремальному значенню цільової функції. Графічно це означає, що ми перебираємо кутові точки багатогранника рішень, покращуючи значення цільової функції.

Симплексний метод полягає у:

1) визначення початкового допустимого базисного розв'язання задачі;

2) переході на краще рішення;

3) перевірці оптимального допустимого рішення.

3.2. Таблична інтерпретація симплексного методу

Симплексним методом вирішуються завдання лінійного програмування, записані у канонічній формі:

Знайти оптимальне рішення

X = (x 1, x 2, ..., x n) (3.1)

що задовольняє системі обмежень (рівнянь)

∑a ij x j = b i (i = 1, m) (3.2)

j=1

та умовам x j ≥ 0 (j=1,n)

і дає екстремальне значення цільової функції

Z(x) = Σ c j x j (3.3)

j=1

Нехай знайдено початкове невід'ємне базисне рішення системи (3.2), де х 1, х 2, х 3 … х m - базисні невідомі, а х m +1, x m +2, …, x n - вільні невідомі.

Тоді система (3.2) перетворюється на дозволену систему

(3.4)

Даній системі відповідає невід'ємне базове рішення виду

X 0 = (b 1, b 2, ..., b m, 0,0 ... 0)

Підставимо отримане рішення на цільову функцію

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

і перетворимо її таким чином, щоб вона залежала тільки від вільних невідомих х m+1, х m+2 , … х n

Усі базисні невідомі х 1, х 2, х 3 … х m виразимо через вільні х m+1, х m+2, … х nі підставимо цільову функцію.

Тоді цільова функція набуде вигляду (3.6)

Введемо поняття оцінки Δj вільних невідомих

(3.7)

Тоді цільова функція набуде вигляду

(3.8)

Введемо до розгляду вектори C = (c 1 , c 2 , …, c m) і B = (a 1j , a 2j , …, a mj) (j=m+1,n) тоді рівність (3.7) можна записати у векторній формі

Δ j =CB j -c j (3.9)

Рівність (3.8) за характером запису не відрізняється від рівнянь системи, тому додамо його до цієї системи та отримаємо розширену систему:

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

Б.М.	C	B	з 1	з 2	...	c m	c m+1	...	c j	...	c n
Б.М.	C	B	x 1	x 2	...	x m	x m+1	...	x j	...	x n
x 1	з 1	β 1	1	0	...	0	a 1(m+1)	...	a 1j	...	a 1n
x 2	з 2	β 2	0	1	...	0	a 2(m+1)	...	a 2j	...	a 2n
...	...	...	...	...	...	...	...	...	...	...	...
x m	c m	β m	0	0	...	1	a m(m+1)	...	a mj	...	a mn
L(X)	Δ j ≥0	Δ 0	0	0	...	0	Δ m+1	...	Δj	...	Δ n

першому стовпці записані базисні невідомі x 1 x 2 … x m; у стовпці C записані коефіцієнти з цільової функції, що відповідають цим базовим невідомим; в стовпці B - вільні члени рівнянь системи, що збігаються з позитивними компонентами початкового базового невід'ємного рішення X 0 . Під невідомими x 1 x 2 … x n в стовпцях записані коефіцієнти із системи.

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

В оціночному рядку нерівність j ≥0 і означає критерій оптимальності опорного плану.

Алгоритм рішення ЗЛП симплекс-метод.

1. Знайти опорний план.

2. Скласти симплекс-таблицю.

3. З'ясувати, чи є хоча б одне від'ємне число Δj

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

4. Знайти напрямний стовпець та рядок. Найбільший стовпець визначається найбільшим по абсолютної величинивід'ємним числом Δ j , А напрямний рядок – мінімальним з відношень компонент стовпця вектора Р 0 до позитивних компонентів стовпця напрямного.

5. За формулами (3.7) – (3.9) визначити позитивні компонентинового опорного плану, коефіцієнти розкладання векторів Р j за векторами нового базису та числа. Всі ці числа записуються в новій симплекс-таблиці.

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

Приклад 3.1.

Для виготовлення різних виробів А, В та С підприємство використовує три різні види сировини. Норми витрати сировини на виробництво одного виробу кожного виду, ціна одного виробу А, В та С, а також загальна кількість сировини кожного виду, яка може бути використанаієм, при ведені у таблиці.

Скласти план виробництва виробів, за якого загальна вартість всієї виробленої продукції буде максимальною.

Рішення:

Складемо математичну модель. Позначимо:

х 1 – випуск виробів виду А;

х 2 – випуск виробів виду;

х3 – випуск виробів виду З.

Запишемо систему обмежень:

Загальна вартість вироблених товарів складає:

F = 9x1+10x2+16x3

За економічним змістом змінні х 1 , х 2 , х 3 можуть набувати лише невід'ємні значення:

x 1 ,x 2 ,x 3 ≥0

Запишемо це завдання у вигляді основної ЗЛП, для цього перейдемо від системи нерівностей до рівностей, для цього введемо три додаткові змінні:

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

Запишемо перетворену систему рівнянь у векторній формі:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

де

Оскільки серед векторів Рj є три одиничних вектори, то для даної задачі можна записати опорний план Х = (0, 0, 0, 360, 192, 180), який визначається системою одиничних векторів Р 4 , Р 5 , Р 6 які утворюють базис тривимірного простору.

Складаємо симплексну таблицю I ітерації та підраховуємо значення F0, zj-cj.

Перевіряємо вихідний план на оптимальність:

F 0 = (З, P 0) = 0; z 1 = (З, P 1) = 0; z 2 = (З, P 2) = 0; z 3 = (З, P 3) = 0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

Для векторів базису zj-cj = 0 (j=4,5,6).

Максимальне від'ємне число Δ j стоїть у 4-му рядку стовпця Р 3 . Отже, базис введемо вектор Р 3 . Визначимо вектор, що підлягає виключення з базису, при цьому знаходимо 0 = min(b i /a ij) для a i3 >0 тобто. Θ = min (360/12; 192/8; 180/3) = 192/8 = 24.

Тобто. обмежуючим чинником виробництва виробів З є наявний обсяг сировини ІІ виду. З урахуванням його наявності підприємство може виготовити 24 вироби С, при цьому сировина II виду буде повністю витрачена.ванно.

Отже, вектор Р 5 підлягає виключенню з базису. Стовпець вектора Р 3 і 2-й рядок є напрямними.

Складемо таблицю II ітерації. Спочатку заповнюємо рядок вектора, знову введеного в базис, тобто. спрямовуючий рядок 2. Елементи цього рядка виходять шляхом поділу відповідних елементів таблиці 1 на роздільний елемент (тобто 8). При цьому в стовпець С б записуємо коефіцієнт С 3 =16, що стоїть у стовпці вводиться в базис вектора Р 3

Для визначення інших елементів таблиці II застосуємо правило трикутника.

Обчислимо елементи таблиці II, які у стовпці Р 0 .

Перший елемент - знаходимо три числа

1) число, що стоїть у т. 1 на перетині стовпця Р0 та 1-го рядка (360);

2) число, що стоїть у т. 1 на перетині стовпця Р3 та 1-го рядка (12);

3) число, що стоїть у т. 2 на перетині стовпця Р0 та 2-го рядка (24).

360-12 · 24 = 72

Другий елемент було обчислено раніше (Θ 0 = 192/8 =24)

Третій елемент -

1) число, що стоїть у т. 1 на перетині стовпця Р0 та 3-го рядка (180);

2) число, що стоїть у т. 1 на перетині стовпця Р3 та 3-го рядка (3);

3) число, що стоїть у т. 2 на перетині стовпця Р0 та 2-го рядка (24).

180-3 · 24 = 108

Значення F 0 в 4-му рядку цього ж стовпця можна знайти двома способами.бамі:

1) за формулою F0 = (C, P0) =0 · 72 +16 · 24 + 0 · 108 = 384;

2) за правилом трикутника:

Обчислимо елементи вектора Р1 т.2. Перші два числа беремо зі стовпівців Р 1 і Р 3 т.1,

а третє число - з т.2 на перетині 2-го рядка та стовпця Р1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Число z 1 -c 1 у 4-му рядку стовпця вектора P 1 таблиці 2

можна знайти двома способами:

1) за формулою z 1 -з 1 =(C,P 1)-c 1 маємо:

0·9+16·3/ 4+0·11/ 4-9 =3

2) за правилом трикутника отримаємо:

-9-(-16) 3/ 4 = 3

Аналогічно знаходимо елементи стовпця вектора P2.

Елементи стовпця вектора Р 5 обчислюємо за правилом трикутника.

виглядають інакше. Проте побудовані визначення цих елементів трикутники

При обчисленні елемента 1-го рядка вказаного стовпця виходитьтрикутник, утворений числами 0; 12 та 1/8. Отже, шуканийелемент дорівнює

0 – 12 (1/8) = -3/2.

Елемент, що стоїть у 3-му рядку даного стовпця, дорівнює

0 - 3 (1 /8) = -3/8.

Після закінчення розрахунку всіх елементів таблиця II в ній отримановий опорний план та коефіцієнти розкладання векторів Р j через базиснівектори P 4 , P 3 , P 6 і значення F 0 "J".

Як видно з цієї таблиці, новим опорним планом завдання єплан X = (0; 0; 24; 72; 0; 108).

Знайдений на II ітерації план завдання є оптимальним.

цього рядка стоїть від'ємне число – 2. Це видно з 4-го рядка таблиці 2, оскільки у стовпці вектора P 2 .

Отже, у базис слід запровадити вектор P 2 , тобто у новому плані слід передбачити випуск виробів.

При визначенні можливого числа виготовлення виробів слід враховувати наявну кількість сировини кожного виду, а саме: можливий випуск виробів визначається min (b i "/a i 2") для a i2 ">0 тобто знаходимо Θ 0 = min(72/9; 24·2/1; 108·2/3) = 72/9= 8.

Отже, виключенню з базису підлягає вектор Р4 іншими словами, випуск виробів обмежений наявним у розпорядженні підприємства сировиною I виду. З урахуванням наявних обсягів цієї сировини підприємству слід виготовити 8 виробів Ст. Число 9 є роздільним елементом, а стовпець вектора P2 і 1 рядок таблиці 2 є напрямними.

Складемо таблицю для ІІІ ітерації.

У таблиці III спочатку заповнюємо елементи 1-го рядка, яка є рядком знову введеного в базис вектора Р2. Елементи цього рядка отримуємо з елементів 1-го рядка таблиці 2 розподілом останніх на роздільну здатність (тобто на 9).

При цьому в стовпці С б даного рядка записуємо з 2 = 10.

Потім заповнюємо елементи стовпців векторів базису і за правилом трикутника обчислюємо елементи інших стовпців.

У результаті таблиці III отримуємо новий опорний план X=(0; 8; 20; 0; 0; 96) і коефіцієнти розкладання векторів Р j через базисні вектори P 1 , P 2 і P 3 відповідні значення F 0 "" і Δ j .

Перевіряємо, чи є даний опорний план оптимальним чи ні. Для цього розглянемо 4-й рядок таблиці 3 . У цьому рядку серед чисел немає негативних. Це означає, що знайдений опорний план є оптимальним та F max =400.

Отже, план випуску продукції, що включає виготовлення 8 виробів і 20 виробів, є оптимальним. При цьому плані випуску виробів повністю використовується сировина I і II видів і залишається невикористаною 96 кг сировини III виду, а вартість продукції дорівнює 400 €.

Оптимальним планом виробництва не передбачається виготовлення виробів А. Введення у план випуску продукції виробів виду А призвело до зменшення зазначеної загальної вартості. Це видно з 4-го рядка стовпця вектора P1, де число 5 показує, що при даному плані включення в нього випуск одиниці виробу А призводить лише до зменшення загальної величини вартості на 5 €.

Приклад 3.2

Заповнити початкову симплексну таблицю для наступної ЗЛП:

Рішення:

Виконаємо наступні діїу вказаному порядку:

-В другий рядок запишемо невідомі x 1, x 2, …, x 5;

-у першому рядку над ними – відповідні коефіцієнти 3, -2, 1,4,-1 з цільової функції;

-під невідомими x 1 x 2 … x 5 заповнимо стовпці, складені з відповідних коефіцієнтів лівих частин рівнянь вихідної системи;

-У стовпець запишемо вільні члени рівнянь 3,1,5;

-У перший стовпець Б.П. помістимо невідомі x 2 ,x 3 , x 5 , оскільки під ними стоять поодинокі стовпці, і тому їх вважатимемо базисними; базисні невідомі розташовуються у такому порядку, щоб одиниці у стовпцях перебували на перетині однакових невідомих;

-у стовпець запишемо коефіцієнти -2,1,-1, з цільової функції при вибраних базисних невідомих x 2 ,x 3 , x 5 ;

-Заповнимо оціночний рядок наступним чином: під стовпцем B помістимо число Δ 0 обчислене за формулою (3.5); під базисними невідомими x 2 ,x 3 , x 5 - нулі, які можна отримати з рівності (3.9); під вільними змінними x 1 , x 4 - Запишемо значення, одержані з рівності (3.9).

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

Виберемо в якості роздільної здатності стовпець х 4 як самий «поганий» (йому відповідає найбільша за модулем негативна оцінка). Далі введемо роздільну здатність наступним чином: для позитивних коефіцієнтів стовпця х 4 обчислимо відносини b i /a i4 запишемо їх у графу θ.

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

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

Отже, вже у таблиці другого кроку критерій оптимальності виконаний. Ми отримали оптимальний план Х(0;0;11/2;3/2;13/2), max L(X) =5.

МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ

Навчальний посібник

УДК 51-77.330.4

МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ

Складемо економіко-математичну модель завдання. Позначимо через xj - кількість вихідного матеріалу (аркушів сталі), які необхідно розкроїти по одному із способів j. Обмеження завдання повинні відповідати плановому виходу заготовок різних видів. Цільова функціязводитися до знаходження мінімуму відходів при розкрої

https://pandia.ru/text/78/539/images/image018_31.gif" width="159" height="105 src=">

приклад 2.На розкрій (розпил, обробку) надходить матеріал одного зразка в кількості одиниць. Потрібно виготовити з нього різних комплектуючих виробів у кількостях, пропорційних числам b1, b2,…,bl (умова комплектності). Кожна одиниця матеріалу може бути розкрита n у різний спосіб, причому використання i-го способу (i = 1, 2,…,n) дає aik одиниць k-го виробу (k = 1, 2,…,l). Необхідно знайти план розкрою, що забезпечує максимальна кількістькомплектів.

Складемо економіко-математичну модель завдання.

Позначимо через xi - число одиниць матеріалу, що розкраюються i-им способом, і x - число комплектів виробів, що виготовляються. Тоді цільова функція зводиться до знаходження

https://pandia.ru/text/78/539/images/image020_30.gif" width="163" height="116 src=">

1.4. Завдання про використання потужностей

Підприємству заданий план виробництва продукції за часом та номенклатурою. Потрібно протягом часу t випустити n1, n2,…,nk одиниць продукції p1, p2,…,pk Продукція виробляється на верстатах s1, s2,…,sm. Для кожного верстата відомі продуктивність aij, тобто кількість одиниць продукції pj, які можна виготовити на верстаті si та витрати bij на виготовлення продукції pj на верстаті si в одиницю часу. Необхідно скласти такий план роботи верстатів, щоб витрати виробництва всієї продукції були мінімальними.

Позначимо через xij - час, протягом якого верстат буде зайнятий виготовленням продукції pj (i = 1, 2, ..., m; j = 1, 2, ..., k) Тоді витрати на виробництво всієї продукції висловляться функцією

https://pandia.ru/text/78/539/images/image023_31.gif" width="133" height="84 src=">

за номенклатурою та не негативністю змінних

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

https://pandia.ru/text/78/539/images/image026_24.gif" width="39" height="20 src=">. Враховуючи балансове, кредитне та ліквідне обмеження, отримаємо систему обмежень нерівностей

https://pandia.ru/text/78/539/images/image028_27.gif" width="65" height="40">, (11)

за умов

(12)

Функція (11) називається цільовою функцією ЗЛП, а умови (12) - обмеженнями ЗЛП.

Визначення..gif" width="108" height="25">, при якому цільова функція набуває максимального або мінімального значення.

Визначення. Основною (або канонічною) ЗЛП називається завдання, яке полягає у визначенні оптимального значення цільової функції, за умови, що система обмежень представлена у вигляді системи рівнянь

https://pandia.ru/text/78/539/images/image032_29.gif" width="175" height="63 src=">

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

https://pandia.ru/text/78/539/images/image034_27.gif" width="157" height="63">

3. ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ ЗАВДАНЬ
ЛІНІЙНОГО ПРОГРАМУВАННЯ

Розглянемо ЗЛП із двома змінними:

https://pandia.ru/text/78/539/images/image037_24.gif" width="112" height="103 src=">

Кожна нерівність системи обмежень задачі геометрично визначає напівплощину відповідно до граничних прямих ai1x1 + ai2x2 = bi, (i = 1,2,…,m). Умову невід'ємності визначають напівплощини з граничними прямими x1 = 0, x2 = 0. Якщо система нерівностей спільна, то область її розв'язків є безліч точок, що належать усім зазначеним напівплощин. Сукупність цих точок називатимемо багатокутникомрішень чи областю допустимих рішень (ОДР) ЗЛП. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з вихідної системи обмежень заміною знаків нерівностей на рівні знаки (граничні прямі).

Області допустимих рішень системи нерівностей можуть бути:

– опуклий багатокутник;

- Випукла багатокутна необмежена область;

- Порожня область;

- Відрізок;

- Єдина точка.

Цільова функція L визначає на площині сімейство паралельних прямих, кожній з яких відповідає певне значення L. Цільова функція без вільного члена c1x1 + c2x2 = 0 проходить через початок координат і називається основною прямою. Вектор перпендикулярний до цієї прямої, вказує напрямок якнайшвидшого зростання L, а протилежний вектор – напрямок зменшення L.

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

Теорема.Якщо ЗЛП має оптимальний план, то цільова функція задачі набуває свого оптимального значення в одній з вершин багатокутника рішень.

Для визначення даної вершини будується L = 0, що проходить через початок координат і перпендикулярно вектору, і пересувається в напрямку цього вектора доти, доки вона не торкнеться останньої точки багатокутника рішень. Координати отриманої точки визначають максимальне значення цільової функції L та максимальний план даної задачі.

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

Якщо напрямку вектора багатокутник рішень необмежений, то .

3.2. Графічний метод розв'язання задач
лінійного програмування

Графічний методзаснований на геометричній інтерпретації ЗЛП та включає наступні етапи:

– будують граничні прямі, рівняння яких одержують у результаті заміни у системі обмежень ЗЛП знаків нерівностей на знаки точних рівностей;

- Знаходять напівплощини, що визначаються кожним з обмежень нерівностей ЗЛП;

- Знаходять багатокутник рішень (область допустимих рішень);

- будують основну пряму с1x1 + c2x2 = 0, що проходить через початок координат та перпендикулярну вектору;

– переміщують пряму L = 0 у напрямку вектора. В результаті знаходять точку (точки), в якою цільова функція приймає оптимальне рішення, або встановлюють необмеженість функції на багатьох планах.

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

Оптимальне (математичне) програмування – розділ прикладної математики, що вивчає завдання умовної оптимізації. В економіці такі завдання виникають при практичній реалізації принципу оптимальності у плануванні та управлінні. До оптимального (математичне) програмування входять:

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

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

Математичне моделювання має дві істотні переваги: 1) дає швидку відповідь на поставлене питання, на що в реальній обстановці можуть знадобитися іноді навіть роки; 2) надає можливість широкого експериментування, здійснити яке реальному об'єкті часто просто неможливо.

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

Визначення тих значень керованих змінних, яким відповідає найкраща (оптимальна) ситуація, і є завданням оптимізації.

Модель економічного завданняоптимізації складається з 3-х частин:

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

ІІ. Система обмежень.

Обмеження бувають основні та додаткові. Основні, зазвичай, описують витрата основних виробничих ресурсів (це консервативна частина моделі). У моделі вони обов'язково є. Додаткові - можуть мати різний характер, є змінною частиною моделі та відображають особливість моделювання завдання.

ІІІ. Умова невід'ємності змінних величин. А також граничні умови, які показують, у яких межах можуть бути значення змінних, що шукаються, в оптимальному рішенні.

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

Однак, слід мати на увазі, що вирішення не всіх оптимізаційних проблем зводиться до побудови математичних моделей та відповідних обчислень. Це пов'язано з тим, що можуть з'явитися обставини, які є суттєвими для вирішення проблеми, проте не піддаються математичній формалізації і, отже, не враховуються в математичній моделі. Однією з таких обставин є людський чинник. У зв'язку з цим можна згадати про так звану «проблему ліфта». Службовці однієї з фірм скаржилися надто довге очікування ліфта. Була спроба вирішити цю проблему математичними методами. Рішення з низки причин виявилося неприйнятним, а подальші дослідження показали, що час очікування ліфта невеликий. Тоді виникла ідея поставити на кожному поверсі поряд із входом у ліфт великі дзеркала. Щойно це було зроблено, скарги припинились. Тепер люди розглядали себе у дзеркалі та забували про довге очікування ліфта. Цей приклад показує необхідність правильно оцінювати можливості математичного опису досліджуваних процесів і пам'ятати, що у сфері організаційного управління в повному обсязі не завжди піддається математичної формалізації і може бути адекватно відбито у математичної моделі.