2. Основи оптимального управління
|
|
Скачати 0.71 Mb.
|
|
3.6. Транспортна задача Транспортна задача – одна з розповсюджених задач лінійного програмування. Її мета – розробка найбільш раціональних шляхів і способів транспортування товарів, усунення найбільш віддалених, зустрічних, повторних перевезень. Все це скорочує час просування товарів, зменшує витрати підприємств, пов’язаних із здійсненням процесів забезпечення сировиною, матеріалами, паливом, обладнанням тощо. У загальному вигляді задачу можна представити наступним чином: у т пунктах виробництва  маємо однорідний вантаж відповідно у кількості  . Цей вантаж необхідно доставити у п пунктів призначення  відповідно у кількості  . Вартість перевезення одиниці вантажу (тариф) із пункту  до пункту  дорівнює  .Необхідно скласти план перевезень, яких дозволяє перевезти весь вантаж при мінімальних транспортних витратах. У залежності від співвідношення між сумарними запасами вантажу і сумарними потребами у них, транспортні задачі можуть бути закритими і відкритими. Якщо  , тоді транспортна задача називається закритою.Якщо  , тоді транспортна задача називається відкритою.Позначимо через  кількість вантажу, який перевозять з пункту до пункту  .Відкрита транспортна задача Умову даної задачі запишемо у вигляді розподільчої таблиці. Математична модель закритої транспортної задачі має наступний вид  при обмеженнях  
Оптимальним розв’язком задачі є матриця  , яка задовольняє системі обмежень і дозволяє мінімізувати цільову функцію.Транспортна задача, яка є задачею лінійного програмування, може бути розв’язана симплексним методом, але наявність великої кількості змінних і обмежень робить обчислення громіздкими. Тому для розв’язання транспортних задач розроблено спеціальний метод, який має ті ж самі етапи, що і симплексний метод, а саме:
Знаходження вихідного опорного розв’язку У розподільчій таблиці клітини, у яких помістимо вантажі, називаються зайнятими і їм відповідають базисні змінні опорного розв’язку. Інші клітини називаються незайнятими або пустими і їм відповідають вільні клітини. У верхньому правому куті кожної клітини будемо записувати тарифи. Існують декілька способів знаходження вихідного опорного розв’язку. Розглянемо метод мінімального тарифу. Згідно з цим методом, вантажі розподіляються у першу чергу в ті клітини, в яких знаходиться мінімальний тариф перевезень . У подальшому поставки розподіляються у незайнятих клітинах з найменшими тарифами з урахуванням запасів, що залишилися у постачальників, і задоволення попиту споживачів. Процес розподілу продовжують до тих пір, доки всі вантажі від постачальників не будуть вивезеними, а споживачі не будуть задоволеними. При розподілі вантажів може бути, що кількість зайнятих клітин менше, ніж  . У цьому випадку недостатня їх кількість заповнюється клітинами з нульовими поставками, такі клітини називаються умовно зайнятими.Нульові поставки розміщують у незайняті клітини з урахуванням найменшого тарифу таким чином, щоб у кожному рядку і стовпці було не менше, ніж по одній зайнятій клітині. Покращення отриманого опорного плану методом потенціалів Після завершення першого етапу розв’язку задачі знайдені невідомі можна розбити на дві групи – базисні (зайняті) і вільні. Представимо цільову функцію наступним чином  ,де  - вільні змінні;  - знайдений опорний план, а значення  отримаємо за допомогою методів потенціалів.Поставимо у відповідність кожному з пунктів відправлення вантажів деяку величину  - „потенціал” пункту . Аналогічно кожному пункту призначення величину  - „потенціалу” пункту .Для кожного базисного невідомого  складаємо рівняння  , де  - вартість перевезення з пункту  до пункту  . Розв’язуємо систему рівнянь і знаходимо всі потенціали та .Тепер для кожної вільної змінної обчислюємо суму  - посередні вартості та заносимо до таблиці.Наступним кроком є визначення різниць  між справжніми вартостями перевезень та посередніми вартостями, які відповідають вільним клітинам.Якщо всі величини невід’ємні, то початковий знайдений розв’язок є оптимальним. Якщо  , тоді необхідно перейти до іншого базису.Альтернативний оптимум у транспортних задачах Ознакою наявності альтернативного оптимуму у транспортних задачах є рівність нулю хоча б однієї з оцінок вільних змінних у оптимальному розв’язку  . Зробивши перерозподіл вантажів відносно клітини, що має  , одержимо новий оптимальний розв’язок  , при цьому значення цільової функції (транспортних витрат) не зміниться.Якщо одна різниця дорівнює нулю, тоді оптимальний розв’язок знаходиться за формулою  , де  .Виродженість у транспортних задачах При розв’язанні транспортної задачі може бути, що кількість зайнятих клітин менша за . У цьому випадку транспортна задача може мати вироджений розв’язок. Для можливого його виключення, доцільно поміняти місцями постачальників і споживачів або ввести у вільну клітину з найменшим тарифом нульову поставку. Нуль вміщують у таку клітину, щоб у кожному рядку і кожному стовпці було не менше однієї зайнятої клітини.Відкрита транспортна задача При відкритій транспортній задачі сума запасів не співпадає з сумою потреб, тобто .При цьому: а). Якщо  , тоді обсяг запасів перевищує обсяг споживання, всі споживачі будуть задоволені повністю і частина запасів залишається не вивезеною. Для розв’язання такої задачі вводять фіктивного ( -го) споживача, потреби якого  .Модель такої задачі набуває вигляду при обмеженнях   б). Якщо  , тоді обсяги споживання перевищують обсяги запасів і частина споживачів залишається незадоволеною. Для розв’язання такої задачі вводять фіктивного ( -го) постачальника, обсяги поставок якого  .Модель такої задачі набуває вигляду при обмеженнях  При введенні фіктивного постачальника або споживача, задача стає закритою і розв’язується за раніше розглянутим алгоритмом, причому тарифи, що відповідають фіктивному постачальнику або споживачу більше або дорівнюють найбільшому з усіх тарифів. У цільовій функції фіктивний постачальник або споживач не враховується. 4. ЦІЛОЧИСЛОВЕ ПРОГРАМУВАННЯ 4.1. Загальна постановка задачі Деякі задачі лінійного програмування вимагають цілочислового розв’язку. До них відносяться задачі з виробництва і розподілу не діленої продукції (випуск верстатів, телевізорів, автомобілів тощо). У загальному вигляді математична модель задачі цілочислового програмування має вигляд  з обмеженнями  Оптимальний розв’язок задачі, яку знайдено симплексним методом, часто не є цілочисловим. Його можна округлити до найближчого цілого числа. Але таке округлення може дати розв’язок, який не є найкращим серед цілочислових розв’язків або привести до розв’язку, що не задовольняє системі обмежень. Тому для знаходження цілочислових розв’язків необхідний особливий алгоритм. Такий алгоритм запропонував Гоморі. 4.2. Метод Гоморі Метод Гоморі полягає у наступному. Симплексним методом знаходять оптимальний розв’язок задачі. Якщо розв’язок цілочисловий, тоді задача розв’язана. Якщо ж він вміщує хоча б одну дробову координату, тоді закладають додаткове обмеження за цілочисельністю і обчислення продовжують до одержання нового рішення. Якщо ж і воно є не цілочисловим, тоді знову накладають нове обмеження за цілочисельністю. Обчислення продовжують до тих пір, доки не буде одержаний цілочисловий розв’язок або показано, що задача не має цілочислового розв’язку. Нехай одержано оптимальний розв’язок  , який не э цілочисловим, тоді останній крок можна представити у вигляді симплексної таблиці, де  - ранг системи обмежень;  - коефіцієнт симплексної таблиці  -го рядка  -го стовпця;  - вільний член -го рядка.
Нехай і хоча б одне з  ( ) – дробові числа.Позначимо через  і  цілі частини чисел і .Цілою частиною числа називається найбільше ціле число, яке не перевищує .Позначимо через  і  цілі частини чисел і .Дробовою частиною чисел і називається різниця  та  .Приклад:   Якщо всі і хоча б одне значення дробові, то з урахуванням введених позначень цілих і дробових чисел, додаткове обмеження за цілочисельністю прийме вигляд Зауваження: 1. Якщо (вільний член) – дробове число, а всі коефіцієнти - цілі числа, тоді задача лінійного програмування не має цілочислового розв’язку.2. Обмеження цілочисельності може бути накладене не на всі змінні, а лише на їх частину. У цьому випадку задача є частково цілочисловою. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Схожі:
| Календарно-тематичний план "Основи кадрового менеджменту" для професії... Теоретико-методологічні основи управління персоналом. Концепція управління людськими ресурсами |
ПЛАН-КОНСПЕКТ проведення заняття з психологічної підготовки з начальницьким... Тема 2 Формування оптимального рівня стану соціально-психологічного клімату в |
| 3. Управління та організаційна структура готельного комплексу Поняття... Організація як функція координації структурних підрозділів готельного комплексу. (для самостійного вивчення на основі повторення... |
Модуль Теоретичні основи стратегічного управління Семінарське заняття... Семінарське заняття №2 Концептуальні засади стратегічного управління підприємством |
| 1. Законодавчо-правові основи управління безпекою життєдіяльності Правова система формує передумови створення, функціонування, удосконалення системи управління безпекою життєдіяльності. Правова система... |
Урок із спецдисциплін операторів комп’ютерного набору Урок-конкурс «Найкращий оператор!» ... |
| ТЕОРЕТИЧНІ ОСНОВИ УПРАВЛІННЯ ДІЯЛЬНІСТЮ СПОРТИВНИХ ОРГАНІЗАЦІЙ Воронова В. А. Пути совершенствования управления физкультурным движением. М.: ФиС,1975 -95с |
Молдован В. В. Основи держави і права. Курс лекцій «Фінанси і кредит», 030509 «Облік і аудит», 030502 «Економічна кібернетика», 030505 «Управління персоналом та |
| РОЗДІЛ ПЕРШИЙ ЦИВІЛЬНИЙ ЗАХИСТ (ЦИВІЛЬНА ОБОРОНА) УКРАЇНИ ТА ОСНОВИ ЇЇ ВЕДЕННЯ Органи управління, аварійно-рятувальні підрозділи Оперативно-рятувальної служби цивільного захисту |
Міністерство освіти і науки України Сумський державний університет... РОЗДІЛ ТЕОРЕТИЧНІ ОСНОВИ УПРАВЛІННЯ ПОРТФЕЛЕМ ІННОВАЦІЙНИХ ПРОЕКТІВ ПІДПРИЄМСТВА |
При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
звернутися до адміністрації
bibl.com.ua