Лінійне програмування - широко поширений метод оптимізації використовування обмежених ресурсів
Як видно з назви, залежність між даними чинниками повинна бути лінійною. В операційному менеджменті лінійне програмування застосовується в першу чергу для оптимізації номенклатури продукції, що випускається, за умови обмежених потужностей.
Необхідно зазначити, що якщо обійти ці обмеження не вдається і можна залишити частину попиту незадоволеною, необхідно знайти таку комбінацію випуску, при якій певний параметр досягав би максимума. Метод полягає в побудові системи рівнянь, що є обмеженнями, і знаходження такого її рішення, що приносило б максимальний прибуток. Якщо в системі беруть участь всього дві змінні (тобто ресурси розподіляються між двома продуктами), рішення можна знайти графічно. Коли змінних більше, звичайно вдаються до допомоги спеціальних комп'ютерних програм.
Слід зазначите, що методи лінійного програмування можуть застосовуватись, якщо поставлена тільки одна ціль: максимізувати (наприклад, прибуток) чи мінімізувати (наприклад, витрати). Коли цілей декілька, використовується цільове програмування. Якщо ж задача ефективніше всього вирішується поетапно чи по часовим інтервалам, аналітику слід скористатися методом динамічного програмування. В ще більш складних задачах при вирішенні можуть стати потрібними інші варіанти даного методу, наприклад нелінійне, чи квадратичне програмування.
Важливо підкреслити, що в практиці операційного менеджменту до типового застосування методів лінійного програмування належать симплексний та транспортний методи. Симплексний метод (Simplex Method) - це алгебраїчна процедура, в результаті якої аналітик послідовно наближається до оптимального рішення.Теоретично даним методом можна вирішувати задачі, які включають будь-яку кількість змінних і обмежень, але якщо в них, наприклад, більше чотирьох змінних чи обмежень, то обчислення краще проводити на комп'ютері. Транспортний метод (Transportation Method) представляє собою спрощений специфічний варіант симплексного методу.Слід зазначити, що він отримав таку назву, тому що широко застосовується для вирішення задач, пов'язаних з транспортуванням продукції з різних джерел в декілька пунктів призначення.
|
|
|
Особливосты нелыныйного програмування
У більшості випадків нелінійність моделі обумовлюється, як правило, структурними співвідношеннями економічного процесу або непропорційністю зміни витрат, випуску продукції, показників якості.У загальній постановці задачу нелінійного програмування (НЛП) записують так:
(max)z(x1, x2, …, xn), де F1(x), …, Fn(x),z(x), x=(x1, x2, …,xn) – довільні функції. Уконкретних задачах частина обмежень (або всі) можуть бути нерівностями.Крім того, на невідомі можуть накладатися умови невід'ємності і т.п.Однією з основних особливостей задач НЛП є можливість різними способами задавати цільову функцію. Якщо в лінійному випадку вона була строго монотонною і досягала свого оптимального значення лише у вершині многокутника розв'язку; то тут картина зовсім інша. Наприклад! Навіть графік функції, однієї змінної, свідчить про те, що вона вже має багато локальних максимумів. Друга особливість задач НЛП випливає із порушення властивості опуклості многокутника розв'язків задач НЛП.
|
|
|
6.Побудова опорного плану транспортної задачі
Завдяки вище згаданим особливостям будови математичної моделі транспортної задачі існують кілька простих методів побудови опорного плану. Розглянемо методи північно-західного кута, мінімальної вартості, подвійної переваги та метод апроксимації Фогеля. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції відповідають рядкам, а споживачі — стовпчикам.
Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.
|
|
|
Очевидно, якщо за побудови опорного плану враховувати вартості перевезень, то сумарна вартість всіх постачань може бути зменшена, і отриманий опорний план буде ближчим до оптимального.
Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами.
Метод подвійної переваги. Якщо розмірність задачі досить велика, то перебір за методом мінімальної вартості ускладнюється. В такому разі спростити пошук клітин з найменшими вартостями можна, застосовуючи метод подвійної переваги.
Згідно з процедурою цього методу перед початком заповнення таблиці необхідно позначити будь-якими символами клітинки, які містять найменшу вартість у рядках, а потім — у стовпчиках. Таблицю починають заповнювати з клітинок, позначених двічі (які містять вартості, що є мінімальними і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (що містять мінімальні вартості або в рядку, або в стовпчику), а вже потім — за методом мінімальної вартості. Застосування для побудови опорного плану даного методу уможливлює отримання найменшого у зіставленні з розглянутими вище значення цільової функції. Отже, такий план є найближчим до оптимального.
|
|
|
Метод апроксимації Фогеля. За цим методом на кожному кроці визначають різницю між двома найменшими вартостями в кожному рядку і стовпчику транспортної таблиці. Ці різниці записують у спеціально відведених місцях таблиці — знизу та справа у кілька рядків та стовпчиків, що відповідають крокам заповнення таблиці. З-поміж усіх різниць вибирають найбільшу і у відповідному рядку чи стовпчику заповнюють клітинку з найменшою вартістю. Якщо ж однакових найбільших різниць кілька, то вибирають будь-який відповідний рядок або стовпчик. Коли залишається незаповненим лише один рядок або стовпчик, то обчислення різниць припиняють, а таблицю продовжують заповнювати за методом мінімальної вартості.
Даний метод побудови опорного плану враховує не лише маршрути з мінімальними витратами перевезень продукції, але й співвідношення витрат у рядку чи стовпчику, тобто розраховується наскільки, може збільшитися вартість постачання на наступних кроках процедури, якщо не здійснити на поточному кроці постачання в клітину з мінімальною вартістю.
Метод апроксимації Фогеля дає змогу особливо для задач великих розмірностей скласти найкращий опорний план.
7. Методи направленого пошуку
Поряд із названими загальними, універсальними прийомами аналізу в ході системних досліджень використовують і евристичні прийоми, які ґрунтуються на інтуїції та досвіді дослідників. Усі евристичні методи поділяються на дві великі групи - методи ненаправленого пошуку ("мозкового штурму", "експертних оцінок", "колективного блокнота", "контрольних питань", "асоціацій та аналогій", ділові ігри та ситуації, кібернетичні наради) та методи направленого пошуку (морфологічний метод, алгоритм розв'язання винахідницьких задач АРВЗ).
МЕТОД МОРФОЛОГІЧНИЙ
рос. метод морфологический
метод, розроблений відомим американським астрономом Ф. Цвінкі у 1942 р. Під морфологією розуміють структуру і форми об'єкта технічної творчості. Основні принципи методу: всебічний аналіз явища; проведення дослідження з самого початку і продовження його навіть тоді, коли всі вважають, що немає сенсу просуватися вперед; нічого не вважати неможливим доти, доки це не буде твердо доведено і всебічно аргументовано. Суть методу полягає в побудові таблиць, які повинні охопити всі мислимі варіанти. М.м. був успішно використаний Ф. Цвінкі для розв'язання технічних задач в американських ракетних розробках.
Алгоритм розв’язання винахідницьких задач(АРВЗ)
Творчий процес, пов'язаний із створенням нової техніки і технології, дуже тісно пов'язаний з винахідництвом, яке є найдавнішим заняттям людини.
Власне, з винаходу перших знарядь праці і почався процес олюднення наших древніх предків.
З століття в століття винахідницькі завдання ставали все більш складними, а методи їх вирішення майже не удосконалювалися, як правило, винахідники йшли до мети шляхом В«проб і помилок В».
Фахівці говорять, що було б дуже зручним, якщо б винаходи були результатом логічного та упорядкованого процесу. На жаль, це не так. Винаходи є продуктом того, що психологи називають В«інтуїцієюВ» - несподіваною спалахом натхнення, механізм якого лежить в глибинах людського розуму.
Раніше процес винахідництва представляв наступну схему процесу:
Перший акт - акт інтуїції і бажання. Походження задуму (постановка завдання).
Другий акт - акт знання і міркування. Вироблення схеми або плану (рішення задачі).
Третій акт - акт вміння. Конструктивне виконання (втілення задачі).
Разом з тим ця схема настільки неконкретна, що практично нічого не дає винахідникові. Аж до недавнього часу.
В даний час процес винахідницької творчості враховує складність завдань по створенню якого-небудь технічного об'єкта. Складність завдань може мати п'ять рівнів, причому на кожному рівні може бути 6 стадій (А, Б, В, Г, Д, Е).
В цілому процес винахідницької творчості складається з наступних стадій:
- вибір завдання;
- вибір пошукової концепції;
- збір інформації;
- пошук ідеї рішення;
- розвиток ідеї в конструкцію;
- впровадження.
8. Алгоритм симплекс-методу для задачі на максимум
1). система обмежень приводиться до канонічного вигляду;
2). система обмежень і цільова функція записується у вигляді таблиці;
3). записується вихідний розв’язок, в якому вільні змінні =0, а базові змінні = вільним членам обмежень, а значення цільової функції=0;
4). Проглядається стовбець вільних членів, якщо всі значення вільних членів більше або = 0, то відбувається перехід до пункту 7; якщо є вільні члени менше 0 то вибирається будь-який з них і відповідний рядок є вирішальним;
5). Проглядаються коефіцієнти А вирішального рядка, якщо коефіцієнти додатні то задача немає розв’язку. Якщо серед коефіцієнтів А вирішального рядка є від’ємний, то вибирається будь-який з них і даний стовбець буде вирішальним;
6). Виконується перерахунок всіх коефіцієнтів таблиці,в тому числі і значення цільової функції;
7). Проглядаються коефіцієнти Z(коефіцієнти цільової функції), якщо вони всі більше або =0, то поточний розв’язок є оптимальний. Обчислювальна процедура припиняється .
8). Якщо коефіцієнти Z менше , то вибирається будь-який з них і відповідний стовбець буде вирішальним. Обчислюється відношення вільних членів В до додатніх коефіцієнтів А вирішального стовпця. Рядок, що відповідає мінімальному з цих відношень буде вирішальним.
9.). виконується перерахунок всіх коефіцієнтів таблиці і здійснюється перехід до пункту 6.
Дата добавления: 2018-04-05; просмотров: 639; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!