Дата конвертації23.03.2017
Розмір98.71 Kb.
Типреферат

Скачати 98.71 Kb.

Побудова економічної моделі c використанням симплекс-методу

<0><0>

Минестерство освіти України

Днепрпетровске державний університет

Курсова робота

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

Роботу виконав:

студент групи РС-97-1

Борщівський Єгор

перевірив:

Доцент кафедри АСУ

Саліков В.А.

Дніпропетровськ тисячу дев'ятсот дев'яносто дев'ять

ЗМІСТ

Анотація _________________________________________ 3

Введення .__________________________________________ 4

1. ОСНОВИ СИСТЕМНОГО ПІДХОДУ _______________ 5

1.1.Основні поняття і визначення системного подхода__ 5

1.1.1. Поняття системи і середовища ________________________ 7

1.1.2. Поняття проблемної ситуації __________________ 11

1.1.3. Поняття мети системи _________________________ 14

1.1.4. Поняття функцій системи ______________________ 16

1.1.5. Структура системи ____________________________ 17

1.1.6. Зовнішні умови системи ______________________ 20

1.1.7. Основні етапи системної діяльності __________ 21

1.2. Моделі систем _________________________________ 22

1.2.1. Визначення і класифікація моделей систем ______ 22

1.2.2. Рівні моделей системи * ______________________ 25

ПРАКТИЧНА ЧАСТИНА ___________________________ 28

Словесний опис ________________________________ 28

Математичний опис .__________________________ 29

Обмеження ______________________________________ 30

Змінні _______________________________________ 31

Цільова функція ___________________________________ 32

Симплекс-метод .__________________________________ 33

Уявлення простору рішень стандартної завдання

лінейногопрограммірованія .______________________ 34

Обчислювальні процедури симплекс-методу .__________ 37

Оптимальне рішення ______________________________ 42

Статус ресурсів ___________________________________ 43

Цінність ресурсу __________________________________ 45

Максимальна зміна запасу ресурсу _______________ 47

Максимальна зміна коефіцієнтів питомої _______ 50

прибутку (вартості) ______________________________ 50

Висновок _______________________________________ 52

Список літератури: ________________________________ 53

анотація

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

Вступ.

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

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

Метою даної курсової роботи було вивчення практичного досвіду використання економіко-статистичних методів прогнозування.

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

Термін "модель" широко використовується в різних сферахчеловеческой діяльності і має безліч смислових значень. Розглянемо тільки такі "моделі", які є інструментами отримання знань.

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

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

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

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

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

1. ОСНОВИ СИСТЕМНОГО ПІДХОДУ

1.1.Основні поняття і визначення системного підходу

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

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

Уміння розпізнати систему, декомпозировать її на елементарні складові, визначити закони управління кожної підсистемою і знову синтезувати систему вимагає розробки ряду спеціальних формальних моделей, процедур алгоритмів. Ще філософ Стародавнього Риму Квіантіліан стверджував, що будь-яку як завгодно складну ситуацію можна повністю структурувати і описати, керуючись такими сім'ю питаннями [2] (рис. 1.1).


Мал. 1.1. Основні чинники системи

Наука, в рамках якої отримали розвиток дослідження, спрямовані на рішення вищеозначених проблем, отримала назву "теорія систем" - "системний підхід" - "системний аналіз". Ця теорія зародилася в 30-х роках ХХ століття і в 50-ті роки сформувалася як самостійна на-учное напрямок. Біля її витоків стояли біологи Берталанфі, Р, Жерар, фахівець з математичних проблем в області біології і психології - А.Рапопорт, економіст - К. Боулдинг [8].

Надалі ці дослідження були продовжені в численних роботах зарубіжних і вітчизняних вчених .: М. Месарочіча, С. Оптнера, С. Янга, Я. Такахару, Р. Акоффа, А.А. Богданова, В. М. Садовського, А.І. Уемова, Ю.І.Черняка, А.А. Денисова та ін.

1.1.1. Поняття системи і середовища

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

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

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

З урахуванням вищевикладеного перерахуємо наступні відмінні якості системи:

• система є щось ціле;

• система є безліч елементів, властивостей і відносин;

• система є організоване безліч елементів;

• система є динамічне безліч елементів.

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

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

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


Рис.1.2. Модель взаємодії системи і середовища

На вхід системи з середовища надходять:

• безліч цілей і обмежень - Z = {Zk} • безліч ресурсів - X = {Xj}

Висновком із системи є безліч кінцевих продуктів, благ і послуг орієнтованих на задоволення потреб зовнішнього середовища - Y = {Yi}.

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

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

На рис. 1.3 представлена ​​узагальнена модель взаємодії підприємства "як системи" з елементами її зовнішнього середовища.


Мал. 1.3. Модель взаємодії підприємства з елементами зовнішнього середовища

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

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

Y1- інженерні кадри;

Y11- інженерні кадри, підготовлені за типовими програмами;

Y12- інженерні кадри, підготовлені на замовлення органів влади і управління;

Y13- інженерні кадри, підготовлені на замовлення фінансових ин-ститутов;

Y14- інженерні кадри, підготовлені на замовлення конкретного підприємства і т.д .;

Y2- інформаційна продукція вузу;

Y21- навчально-методична література;

Y22- науково-технічна література;

Y23- звітна інформація про діяльність вузу;

Y3- науково-технічні розробки вузу;

Y4- кадри вищої кваліфікації.

В якості вхідних ресурсів навчального закладу виділимо:

X1 - фінансові ресурси для організації навчального процесу;

X11 - федеральний бюджет;

X12 - місцевий бюджет;

X13 - позабюджетні фонди;

X14 - благодійні фонди;

X15 - кредити банків;

X2 - фінансові ресурси для організації науково-дослідницької діяльності;

X3 - фінансові ресурси для організації адміністративно-господар-ської діяльності;

X4 - абітурієнти, які у вуз;

X41 - на основі держбюджетного фінансування;

X42 - на замовлення органів влади і управління;

X43 - на замовлення фінансових інститутів;

X44 - на замовлення конкретних промислових підприємств.

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

• по навчальної діяльності -

Z11 - вимоги ГОС на підготовку фахівців з конкретної спе-ціальностей;

Z12 - вимоги органів влади і управління на підготовку фахів-листів;

Z13 - вимоги фінансових структур на підготовку фахівців;

• по науково-дослідницької діяльності -

Z21 - вимоги федеральних органів до якості виконання госбюд-житніх тим;

Z22 - вимоги замовників до якості виконання госпдоговірних тем.

1.1.2. Поняття проблемної ситуації

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

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

Y = {Yip}; X = {Xjp}; Z = {Zkp}

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

• встановлення змісту проблеми, тобто з'ясування, чи є в дійсності проблема або вона є надуманою;

• визначення новизни проблемної ситуації;

• встановлення причин виникнення проблемної ситуації;

• визначення ступеня взаємозв'язку проблемних ситуацій;

• визначення повноти та достовірності інформації про проблемної ситуації; • визначення можливості вирішення проблеми.

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

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

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

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

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

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

Складність і різноманіття систем і проблемних ситуацій вимагають розробки формальних процедур організації такого роду діяльності. В [3] пропонується наступний перелік методів, що дозволяють систематизувати аналіз і оцінку проблемних ситуацій:

• анкетне обстеження;

• прогнозування на базі тимчасових рядів;

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

• моделювання на базі факторного і регресійного аналізу (уста-новлення причинно-наслідкових зв'язків між деякими чинниками і змінною величиною, яку необхідно визначити);

• метод мозкового штурму;

• метод Дельфі;

• метод розробки сценаріїв.

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

• на взаємозв'язку X14 - низька якість підготовки фахівців під вимоги сучасного виробництва;

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

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

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

1.1.3. Поняття мети системи

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

• "бажане стан виходів системи";

• "певне ззовні або встановлене самою системою стан її виходів"; • "ідеальний образ того, чого людина або група людей хоче досягти"; • "передбачення у свідомості результату, на досягнення якого спрямовані дії";

• "необхідні зовнішнім середовищем результати діяльності системи, за-дані на безлічі вихідних кінцевих продуктів".

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

Подальший виклад матеріалу будемо проводити виходячи з наступної класифікації цілей (рис. 1.4).


Мал. 1.4. класифікації цілей

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

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

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

• ефективність;

• продуктивність;

• організація функціонування;

• інновації;

•матеріальні ресурси;

•фінансові ресурси;

•соціальна відповідальність.

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

1.1.4. Поняття функцій системи

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

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

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

• метод мозкового штурму;

• метод Дельфі;

• метод розробки сценаріїв.

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

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

1.заключеніе договорів по цільову підготовку фахівців;

2.перевод студентів на індивідуальне навчання;

3.подготовка циклу спеціалізованих занять під вимоги підприємства; 4.Развитие матеріальної бази навчального процесу і т.д.

1.1.5. структура системи

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

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

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

У свою чергу матеріальна структура є носієм конкретних типів і параметрів елементів системи і їх взаємозв'язків.

Наведені міркування дозволяють зробити два висновки щодо сутності формальних структур: фіксованою мети відповідає як правило одна і тільки одна формальна структура; одній формальній структурі може відповідати безліч матеріальних структур.

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

• відповідає існуюча структура новим цілям і функціям системи; • чи потрібно реорганізація існуючої структури або необхідно спроектувати принципово нову структуру;

• яким чином розподілити (перерозподілити) нові і старі функції системи за елементами структури.

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


Мал. 1.5. Типи (види) структур

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

Кільцева структура (рис.1.5, б) відрізняється замкнутістю, будь-які два елементи мають дві напрямками зв'язку. Це підвищує швидкість спілкування, робить структуру більш живучою.

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

Багатозв'язна структура (рис.1.5, г) має структуру повного графа. Надійність функціонування максимальна, ефективність функціонує-вання висока, за рахунок наявності найкоротших шляхів, вартість - максимальна. Окремим випадком многосвязной структури є "колесо" - (рис.1.5, д).

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

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

Графова структура (рис.1.5, з) є інваріантної стосовно ієрархічної і використовується зазвичай при описі виробничо-технологічних систем.

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

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

Централізація визначає можливості виконання одного з елементів системи керівних функцій. Чисельно централізація визначається середнім числом зв'язків центрального (керівного) елемента з усіма іншими.

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

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

Обсяг є кількісною характеристикою структури і визначається зазвичай загальною кількістю елементів або середньою щільністю.

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


1.1.6. Зовнішні умови системи

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

• зовнішні ресурси: фінансові, матеріальні, трудові;

• обмеження: законодавчі акти, нормативно-правові документи і т.д.

Очевидно, і ті і інші дії можуть впливати як на структуру, так і на функції системи.

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

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

Приклад. Як ресурси зовнішнього середовища при реалізації функції "підготовка фахівців під вимоги конкретного підприємства" можна розглядати:

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

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

1.1.7. Основні етапи системної діяльності

Використання наведених понять і визначень в системної діяльності дозволяє відповісти на сукупність взаємопов'язаних питань: "що?", "Як?", "Хто?" і чим?". Іншими словами слід відповісти на питання: наявність або відсутність проблемної ситуації і визначити основні напрямки (цілі) її ліквідації; які функції системи при цьому треба реалізувати і якою структурою; і, нарешті, чи є для цієї реалізації відповідні ресурси.

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


Рис.1.6. Модель етапів системної діяльності

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

1.2. моделі систем

1.2.1. Визначення і класифікація моделей систем

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

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

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

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

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

В автоматизованих системах обробки інформації та управління в якості об'єкта моделювання можуть виступати:

• виробничі процеси; процеси адміністративного управління; процеси функціонування комплексу технічних засобів; процеси організації та функціонування інформаційного

• забезпечення АСУ; процеси функціонування програмного забезпечення АСУ. Переваги моделювання полягають у тому, що з'являється

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

Як правило, моделювання використовується:

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

2.На етапі проектування для аналізу та синтезу різних видів структур і вибору найкращого варіанту реалізації з урахуванням сформульованих критеріїв оптимальності і обмежень;

3.на етапі експлуатації системи для отримання оптимальних режимів функціонування та прогнозних оцінок її розвитку.

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

Коротко зупинимося на класифікації використовуваних на практиці моделей:

• за способом опису моделі поділяються на описові (НЕ-формалізовані) і формалізовані;

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

• за своєю природою використовуваних елементів моделі поділяються на фізичні (аналогові, електричні, графічні, креслення, фотографії) і математичні.

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

• статистичні і динамічні;

• детерміновані і імовірнісні;

• дискретні і безперервні;

• аналітичні та чисельні.

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

1.2.2. Рівні моделей системи *

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

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

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


Мал. 1.7

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

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

Побудова моделі базується на виборі з нескінченної кількості зв'язків системи із середовищем їх кінцевого безлічі, адекватно відображає цілі дослідження. Очевидно. Що такі моделі не треба зводити до моносистемами (тобто системі з одним входом і виходом), а для обґрунтування необхідного і достатнього кількості параметрів множин X і Y широко використовувати методи математичної статистики, залучати досвідчених експертів.


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

Мал. 1.8. Модель складу системи

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

Побудова моделі складу в силу різноманіття природи і форм елементів також не є простою справою. Це можна пояснити трьома факторами:

1.неоднозначностью поняття "елементарного елемента";

2.многоцелевим характером об'єкта, об'єктивно вимагає виділити під кожну мету відповідний їй склад;

3. Умовна (суб'єктивністю) процедури розподілу цілого на частини (системи на підсистеми, елементи).

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

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

ПРАКТИЧНА ЧАСТИНА

словесний опис

Фірма, яка виробляє деяку продукцію здійснює її рекламу двома способами через радіомережа і через телебачення. Вартість реклами на радіо обходиться фірмі в 5 $, а вартість телереклами - в 100 $ за хвилину.

Фірма готова витрачати на рекламу по 1000 $ в місяць. Так само відомо, що фірма готова рекламувати свою продукцію по радіо принаймні в 2 рази частіше, ніж по телебаченню.

Досвід попередніх років показав, що телереклама приносить в 25 разів більший збут продукції ніж радіореклама.

Завдання полягає в правильному розподілі фінансових коштів фірми.

Математичний опис.

X1- час витрачений на радіорекламу.

X2 - час витрачений на телерекламу.

Z - шукана цільова функція, оражает максимальний збут від 2-ух видів реклами.

X1 => 0, X2 => 0, Z => 0;

Max Z = X1 + 25X2;

5X1 + 100X2 <= 1000;

X1 -2X2 => 0

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

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

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

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

У гл 2 було показано, що права і ліва частини обмежень лінійної моделі можуть бути пов'язані знаками <=, = і =>. Крім того, змінні, які фігурують в задачах ЛП, можуть бути невід'ємними або не мати обмеження в знаку. Для побудови загального методу розв'язання задач ЛП відповідні моделі повинні бути представлені в деякій формі, яку назвемо стандатрной формою лінійних оптимізаційних моделей. При стандартній формі лінійної моделі

1. Всі обмеження записуються у вигляді рівності з неотрицательной правою частиною;

2. Значення всіх змінних моделі невід'ємні;

3. Цільова функція підлягає максимізації або мінімізації.

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

обмеження

1. Початкове обмеження, записане у вигляді нерівності типу <= (=>),

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

Наприклад, в ліву частину вихідного обмеження

5X1 + 100X2 <= 1000

вводістя залишкова змінна S1> 0, в результаті чого вихідна нерівність звертається в рівність

5X1 + 100X2 + S1 = 1000, S1 => 0

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

Розглянемо вихідне обмеження іншого типу:

X1 - 2X2 => 0

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

X1 - 2X2 - S2 = 0, S2 => 0

2. Праву частина рівності завжди можна зробити неотрицательной, множачи обі частини на -1.

Наприклад рівність X1 - 2X2 - S2 = 0 еквівалентно рівності - X1 + 2X2 + S2 = 0

3. Знак нерівності змінюється на протилежний при множенні обох частин на -1.

Наприклад можна замість 2 <4 записати - 2> -4, нерівність X1 - 2X2 <= 0 замінити на - X1 + 2X2 => 0

змінні

Будь-яку зміну Yi, яка не має обмеження в знаку, можна подати як різницю двох невід'ємних змінних:

Yi = Yi'-Yi '', де Yi ', Yi' '=> 0.

Таку підстановку варто використовувати у всіх обмеженнях, які містять вихідну зміну Yi, а також у натуральному вираженні для цільової функції.

Зазвичай знаходять рішення задачі ЛП, в якому фігурують змінні Yi 'і Yi' ', а потім за допомогою зворотного підстановки визначають величину Yi. Важлива особливість змінних Yi 'і Yi' 'полягає в тому, що при будь-якому допустимому ухвалі тільки одна з цих змінних може приймати позитивне значення, тобто якщо Yi '> 0, то Yi' '= 0, і навпаки. Це дозволяє розглядати Yi 'як залишкову зміну, а Yi' '- як надлишкову зміну, причому лише одна з цих змінних може приймати позитивне значення. Зазначена закономірність широко використовується в цільовому програмуванні і фактично є передумовою для використання відповідних перетворень в завданню 2.30

Цільова функція

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

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

Z = X1 + 25X2

еквівалентна мінімізації функції

(-Z) = -X1 - 25X2

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

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

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

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

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

1. Кожна наступна кутова точка повинна бути суміжною з попередньої. Цей перехід здійснюється за кордонів (ребрах) простору рішень.

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

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

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

.

геометричне визначення Алгебраїчне визначення (симплекс метод)
простір рішень Обмеження моделі стандартної форми
кутові точки Базисне рішення задачі в стандартній формі

Уявлення простору рішень стандартної завдання лінейногопрограммірованія.

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

максимізувати

Z = X1 + 25X2 + 0S1 + 0S2

при обмеженнях

5X1 + 100X2 + S1 = 1000

- X1 + 2X2 + S2 = 0

X1 => 0, X2 => 0, S1 => 0, S2 => 0

Кожну точку простору варіантів розв'язання задачі, представлену на рис.1, можна визначити за допомогою змінних X1, X2, S1 і S2, що фігурують в моделі стандартної форми. При S1 = 0 і S2 = 0 обмеження моделі еквівалентні равенствам, які надаються відповідними ребрами простору рішень. Збільшення змінних S1 і S2 відповідатиме зміщення допустимих точок з кордонів простору рішень в його внутрішню область. Змінні X1, X2, S1 і S2, асоційовані з екстремальними точками А, В, і С мож н про впорядкувати, виходячи з того, яке значення (нульове і л і нульове) має дана змінна в екстремальній точці.

екстремальна точка нульові змінні ненульові змінні
А S2, X2 S1, X1
В S1, X2 S2, X1
З S1, S2 X1, X2

Анал і з і ю табл і цу, легко замет і ть дві з акономерності:

1. Стандартна модель утримуючі і т два рівняння і чотири
невідомих, тому в кожній і з екстрем а льних точок дві (= 4 - 2) змінні е повинні і міть нульові значення.

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

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

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

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

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

C п т = n! / [(N - m)! M! ]

Друга з ран е е зазначених законом е р н остей виявляється
вельми підлогу е спеку для п остроеніі вирахує е льних процедур симп-
лекс-методу, при реал і за ц ії якого здійснюється послідовно -
вальний п ер е хід від однієї е КСТР е мально й точк і до іншої, смежнойс ній.Так як суміжні екстр е Малнів е точ до і відрізняються тільки
однією п Єремії н ой, можна визначити кожну наступну (смеж-
ву) екстремальну точку шляхом зам е ни одного і з поточних не-
базисних (нульових) змінних поточної базис н ой змінної.
У нашому випадку отримано рішення, соотв е тствующее точці А, звідки слід здійснити перехід в точку В. Для цього нужн про повів і чи в ать небазисной змінну X 2 від вихідного н нульову з н аче н ія до значення
ня, що відповідає точці В (див. рис. 1). У точці B змінна
S 1 (яка в точці А була баз і сної) автоматичних т і звертається в
нуль і, отже, стано ви ться небазисной п Яремі н ної. Таким
чином, між безліччю небазисних і множин про м базисних
змінних відбувається взаємообмін н п Єрем ен ними X 2 і S 1. цей
процес можна нагляд н о пред з тав і ть у вигляді наступної таблиці.

екстремальна точка нульові змінні ненульові змінні
А S2, X2 S1, X1
В S1, X2 S2, X1

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

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

Обчислювальні процедури симплекс-методу.

симплекс-алгоритм складається з наступних кроків.

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

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

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

Крок 3. Знаходиться нове базисне рішення, відповідне
нових складів небазисних і базисних змінних. Здійснюється перехід до кроку 1.

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

Z - X1 - 25X2 + 0S 1 -0S 2 = 0 (Цільова функція)

5X1 + 100X2 + S1 = 1000 (Обмеження)

-X1 + 2X2 + S2 = 0 (Обмеження)

Як зазначалося раніше, в якості початкового пробного рішення
використовується рішення системи рівнянь, в якій дві змінні приймаються рівними нулю. Це забезпечує едінст
венность і допустимість одержуваного рішення. В даному
випадку очевидно, що підстановка X1 = X2 = 0 відразу ж призводить до наступного результату: S1 = 1000, S2 = 0 (т. е. рішенню, відповідному точці А на рис. 1). Тому точку А можна використовувати як початкова дозволене рішення. Величина Z в цій точці дорівнює нулю, так як і X1 і X2 мають нульове значення. Тому, перетворивши рівняння цільової функції так, щоб його права частина стала рівною нулю, можна переконатися в тому, що праві частини рівнянь цільової функції і обмежень повністю характеризують початкова рішення. Це має місце у всіхвипадках, коли початковий базис складається з залишкових змінних.

Отримані результати зручно представити у вигляді таблиці:

базисні змінні Z X1 X2 S1 S2 Рішення
Z 1 -1 - 25 0 0 0 Z - рівняння
S1 0 5 100 1 0 1000 S1 -уравненіе
S2 0 -1 2 0 1 0 S2 - рівняння

Ця таблиця інтерпретується наступним чином. стовпець
«Базисні змінні» містить змінні пробного базису S1,
S2, значення яких наведені в стовпці «Рішення». при
цьому мається на увазі, що небазисних змінні X1 і X2 (НЕ перед-
ставлені в першому стовпці) дорівнюють нулю. Значення цільової функ-
ції Z = 1 * 0 + 25 * 0 + 0 * 1000 + 0 * 1 дорівнює нулю, що і показано в останньому стовпчику таблиці.

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

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

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

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

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

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

Тип 1 (формування ведучого рівняння).

Нова ведуча рядок = Попередня провідна рядок / Ведучий елемент

Тип 2 (формування всіх інших рівнянь, включаючи Z - yравненіе).

Нове рівняння = Попереднє рівняння -

é Коефіцієнт ù

ê ведучого шпальти ê * (Нова ведуча рядок).

ê попереднього ê

ë рівняння û

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

базисні змінні Z X1 X2 S1 S2 Рішення
Z
S1
S2 0 - 1/2 1 0 1/2 0

Щоб скласти нову симплекс-таблицю, виконаємо необхідні обчислювальні процедури типу 2.

1. Нове Z - рівняння.

старе Z - рівняння: (1 -1 -25 0 0 0)

(- (-25) * (0 -1/2 1 0 1/2 0)

(1 -13 1/2 0 0 12 1/2 0)

2. Нове S 1 - рівняння

старе S 1 - рівняння: (0 5 100 1 0 1000)

(- 100) * (0 - 1/2 1 0 1/2 0)

(0 5 5 0 1 - 50 1000)

Нова симплекс-таблиця буде мати вигляд:

базисні змінні Z X1 X2 S1 S2 Рішення
Z 1 -13 1/2 0 0 12 1/2 0 Z - рівняння
S1 0 55 0 1 -50 1000 S1 -уравненіе
X2 0 - 1/2 1 0 1/2 0 X2 - рівняння

У новому рішенні X 1 = 0 і S 2 = 0.Значення Z не змінюється.

Зауважимо, що нова симплекс-таблиця має такі ж ха-
рактеристиками, як і попередня: тільки небазисних змінні
X 1 і S 2 дорівнюють нулю, а значення базисних змінних, як і раніше,
представлені в стовпці «Рішення». Це в точності відповідає
результатами, що отримуються при використанні методу Гаусса-Жор-
дана.

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

Z-ypaвненіі дорівнює -13 1/2. Виходячи з умови допустимості, визначаємо, що исключаемой змінної буде S 1. Відносини, які фігурують в правій частині таблиці, показують, що в новому базисному рішенні значення включається змінної X 1 буде дорівнює 1000/5 5 (= мінімального відношенню). Це призводить до збільшення цільової функції на (1000/55) * (-13 1/2) = (245 5/11).

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

1) Нове провідне S 1 -уравненіе = Попереднє S 1 -уравненіе / (55).

базисні змінні Z X1 X2 S1 S2 Рішення
Z
S1 0 1 0 1/55 - 50/55 1000/55
X2

2) Нове Z - рівняння = Попереднє Z - рівняння - (-13 1/2) * Нове / провідне рівняння:

(1 -13 1/2 0 0 12 1/2 0)

- (-13 1/2) * (0 1 0 1/55 - 50/55 1000/55)

(1 0 0 27/110 5 /22 245 5/11)

3) Нове X 2 -уравненіе = ПредидущееX 2 - рівняння - (- 1/2) * Нове провідне рівняння:

(0 - 1/2 1 0 1/2 0)

- (- 1/2) * (0 1 0 1/55 - 50/55 1000/55)

(0 0 1 1/110 1 /22 9 1/11)

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

базисні змінні Z X1 X2 S1 S2 Рішення
Z 1 0 0 27/110 5/2 + 2 245 5/11
X1 0 1 0 1/55 - 50/55 100 0/5 5
X2 0 0 1 1/110 1/22 9 1/11

У новому базисному рішенні X 1 = 1000/55 і X 2 = 9 1/11. Значення Z збільшилася з 0 (попередня симплекс-таблиця) до 245 5/11 (остання симплекс-таблиця). Цей результуючий пріростцелевой функції обумовлений збільшенням X 1 від Одо 1000/55, так як з Z -строкі попередньої симплекс-таблиці випливає, що зростанню даної змінної на одиницю відповідає збільшення цільової функції на (-13 1/2).

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

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

Умова оптимальності. Введеної перемінної взадаче максимізації (мінімізації) є небазисная змінна, має в Z -уравненіі найбільший негативний (позитивний) коефіцієнт, Що стосується рівності таких коеффіціентовдля декількох небазисних змінних вибір робиться довільно, коли всі коефіцієнти при небазисних змінних в Z -уравненіі невід'ємні (непозитивні), отримане рішення є оптимальним.

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

Оптимальне вирішення

З точки зору практичного використання результатів ре-
шення завдань ЛП класифікація змінних, що передбачає
їх поділ на базисні і небазнсние, не має значення і при
аналізі даних, що характеризують оптимальне рішення, може
не враховуватися. Змінні, відсутні в стовпці «Базисні
змінні », обов'язково мають нульове значення. значення ос-
тальних змінних наводяться в стовпці «Рішення». при інтер
претации результатів оптимізації в нашому завданні нас перш за все цікавить кількість часу, який замовить наша фірма на радіо і телебачення, т. е. значення керованих змінних X 1 і X 2. Використовуючи дані, що містяться в симплекс-таблиці для оптимального рішення, основні результати можна представити в наступному вигляді:


керовані змінні оптимальні значення Рішення
X 1 1000/55 Час що виділяється фірмою на телерекламу
X 2 9 1/11 Час що виділяється фірмою на радіорекламу
Z 245 5/11 Прибуток отримується від реклами.

Зауважимо, що Z = X 1 + 25X 2 = 1000/55 + 25 * 9 1/11 = 245 5/11. Це рішення відповідає даним заключній симплекс-таблиці.

статус ресурсів

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

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

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

:

ресурси залишкова змінна статус ресурсу
Обмеження по бюджету S 1 дефіцитний

Перевищення часу реклами радіо над тілі

S 2 дефіцитний

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

Ресурси, збільшення запасів яких дозволяє поліпшити ре-
шення (збільшити прибуток), - це залишкові змінні S 1 і S 2, по-
кільки з симплекс-таблиці для оптимального рішення видно,
що вони дефіцитні. У зв'язку з цим логічно поставити наступне
питання: яким з дефіцитних ресурсів слід віддати перева-
ня при вкладенні додаткових коштів на збільшення їх запа-
сов, з тим щоб отримати від них максимальну віддачу? Відповідь на
це питання буде дано в наступному підрозділі цієї глави, де рас-
сматривается цінність різних ресурсів.

цінність ресурсу

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

Інформація для оптимального рішення задачі представлена ​​в симплекс-таблиці. Звернемо увагу на з н аченія коефіцієнтів Z -уравненія, що стоять ін і пере м енн и х начальног про базису S 1 і S 2. Виділимо дл я зручності соответстзующую частина сім п лекс-табл і ци:

базисні змінні Z X1 X2 S1 S2 Рішення
Z 1 0 0 27/110 5/2 + 2 245 5/11

Як випливає і з теорії розв'язання задач Л П, це н ність ресурсів завжди можна визна е лити за значеннями коефіцієнтом н тов п ри змінних початкового баз і з а, що фігурують в Z -уравненіі оптимальної симплекс-табл і ці, таким чином Y 1 = 27/110, а Y 2 = 5/2 2.

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

Z = 245 5/11 - (27/110 S 1 + 5/2 2 S 2).

Позитивне прирощення змінної S 1 щодо її поточного
нул е вого значення призводить до пропорційного зменшення Z,
причому коеф і цієнт пропорційності дорівнює 27/110.Але, як випливає з першого обмеження моделі:

5X1 + 100X2 + S 1 = 1000

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

Звідси випливає, що зменшення кількості грошей виділених на рекламу викликає пропорційне зменшення цільової функції з тим же коеф і цієнт пропорційності, рівним 27/110.Так як
ми оперуємо з лінійними функціями, отриманий висновок можна
обоб щ ить, вважаючи, що і збільшення кількості грошей виділених на рекламу (еквівалентно е в вед е ню і з б иточной перем е ної S 1 <0) призводить до пропорц і нального збільшення Z з тим же коефіцієнтом пропорційності, рівним 27/110. Аналогічні міркування спра в ед-
ліб для обмеження 2.

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

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

Максимальна зміна запасу ресурсу

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

У нашій задачі запас першого ресурсу змінився на D 1 т. Е. Запас бюджету становитиме 1000 + D 1. При позитивній велічінеD 1 запас даного ресурсу збільшується, при негативній - зменшується. Як правило, досліджується ситуація, коли обсяг ресурсу збільшується (D 1> 0), однак, щоб отримати результат в загальному вигляді, розглянемо обидва випадки.

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

рівняння Значення елементів правій частині на відповідних ітераціях
(Початок обчислень) 1 2 (оптимум)
Z 0 0 245 5/11
1 1000 1000 + D 1 1000/55 + D 1
2 0 0 9 1/11

Фактіческівce зміни правих частин обмежень, обуслов-
лені введенням D 1, можна визначити безпосередньо за даними,
містяться в симплекс-таблицях. Насамперед зазначимо, що
на кожній ітерації нова права частина кожного обмеження перед-
являє собою суму двох величин: 1) постійної і 2) члена, ли-
Нейн залежить від D 1. Постійні відповідають числам, які
фігурують на відповідних ітераціях в правих частинах ограніченійсімплекс-таблиць до введення D 1. Коефіцієнти пріD 1 по друге доданків рівні коефіцієнтам при S 1 на тій же ітерації. Так, наприклад, на последнеи ітерації (оптимальне рішення) постійні (245 5/11, 1000/55, 9 1/11) представляють СОБОЮ числа, які фігурують в правих частинах обмеження оптимальної симплекс-таблиці до введення D 1. Коефіцієнти (27/110; 1/55; 1/110) рівні коефіцієнтам при S 1 в тій же симплекс-таблиці тому, що ця змінна пов'язана лише з цим обмеженням. Іншими словами, при аналізі впливу змін в правій частині другого обмеження потрібно користуватися коефіцієнтами при змінної S 2.

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

X 1 = 100 0/5 5+ (1/55) D 1 => 0 (1)

X 2 = 9 1/11 + (1/110) D 1 => 0 (2)

Для визначення допустимого інтервалу зміни D 1 роз-
трім два випадки.

Випадок 1: D 1 => 0Очевідно, що обидва неравнества за цієї умови завжди будуть невід'ємними.

Випадок 2: D 1 <0.

(1/55) D 1 => - 100 0/5 5. З цього випливає, що D 1 => - 1000

(2)

(1/110) D 1 => - 9 1/11. З цього випливає, що D 1 => - 1000

Об'єднуючи результати, отримані для обох випадків, можна
зробити висновок, що при - 1000 <= D 1 <= + ¥ рішення розглянутої зав-
чи завжди буде допустимим, будь-яке значення D 1, що виходить за
межі вказаного інтервалу, призведе до неприпустимість рішення і
нової сукупності базисних змінних.

Тепер розглянемо в яких межах може змінюватися запас ресурсу 2 аналіз проведемо за аналогічною схемою:

Запас 2-ої ресурсу змінився на D 2 т. е. запас рекламного часу складе 0 + D 2. Як змінилася симплекс-таблиця при зміні величини запасу ресурсу на D 2.

рівняння Значення елементів правій частині на відповідних ітераціях
(Початок обчислень) 1 2 (оптимум)
Z 0 0 245 5/11
1 1000 1000 1000/55
2 0 0 + D 2 9 1/11 + D 2

Знайдемо інтервал обмежує велічінуD 2

X 1 = 1000/55 - (50/55) D 2 (1)

X 2 = 9 1/11 + (1/22) D 2 (2)

Для визначення допустимого інтервалу зміни D 1 роз-
трім два випадки.

Випадок 1: D 2 => 0: (1)

(50/55) D 2 <= 1000/55 з цієї нерівності випливає, що D 2 <= 20

(2)

Очевидно, що 2-е рівняння неотрицательно на даній ділянці.

Об'єднуючи 2 рівняння для Випадку 1 ми отримаємо інтервал для D 2.

D 2 Î [0; 20]

Випадок 2: D 2 <0. : (1)

(50/55) D 2 => - 1000/55. З цього випливає, що D 2 <= 20

(2)

(1/22) D 2 => - 9 1/11. З цього випливає, що D 2 => - 200

Об'єднуючи 2 рівняння для Випадку 2 ми отримаємо інтервал для D 2.

D 2 Î [- 200; 0]

Об'єднуючи 2 випадки ми отримаємо інтервал [- 200; 20]

Максимальна зміна коефіцієнтів питомої

прибутку ( вартості)

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

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

X 1 змінюється від 1 до 1 + d 1 гдеd 1 може бути як позитивним, так і негативним числом. Цільова функція в цьому випадку приймає наступний вигляд:

Z = (1 + d 1) X 1 + 25X 2

Якщо скористатися даними початковій симплекс-таблиці і
виконати всі обчислення, необхідні для (отримання заключн-
котельної симплекс-таблиці, то останнім Z-рівняння буде вигля
діти в такий спосіб:

базисні змінні X1 X2 S1 S2 Рішення
Z 0 0 27/110 + 1/55 d 1 5/2 + 2 - 50/55 d 1 245 5/11 + 100 0/5 5 d 1

Коефіцієнти при базисних змінних X 1, X 2 і залишкових я рівними нулю. Це рівняння відрізняється від Z-рівняння до введення d 1, тільки наявністю членів, містять d 1. Коефіцієнти при d 1 дорівнює коефіцієнту при відповідних змінних в Z-рівнянні симплекс-таблиці для отриманого раніше оптимального рішення

базисні змінні X1 X2 S1 S2 Рішення
X1 1 0 1/55 - 50/55 100 0/5 5

Ми розглядаємо X 1 - рівняння, так як коефіцієнт саме при
Етон змінної у виразі для целевоі функції змінився
на d 1.

Оптимальні значення змінних залишатимуться неизмен-
ними при значеннях d 1, б відповідала умовам неотріцатель-
ності (завдання на відшукання максимуму) всіх коефіцієнтів при не-
базисних змінних в Z-рівнянні. Таким чином, повинні виконуватися наступні нерівності:

27/110 + 1/55 d 1 => 0

5/2 + 2 - 50/55 d 1 => 0

З першого нерівності отримуємо, що d 1 => - 13,5, а з другого слід що d 1 <= 1/4. Ці результати визначають межі зміни коефіцієнта C 1 у вигляді наступного співвідношення: - 13,5 <= d 1 <= 1/4. та-
ким чином, при зменшенні коефіцієнта цільової функції при
змінної X 1 до значення, рівного 1 + (- 13,5) = - 12,5 або при його збільшенні до 1 + 13,5 = 14,5 оптимальні значення змінних залишаються
незмінними. Однак оптимальне значення Z буде змінюватися (відповідно до вираження 245 5/11 + 100 0/5 5 d 1, де - 13,5 <= d 1 <= 1/4

X 2 змінюється від 25 до25 + d 2 гдеd 2 може бути як позитивним, так і негативним числом. Цільова функція в цьому випадку приймає наступний вигляд:

Z = (25 + d 2) X 2 + X 1

Все попереднє обговорення стосувалося дослідження зміни коефіцієнта при змінної, якій поставлено у відповідність обмеження, яке фігурує в симплекс-таблиці. Однак таке обмеження є лише в тому випадку, коли дана змінна є базисною (наприклад X 1 і X 2). Якщо змінна небазисная, то в стовпці, що містить базисні змінні, вона не буде представлена.

Будь-яка зміна коефіцієнта цільової функції при небазисной змінної призводить лише до того, що в заключній сімплкс-таблиці змінюється тільки цей коефіцієнт. Розглянемо в якості ілюстрації випадок, коли коефіцієнт при змінної S 1 (першої залишкової змінної) змінюється від 0 до d 3. Виконання перетворень, необхідних для отримання заключній симплекс таблиці, призводить до наступного результуючому Z-рівняння:

базисні змінні X1 X2 S1 S2 Рішення
Z 0 0 27/110 + 1/55 d 1 5/2 + 2 245 5/11

висновок

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


Список літератури :

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

Список серверів:

www.citforum.ru

www.rambler.ru

www.msu.ru

www.ntcf.ru

www.yandex.ru


Головна сторінка


    Головна сторінка



Побудова економічної моделі c використанням симплекс-методу

Скачати 98.71 Kb.