Завжди і у всіх сферах своєї діяльності людина приймав рішення. Важлива область прийняття рішень пов'язана з виробництвом. Чим більше обсяг виробництва, тим важче прийняти рішення і, отже, легше Допус помилку. Возніает природне запитання: чи не можна, щоб уникнути таких помилок використовувати ЕОМ?
Відповідь на це питання дає наука, яка називається кібернетика. Кібернетика (походить від грецького "kybernetike" - мистецтво управління) - наука про загальні закони одержання, зберігання, передачі і переробки інформації.
Найважливішою галузі кібернетики є економічна кібернетика - наука, що займається додатком ідей і методів кібернетики до економічних систем.
Економічна кібернетика використовує сукупність методів дослідження процесів управління в економіці, включаючи економіко-математичні методи.
У даний час застосування ЕОМ в управлінні виробництвом досягло великих масштабів. Однак, у більшості випадків за допомогою ЕОМ вирішують так звані рутинні завдання, тобто завдання, пов'язані з обробкою різних даних, які до застосування ЕОМ вирішувалися так само, але вручну. Інший клас задач, які можуть бути вирішені за допомогою ЕОМ - це задачі прийняття рішень. Щоб використовувати ЕОМ для прийняття рішень, необхідно скласти математичну модель. Так чи необхідне застосування ЕОМ при прийнятті рішень? Можливості людини досить різноманітні. Якщо їх впорядкувати, Так уже влаштована людина, що того, чим він володіє, йому мало. І починається нескінченний процес збільшення його можливостей. Щоб більше підняти, з'являється одне з перших винаходів - важіль, щоб легше переміщати вантаж - колесо. У цих знаряддях поки ще використовується тільки енергія самої людини. Згодом починається застосування зовнішніх джерел енергії: пороху, пари, електрики, атомної енергії. Неможливо оцінити, наскільки використовувана енергія зовнішніх джерел перевищує сьогодні фізичні можливості людини.
Що ж стосується розумових здібностей людини, то, як кажуть, кожен незадоволений своїм станом, але задоволений своїм розумом. А чи можна зробити людину розумніше, ніж він є Щоб відповісти на це питання, слід уточнити, що вся інтелектуальна діяльність людини може бути підрозділена на формализуема і формалізації.
Формализуемой називають таку діяльність, яку виконують за певними правилами. Наприклад, виконання розрахунків, пошук в довідниках, графіческаіе роботи, безсумнівно можуть бути доручені ЕОМ. І як все, що може робити ЕОМ, вона це робить краще, тобто швидше і якісніше, ніж людина.
Формалізації називають таку діяльність, яка відбувається із застосуванням будь-яких неізвестнихи нам правил. Мислення, міркування, інтуїція, здоровий глузд - ми поки ще не знаємо, що це таке, і природно, усе це не можна доручити ЕОМ, хоча б тому, що ми просто не знаємо, що доручати, яке завдання поставити перед ЕОМ.
Різновидом розумової діяльності є прийняття рішень.
Прийнято вважати, що прийняття рішень відноситься до формалізації діяльності. Однак це не завжди так. З одного боку, ми не знаємо, як ми приймаємо рішення. І об'яснеіе одних слів за допомогою інших типу "приймаємо рішення за допомогою здорового глузду" нічого не дає. З іншого боку, значна кількість задач прийняття рішень може бути формалізована. Одним з видів задач прийняття рішень, які можуть бути формалізовані, є завдання прийняття оптимальних рішень, або завдання оптимізації. Рішення задачі оптимізації проводиться за допомогою математичних моделей і застосування обчислювальної техніки.
Сучасні ЕОМ відповідають найвищим вимогам. Вони здатні виконувати мільйони операцій за секунду, в їх пам'яті можуть бути всі необхідні відомості, комбінація дисплей-клавіатура забезпечує діалог людини і ЕОМ. Однак не слід змішувати успіхи у створенні ЕОМ з досягненнями в області їх застосування. По суті, все що може ЕОМ - це по заданій людиною програмі забезпечити перетворення вихідних даних у результат. Треба чітко собі уявляти, що ЕОМ рішення не приймає і приймати не може. Рішення може приймати тільки людина-керівник, наділений для цього певними правами. Але для грамотного керівника ЕОМ є веліколним помічником, здатним виробити і запропонувати набір самих різних варіантів рішень. А з цього набору людина вибере той варіант який з його точки зору виявиться більш придатним. Звичайно, далеко не всі завдання прийняття рішень можна вирішити за допомогою ЕОМ. Тим не менш, навіть якщо рішення задачі на ЕОМ і не закінчується повним успіхом, то все одно виявляється корисним, тому що сприяє більш глибокому розумінню цього завдання і більш суворої її постановці.
Щоб людині прийняти рішення без ЕОМ, найчастіше нічого не треба. Подумав і вирішив. Людина, добре чи погано, вирішує всі виникаючі перед ним завдання. Правда ніяких гарантій правильності при цьому немає. ЕОМ ж ніяких рішень не приймає, а тільки допомагає знайти варіанти рішень. Даний процес складається з наступних етапів:
1) Вибір завдання.Рішення завдання, особливо досить складною - досить важка справа, яка потребує багато часу. І якщо завдання обрана невдало, то це може призвести до втрати часу і розчарування в застосуванні ЕОМ для прийняття рішень. Яким же основним вимогам повинна задовольняти завдання?
А. Має існувати як мінімум один варіант її рішення, адже якщо варіантів рішення немає, значить вибирати нема з чого.
Б. Треба чітко знати, в якому сенсі шукане рішення має бути найкращим, адже якщо ми не знаємо чого хочемо, ЕОМ допомогти нам вибрати найкраще рішення не зможе.
Вибір завдання завершується її змістовної постановкою. Необхідно чітко сформулювати завдання на звичайній мові, виділити мета дослідження, вказати обмеження, поставити основні питання на які ми хочемо отримати відповіді в результаті рішення задачі.
Тут слід виділити найбільш суттєві риси економічного об'єкта, найважливіші залежності, які ми хочемо врахувати при побудові моделі. Формуються деякі гіпотези развітіця об'єкта дослідження, вивчаються виділені залежності та співвідношення. Коли вибирається завдання і здійснюється її змістовна постановка, доводиться мати справу з фахівцями в предметної області (інженерами, технологами, конструкторами і. Т. д.). Ці фахівці, як правило, чудово знають свій предмет, але не завжди мають уявлення про те, що потрібно для вирішення задачі на ЕОМ. Тому, змістовна постановка задачі найчастіше виявляється перенасиченої відомостями, які абсолютно зайві для роботи на ЕОМ.
2) Складання моделіПід економіко-математичної моделлю розуміється математичний опис досліджуваного економічного об'єкта або процесу, при якому економічні закономірності виражені в абстрактному вигляді за допомогою математичних співвідношень.
Основні принципи складання моделі зводяться до таких двох концепцій:
1. При формулюванні завдання необхідно досить широко охопити моделируемое явище. В іншому випадку модель не дасть глобального оптимуму і не буде відображати суть справи. Небезпека полягає в тому, що оптимізація однієї частини може здійснюватися за рахунок інших і на шкоду загальній організації.
2. Модель повинна бути настільки проста, наскільки це можливо. Модель повинна бути така, щоб її можна було оцінити, перевірити і зрозуміти, а результати отримані з моделі повинні бути зрозумілі як її творцеві, так і тим, хто приймає рішення. На практиці ці концепції часто вступають у конфлікт, перш за все через те, що у збір і введення даних, перевірку помилок та інтерпретацію результатів включається людський елемент, що обмежує розміри моделі, яка може бути проаналізована задовільно. Розміри моделі використовуються як фактор, що лімітує, і якщо ми хочемо збільшити широту обхвату, то доводиться зменшувати деталізацію і навпаки.
Введемо поняття ієрархії моделей, гдте широта охоплення збільшується, а деталізація зменшується в міру того, як ми переходимо на більш високі рівні ієрархії. На більш високих рівнях у свою чергу формуються обмеження і цілі для більш низьких рівнів.
При побудові моделі горизонт планування в основному збільшується із зростанням ієрархії. Якщо модель довгострокового планування всієї корпорації може містити моло щоденних поточних деталей то модель планування виробництва окремого підрозділам складається в основному з таких деталей.
При формулюванні завдання необхідно враховувати наступні три аспекти:
1) Досліджувані фактори: Цілі дослідження визначені досить вільно і у великій мірі залежать від того, що включено в модель. У цьому відношенні Легше інженерам, так як досліджувані фактори у них зазвичай стандартні, а цільова функція виражається в термінах максимуму доходу, мінімуму витрат або, можливо, мінімуму споживання якого-небудь ресурсу. У той же час соціологи, наприклад, звичайно задаються метою "суспільної корисності" або в цьому роді і опиняються в складному становищі, коли їм доводиться приписувати певну "корисність" різних дій, висловлюючи її в математичній формі.
2) Фізичні кордону: Просторові аспекти дослідження вимагають детального розгляду. Якщо виробництво зосереджено більш як в одній точці, то необхідно врахувати в моделі відповідні розподільчі процеси. Ці процеси можуть включати складування, транспортування, а також завдання календарного планування іещенія обладнання.
3) Часові межі: Тимчасові аспекти дослідження приводять до сдерьезной дилеми. Зазвичай горизонт планування добре відомий, але треба зробити вибір: або моделювати систему в динаміці, з тим, щоб отримати тимчасові графіки, або моделювати статичне функціонування в певний момент часу. Якщо моделюється динамічний (багатоетапний) процес, то розміри моделі збільшуються відповідно до числа розглянутих пріодов часу (етапів). Такі моделі зазвичай ідейно прості, так що основна складність полягає скоріше в можливості вирішити задачу на ЕОМ за прийнятний час, ніж в умінні інтерпретувати великий обсяг вихідних даних. з Найчастіше буває досить побудувати модель системи в якийсь заданий момент часу, наприклад у фіксований рік, місяць, день, а потім повторювати розрахунки через певні проміжки часу. Взагалі, наявність ресурсів у динамічній моделі часто оцінюється приблизно і визначається факторами, що виходять за рамки моделі. Тому необхідно ретельно проаналізувати, чи дійсно необхідно знати залежність від часу зміни характеристик моделі, або той же результат можна отримати, повторюючи статичні розрахунки для ряду різних фіксованих моментів.
3) Складання алгоритму.Алгоритм - це кінцевий набір правил, які дозволяють чисто мехаіческі вирішувати будь-яку конкретну задачу з деякого класу одотіпних завдань. При цьому мається на увазі:
а. - Вихідні дані можуть змінюватися в певних межах: {масовість алгоритму}
б. - Процес застосування правил до вихідних даних (шлях вирішення завдання) визначено однозначно: {детермінованість алгоритму}
в. - На кожному кроці процесу застосування правил відомо, що вважати результатом цього процесу: {результативність алгоритму}
Якщо модель описує залежність між вихідними даними і шуканими величинами, то алгоритм являє собою послідовників дій, які треба виконати, щоб від вихідних даних перейти до шуканим величинам.
Зручною формою запису алгоритму є блок схема. Вона не тільки досить наочно описує алгоритм, але і є основою для складання програми. Кожен клас математичних моделей має свій метод рішення, який реалізується в алгоритмі. Тому дуже важливою є класифікація завдань за вигляд математичній моделі. При такому підході завдання, різні за змістом, можна вирішувати за допомогою одного і того ж алгоритму. Алгоритми задач прийняття рішень, як правило, настільки складні, що без застосування ЕОМ реалізувати їх практично неможливо.
4) Складання програми.Алгоритм записують за допомогою звичайних математичних символів. Для того, щоб він міг бути прочитаний ЕОМ необхідно скласти програму. Програма - це опис алгоритму розв'язання задачі, заданий на мові ЕОМ. Алгоритми і програми об'єднуються поняттям "математичне забезпечення". В даний час витрати на математичне забезпечення складають приблизно півтори вартості ЕОМ, і постійно відбувається подальше відносне подорожчання математичного забезпечення. Вже сьогодні предметом придбання є саме математичне забезпечення, а сама ЕОМ лише тарою, упаковкою для нього.
Далеко не для кожного завдання необхідно складати індивідуальну програму. На сьогоднішній день створені потужні сучасні програмні засоби - пакети прикладних програм (ППП). ППП - це об'єднання моделі, алгоритму і програми. Найчастіше, до задачі можна підібрати готовий пакет, який чудово працює, вирішує багато завдань, серед яких можна знайти і наші. При такому підході багато завдань будуть вирішені досить швидко, адже не треба займатися програмуванням. Якщо не можна використовувати ППП для рішення задачі без зміни його або моделі, то потрібно або модель підігнати під вхід ППП, або доопрацювати вхід ППП, щоб у нього можна було ввести модель. Таку процедуру називають адаптацією. Якщо відповідний ППП знаходиться в пам'яті ЕОМ, то робота користувача полягає в тому, щоб ввести необхідні шукані дані і отримати необхідний результат.
5) Введення вихідних даних.Перш ніж ввести вихідні дані в ЕОМ, їх, природно, необхідно зібрати. Причому не всі наявні на виробництві вихідні дані, як це часто намагаються робити, а лише ті, які входять до математичної моделі. Отже, збір вихідних даних не тільки доцільно, а й необхідно проводити лише після того, як буде відома математична модель. Маючи програму і вводячи в ЕОМ вихідні дані, ми отримаємо рішення задачі.
6) Аналіз отриманого розв'язкуНа жаль досить часто математичне моделювання змішують з одноразовим рішенням конкретної задачі з початковими, найчастіше недостовірними даними. Для успішного управління складними об'єктами необхідно постійно перебудовувати модель на ЕОМ, коректуючи вихідні дані з урахуванням нової ситуації. Недоцільно витрачати час і кошти на складання математичної моделі, щоб по ній виконати один єдиний розрахунок. Економіко-математична модель є прекрасним засобом отримання відповідей на широке коло росів, що виникають при плануванні, проектуванні і в ході виробництва. ЕММ може стати надійним помічником при прийнятті щоденних рішень, що виникають у ході оперативного управління виробництвом.
ВИКОРИСТАННЯ БЛОК-СХЕМФізична природа модельованої системи може бути представлена за допомогою блок-схеми. Простий приклад - попередня блок-схема, хоча вона недостатньо докладна.
Виділимо основні складові блок схеми:
1) Прямими лініями представлені матеріальні потоки, які характеризуються певними властивостями. Це не обязаельно повинні бути потоки якогось фізичного речовини; таким же чином можуть бути представлені, наприклад, потоки інформації, грошей. Якщо два матеріальних потоку характеризуються різними властивостями і ці відмінності істотні для моделі, то ми повинні зобразити їх різними лініями.
2) Прямокутниками представлені блкі підприємства та устаткування, або, в більш загальному випадку, підсистеми, які мають своє певне призначення. Характеристики потоків змінюються, а блоки є точками входу і виходу для множин ліній, що представляють потоки.
3) Прийнято, що загальний напрямок руху потоків відбувається зліва направо. Таким чином, в блок-схемі, яка описує виробничий процес, сировина, що надходить зображено стрілками входу в лівій частині блок-схеми, а кінцеві потоки - лініями, що закінчуються праворуч у стовпцях, иотвечающіх кінцевим продуктам. Такі стовпчики особливо зручні, коли кінцевий продукт виходить з'єднанням декількох потоків, як ми це побачимо в нашому прикладі.
Описова ОБМЕЖЕННЯЦі обмеження описують функціонування досліджуваної системи. Вони становлять особливу групу балансових рівнянь, пов'язаних з характеристиками окремих блоків, такими як маса, енергія, витрати.
Той факт, що в моделі ЛП балансові рівняння повинні бути лінійними, виключає можливість подання таких принципово нелінійних залежностей, як складні хімічні реакц зміни умов функціонування, які допускають лінійне опис (хоча б приблизно) можуть бути враховані в моделі. Балансові співвідношення можуть бути введені для якоїсь закінченої частини блок-схеми, наприклад для окремого блоку; зазвичай вони виписуються для кожного технологічедского потоку, який у блок-схемі зображується лінією. Кількість речовини, отриманого, може бути, більш ніж з одного блоку, що входить у потік, дорівнює кількості цієї речовини, що виходить з потоку (і надходить як сировина, можливо, більш, ніж в один блок).
У статичних (одноетапного) моделях такі співвідношення можна представити у вигляді: - вхід + вихід = 0
Динамічний (багатоетапний) процес описується співвідношеннями:
- Вхід + вихід + накопичення = 0, де під накопиченнями розуміється чистий приріст за аналізований період.
Нехай K потоків входить в якийсь блок, і Xk, k = 1. . . K, кількість сировини, переданої в блок кожним потоком. Нехай також з кожної одиниці k-го сировини в блоці проводиться кількість Aik якогось i-го продукту. Тоді загальна кількість виробленого продукту визначиться формулою: E Aik * Xk.
Припустимо далі, що цей продукт сам надходить на вхід якого-то тільки одного блоку в кількості, що дорівнює Xi. Тоді балансове співвідношення (рядок i для потоку цього продукту має вигляд: - E Aik * Xk + 1. 0Xj = 0 (2. 2)
Кожен потік складається з продуктів, вироблених блоками, і сировини і з'єднує різні блоки. Тоді при складанні балансових
співвідношень потоків передбачається наступне:
1. Для кожного потоку визначається балансове рівняння, якому відповідає рядок i.
2. Кожному входу потоку в якийсь блок ставиться у відповідність стовпець з коефіцієнтом, рівним +1. 0. Кожному стовпцю відповідає мінлива Xj, значення якої визначає обсяг потоку, що входить до блоку. Потік може входити більше ніж в один блок, тоді в рівнянні 2. 2. з'явиться кілька членів +1. 0Xj, кожен з яких представлятиме обсяг потоку на вході до відповідного блоку.
3. Стовпець (якому відповідає, наприклад, мінлива Xk), відповідний виходу потоку продукту з блоку, містить коефіцієнт, рівний-Aik. Зауважимо, що в одному і тому ж балансовому рівнянні можуть з'явитися додаткові члени, якщо однакові потоки (тобто потоки з однаковими характеристиками) надходять з різних блоків або сировинних джерел.
У результаті отримуємо балансове рівняння віа:
- E Aik * Xk + 1. 0Xj = 0, в якому може бути кілька членів виду +1. 0Xj, якщо потік входить більш ніж в один блок.
Отже, рядок балансового рівняння відповідає потоку, який характеризується набором певних властивостей і може мати більше, ніж по одній точці входу і виходу. Стовпець, якому відповідає мінлива Xj, відповідає кожній новій точці входу потоку в блок.
Подальше умова загального вигляду, що стосується всіх типів обмежень, полягає в тому, що негативні коефіцієнти вказують на те, що продукт виготовлений системою, а позитивні - що він спожитий нею.
ОБМЕЖЕННЯ НА РЕСУРСИ і кінцеве споживанняЗ цими обмеженнями ситуація досить ясна. У самому простому вигляді обмеження на ресурси - це обмеження зверху на змінні, що представляють витрати ресурсів, а обмеження на кінцеве споживання продуктів - це обмеження знизу на змінні, що представляють виробництво продукту. Обмеження на ресурси мають такий вигляд:
Ai1X1 +. . . + AijXj +. . . + AinXn <= Bi,
де Aij - витрата i-го ресурсу на одиницю Xj, j = 1. . . n, а Bi загальний обсяг наявного ресурсу.
Якщо ж ввести нову змінну, наприклад Xn +1, представляє сумарний витрата, обмеження набуде вигляду:
Ai1X1 +. . . + AijXj +. . . + AinXn - Xn +1 = 0,
Xn +1 <= Bi,
Визначаючи Aij як вихід i-го продукту на одиницю Xj, j = 1. . . n, і помінявши знак нерівності на протилежний, ми отримаємо аналогічні співвідношення для обліку кінцевого споживання, де Bi буде представляти загальне споживання i-го продукту. Зауважимо, що обмеження на потужність заводу та обладнання можна врахувати таким же чином, як обмеження на ресурс. Залежність витрат від обсягу використовуваних ресурсів (або кінцевого споживання можна також відобразити в моделі.
Умов, що накладаються ЗЗОВНІЧастина обмежень на систему можна розглядати як зовнішні. Так умови на якість продуктів встановлюються законодавчими органами. Аналогічно облік навколишнього середовища накладає обмеження на деякі властивості продуктів (наприклад на кількість сірки в нафтопаливі) і на режим роботи підприємства і обладнання (наприклад на якість стічної води), що можна виразити як додаткові витрати.
Розглянемо ситуацію, коли змішуються кілька різних потоків, щоб утворити конечнилй продукт. Якщо якась властивість i-ої компоненти суміші характеризується коефіцієнтом Pi, а Pb визначає нижню допустиму межу зазначеної властивості суміші, то обмеження можна записати у вигляді: P1X1 +. . . + PiXi => PbXb де в лівій частині виробляється підсумовування по всіх змішуються потокам, а Xb представляє загальна кількість виробленої суміші. Обмеження на якість продуктів краще всього задавати за допомогою таблиць.
ВИЗНАЧЕННЯ ЦІЛЬОВОЇ ФУНКЦІЇЦільова функція моделі зазвичай складається з наступних компонент:
1) Вартість виробленого продукту.
2) Капіталовкладення в будівлі та обладнання.
3) Вартість ресурсів.
4) Експлуатаційні витрати і витрати на ремонт обладнання.
1) Вартість виробленого продукту.
Якщо система моделюється з точки зору прибутку, то вартість продукту вимірюється в грошах. Якщо метою системи є максимізація суспільної корисності, то вихід системи описується в термінах корисності, причому відмінності у визначенні цієї корисності можуть призвести до різних відповідей. Так при плануванні медичного обслуговування навряд чи виявиться корисним для суспільства, якщо в якості мети вибирається максимальне число пацієнтів, що обслуговуються в одиницю часу.
У найпростішому випадку цільову функцію можна сформулювати так:
якщо ми позначимо через Xi кількість продукту, а через Ci вартість одиниці цього продукту, то ми отримаємо член цільової функції CiXi. Але цільова функція може бути описана і більш складним чином. Наприклад вартість може залежати від кількості проданого продукту, ця залежність зображена на графіку:
2) Капіталовкладення в будівлі та обладнання.
Якщо розглядається статична модель на певний момент часу, то всі витрати повинні бути віднесені до якогось періоду часу, наприклад робочого дня (або року). Одноразові капіталовкладення виражаються через щоденні (річні) витрати. Це здійснюється множенням капіталовкладень на норму амортизації (коефіцієнт відновлення капіталу - CRF). Щоб перейти від річних витрат до щоденних, CRF зазвичай просто ділять на 365 або якщо заводд працює не цілий рік (наприклад проводяться регулярні планові ремонтні роботи) на число робочих днів у році, чоби отримати витрати віднесені до робочого дня. Дані витрати частіше запам'ятовуються як константа і додаються до значення цільової функції після одержання рішення.
3) Вартість ресурсів.
Спосіб визначення вартості ресурсів збігається з визначенням вартості виробленого продукту (п. 1): якщо Xi-кількість використовуваного ресурсу, а Ci - вартість одиниці цього ресурсу, то ми отримаємо член цільової функції, рівний - CiXi. Тут ми знову можемо врахувати в моделі залежність вартості ресурсу від його кількості, як наприклад на графіку:
4) Експлуатаційні витрати і витрати на ремонт обладнання.
Ці витрати зазвичай є функцією розмірів будівель та обладнання, тому їх можна включити в амортизаційні капітальні витрати. Сюди необхідно включити також: трудові витрати, витрати на енергоресурси для виробничих потреб (пар, електрика, вода, стиснене повітря і. Т. д.), орендну плату за розробку надр, витрати на каталізатори та інші технологічні потреби.
ПРИКЛАДМи хочемо дослідити різні варіанти розширення існуючих блоків і створення нових блоків для максимізації чистого доходу. Нам необхідно:
1) Ввести в ЛП-матрицю обмеження на потужність для кажудого блоку.
2) Максимізувати прибуток при фіксованих потужностях.
3 но від моделі ЛП а потім відняти їх з величини прибутку.
4) Провести параметричне зміна потужностей і повторити кроки, починаючи з кроку 1.
Цільова функція буде виражатися в тис. дол / робочий день, так що якщо Xi виражається в одиницях MBSD, то вартість Ci повинна виражатися в дол / барель.
Ми будемо максимізувати цільову функцію, тому коефіцієнти, що відповідають цінами будуть позитивними, а коефіцієнти, що відповідають витратам - негативними.
ПОБУДОВА МАТРИЦІ ВЕЛИКОГО РОЗМІРУОбмеження заачі представляють систему рівнянь (нерівностей), кожному з яких ставиться у відповідність рядок матриці обмежень, в той же час в ЛП матрицю обмежень зручніше представляти у вигляді впоследовательності стовпців. При цьому зручніше об'єднувати в одну групу стовпці відповідні одному блоку підприємства з іспоользованіем табличній форми запису даних: таблиці даних складаються для кожного блоку підприємства і для кожного набору спеціальних обмежень на продукт. Оскільки кожному рядку і кожному стовпцю приписується своє ім'я, всю матрицю обмежень можна побудувати, склавши список імен всіх таблиць, потім списки імен стовпців кожної таблиці, а потім перерахувавши всі ненульові елементи кожного такого стовпця.
Рівняння з нашого прикладу пояснюють як складаються таблиці. За допомогою цих рівнянь детально описані сировинні потоки, що входять до блоку газового насичення, і потоки продуктів, що виходять з нього. Входам сировинних потоків BOLNP і COLNP відповідають два стовпці LNB і LNC на це вказують коефіцієнти +1. 0 у відповідних цим потокам баласових рядках, негативні коефіцієнти в балансових рядках потоку продкта представляють вихід цього продукту на одиницю сировини, що надходить до блоку. Можна скласти таблицю, що описує весь блок газового насищеія, додавши стовпці, які представляють входи до цього блоку сировинних потоків 90BBG, 9BBG, HYDBBG.
При складанні таблиць, що описують блоки підприємства, ми будемо керуватися наступними правилами:
1) Визначити стовпець j для кожного сировинного потоку, що входить в блок (тоді Xj - кількість j-го сировини). Виконати кроки 2 - 6 для кожного такого стовпця.
2) Записати коефіцієнт рівний +1. 0 в балансову рядок, що відповідає входить сировинному потоку.
3) Для кожного продукту, виробленого в блоці з цього сировинного потоку, записати коефіцієнт-Aij у відповідну балансову рядок потоку продукту, де Aij - кількість продукту i, отриманого з одиниці сировини j.
4) Якщо для блоку існує обмеження по потужності визначається кількістю сировини, записати коефіцієнт +1. 0 в рядок обмеження по потужності. Компонента вектора обмежень, відповідна цьому рядку, дорівнює граничному значенню сумарного сировинного па.
5) У кожен рядок, що представляє обмеження на ресурс, записати коефіцієнт + Aij, де Aij - споживання ресурсу i на одиницю сировини j, (наприклад потреби в енергоресурсах для нашої задачі).
6) Кожній одиниці сировини j приписати коефіцієнт витрат Cj в рядку цільової функції.
Ми можемо скласти подібні таблиці і для кінцевих продуктів, дійсно, ми могли б представити процес виробництва або змішування кінцевого продукту у вигляді окремого блоку, в який входить кілька сировинних потоків, а виходить тільки один потік (сам кінцевий продукт). Крім балансових співвідношень тут можуть з'явитися рядка обмежень спеціального типу.
При складанні таблиць, що описують змішування потоків для отримання кінцевого продукту правила будуть такі:
1) Визначити стовпець j для кожного сировинного потоку, що надходить в змішувач (Xj - кількість j-го сировини). Виконати кроки 2 - 6 для кожного такого стовпця.
2) Записати коефіцієнт рівний +1. 0 в балансову рядок, що відповідає входить сировинному потоку.
3) Записати відповідний коефіцієнт -1. 0 в балансову рядок для кінцевого продукту (наприклад EVOLPROD).
4) Для кожного обмеження знизу на якийсь властивість суміші записати коефіцієнт-Pi в рядок, відповідний цьому обмеженню.
5) У рядок, відповідну обмеження зверху на якийсь властивість суміші записати коефіцієнт + Pi.
6) Виконавши кроки 2 - 5 для всіх сировинних потоків j, визначити стовпець для кінцевого продукту (суміші), (наприклад B, тоді Xb кількість кінцевого продукту). У цей стовпець записати наступні коефіцієнти:
а) до балансової рядок (EVOLPROD) цього кінцевого продукту записати +1. 0,
б) у рядок, що відповідає обмеження знизу на якийсь властивість кінцевого продукту, записати коефіцієнт рівний + Pb,
в) у рядок, що відповідає обмеження зверху на якийсь властивість кінцевого продукту, записати коефіцієнт-Pb,
г) якщо є обмеження на споживання кінцевого продукту, записати +1. 0 у відповідний рядок, що відповідає цьому обмеженню (або врахувати його просто як обмеження на змінну Xb),
д) ввести в рядок цільової функції коефіцієнт вартості кінцевого продукту Cb.
Класифікація економіко-математичних моделейВажливим етапом вивчення явищ предметів процесів є їх класифікація, що виступає як система супідрядних класів об'єктів, що використовується як засіб для встановлення зв'язків між цими класами об'єктів. Основою класифікації є істотні ознаки об'єктів. Оскільки ознак може бути дуже багато то і виконані класифікації можуть значно відрізнятися один від одного. Будь-яка класифікація повинна переслідувати досягнення поставлених цілей. вибір мети класифікації визначає набір тих ознак, за якими будуть класифікуватися об'єкти, що підлягають систематизації. Мета нашої класифікації - показати, що завдання оптимізації, зовсім різні за своїм змістом, можна вирішити на ЕОМ за допомогою декількох типів існуючого програмного забезпечення.
Класифікацію задач оптимізації, що виникають на виробництві, виконаємо за такими ознаками: 1. Область застосування 2. Зміст завдання 3. Клас математичної моделі 1. Забезпечення виробництва включає в себе: 1. 1 Організацію та управління 1. 2 Проектування виробів 1. 3 Розробку технологічних процесів
У всіх цих елементах виробництва виникають задачі оптимізації. Так досить широке коло найрізноманітніших робіт можна розглядати як перетворення ресурсів у результат. У зв'язку з цим основні завдання, що виникають при управлінні, можуть бути віднесені до класу задач розподілу ресурсів.
Об'єкт проектування пристроєм і дією. Пристрій визначається структурою і параметрами. Дія характеризується процесом функціонування. При вирішенні цих трьох питань виникають завдання: 1. 2. а Оптимізація параметрів об'єкта проектування. 1. 2. б Оптимізація структури об'єкту проектування. 1. 2. в Оптимізація функціонування
Технологічний процес визначається послідовністю робіт, які забезпечують перетворення сировини в готову продукцію. Таку послідовність робіт називають маршрутом. Кожна операція, що входить у маршрут характеризується режимами обробки. Очевидно що завдання, що вимагають оптимального рішення виникають як при виборі маршруту так і при визначенні параметрів операцій. 1. 3. а Оптимізація маршруту виготовлення виробу 1. 3. б Оптимізація параметрів технологічних процесів.
Важливою ознакою класифікації є клас математичної моделі. Проведемо класифікацію за елментам математичної моделі: 1 Вихідним даними 2 Потрібним змінним 3 залежною, що описує обмеження і цільову функцію
1. 1 Вихідні дані, які задані певними величинами називають детермінованими 1. 2 Вихідні дані, які залежать від випадкових факторів, наприклад від своєчасності постачання ресурсів, справності обладнання і. т. д. називають випадковими величинами.
2. 1 Змінні можуть бути безперервними і дискретними. Безперервними називають такі величини, які в заданому інтервалі можуть приймати будь-які значення. Так маса вугілля, що видобувається або обсяг випуску тканини представляють собою безперервні величини. 2. 2 Дискретними називають такітолько цілі значення. Так наприклад не можна випустити 0. 7 тепловоза або здати будівельний об'єкт з 1. 45 будівлі.
3. 1 Залежності межу змінними як в цільовій функції так і в обмеженнях можуть бути лінійними і нелінійними. Лінейпервой ступеня і немає їхні твори. 3. 2 Якщо змінні входять не в першому ступені або є твір змінних, то залежності є нелінійними.
Поєднання різних елементів моделі призводить до різних класів задач оптимізації. Різні класи задач вимагають різних методів рішення а сле
Найбільш поширеними завданнями оптимізації виникають в економіці є завдання лінійного програмування. Така їх поширеність пояснюється наступним: 1) З їх допомогою вирішують завдання розподілу ресурсів, до яких зводиться дуже велику кількість різних завдань 2) Розроблено надійні методи їх вирішення, які реалізовані в постачався програмному забезпеченні 3) Низка більш складних завдань зводиться до завдань лінійного програмування
Математичне моделювання в управлінні та плануванніОдин з потужних інструментів яким мають люди, відповідальні за управління складними системами - моделювання. Модель є представленням реального об'єкта, системи чи поняття в певній формі, відмінній від форми їх фактичного реального існування. Зазвичай модель служить засобом, що допомагає в поясненні, розумінні або совершенствованііточной копією цього об'єкта, виконаної в іншому масштабі або з іншого матеріалу, або відображати деякі характерні властивості об'єкта в абстрактній формі, зокрема у вигляді математичних виразів. Аналіз математичних моделей дає в руки менеджерів та інших керівників ефективний інструмент, який може використовуватися для передбачення поведінки систем і порівняння отриманих результатів. Моделювання дозволяє логічним шляхом прогнозувати наслідки альтернативних дій і досить впевнено показує якого з них слід віддати перевагу.
Прих суджень та інтуїції. Для досягнення мети практично завжди існує кілька варіантів з яких потрібно вибрати оптимальний. Для визначення кращого варіанту користуються критерієм ефективності або цільової функцією.
КЕРІВНИЦТВО ПІДПРИЄМСТВОМДля досягнення поставленої мети підприємству потрібні матеріали, обладнання, енергія, робоча сила та інші ресурси. Кожне підприємство такими ресурсами має в своєму розпорядженні, але загальні запаси ресурсів обмежені. Тому виникає важливе завдання: вибір оптимального варіанту, що забезпечує досягнення мети з мінімальними витратами ресурсів. Таким чином ефективне керівництво виробництвом передбачає таку організацію процесу, при якій не тільки досягається мета, але і виходить екстремальне (MIN, MAX) значення деякого критерію ефективності: К = F (X1, X2,..., Xn) => MIN (MAX ) Функція До є математичним виразом результату дії, спрямованого на досягнення поставленої мети, і тому її називають цільовою функцією.
Функціонування складної виробничої системи завжди визначається великим числом параметрів. Для отримання оптимального рішення частину цих параметрів потрібно звернути в максимум, а інші в мінімум. Виникає питання: чи існує взагалі таке рішення, яке найкращим чином задовольняє всім вимогам відразу? Можна впевнено відповісти - ні. На практиці рішення, при якому будь-якої показник має максимум, як правило, не звертає інші показники ні в максимум ні в мінімум. Тому вирази типу: виробляти продукцію найвищої якості з найменшими витратами - це просто урочиста фраза по суті невірна. Правильно було б сказати: отримати продукцію найвищої якості при тій же вартості, або знизити витрати на виробництво продукції не знижуючи її якості, хоча такі вирази звучать менш красиво, але зате вони чітко визначають цілі. Вибір мети і формулювання критерію її досягнення, тобто цільової функції, представляють собою важку проблему вимірювання та порівняння мноазнородних змінних, деякі з яких у принципі несумірні один з одним: наприклад безпека і вартість, або якість і простота. Але саме такі соціальні, етичні та психологічні поняття часто виступають як фактори мотивації при визначенні мети і критерію оптимальності. У реальних задачах управління виробництвом потрібно враховувати те, що деякі критерії мають велику важливість ніж інші. Такі критерії можна ранжувати, тобто встановлювати їх відносну значимість і пріоритет. У подібних умовах оптимальним доводиться вважати таке рішення, при якому критерії мають найбільший пріоритет отримують максимальні значення. Граничним випадком такого підходу є принцип виділення головного критерію. При цьому один якийсь критерій приймається як основного, наприклад міцність сталі, калорійність продукту і. т. д. За цим критерієм проводиться оптимізація, до решти пред'являється тільки одна умова, щоб вони були не менше якихось заданих значень. Між ранжируваною параметрами не можна проводити звичайні арифметичні операції, можливо лише встановлення їх ієрархії цінностей і шкали пріоритетів, що є істотною відмінністю від моделювання в природничих науках.
При проектуванні складних техіческіх систем, при управлінні великим виробництвом або керівництві військовими діями, тобто в ситуаціях де необпрактіческій досвід, що дає можливість виділити найбільш істотні фактори, охопити ситуацію в цілому і вибрати оптимальний шлях для досягнення поставленої мети. Досвід помогае також знайти аналогічні випадки в минулому і по можливості уникнути помилкових дій. Під досвідом мається на увазі е тільки власна практика особи, яка приймає рішення але і чужий досвід, який описаний в книгах, узагальнений в інструкціях, рекомендаціях та інших керівних матеріалах. Єство, коли рішення вже апробовано, тобто відомо яке саме рішення найкращим чином задовольняє поставленим цілям проблеми оптимального управління не існує. Однак насправді практично ніколи не буває абсолютно однакових ситуацій, тому приймати рішення і здійснювати управління завжди доводиться в умовах неповної інформації. У таких випадках відсутню інформацію намагаються отримати використовуючи здогадки, припущення, результати наукових досліджень і особливо вивчення на моделях. Науково обгрунтована теорія управління багато в чому представляє собою набір методів поповнення недостатньої інформації про те як поведе себе об'єкт управління при вибраному впливі.
Прагнення отримати якомога більше інформації про керовані об'єкти і процеси включаючи і особливості їх майбутньої поведінки може бути задоволена шляхом дослідження інтересуюіх нас властивостей на моделях. Модель дає спосіб представлення реального об'єкту, який дозволяє легко і з малими витратами ресурсів дослідити деякі його властивості. Тільки модель дозволяє досліджувати не всі властивості відразу, а лише ті з них, які найбільш істотні при даному розгляді. Тому моделі поволяют сформувати спрощене уявлення про систему й отримати потрібні результати простіше і швидше ніж при вивченні самої системи. Модель виробничої системи в першу чергу створюється у свідомості працівника здійснює управління. На цій моделі він подумки намагається представити всі особливості самої системи і деталі її поведінки, передбачити всі труднощі і передбачити всі критичні ситуації, які можуть вознікуть в різних режимах експлуатації. Він робить логічні висновки, виконує креслення плани і розрахунки.
Складність сучасних технічних систем і виробничих процесів призводить до того, що для їх вивчення доводиться використовувати різні види моделей.
Найпростішими є масштабні моделі в яких дотримується розмірів множаться на постійний розмір - масштаб моделювання. Великі об'єкти представляються у зменшеному вигляді, а малі в збільшеному.
У аналогових моделях досліджувані процеси вивчаються не безпосередньо а за аналогічними явищам, тобто по процесах мають іншу фізичну природу, але які описуються такими ж математичними співвідношеннями. Для такого моделювання використовуються аналогії між механічними, тепловими, гідравлічними, електричними та іншими явищами. Наприклад коливання вантажу на пружині аналогічні коливань струму в електричному контурі, також рух маятника аналогічно коливань напруги на виході генератора змінного струму.
Найбільш загальним методом наукових досліджень є використання математичного моделювання. Математичної моделлю описує формальну залежність між значеннями параметрів на вході модельованого об'єкта або процесу і вихідними параметрами. При математичному моделюванні абстрагуються від конкретної фізичної природи об'єкту і відбуваються в ньому і розглядають тільки перетворити вхідних величин у вихідні. Аналізувати математичні моделі простіше і швидше, ніж експеріметально визначати поведінку реального об'єкта в різних режимах роботи. Крім того аналіз математичної моделі дозволяє виділити найбільш суттєві властивості даної системи, на які треба звернути особливу увагу при прийнятті рішення. Додаткова перевага полягає в тому, що при математичному моделюванні не становить труднощів випробувати досліджувану систему в ідеальних умовах або навпаки в екстремальних режимах, які для реальних об'єктів або процесів вимагають великих витрат або пов'язані з ризиком.
Залежно від виду системи і конкретних цілей, які ставляться при аналізі, можливі різні методи опису систем, тобто існує кілька різних підходів до матемтіческому моделювання і системного аналізу. В основі кожного підходу лежать ті чи інші уявлення, якийсь набір основних ідей і теоретичних передумов або як прийнято говорити певна концепція.
1) Одна з можливих цілей математичного моделювання пов'язана з бажанням розібратися у властивостях систем взагалі. У цьому випадку потрібно мати таку модель, яка охоплювала б як можна більш широкий клас об'єктів і процесів.
2) Інше завдання полягає у ретельному, кількісному вивченні систем певного класу. При цьому необхідно дати докладний математичний опис об'єктів цікавить класу і настільки ж докладний математичний опис відбуваються в них процесів.
3) Нарешті третій підхід з яким часто доводиться стикатися пов'язаний з прагненням використовувати для аналізу якісь конкретні види математичних моделей.
Саме прийняття рішення виходить за рамки математичного моделювання і належить до компетенції відповідального особи якому надано право окончательногос рекомендаціями, що випливають з математичного розрахунку, ще ряд міркувань, які цим розрахунком не були враховані.
У залежності від того, якою інформацією володіють керівник і його співробітники, які готують рішення, змінюються і умови прийняття рішень і математичні методи, які застосовуються для вироблення рекомендацій.
Якщо відомі всі діючі в системі фактори, тобто отстствуют випадкові впливу, то це буде прийняття рішень в умовах визначеності.
Коли рішення може привести не до певного результату, а до одного з безлічі можливих з різними імовірностями їх здійснення, то приймає рішення ризикує отримати не т результат, на який він розраховує. Оскільки результат кожної конкретної реалізації випадковий і тому зара точно не передбачуваний, метод називають прийняттям рішень в умовах ризику.
Якщо ж результат операції залежить не тільки від стратегії обрання керівника, а й від низки факторів, не відомих у момент прийняття рішення, наприклад, дій кокурентов, така задача називається прийняттям рішень в умовах невизначеності.
Операцією називається комплекс заходів об'єднаних загальним задумом і спрямованих на досягнення поставленої мети. Операція є керованим заходом.
У загальному випадку мета операції виражається в прагненні до досягнення екстремального значення критерію ефективності. При наявності еопределенності це вже не строго математична задача, яка дає однозначне рішення. Тепер вона повинна формулюватися таким чином:
При заданих обмеженнях B1. . . Вn знайти такі елементи управління X1. . . Xm які з урахуванням випадкових впливів Q1. . . Qr по можливості забезпечують максимальне значення критерію ефективності До max (min). Тепер немає впевненості в тому, що можна буде отримати рішення, а якщо воно буде отримано то немає гарантії в тому, що воно буде правильним. Саме тому у формулюванні завдання доводиться робити застереження "по можливості". Таким чином при вирішенні проблем вознікющіх в реальному житті математична теорія і науково обгрунтовані методи не дають точного рішення. Причина цього в тому, що коли немає точних даних, тобто немає повної інформації залишається лише припускати і будувати здогади але не можна вважати що всі прогнози збудуться. І все таки рішення, прінятоматематіческіх розрахунків буде краще ніж взяте навмання. Завдання полягає в тому, щоб це рішення якомога більшою мірою містило риси розумності, саме в цьому сенсі слід розуміти визначення "по можливості оптимальну". Складність математичного моделювання в умовах невизначеності залежить від того яка природа невідомих факторів. За цією ознакою завдання діляться на два класи.
1) Стохастичні завдання, коли невідомі чинники являють собою випадкові величини, для яких відомі закони розподілу ймовірностей та інші статистичні харакерістікі.
2) Невизначені завдання, коли невідомі чинники не можуть бути описані статистичними методами.
Ось приклад стохастичною завдання:
Ми вирішили організувати кафе. Яка кількість відвідувачів прийде в нього за день нам невідомо. Також невідомими скільки часу триватиме обслуговування кожного відвідувача. Проте характеристики цих випадкових величин можуть бути отримані статистичним шляхом. Показник ефективності, що залежить від випадкових величин також буде випадковою величиною.
У даному випадку ми в якості показника ефективності беремо не саму випадкову величину, а її середнє значення і вибираємо таке рішення при якому це середнє значення звертається в максимум або мінімум.
Двоїсті оцінки, економічна інтерпретація і властивостіРозглянемо економічний сенс двоїстих оцінок (оцінок оптимального плану) на прикладі економіко-математичної задачі найкращого використання ресурсів (зокрема фонду часу роботи виробничого обладнання), формульованій з різними критеріями оптимальності:
1. Максимум прибутку.
2. Мінімум собівартості.
3. Максимум випуску продукції в заданому асортиментному співвідношенні.
Розглянемо послідовно формулювання прямих і подвійних завдань і проаналізуємо економічні властивості двоїстих оцінок в кожному випадку.
$ 1 Оцінки ресурсів - економічна інтерпретаціяКанонічна форма дає можливість економічної інтерпретації значень двоїстих змінних. У точці оптимуму двоїсті змінні (у) визначаються як відносні оцінки додаткових змінних прямої задачі лінійного програмування. а) Припустимо що додаткова мінлива хij відповідає i-му обмеження є небазисной в точці оптимуму а саме обмеження має вигляд:
E Aij * Xj + Xs = Bi
Так як Xs поза базису дорівнює нулю вихідне обмеження
E Aij * Xj <= Bi можна розглядати як рівність у точці оптимуму, тобто E Aij * Xj = Bi
Тепер за визначенням відносна оцінка цієї небазисной змінної - це величина на яку може зрости цільова функція при збільшенні цієї змінної на одиницю. Так як рішення оптимально то відносна оцінка позитивна (неотрицательна) і тому цільова функція повинна зменшуватися якщо додаткова змінна зростає і зростатиме якщо додаткова мінлива зменшується Нехай наприклад i-я компонента вектора обмежень збільшилася на одиницю, так що обмеження набуде вигляду
_
E Aij * Xj = Bi + 1
або після перестановки _
E Aij * Xj + (-1) = Bi
тобто додаткова мінлива Xs повинна прийняти значення рівне -1 щоб i-е обмеження залишалося рівністю а відносна оцінка дасть відповідне прирощення цільової функції. Таким чином відносна оцінка i-ої додаткової змінної дає величину приросту цільової функції на одиницю збільшення елемента Bi вектора обмежень. Оскільки елемент Bi звичайно являє собою обсяг i-го ресурсу то відносна оцінка рівна Yi називається оцінкою ресурсу (оцінкою одиниці i-го ресурсу) бо вона представляє відносну цінність одиниці додаткового ресурсу. Ці щодо відповідності оцінки є маргінальними оцінками в тому сенсі що вони дійсні лише при такому діапазоні зміни ресурсів Bi коли поточний базис залишається оптимальним. в) Якщо додаткова змінна є базисної в точці оптимуму то її відносна оцінка за визначенням дорівнює нулю. Це також має сенс тому що якщо ресурс використаний не повністю
_
E Aij * Xj <Bi то ціна яку ми повинні були б заплатити за додаткову одиницю цього ресурсу дорівнює нулю. Це призводить до умови доповнює нежорсткої:
В оптимальному рішенні або E Aij * Xj = Bi або Yi = 0 (або і те і інше)
або E Aij * Yi = Cj або Xj = 0 (або і те і інше)
Зауважимо що змінні Y неприпустимі протягом усіх ітерацій симплекс-методу до тих пір поки не буде досягнуто оптимальне рішення.
Маргінальні ОЦІНКИОцінки ресурсів пов'язані скоріше з обмеженнями а не із змінними.
Однак вони часто використовуються для обчислення оціночних або вартісних показників, пов'язаних зі змінними прямої задачі. Розглянемо приклад. Нехай у задачі пов'язаної з добовою переробкою нафти деяка змінна Xj відповідає обсягу неочищеної нафт закуповується за ціною 12. 65 дол / барель (Сj = -12. 65) Існує обмеження зверху на обсяг закупленої за цією ціною неочищеної нафти дорівнює 50 тис. барель / день.
Це можна записати рівнянням: Xj + Xs = 50
Де Xs - це додаткова змінна. Нехай вона має відносну оцінку рівну 1. 04 дол / барель в оптимальному рішенні - що це означає? Оцінка ресурсу неочищеної неочищеної нафти дорівнює 1. 04 дол / барель, але це зовсім не означає, що ми повинні були заплатити лише 1. 04 дол за кожен додатковий барель неочищеної нафти. Це означає що ми повинні бути готові заплатити ще по 1. 04 дол / барель за можливість купувати додатковий обсяг цієї нафти за умови, що наступні закупівлі будуть здійснюватися за ціною 12. 65 дол / барель: тобто цільова функція буде збільшуватися на 1. 04 дол за кожен додатковий барель, який ми зможемо купити за ціною Сj вже врахованої в цільовій функції. Це означає, що м повинні бути готові до підвищення ціни до 12. 65 + 1. 04 = 13. 69 дол / барель за додаткову поставку неочищеної нафти.
Зауважимо, що 13. 69 дол / барель - це рівноважна ціна при якій ми будемо збільшувати нашу цільову функцію Р, якщо будемо купувати за більш дешевою ціною ніж ця: будемо зменшувати Р якщо будемо купувати за більшу ціну: збережемо Р незмінною якщо будемо купувати точно за 13. 69 дол / барель.
Якщо ми визначимо що маргінальні ОЦІНКА = Рівноважна ціна
Фактична ціна, то в нашому прикладі Маргінальні ОЦІНКА = 13. 69 - 12. 65 = 1. 04 дол / барель.
Маргінальна оцінка змінної Xj - Мето чистий дохід, який може бути отриманий за кожну одиницю Xj закуплену понад існуючого
ліміту і дорівнює оцінці ресурсу, тобто двоїстої змінної того умови завдання яке обмежує кількість наявного ресурсу
Маргінальна оцінка залишається постійною тільки всередині деякої околиці існуючого оптимуму, відповідної меж, всередині
яких поточний базис залишається оптимальним як при збільшенні так і при зменшенні обсягу ресурсів (обсягу закупівель). Відносну оцінку яка відповідає небазисной змінної рівної своїй нижній границі часто розглядають як чистий ефект цієї змінної. Якщо приймається рішення (неоптимальне) збільшити небазисную змінну рівну своїй нижній границі то ця відносна оцінка показує зменшення Р на одиницю збільшення змінної (до деяких меж). Тут відносні оцінки вказують на ефект (збитки), обумовлений відхиленням від оптимального рішення.
Так як компоненти вектора Aj (де j - номер небазисной змінної)
показують величину зміни значень поточних базисних змінних
то їх часто називають (маргінальними) нормами заміщення, так що Aij
- Це норма заміщення способу виробництва i на спосіб
виробництва j.
ДІАПАЗОНУ СТІЙКОСТІЧасто кажуть, що постоптімальний аналіз - найбільш важлива частина лінійного програмування і неважко зрозуміти чому робиться такий висновок. Більша частина параметрів задачі ЛП точно не відома і на практиці зазвичай беруться наближені значення, яким повинні бути рівні ці параметри. Таким чином нас цікавлять такі діапазони зміни цих параметрів, в яких оптимальне рішення залишається оптимальним у тому сенсі, що не змінюється базис. Досліджуємо три класи параметрів:
коефіцієнти цільової функції Cj
компоненти вектора обмежень Bi
коефіцієнти матриці Aij
Зміни коефіцієнтів цільової функціїа) небазисная змінна
Зміна коефіцієнта цільової функції небазисной змінної впливає на відносну оцінку тільки цієї змінної. Нехай коефіцієнт цільової функції зміниться на величину q тоді
Cj = Cj + q звідси Dj = Dj - q
Наприклад нехай матрицею А заданий виробничий процес і нехай мінлива Xj представляє кількість деякого виробленого продукту, який може бути проданий за ціною Cj = 20 дол / од В оптимальному рішенні ця мінлива небазисная (= 0) і її відносна оцінка = 1. 40 дол / од Таким чином якщо цін зросте до 21. 40 дол / од продукту то відносна оцінка стане = 0 і подальше збільшення ціни призведе до негативної відносної оцінці. Це означає що поточне рішення перестає бути оптимальним. У такому випадку вигідно виробляти продукт представлений змінною Xj Отже 21. 40 дол / од продукту це рівноважна ціна для Xj, при будь-якій більш низькою ціною оптимальне рішення буде полягати в тому щоб зовсім не виробляти цей продукт (Xj залишається небазисной) а при більш високій ціні вигідно ввести Xj в базис. Для небазисной змінної діапазон стійкості в якому Cj може змінюватися так щоб поточне рішення залишалося оптимальним задається виразом _
Cj + q, де-оо <q <= Dj
і де Dj - відносна оцінка змінної Xj відповідає оптимального рішення. Зауважимо що при будь-якому негативному q відносна оцінка цієї змінної залишиться позитивною. Багато ППП ЛП дають інформацію і про діапазон зміни змінної Xj (від нульового до деякого предельного_значенія) при якому не відбувається зміни базису. Якщо q = Dj то відносна оцінка = 0 що означає що Xj можна збільшувати не змінюючи значення цільової функції. Граничне значення до якого можна збільшувати Xj визначається формулою MIN (B / Aj) i Наприклад припустимо що в оптимальному вирішенні вектор базисних змінних, -1 -1 поточний вектор обмежень B = B * b і вектор Aj = B * aj задані у вигляді:
X5 3. 2 0. 6
Xb = X1 B = 1. 5 Aj = 0. 3
X6 5. 6 -1. 2
Тоді отримуємо MIN (Bi / Aij) = 1. 5 / 0. 3 = 5. 0
Таким чином ми можемо зробити висновок про те що при ціні в 21. 40 дол / од продукту або більше стає вигідним виробляти продукт Xj тобто продукт якому відповідає мінлива Xj; на кожну одиницю виробленого продукту Xj змінні X5 X1 X6 зменшуються відповідно на 0. 6 0. 3 -1. 2 одиниць. Якщо ми зробимо 5. 0 од продукту Xj то змінна X1 звернеться в нуль і подальше збільшення Xj зажадає зміни базису. Зауважимо, що ми отримали всю інформацію не вирішуючи завдання заново, для продовження аналізу нам потрібно лише виконати операцію виключення відповідну зміни базису.
б) Базисна мінлива
Зміна коефіцієнта цільової функції базисної змінної впливає на відносні оцінки небазисних змінних Розглянемо збільшення коефіцієнта цільової функції i-ої баісной змінної. У цьому випадку вектор коефіцієнтів цільової функції зміниться наступним чином
_
Cb = Cb + q * Ei, де Ei - вектор спеціального виду i-а компонента якого = 1 а решта нулю. Наприклад
E3 = 0
Відносна оцінка j-ої небазисной змінної стане тепер рівної
Dj = Dj + q * Aij
Для того щоб рішення залишалося оптимальним повинна виконуватися умова
Dj => 0 тобто Dj ^ + q * Aij => 0, де Dj ^ - відносна оцінка відповідає поточному оптимального рішення.
Для базисної змінної діапазон стійкості в якому може змінюватися Ci залишаючи оптимальним поточне рішення адается виразом Ci + q, де
MAX {Dj ^ /-Aij} <= q <= MIN {Dj ^ /-Aij}
i / Aij> 0 i / Aij <0
Якщо відсутні коефіцієнти Aij <0 то q <+ oo і аналогічно якщо немає Aij> 0 то q>-oo
Наприклад нехай оптимальне рішення задано наступним чином:
Максимізувати Р = 31. Травень -3. 5X4 -0. 1X3 -0. 25X5
За умов X1 = 3. 2 -1. 0X4 -0. 5X3 -0. 60X5
X2 = 1. Травень +0. 5X4 +1. 0X3 -1. 00X5
X6 = 5. 6 -2. 0X4 -0. 5X3 -1. 00X5
Якщо коефіцієнт цільової функції змінної X2 стане рівним С2 + q то відносні оцінки небазисних змінних зміняться наступним чином:
D4 = 3. 5 + q * (-0. 5)
D3 = 0. 1 + q * (-1. 0)
D5 = 0. 25 + q * (+1. 0)
Зауважимо що величини Aij мають знаки протилежні тим, що наведені вище.
Діапазон значень для q обчислюється відповідно до формули:
(0. 25/-1. 0) <= q <= MIN (3. 5 / 0. 5, 0. 1 / 1)
-0. 25 <= q <= 0. 1
Якщо q приймає значення дорівнює одній з двох кордонів то відносна оцінка деякої небазисной змінної стає рівною нулю Граничне значення до якого можна збільшувати таку змінну обчислюється як і в предидуащем прикладі з небазисних змінними
Так у нашому прикладі при q = 0. 1 відносна оцінка змінної X3 дорівнює нулю так що якщо коефіцієнт цільової функції змінної X2 збільшиться на 0. 1 або більше стане вигідно виробляти X3 і ми зможемо виробляти MIN {3. 2 / 0. 5, 5. 6 / 0. 5} = 6. 4 одиниць X3 коли X1 звернеться в нуль і буде потрібно зміна базису.
1. Існує діапазон зміни q коефіцієнтів цільової функції як базисних так і небазисних змінних в яких поточне оптимальне рішення залишається оптимальним. Для небазисних змінних існує лише верхня межа діапазону зміни q; для базисних змінних зазвичай існує і нижня і верхня межа.
При значенні коефіцієнта цільової функції, що виходить за межі цього діапазону поточне оптимальне рішення стає неоптимальним, оскільки з'явиться небазисная змінна з негативною відносної оцінкою.
2. Зміна коефіцієнта цільової функції базисної змінної приводить до зміни значення цільової функції.
3. Ефект від зміни коефіцієнтів цільової функції можна розглядати з двох позицій: з точки зору збуту нас цікавлять рівноважні ціни; з точки зору виробництва нас цікавить діапазон зміни коефіцієнтів цільової функції, в межах якого поточний план (представлений поточним базисом) залишається оптимальним.
Зміна компонент вектора обмеженьРозглянемо вплив зміни Bi = Bi + q для деякого 1 <= i <= m Зазвичай прийнято розглядати випадок, коли компонента Bi є правою частиною обмеження-нерівності в яке введена додаткова змінна. Ми хочемо визначити такий діапазон зміни Bi в якому поточне рішення залишається оптимальним. У разі обмеження-рівності ми могли б розглядати відповідну штучну змінну як неотрицательную додаткову (яка повинна бути небазисной в допустимому ухвалі)
а) Базисна додаткова змінна
Якщо додаткова змінна i-го обмеження базисна то це обмеження не є активним у точці оптимуму. Аналіз простий: значення додаткової базисом змінної дає діапазон зміни, у якому відповідну компоненту Bi зменшується (збільшується у випадку обмеження типу =>).
Рішення залишається допустимим і оптимальним у діапазоні Bi + q, де
-Xs <= q <= + oo для обмежень типу <=
-Oo <= q <= Xs для обмежень типу =>
Тут Xs - значення відповідної додаткової змінної. Наприклад розглянемо обмеження-нерівність:
3X1 + 4X2 + 7X3 <= 100
Наведемо його до рівності ввівши додаткову зміну
3X1 + 4X2 + 7X3 + X4 = 100
Якщо в оптимальному вирішенні X4 = 26 то залишилися змінні задовольняють нерівності:
3X1 + 4X2 + 7X3 <= 74
а також будь-якому нерівності того ж виду зі значенням правої частини великим 74.
б) небазисная додаткова змінна
Якщо додаткова змінна небахзісная і дорівнює нулю, то вихідне обмеження-нерівність є активним у точці оптимуму. На перший погляд може здатися що так як це обмеження активну то відсутня можливість зміни значення правої частини такого обмеження, зокрема можливість зменшення значення Bi (для обмежень типу <=). Виявляється що змінюючи вектор У ми міняємо також вектор Xb і так як існує діапазон змін в якому Xb неотрицатель, то рішення залишається ще й оптимальним у тому сенсі, що базис не змінюється. (Зауважимо що при цьому змінюється значення як Xb так і Р).
Розглянемо обмеження: Ak1X1 + Ak2X2 +. . . + Xs = Bk де Xs - додаткова змінна. Нехай тепер права частина стане рівною Bk + q, тоді рівняння можна переписати так: 1. 1) Ak1X1 + Ak2X2 +. . . + (Xs-q) = Bk
Так що (Xs - q) замінює Xs Отже, якщо в оптимальному вирішенні мінлива Xs небазисная і дорівнює нулю то ми маємо Xb = B - As * (-q) де As - стовпець кінцевої таблиці відповідний Xs. Так як Xs повинен залишатися невід'ємним то ми отримуємо співвідношення: B - As * (-q) => 0 яке визначає діапазон зміни q:
MAX {Bi /-Ais} <= q <= MIN {Bi /-Ais}
i / Ais> 0 i / Ais <0
Якщо немає ні одного Ais> 0 то q>-oo,
а якщо немає жодного Ais <0 то q <+ oo
Для обмежень типу => q змінює знак, тому що замість нерівності E AijXj => Bi ми можемо розглядати
-E AijXj <=-Bi
Тому в рівнянні 1. 1) замість + (Xs-q) ми повинні писати - (Xs + q).
Знову розглянемо приклад:
Максимізувати Р = 31. Травень -3. 5X4 -0. 1X3 -0. 25X
За умов X1 = 3. 2 -1. 0X4 -0. 5X3 -0. 60X5
X2 = 1. Травень +0. 5X4 +1. 0X3 -1. 00X5
X6 = 5. 6 -2. 0X4 -0. 5X3 -1. 00X5
Нехай X4 - додаткова змінна певного обмеження i (типу <=). Якщо компонену Bi змінити на величину q, ми отримаємо:
X1 = 3. 2 - 1. 0 * (-q)
X2 = 1. 5 + 0. 5 * (-q)
X6 = 5. 6 - 2. 0 * (-q)
3. 2 1. 0
тобто B = 1. 5 As = -0. 5
5. 6 2. 0
Тоді,
X1 => 0 при 3. 2 - 1. 0 * (-q) => 0, тобто q => 3. 2/-1. 0,
X2 => 0 при 1. 5 + 0. 5 * (-q) => 0, то ЄАВТ q <= 1. 5 / 0. 5,
X6 => 0 при 5. 6 - 2. 0 * (-q) => 0, тобто q => 5. 6/-2. 0
Значить q може змінюватися в діапазоні:
MAX {3. 2/-1. 0; 5. 6/-2. 0} <= q <= 1. 5 / 0. 5, тобто -2. 8 <= q <= 3. 0
Виродження1. Виродженість прямої задачі
Вироджені рішення прямої задачі характеризується тим, що його базисна компонента дорівнює нулю. Виродженість прямої задачі може часто виявлятися через проміжні (неоптимальні) виродження базисні рішення. Так наприклад не відбудеться поліпшення цільової функції від введення в базис змінної, для якої позитивна відповідна компонента вектор а Aq.
Можливий випадок, коли пряме завдання ЛП має виродження проміжне але невироджені оптималь рішення. Якщо оптимально рішення прямої задачі виродилися, то двоїста задача має нескінченно багато оптимальних рішень.
2. Виродженість двоїстої задачі
З виродженим двоїстої задачі ми стикаємося, коли відносна оцінка, що відповідає небазисной змінної, дорівнює нулю.
Це означає, що небазисная змінна може збільшуватися, не змінюючи при цьому значення цільової функції. Якщо така нульова відносна оцінка відповідає оптимальному вирішенню, то є безліч оптимальних рішень так як Р не змінюється). Зауважимо, що ми отримали вироджені рішення двоїстої задачі, що відповідає кордоні діапазоа стійкості коефіцієнта цільової функції, а також вироджені рішення прямої задачі відповідне межі діапазону стійкості компоненти вектора обмежень.
Як приклад джерела цінної інформації, одержуваної при постоптімальном аналізі, розглянемо наступну виробничу задачу. Підприємство з переробки руди виробляє два сорти очищеної продукції, яка продається підприємствам металургійної промисловості. Схема роботи підприємства виглядає наступним чином.
Переробляються два види руди: А і В. Заводу може бути поставлено до 100 тис. т на день руди виду А за ціною 3. 25 дол / т і д 30 тис. т в день руди виду У більш високої якості за ціною 3. 40 дол / т. Загальна потужність основного процесу переробки дорівнює 100 тис. т руди на день при витратах на переробку 0. 35 дол / т.
Основний процес переробки дозволяє отримати з кожної тонни руди виду А 0. 15 т продукту 1 і 0. 85 т продукту 2, а з кожної тонни руди виду В 0. 25 т продукту 1 і 0. 75 т продукту 2.
Продукт 1 більш цінний, і агрегат, званий конвертером, здатний з кожної тонни продукту 2 одержати 0. 5 т продукту 1 і 0. 5 т продукту, який може бути проданий як продукт 2, але який не можна повторно переробляти конвертером. Потужність конвертера 50 тис. т сировини на день при витратах на конвертерну обробку 0. 25 дол / т сировини. Умови реалізації наступні. Продукт 2 може бути проданий в необмеженій кількості по ціні 3. 8 дол / т, продукт 1 продається за ціною 5. 5 дол / т і його можна продати за цією ціною до 45 тис. т / день. Існуючий контракт вимагає, щоб менш 40 тис. т / день продукту 1. Запаси продукту 1 можуть збільшуватися зі швидкістю 4 тис. т / день і ці запаси оцінюються з розрахунку 5. 20 дол / т. Надлишок продукту 1 може бути проданий в необмеженій кількості за зниженою ціною, яка дорівнює 5. 0 дол / т. Обидва продукти можна при необхідності докупити: закупівельна ціна продукту 1 дорівнює 5. 75 дол / т; закупівельна ціна продукту 2 дорівнює 4. 0 дол / т.
Для побудови моделі введемо такі позначення змінних:
X1 - кількість переробленої руди виду А
X2 - кількість переробленої руди виду В
X3 - кількість докуплений продукту 1
X4 - кількість докуплений продукту 2
X5 - кількість продукту 2 переробленого в конвертері
X6 - кількість продукту 1 на складі
X7 - кількість продукту 1 проданого за зниженою ціною
X8 - додаткова змінна обмеження на використовувані ресурси руди виду В (<= 30)
X9 - додаткова змінна умови, що обмежує зверху кількість продукту 1 яке можна продати за звичайною ціною (<= 45)
X10 - додаткова змінна умови, що обмежує знизу кількість продукту 1 яке можна продати за звичайною ціною (<= 40)
X11 - додаткова змінна умови, що обмежує зверху об'єм складованого запасу продукту 1 (<= 4)
X12 - додаткова змінна умови, що обмежує зверху потужність основного процесу обробки (<= 100)
X13 - додаткова змінна умови, що обмежує зверху потужність конвертера (<= 50)
X14 - надлишок продукту 2, який йде безпосередньо на продаж не проходячи конвертерної обробки
Обмеження
0. 15X1 + 0. 25X2 + X3 + 0. 5X5 - X6 - X7 + X9 = 45 [1]
0. 15X1 + 0. 25X2 + X3 + 0. 5X5 + X6 - X7 - X10 = 40 [2]
X2 + X8 = 30 [3]
X6 + X11 = 4 [4]
X1 + X2 + X12 = 100 [5]
X5 + X13 = 50 [6]
- 0. 85X1 - 0. 75X2 - X4 + X5 + X4 = 0 [7]
Цільова функція
5. 50 * (0. 15X1 + 0. 25X2 + 0. 5X5) + 3. 80 * (0. 85X1 + 0. 75X2 - 0. 5X5)
- 0. 35 * (X1 + X2) - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 1 * (0. 15X1 +
0. 25X2) - 0. 25X3 - 0. 20X4 - 0. 30X6 - 0. 5X7 - MAX
0. 825X1 + 1. 375X2 + 2. 750X5 + 3. 230X1 + 2. 85X2 - 1. 9X5 - 0. 35X1
- 0. 35X2 - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 015X1 - 0. 025X2 - 0. 25X3
- 0. 20X4 - 0. 30X6 - 0. 5X7 -> MAX
0. 44X1 + 0. 45X2 + 0. 6X5 - 0. 25X3 - 0. 2X4 - 0. 3X6 - 0. 5X7 -> MAX
Оцінки ресурсівОцінка обмеження на потужність основного процесу переробки дорівнює 0. 44 дол / т (відносна оцінка, відповідна змінної X12 дорівнює 0. 44). Ця оцінка справедлива в діапазоні зміни потужності основного процесу визначається виразом 100 + q, де MAX {3/-0. 15; 70/-1; 32/-0. 85} <= q <= MIN {2 / 0. 15} звідси -20 <= q <= 13. 33
Таким чином, поточний дохід можна збільшити на 0. 44 дол. за кожну тонну збільшення потужності основого процесу обробки, якщо будемо збільшувати цю потужність лише до 113, 33 тис. т / день.
Оцінка обмеження на потужність конвертера дорівнює 0. 6 дол / т (відносна оцінка, відповідна змінної X13 дорівнює 0. 6) Ця оцінка справедлива в діапазоні зміни 50 + q, де MAX {3/-0. 5; 50/-1} <= q <= MIN {2 / 0. 5} звідси -6 <= q <= 4
Таким чином, поточний дохід можна збільшить на 0. 6 дол за кожну тонну збільшення потужності конвертера, якщо будемо збільшувати цю потужність лише до 54 тис. т / день.
Маргінальна оцінкаМаргінальна оцінка руди В дорівнює 0. 01 дол / т і справедлива в діапазоні 30 + q, де MAX {3/-0. 1; 30/-1} <= q <= MIN {2 / 0. 1; 70 / 1, 32 / 0. 1} звідси -30 <= q <= 20
Якщо лq = -30, то X2 = 0, то є руда виду В закуповуватися не буде. Якщо q = 20, то X2 = 50, тобто можна купувати до 50 тис. т руди У в день.
Можна зробити висновок, що ми отримаємо чистий дохід по 0. 01 дол за кожну тонну руди виду В, куплену понад 30 тис. т / день, за умови, що загальна кількість купується руди цього виду не перевищить преела 50 тис. т / день, у якому змінюється маргінальна оцінка з-за зміни базису. Точно так само ми втратимо по 0. 01 дол за кожну відсутню тонну руди виду В, якщо ми будемо купувати менше 30 тис. т / день. Ми можемо міркувати інакше, а саме, що ми могли б вести переговори про додаткову закупівлю руди виду В понад 30 т / день (але не більше ніж на 20 тис. т / день) за ціною до
3. 40 + 0. 01 = 3. 41 дол / т.
Зміни коефіцієнтів цільової функції1. (Небазисних змінні)
X4: відносна оцінка = 0. 2
Естлі продукт 2 можна купувати по 4. 00 - 0. 2 =. 80 дол / т або дешевше, то це вигідно робити і ми можемо купувати необмежену кількість цього продукту.
X6: відносна оцінка = 0. 3
Якщо ціна продукту 1 зберігається на складі збільшиться до 5. 20 + 0. 30 = 5. 50 дол / т або більше те вигідно зберігати запас, збільшуючи його до MIN {3 / 1, 4 / 1} = 3 тис. т / день (до того як відбудеться зміна базису).
X7: відносна оцінка = 0. 5
Якщо знижена ціна продукту 1 зросте до 5. 00 + 0. 5 = 5. 50 дол / т або більше, його вигідно продавати на такому ринку, причому ежеднневно можна продавати до 3 тис. т, перш ніж зміниться базис.
X3: відносна оцінка = 0. 25
Якщо продукт 1 можна купити за ціною 5. 75 - 0. 25 = 5. 50 дол / т або дешевше, вигідно зробити це, причому можна купувати до 2 тис. т / день перш ніж зміниться базис.
2. (Базисні перемінні)
X2: коефіцієнт цільової функції = -3. 40
Коефіцієнт цільової функції може змінюватися в діапазоні С2 + q, де 0. 01/-1 <= q <= оо
Якщо ціна руди виду В стане рівною 3. 41 дол / т або більше (С2 = -3. 40 - 0. 01) то вигідно збільшити X8, тобто зменшити кількість купується руди виду В; діапазон зміни X8 задається співвідношеннями MAX {2/-0. 1; 70/-1; 32/-0. 1} <= X8 <= MIN {3 / 0. 1; 30 / 1}
Зазвичай нас цікавлять тільки позитивні межі. У нашому прикладі X8 може змінюватися до 30 тис. т / день, перш ніж буде потрібно змінити базис (X2 Оратів в нуль). Дослідження отриманих результатів показує, що обчислення меж здійснюється аналогічно обчисленню маргінальних оцінок, виполненномоу раніше.
Це вказує нам шлях обчислення маргінальних оцінок для змінних, які не рівні значенням своєї верхньої межі (як ми побачимо для руди виду А (X1))
X1: коефіцієнт цільової функції = - 3. 25
Коефіцієнт цільової функції може змінюватися в діапазоні С1 + q, де - 0. 44 <= q <= 0. 01
Якщо ціна руди виду А зменшиться до 3. 24 дол / т або ще менше (С1 = -3. 25 + 0. 01), то стане вигідно збільшити X8 (тобто замінити руду виду В рудою виду А) до X8 = 30, що відповідає X1 = 100, X2 = 0. Таким чином маргінальна оцінка руди виду А у діапазоні 50-70 тис. т / день дорівнює 0. 44 дол / т.
Зауважимо, що стрибок маргінальної оцінки, що відповідає базисної змінної, відбувається при значенні, яке ця переменнаяi приймає в оптимальному рішенні (у нашому прикладі при X1 = 70) Маргінальні оцінки інтерпретуються трохи інакше, ніж зміни цін, що вимагаються для того, щоб змінити оперативний план. Якщо руда виду А може бути закуплена дешевше на 0. 01 дол / т, то від заміни такої рудою руди виду В цільова функція не зміниться; якщо ціна руди виду А зросте на 0. 44 дол / т, то зменшення її закупівлі на величину, що не перевищує 20 тис. т / день, також не змінить значення цільової функції.
Зміни компонент вектора обмежень1. (Базисна додаткова змінна)
Величина зміни може бути обчислена безпосередньо:
X9 = 2 і X10 = 3 вказують, що кількість продукту 1, яке можна продавати за звичайною ціною одно 43 (менше верхньої межі на 2 і більше нижньої межі на 3).
Значення X11 показує, що верхня межа запасу продукту 1 може бути зменшений на 4.
2. (Небазисная додаткова змінна)
Діапазони зміни компнент вектор обмежень вже розглядалися вище при обговоренні оцінок ресурсів, маргінальних оцінок і змін коефіцієнтів вектора цільової функції. Однак нам може знадобитися дослідити окремо вплив зміни наявних ресурсів безвідносно до зміни цін. Тому ми коротко підсумуємо результати зміни тільки компонент вектора обмежень і вкажемо діапазони, усередині яких поточне рішення залишиться оптимальним.
X12: Потужність основного процесу обробки може змінюватися в диапазон MAX {3/-0. 15; 70/-1; 32/-0. 85} <= q <= MIN {2 / 0. 15} тобто -20 <= q <= 13. 33
X8: Ресурси руди типу В можуть змінюватися в діапазоні 30 + q, де MAX {3/-0. 1; 30/-1} <= q <= MIN {2 / 0. 1; 70 / 1, 32 / 0. 1} тобто -30 <= q <= 20
X13: Потужність конвертера може змінюватися в діапазоні 50 + q, де MAX {3/-0. 5; 50/-1} <= q <= MIN {2 / 0. 5} тобто -6 <= q <= 4
Оптимальність зберігається в тому сенсі, що базис не змінюється, хоча значення змінних і цільової функції змінюються, але залишаються допустимими.
Завдання до семінарського заняттяПідприємство може переробляти двавіда руди: руда виду А може бути поставлена в обсязі 50 тис. т / день за ціною 2. 80 дол / т, руда виду Б може бути поставлена в обсязі 75 тис. т / день за ціною 2. 50 дол / т.
Обидва види руди проходять через блок основний переробки. На заводі є ще три блоки, ксплуатаціонние витрати і граничні потужності яких задаються наступною таблицею:
Блоки Експлуатаційні Граничні потужності витрати ($ / т) тис. т / день
Блок основної переробки 0. 20 100
Збагачення 0. 15 25
Подрібнення 0. Жовтень 1940
Очищення 0. 15 40
Дані з продажу:
Продукт Дохід (дол / т) Споживання (МАХ)
1 6. 00 Чи не огранічео
2 5. 00 60 тис. т / день
3 4. 00 Не обмежено
Вихід продуктів (в т / т сировини)
Процес основного обробітку Збагачення
Руда А Руда Б proc1 proc2 gr1
proc1 0. 15 0. 12 tret1 0. 15 0. 20 0. 18
proc2 0. 10 0. 10 tret2 0. 35 0. 38 0. 40
proc3 0. 20 0. 15 tret3 0. 50 0. 42 0. 42
proc4 0. 23 0. 25
proc5 0. 32 0. 33
Подрібнення Очищення
proc4 proc5 proc3 gr2
gr1 0. 15 0. 10 gr2 0. 20 0. 20 ref2 0. 55 0. 70
gr3 0. 25 0. 35
gr4 0. 40 0. 35
Кожен стовпець відповідає потоку сировини, що надходить, так щось даними можна легко побудувати блок-схему потоків.
Характеристика якості продукту:
Продукти 1 і 3 не мають ніяких обмежень на якість.
Продукт 1 складається з tret1 і ref1.
Продукт 3 складається з tret3, ref2 і gr4.
Продукт 2:% окису металу => 55
Запаси сумішей сировини для продукту 2:
tret2 tret3 ref1 ref2 gr3 gr4
% Окисів металів 65 60 53 50 45 40
Ми хочемо максимізувати чистий дохід за день!
МАТЕМАТИЧНА МОДЕЛЬx1 + x21 = 50. . . . ruda1
x2 + x22 = 75. . . . ruda2
x1 + x2 + x23 = 100. . . . blok osn
0. 15x1 + 0. 12x2 = x3. . . . pr1
0. 10x1 + 0. 10x2 = x4. . . . pr2
0. 20x1 + 0. 15x2 = x5. . . . pr3
0. 23x1 + 0. 25x2 = x6. . . . pr4
0. 32x1 + 0. 33x2 = x7. . . . pr5
0. 15x6 + 0. 10x7 = x9. . . . gr1
0. 20x6 + 0. 20x7 = x10. . . . gr2
0. 25x6 + 0. 35x7 = x11. . . . gr3
0. 40x6 + 0. 35x7 = x12. . . . gr4
0. 15x3 + 0. 20x4 + 0. 18x9 = x13. . . . tr1
0. 35x3 + 0. 38x4 + 0. 40x9 = x14. . . . tr2
0. 50x3 + 0. 42x4 + 0. 42x9 = x15. . . . tr3
0. 45x5 + 0. 30x10 = x16. . . . ref1
0. 55x5 + 0. 70x10 = x17. . . . ref2
0. 5x13 + 0. 5x16 = x18. . . . Q1
0. 3x15 + 0. 3x17 + 0. 4x12 = x19. . . . Q3
65x14 + 60x15 + 53x16 + 50x17 + 45x11 + 40x12 = 55x20
ПРИСТРІЙ ПКПерсональний комп'ютер - це настільна ЕОМ організована таким чином, що для роботи на ній не обов'язково бути фахівцем з обчислювальної техніки і програмування, а достатньо про мати лише саме загальне уявлення про ЕОМ. Найбільшого поширення в світі отримали комп'ютери фірми IBM - IBM PC.
Типова система IBM PC включає системний блок, де розміщені основи електроніки комп'ютера і накопичувачі, клавіатуруЂ, дисплей та принтер. Системний блок має розміри близько 15 * 40 * 50см і важить близько 13 кг.
Усередині системного блоку перебувають головні компоненти, що виконують функції комп'ютера: блок живлення, основна системна плата (центральний процесор) з мікросхемами пам'яті, і гнізда для підключення додаткових пристроїв.
Системний блок IBM PC складається з наступних основних компонентів:
1. Центральний процесор представляє собою мікросхему, і
включає в себе:
А) Пристрій управління, що інтерпретує команди комп'ютера і ініціює сигнали, які змушують схеми комп'ютера виконувати певні дії;
Б) Арифметико-логічний пристрій виконує всі обчислення. Центральний процесор визначає швидкодія комп'ютера. Модель IBM PC / AT використовує мікропроцесор Intel-80286 і математичний співпроцесор Intel-80287 забезпечують досить високу продуктивність і швидкодія.
2. Блок пам'яті, кото використовується для зберігання програм, даних і результатів. Цей блок включає в себе два типи пам'яті:
А) Оперативний запам'ятовуючий пристрій (ОЗП) - Оперативна пам'ять в якій розташовуються програми, які виконуються комп'ютерів і дані використовуються програмами. Ємність оперативної пам'яті зазвичай дорівнює 640 Кбайт (байт-одиниця інформації). З ОЗУ можна прочитувати і в нього записувати інформацію. При виключенні питан зберігалася в ОЗУ буде втрачена, якщо вона попередньо не збережена на диску.
Б) постійні запам'ятовуючий пристрій (ПЗП) - Основна пам'ять з нього можна тільки зчитувати інформацію. У ПЗУ програми записуються при виготовленні комп'ютера і залишаються там навіть при відсутності живлення. У ПЗУ зберігається частина операционой системи DOS, що забезпечує тестування комп'ютера, початкове завантаження операційної системи, а також виконання основних низькорівневих послуг введення-виведення.
3. Контролери - електроанние схеми, що керують роботою різних пристроїв входять в комп'ютер (дисководів, монітора і. Т. д.).
4. Порти введення-виведення через які процесор обмінюється даними з зовнішніми пристроями. Є спеціалізовані порти, через які відбувається обмін даними з внутрішніми пристроями комп'ютера, і порти загального назаченія, до яких можуть підключатися різні додаткові весняні пристрої (принтер, миша і. Т. д.).
Порти загального призначення бувають двох видів: паралельні (що позначаються LPT1, LPT2...) І асинхронні послідовні (позначаються COM1, COM2...). Паралельні порти виконують введення і висновок з більшою швидкістю ніж послідовні, але вимагають і більшого числа проводів для обміну даними.
5. Дисководи для гнучких магнітних дисків - дискет, використовувані для читання і запису на дискетах. Найбільш поширені дискети розміром 5. 25 дюйми (133мм) В даний час найчастіше використовуються дискети ємністю 360 Кбайт і 1. 2 Мбайта. Для читання і запису дискет ємністю 1. 2 Мбайта призначені спеціальні дисководи, які встановлюються на комп'ютерах моделей IBM PC / AT. Ці дисководи можуть також читати дікети ємністю 360 Кбайт. Часто використовуються і накопичувачі на дискетах розміром 3. 5 дюйма (89мм) і ємністю 0. 7 і 1. 4 Мбайта.
Дискети - прецезіонние пристрої і тому вимагають дуже обережного поводження. Щоб уникнути псування записаної на дискетах інформації їх слід зберігати подалі від джерел магнітних полів телевізорів, електромотор. д. Дискети не слід гнути і чіпати руками відкриті ділянки магнітного покриття. Більшість дискет має захист від випадкового псування міститься на них. Так дискети розміром 5. 25 дюйми мають на бічній кромці проріз дозволу запису дозволяє проводити запис на дискеті при встановленні її в дисковод. Щоб захистити таку дискету, досить закрити виріз непрозорою наклейкою. При цьому повторна запис необхідно її спеціальним чином відформатувати.
6. Накопичувач на жорсткому диску - вінчестер, призначений для постійного зберігання інформації, яка використовується при роботі з комп'ютером: програм операційної системи, часто використовуваних ПП, редакторів документів, трансляторів з мов програмування і. т. д. Наявність вінчестера зачительному підвищує зручність роботи з комп'ютером. У порівнянні з гнучкими дисками час доступу до інформації на жорсткому диску значно менше. На моделях IBM PC / AT жорсткий диск найчастіше має ємність 40 Мбайт.
Клавіатура IBM PC - розміри 6 * 20 * 51 см., пристрій, призначений - - для введення в комп'ютер інформації. Найбільш широке поширення отримала клавіатура з 102 клавішами, (де деякі клавіші продубльовані в цілях зручності роботи), які можуть генерувати всі 128 символів в кодах ASCII (Американський стандартний код для обміну інформацією), а також спеціальні символи і графічні знаки. Рсположеніе латинських букв на клавіатурі IBM PC, як правило таке ж як на англійській друкарській машинці, а букв кирилиці - як на російській друкарській машинці.
З правого боку клавіатури є цифрові клавіші, деякі з них іспользуютс також для управління курсором - (клавіші зі стрілками, клавіші Home, End, Page Up, Page Down). Для зручності користувача частина цих клавіш продубльована.
У верхньому ряду розташовані 12 програмованих функціональних клавіш. Функції цих клавіш програмуються розробником математичного забезпечення. Зазвичай їх дію вказується в нижній частині екрана.
На клавіатурі є ще ряд спеціальних клавіш: Enter, Control, Altenate, Tab, Insert, Delete та інші. Деякі з цих клавіш можна натискати одночасно, щоб виконувати спеціальні функції. Наприклад натискаючи клавіші CTRL, ALT і DEL можна перезавантажити систему (так звана "тепла перезавантаження DOS"). Натиснення на будь-яку клавішу в Тече напівсекунди призведе до автоматичного повторення символу. На відміну від клавіатур інших комп'ютерів клавіатура IBM PC містить електронні схеми, що розширюють можливості клавіш і дозволяють перевизначати їх.
Дисплей і принтер - ці пристрої роблять комп'ютер закінченою системою.
Дисплеї (монітори) бувають кольоровими і монохромними. Вони можуть працювати в одному з двох режимів: текстовому або графічному. У текстовому режимі екран монітора умовно розбивається на окремі ділянки - знакоместа, найчастіше на 25 рядків по 80 символів.
У кожне знакомісце може бути виведений один з символів. Графічний режим призначений для виведення на екран малюнків, графіків і. т. д. У цьому режимі можна виводити і текстову інформацію причому букви і цифри можуть бути довільного розміру. У графічному режімет екран монітора складається з точок. Кількість точок по горизонталі й вертикалі називається роздільною здатністю монітора в даному режимі. Наприклад роздільна здатність 640 * 350 означає, що в даному режимі монітор виводить 640 точок по горизонталі і 350 по вертикалі. Найбільш широке поширення в комп'ютері IBM PC одержали кольорові монітори EGA і VGA. У текстовому режимі вони працюють приблизно однаково, а в графічному VGA забезпечує більш високу роздільну здатність, тобто виводить більшу кількість точок на екран, що підвищує якість зображення і знижує стомлення очей.
Принтер преедназначен для виведення інформації на папір. Всі принтери можуть виводити текстову інформацію, а багато хто також малюнки і графіки. З IBM PC сумісний ряд принтерів. Фірма IBM рекомендує і продає графічне матричне друкуючий пристрій вироблене фірмою EPSON. Принцип роботи матричних притерся такий: друкуюча головка принтера містить вертикальний ряд тонких металевих стрижнів (голок). Головка рухається уздовж друкованої рядки, а голки в потрібний момент ударяють по паперу через фарбувальну стрічку. Швидкість друку матричних принтерів в залежності від необхідної якості друку від 10 до 60 секуд на сторінку.
Існують і інші види принтерів: струминні, літерні, лазерні і. т. д. але вони як правило більше дорогі і не завжди сумісні з наявними програмами.
До комп'ютера IBM PC можуть підключатися й інші пристрої: Миша - маніпулятор для введення інформації в комп'ютер. Свою назву цей пристрій отримав за свій зовнішній вигляд: невелика ікоробочка зазвичай сірого кольору з двома або трьома клавішами, легко вміщується у долоні. Разом з проводом для підключення до комп'ютера дійсно сильно нагадує миша з хвостом. Щоб змінити положення курсору на екрані монітора користувач переміщує мишу по столу, натиснувши на ту чи іншу клавішу. Деякі програми розраховані тільки на роботу з мишею але більшість програм допускають введення як з клавіатури так і з миші.
Сканер - пристрій для зчитування графічної і текстової інформації в комп'ютер. Сканери бувають настільні, що дозволяють обробляти звістку лист цілком або ручні їх потрібно порядково проводити над потрібним малюнком чи текстом.
Модем - пристрій використовується при прийомі або передачі інформації по телефонній лінії. Модем може з'єднати комп'ютер з іншим омпьютером використовуючи стандартну телефонну лінію. Існує широкий вибір і інших периферійних пристроїв вбудованих в комп'ютер: графобудівники, ігрові адаптери, блоки розширення пам'яті, стриммерів і. т. д.
ОПЕРАЦІЙНА СИСТЕМАОпераційна система - це програма, яка завантажується при включенні комп'ютера. Вона робить діалог з користувачем, здійснює керування комп'ютером, запускає інші програми. Операційна система забезпечує користувачу зручний спосіб. спілкування (інтерфейс) із пристроями комп'ютера.
Основна причина необхідності операційної системи полягає в тому, що елементарні операції для роботи з пристроями комп'ютера - це операції дуже низького рівня, тому дії, необхідні користувачу складаються з тисяч таких елементарних операцій. Так навіть для виконання такого простого дії як копіювання файлу з однієї дискети на іншу необхідно виконати тисячі операцій по запуску команд дисководів, перевірки їх виконання, пошуку та обробці інформації в таблицях розміщення файлу на диску і. т. д. Операційна система приховує від користувача ці складні і непотрібні йому подробиці і надає йому зручний інтерфейс для роботи. Як правило IBM PC працює під управлінням операційної системи MS DOS фірми Microsoft Corp. MS DOS отримала широке поширення завдяки порівняно невеликій займаному дисковому простору і затрачуваної оперативної пам'яті, зручному інтерфейсу хорошою сумісності з різною периферією.
Операційна система MS DOS складається з наступних частин:
1) Базова система введення-виведення знаходиться в ПЗУ до Ця частина ОС є вбудованою в комп'ютер. Вона виконує найбільш прості та універсальні послуги ОС пов'язані зі здійсненням уведення-виводу і містить тест комп'ютера, що перевіряє роботу його пристроїв і пам'яті при включенні електроживлення. Базова система введення-висновку містить програму виклику завантажника ОС.
2) Завантажувач операційної системи - це коротка програма, що знаходиться в першому секторі дискети з ОС або вінчестера. ЇЇ функція полягає в зчитуванні в пам'ять ще двох модулів ОС.
3) Дискові файли IO. SYS і MSDOS. SYS. Вони завантажуються в пам'ять завантажувачем ОС і залишаються в пам'яті комп'ютера. Файл IO. SYS є доповнення до базової системи введення-висновку в ПЗУ. Файл MSDOS. SYS реалізує основні високорівневі послуги MSDOS.
4) Командний процесор DOS - обробляє команди вводяться користувачем. Командний процесор знаходиться у файлі COMMAND. COM на диску з якого завантажується ОС. Деякі команди користувача, звані внутрішніми наприклад DIR або COPY командний процесор виконує сам. Для виконання інших (зовнішніх) команд він шукає на дисках програму з відповідним ім'ям і якщо знаходить те завантажує її в пам'ять і передає їй управління. Після закінчення роботи командний процесор видаляє програму з пам'яті і видає запрошення DOS.
5) Зовнішні команди DOS - це програми поставляються разом з ОС у вигляді окремих файлів. Вони виполяют дії обслуговуючого характеру, наприклад форматування дискет, тестування дисків і. т. д.
6) Драйвери пристроїв - це спеціальні програми, які доповнюють систему введення-виведення DOS і забезпечують обслуговування нових пристроїв. Драйвери завантажуються в пам'ять комп'ютера при завантаженні ОС і їхні імена вказуються в спеціальному файлі CONFIG. SYS. Це полегшує додавання нових пристроїв і дозволяє робити це не зачіпаючи системних файлів DOS.
Початкова завантаження DOS виконується автоматично в наступних випадках:
а) При включенні електроживлення.
б) При натисканні на клавішу "Reset"
в) При одночасному натисканні клавіш C На початку завантаження працюють програми перевірки обладнання знаходяться в ПЗУ. Після закінчення тестування програма початкової завантаж намагається прочитати з дискети встановленої в дисководі А програму-завантажувач ОС. Якщо на дисководі А немає дискети то завантаження ОС буде проводитися з вінчестера. Якщо на дисководі А знаходиться дискета без ОС то буде видане повідомлення про помилку. Слід змінити дискету на системну або прибрати дискету і повторити завантаження. Після того як з диска прочитана програма-завантажувач ОС, вона зчитує в пам'ять комп'ютера модулі ОС - файли IO. SYS і MSDOS. SYS і передає їм керування.
Далі з того ж диску читається файл конфігурації CONFIG. SYS і відповідно до вказівок містяться в ньому, завантажуються драйвери пристроїв і встановлюються параметри ОС.
Після цього з системного диска читається файл COMMAND. COM і йому передається управління. COMMAND. COM шукає в кореневому каталозі системного диска файл AUTOEXEC. BAT у якому вказуються команди і програми, які виконуються при кожному запуску комп'ютера. Наприклад програма, що забезпечує роботу з російськими літерами на клавіатурі, програма-оболонка NORTON COMMANDER. Після виконання файлу AUTOEXEC. BAT процес завантаження ОС закінчується і DOS видає запрошення показує, що вона готова до прийому команд: наприклад, C:>
Мережеве планування за методом критичного шляху.
(Critical Path Method) CPM
CPM є одним з найпопулярніших інструментів при плануванні господарських проектів. Мережевий графік являє собою графічне зображення проекту, в якому окремі операції, тобто роботи з виконання проекту, зображуються стрілками. Початок і кінець стрілки позначають початок і закінчення операції відповідно. Час, який передбачається затратити на виконання операції, називається її плановою тривалістю. Для ясності на мережевому графіку даються короткий опис і тривалість кожної операції (рис. 1)
Одне з найважливіших понять мережевого графіка-шлях. Шлях-це будь-яка послідовність робіт, в якій кінцева подія кожної роботи збігається з початковим подією наступної за нею роботи. Серед различ-них шляхів мережного графіка найбільший інтерес представляє повний шлях. Повний шлях-це будь-який шлях, початок якого збігається з вихідним подією мережі, а кінець із завершальним подією мережі. Найбільш тривалий шлях в мережевому графіку називається критичним. Критичними називаються також роботи і події, розташовані на цьому шляху. Критичний шлях має особливе значення, оскільки роботи цього шляху визначають загальний цикл завершення всього комплексу робіт, що плануються при допомозі мережевого графіка. І для скорочення тривалості проекту необхідно в першу чергу скорочувати тривалість робіт, що лежать на критичному шляху. Якщо одиниця часу (день, тиждень) одна й та ж для всіх операцій мережевого графіка, то для вказівки тривалості достатньо навести лише кількість цих одиниць. Зображення операцій робиться без урахування масштабу. Розрізняють три види операцій: а) Дійсна операція-процес, що вимагає витрат часу і pесурсов виконання монтажних робіт, підвіз матеріалів і. т. д.) б) Операція-очікування-процес, що вимагає тільки витрат часу (затвердіння бетону, сушка штукатурки і. т. д)
в) Фіктивна операція-логічна залежність, яка відображає технологічну або ресурсну залежність у виконанні деяких операцій. Її позначають штриховими стрілками. Така операція має нульову тривалість і не вимагає виконання будь-якої роботи. Для кожної операції в мережевому графіці можуть існувати операції, які закінчуються до її початку, що виконуються паралельно з нею або починаються тільки після її завершення. Мережевий графік не повинен мати замкнутих циклів; всі його операції спрямовані зліва направо. Його слід викреслювати кілька разів, домагаючись мінінума перетинань і поступово покращуючи ясність. Мережевий графік для великого проекту може містити тисячі операцій.
Тому необхідний простий спосіб визначення і позначення операції. Кожна операція визначається двома вузлами (подіями)-початковим і кінцевим. Сенс назви вузла 'подією' полягає в тому, що він зображує як раз такий момент, коли всі операції, що входять у цей вузол, закінчуються, і, тому можуть бути розпочаті всі операції, що виходять з цього вузла. Для нумерації операцій зручно використовувати ij правило, причому номер i завжди менше номера j. Проблема позначення виникає у разі, якщо дві або більше операції з'єднують два або більше вузла.
Для її вирішення використовується фіктивна оерація. Іноді події нумеруються не послідовні чином (1, 2, 3...) А отримують номери 10, 20, 30, 40. . . . Це полегшує додавання в мережевий графік нових операцій. Такі операції отримують проміжні номери, наприклад 11-12, 14-18 і. т. п. Складаючи мережевий графік, необхідно ретельно аналізувати його логіку, постійно задаючись наступними питаннями: а) Які операції повинні бути закінчені перш, ніж ця операція може початися? б) Які операції можуть починатися одночасно з даної? в) Які операції залежать від звершення цієї операції?
На кожній стрілці следут передбачити горизонтальну ділянку, на якому зазначаються опис і длтельность операції. Опис слід поміщати над стрілкою, а тривалість-під неї. Стрілки йдуть малювати зліва направо. Нумерувати вузли слід тільки після того, як побудова діограмми закінчено.
З метою ясності слід уникати перетину, наскільки це можливо, навіть якщо заради цього доведеться змінити структуру графіка.
МОМЕНТИ ПОДІЙ.
Подією вважається момент часу, коли виконані всі попередні операції і можуть бути розпочаті всі безпосередньо следуюшіе операції. У методі СPM з кожною подією асоціюються два моменти часу: ранній момент події і пізній момент події.
a) Ранній момент події визначається як найбільш ранній час, коли можуть бути розпочаті операції, які виходять з відповідного вузла. Обчислювальний процес, який використовується для визначення ранніх моментів подій мережного графіка, називається прямим проходом. пріпрямом проході обчислення починаються з правого вузла і продовжуються послідовно зліва направо до тих пір, поки не будуть визначені ранні моменти для кожної події мережного графіка Для початкового вузла ранній момент події вважається рівним нулю. ранній момент для подальшого події визначається додаванням тривалості попередньої операції до раннього моменту попереднього події. Якщо у вузол входять кілька операцій, то його раннім моментом події вважається найбільше з усіх ранніх часів закінчення операцій.
б) Пізній момент події для даного вузла визначається як найбільше з усіх пізніших часів закінчення операцій, що входять у цей вузол. Обчислювальний процес для визначення позлніх моментів подій називається зворотним підходів. При зворотному проході обчислення починаються з останнього вузла і продовжуються послідовно для кожної події мережного графіка аж до початкового. Пізній момент останньої події вважається рівним раннього моменту цієї події, знайденому при прямому проході. Очевидно, що немає ніякого резону в затягуванні проекту на час більше, ніж фактично потрібно для його виконання. Пізній момент попереднього події перебуває вирахуванням тривалості прешествующей операції з пізнього моменту подальшого події. Якщо з вузла виходить кілька операцій, то перед визначенням пізнього моменту відповідного (в цьому вузлі) слід розглянути пізні начальнче моменти подій для кожної операції, яка з цього вузла. Ясно, що в якості пізнього моменту події потрібно взяти пізніший момент початку тієї операції, яка повинна початися першої за часом.
Початок і закінчення ОПЕРАЦІЙ.У методі CPM моменти початку і закінчення операцій розраховуються за допомогою моментів подій і зазвичай табулюючу, а представляються на мережевому графіку. Раннім початком будь-якої операції називається ранній момент попереднього їй події. Пізно закінченням будь-якої операції називається пізній момент наступного за нею події. Пізно початком початком операції називається її пізніше закінчення за вирахуванням тривалості операції. Рано закінченням операції називається її ранній початок + тривалість операції. Пізніше початок операції завжди не менше пізнього моменту події попереднього вузла. Раннє закінчення операції всегла не більше ранього моменту подій подальшого вузла. Якщо є мережевий графік з розрахованими ранніми і пізніми моментами подій, то для розрахунку і табулювання моментів початку і закінчення операцій можна використовувати наступну процедуру з 6 кроків: 1. Впорядкує нію номери i, а потім для кожного i порядок їх за зростанням номера j). 2. Занести назву кожної операції в колонці 2, а їх тривалості у стовпець 3 3. Занести моменти раннього початку для кожної операції у стовпці 4. Ними є ранні моменти подій, відповідних i версій сайту операцій. 4. Визначити моменти раннього закінчення для кожної операції додаванням її тривалості до моменту раннього початку та помістити дані в стовпці 5. 5. Занести моменти пізнього окнчанія для кожної операції у стовпці 7. Ними є пізні моменти подій, соответствуюшей j версій сайту операцій. 6. Визначити момент пізнього початку для кожної операції вирахуванням її тривалості з моменту пізнього закінчення і помістити дані в стовпці 6.
РЕЗЕРВ: ПОЧАТКОВИЙ І КІНЦЕВИЙ.Кожна операція проекту повинна бути завершена в межах від моменту раннього початку до моменту пізнього закінчення. Якщо всі операції закінчуються в цих межах, то проект буде закінчено вчасно. Коли проміжок часу між цими двома межами перевищує тривалість операцій, тоді є вільний час, або до початку, або після закінчення операції. Це вільний час називають резервом. Проміжок часу між пізнім закінченням операції і її раннім початком називається початковим резервом, а проміжок часу між пізнім закінченням операції і її раннім закінченням називається кінцевим резервом, тобто:
ПОЧАТКОВИЙ РЕЗЕРВ = ПІЗНЄ ПОЧАТОК-РАННЄ ПОЧАТОК
КІНЦЕВИЙ РЕЗЕРВ = ПІЗНЄ ЗАКІНЧЕННЯ-РАННЄ ЗАКІНЧЕННЯ
Початковий резерв часу для операції дорівнює кінцевому.
РЕЗЕРВ: ПОВНИЙ.
Найбільш значущим з ВСІХ РЕЗЕРВІВ Є ПОВНИЙ РЕЗЕРВ.
Він вказує кількість часу, на яке може бути збільшена тривалість операції без загрози зриву планового терміну завершення поектов. Тому слід відрізняти затримку, що вселяє побоювання, від затримки, що не представляє загрози для терміну завершення проекту. Повний резерв визначається як момент пізнього закінчення операції-момент раннього початку-тривалість операції.
ВІЛЬНИЙ І НЕЗАЛЕЖНИЙ РЕЗЕРВ.Вільний резерв FF визначається, як ранній момент Еj подальшого події мінус ранній момент Eiпредшествующего події мінус тривалість операції D визначається цими подіями:
FF = Ej-Ei-D
Вільний резерв використовується в основному для виявлення операцій, виконання яких може затримуватися без шкоди для повного резерву подальших операцій.
Незалежний резерв IF визначається зазвичай як ранній момент подальшого події мінус тривалість операції D, обумовленою цими подіями:
IF = Ej-Li-D
Heзавісімий резерв дозволяє виявити операції, затягування яких не впливає на повний резерв ні попередніх, ні подальших операцій. Повний резерв (вільний і незалежний) підраховуються і табулюючу з використанням моментовначала і закінчення операцій. Якщо повний резерв дорівнює нулю, то нульовими є також вільний і незалежний резерви. Тому, коли підрахунок призводить до нульового повного резерву і одночасно ненульовому іншому резерву, то це свідчить про помилку в обчисленнях.
АНАЛІЗ КРИТИЧНОГО ШЛЯХУ.Послідовність операцій, що вимагає найбільшого часу для її завершення визначає найменший час за який може бути виконаний проект. той час називається тривалістю виконання проекту. Зазначена послідовність операцій, що визначає тривалість проекту є дуже важливою і називається критичним шляхом. Критичний шлях завжди починається з самого першого події мережного графіка й проходить через весь графік, закінчуючись останньою подією. Кожна операція критичного шляху являетсякрітіческой операцією. Для аналізу мережевого графіка важливо визначити всі критичні операції. Критичні операція повинна одночасно задовольняти наступним трьом критеріям: 1) Ранній і пізній моменти подій для вузла i повинні бути рівними:
Ei = Lj 2) Ранній і пізній моменти подій j рівні теж:
Ei = Lj 3) Тривалість операції повинна дорівнювати різниці між пізнім моментом події j і раннім моментом події i:
Lj-Ei-D = 0
Tретье умова означає, що критична операція не повинна мати резерву. Тому повний резерв виявляється корисним інструментом для виявлення критичної операції. Часто на мережевому графіку існує декілька критичних шляхів. Іноді короткі ланцюги, що містять критичні операції можуть відходити від основного критичного шляху і знову повертатися до нього. Критичні операції повинні бути завершені вчасно, інакше терміни виконання проекту будуть зірвані. Некритичними операціями називаються лише ті, у яких достатній розмір резерву. Операції з великим резервом є субкритичних, взагалі, чим більше резерв операції, тим менше вона критична по відношенню з іншими. Критичні операції повинні контролюватися керівником проекту в першу чергу, тому що затримка кожної з них збільшує тривалість проекту. Оскільки критичні операції складають у проекті, як правило, 10-15%, зосередження уваги керівництва на них цілком реально перш за все за рахунок менш важливих операцій. Важливим достоїнством методу є возожность концентрувати увагу керівництва на найбільш відповідальних операціях, що абсолютно необхідно у великих, складних проектах.
Мережеве планування в умовах невизначеностіПри визначенні часових параметрів мережного графіка до цих пір
передбачалося що час виконання кожної роботи точно відомо. Таке припущення в дійсності виконується рідко: адже мережеве планування зазвичай застосовується для розробки складних ***** часто не мали в минулому ніяких аналогів. Найчастіше тривалість роботи
по мережевому графіку заздалегідь не відома і може приймати лише однією з низки своїх можливих значень. Іншими словомі, тривалість роботи є випадковою веелічіной, що характеризується своїм законом розподілу, а значить, своїми числовими характеристиками-очікуваної тривалістю і мірою розкиду.
Мережеві графіки можуть мати детерміновану або стохастичну структуру. Причому слід чітко розрізняти відмінності між детерменірованнимі та стохастичними структурами. а) Якщо всі операції мережевого графіка ії їх взаємозв'язок чітко визначені,
то така структура графіка називається детерменнірованой. б) Стохастична структура означає, що всі операції включаються в мережу з деякою ймовірністю. Те еесть в деяких у деяких проектах на окремих етапах той чи інший комплекс робіт залежить від невідомого заздалегідь результату та його фактичне виконання може бути передбачене лише з деякою ймовірністю. Так наприклад, в науково-дослідних і дослідно-крнструкторскіх розробках заздалегідь не відомі не тільки тривалість окремих операцій, але і їх перелік, а також структура мережі.
Розрахунок параметрів і аналіз графіків стохастичної структури пов'язаний зі значними труднощами, тому на практиці звичайно застосовуються графіки з детермінованою структурою і з випадковими тимчасовими оцінками операцій. Такі мережі отримали назву стохастичних або імовірнісних мереж.
При дослідженні імовірнісних мереж можуть зустрітися два випадки: 1) Операції не є новими, і ми наближено знаємо для кожної ізніх функцію розподілу тривалості виконання. 2) Операції є новими, маловивченими, і для них функції розподілу тривалостей невідомі.
У першому випадку очікувана тривалість і міра розкиду визначаються за відомою функції розподілу.
У другому випадку застосовується метод усереднення. вихідними даними для методу усереднення є імовірнісні оцінки тривалості кожної операції: а-мінімальна тривалість (оптимістична оцінка) операції, б-максимальна продолжіітельность (пссімістіческая оцінка) операції, m-найбільш ймовірна тривалість операції. Ці оцінки часу задаються відповідальним виконавцем або групою експертів.
Статистичний аналіз, проведений емпірико-експеріментадьним шляхом розробниками математичного апарату мережевого планування в умовах невизначеності встановити що: a +4 m + b Очікувана тривалість ij операції-Fij = 6
ba Міра розкиду ***= 6
Після визначення очікуваних тривалостей тривалостей операцій по даній формулі, проводиться розрахунок часових параметрів мережі, як і в детермінованому випадку. Очікувану тривалість критичного шляху розглядають як суму випадкових величин, т. e. робіт вирішальних на *****
(Fкр) = Е F (ij) кр.
(I, j) кр Міру розкиду тривалості критичного шляху вважають рівною сумі шляхи:
d (Ткр) = Е dij (Fij)
(I, j) кр Розрахунок часових параметрів мережі за очікуваними длительностям тривалостей операцій не дозволяє строго визначити термін завершення комплексу операцій. Фактичне відхилення випадкових величин Tij від їх середніх значень Tij може бути як у большиию так і в меншу сторону. Тому фактична тривалість виконання комплексу операцій може бути більше чи менше Ткр (очікуваної тривалості критичного шляху) У зв'язку з цим великий інтерес представляє оцінка ймовірності завер шення комплексу операцій до певного терміну, яка залежить від міри розкиду тривалості критичного шляху. При одних значеннях величин Tij можт бути один критичний шлях, при інших-другий.
Якщо операція виконується при досить сприятливих умовах то вона буде завершена в порівняно короткі терміни. Так визначається оптимістична оцінка діяльності. Вірогідність її фактичної реалізації становить близько 0. 01. Якщо ж операція виконується при вкрай несприятливих умовах, то виконання її затягнеться. З цих міркувань визначається песимістична оцінка тривалості операцій, імовірність її реалізації складає також приблизно 0. 2001 У переважній більшості випадків тривалість операції буде перебувати в інтервалі, обмеженому попередніми двома оцінками. Оцінка ж тривалості найбільш близька до дійсної називають найбільш вірогідним.
Розглянемо наступний приклад операцій:
Оптимістична оцінка тривалості: a = 4
Найбільш ймовірна тривалість: m = 6
Песимістична оцінка тривалості: b = 7 Три оцінки відображають ступінь правдоподібності часу виконання завдання; одна оцінка достатня лише для випадку повної впевненості. У свою чергу, правдо подібність може бути виражене у статистичних термінах, тобто у вигляді кривої щільності розподілу, яка описує частоту реалізації різних тривалостей операції, виконуваної велике число аз.
Ймовірність завершення операції у розглянутому прикладі за 4 (або за 7) робочих днів складає, як зазначалося вище, 0. 01. Найбільш ймовірно, що операція закінчиться за 6 днів. Передбачається, що якщо операція виконується велике число разів, причому ведеться реєстрація всіх даних, то графік частот тривалості дасть асиметричну криву, яка називається функцією. Наведені числові оцінки тривалості виконання операцій і ймовірність реалізації представлені b-функцією на схемі 1. Вертикальні лінії над крапками 4. 0 6. 0 7. 0 позначають частоту реалізації операції за те число робочих днів, яке вимірюється по горизонтальній лінії.
Внаслідок того, що вертикальна лінія в точці 6. 0 не ділить площу під кривою на дві рівні частини, ймовірність завершення цієї операції за 6 (або менше) робочих днів не дорівнює 0. 5. Для визначення очікуваної тривалості операції цього типу використовуються средневзвешанние значення. Очікувана тривалість, або математичне очікування, як ми пам'ятаємо, обчислюється за формулою;
а +4 m + b = 6
Тобто в нашому прикладі дорівнює
4 +4 * 6 +7 = 5. 8
Особа, оцінити найбільш ймовірну тривалість операції на 6 днів, було налагоджено песимістично, оскільки 5. 8 менше 6.
На схемі 2 ділить площу під-функцією на 2 рівні частини.
Таким чином, ймовірність закінчення операції не більш ніж за 5. 8 робочого дня дорівнює 0. 5.
Інша інтерпретація цього обставини така; є тривалість, для якої існують рівні шанси на закінчення операції або раніше, або пізніше.
Розглянемо інший випадок, де оцінки такі, а = 4 m = 5 b = 18
(4 +4 * 5 +18) / 6 = 7. 0
Це показано на малюнку 3. Як і на попередньому малюнку, тут ділить площу під b-функцією на дві рівні частини. Т. о. , Ймовірність закінчення операції за очікуваний час 7. 0 робочих днів дорівнює 0. 5. У цьому випадку прогноз був оптимістичним, оскільки більше оцінки найбільш вірогідною тривалості, що дорівнює 5.
МІРА РозкидРозглянемо дві операції А1 і А2 з наступними длительностями;
А1 А2
а = 4 а = 3
m = 6 m = 5
b = 8 b = 13
= (4 +24 +8) / 6 = 6 = (3 +20 +13) / 6 = 6
Для кожної операції = 6, хоча оптимістична, найбільш вірогідна, і песимістична оцінки дуже різняться. Міра розкиду зазначених оцінок називається дисперсією D.
D () = ((ba) / 6) ^ 2
D (А1) = ((8-4) / 6) ^ 2 = 0. 444
D (А2) = ((13-3) / 6) = 2. 777
По суті міра розкиду характеризує невизначеність, пов'язану з процесом оцінювання тривалості операції. Якщо міра розкиду велика, тобто оптим істіческая і песимістична оцінки сильно відрізняються один від одного, то це означає більшу невизначеність щодо часу завершення оаераціі. Відповідно мала міра розкиду вказує на порівняльну визначеність часу завершення операції.
****, Тривалість виконання проекту і резерви можуть бути розраховані за допомогою прямого і зворотного проходу.
Оскільки ймовірність виконання кожної операції за очікуваний час t (ij) = 0. 5. , То ймовірність закінчення всього проекту за час Ts = сумі t (ij), також дорівнює 0. 5. Але тривалість виконання проекту вже не описується B-функцією, як це має місце для окремих операцій проекту. Припускаючи, що проект складається з великої кількості операцій, отримаємо результуюче розподіл його тривалості, близький до нормального, тому можна прийняти, що очікувана тривалість виконання проекту має нормальний розподіл.
Може оказати, що очікувана тривалість виконання проекту Ts неприемлима для керівництва, замість неї вибирається інший час Tc, менше, ніж Ts. Tc <Ts.
Для визначення ймовірності реалізації проекту за Tc потрібно розглянути стандартне відхилення кривої нормального розподілу, яке обчислюється за формулою:
g (t) = корінь квадратний з суми заходів розкиду операцій.
Розглянемо приклад складається з чотирьох операцій:
ABCD 1-2-3-4-5
a = 4 a = 3 a = 2 a = 4
m = 6 m = 8 m = 4 m = 5
b = 8 b = 9 b = 7 b = 6
******= 6 +7. 33 + 4. 17 + 5 = 22. 5
Величина стандартних відхилень тривалості виконання проекту дорівнює
g (t )=***********= 1. 5
на малюнку зображено щільність розподілу ймовірностей тривалості виконання проекту для нашого прикладу.
Тут стандартне відхилення ілюструє ступінь невизначеності проекту виконання за час Tc. У межах одного стандартного відхилення з обох сторін від Ts тривалість виконання проекту може змінитися від 21 до 24 одиниць часу (22. 5 + -1. 5) ймовірність цього дорівнює 0. 68. (Площа під кривою в межах +-g)
Щоб знайти ймовірність завершення проекту до певного моменту часу необхідно обчислити величину Z за формулою планована тривалість - очікувана тривалість
Z = стандартне відхилення а потім використовувати цю величину для визначення ймовірності по таблиці стандартного нормального розподілу, де для кожної величини Z відповідає певна величина ймовірності. У нашому прикладі визначимо ймовірність виконання проекту не пізніше, ніж за 21. 5 днів.
21. 5 - 22. 5
Z =- = - 0. 67.
1. 5 в таблиці для даного Z ймовірність виконання складе 0. 25.
І субкритичних, тривалістю трохи менше.
Але якщо сума заходів розкиду для цього субкритичних шляху більше, ніж для критичного, то на практиці такий субкритичних шлях з великою ймовірністю може стати критичним.
Так, маю критичний шлях очікуваної тривалістю = 80 од. часу і стандартному відхиленні = 2, ймовірність закінчення проектаі 86 од. часу дорівнює 0. 9987.
Якщо субкритичних шлях має тривалість = 78, то стандартне від лень = 5, то з тією ж імовірністю 0. 9987 робота на цьому шляху буде закінчена між 1963 і 93. Звідси випливає, що перетворення субкритичних шляху в критичний досить ймовірно.