Знаете какво означава да оптимизирате система, за да получите възможно най-добрия резултат, ако сте студент по инженерство или инженер.
Оптимизирането на решение е ключът към успеха във всичко - от изграждането на мостове до създаването на софтуер.
Идеята за основно осъществимо решение идва в този момент.
Това е основна идея в линейното програмиране, която ви позволява да разберете кое от набор от възможни решения е най-доброто.
Но защо има толкова голямо значение? В тази статия ще говоря за основните осъществими решения и как те могат да бъдат използвани за решаване на инженерни проблеми в реалния свят.
Ще говоря за това как да ги намерите, от какво са направени и защо са важни.
Така че, независимо дали сте опитен инженер или студент, който току-що започва, елате с нас, докато се гмуркам в света на основните осъществими решения и ви показвам как да използвате силата на линейното програмиране.
Разбиране на основното осъществимо решение
Официална дефиниция:
Базово решение на линеен програмен модел, в който всички променливи са неотрицателни.
Основното изпълнимо решение (BFS) е ключова идея в линейното програмиране, която помага да се намерят най-добрите решения.
BFS е решение с възможно най-малкия брой ненулеви променливи.
Това е ъгъл на полиедъра на възможните решения.
С други думи, BFS е основно решение, което отговаря на неотрицателните ограничения и е в осъществимия регион или проблемна област.
Намиране на оптимално основно осъществимо решение
За да намерим най-добрия BFS, трябва да направим следното:
- Напишете програмата в стандартна форма за линейна последователност.
- Превърнете системата от неравенства в разширена матрица.
- Разберете кои променливи са основни и кои не.
- Разберете какви са основните променливи по отношение на другите променливи.
- Поставете тези изрази в целевата функция, за да получите функция само на променливите, които не са основни.
- Намерете неосновна променлива, която може да бъде увеличена, без да се нарушават никакви ограничения, и която ще направи целта функция по-добра.
Тази променлива вече е основна променлива, а една от другите основни променливи вече не е основна променлива.
Ако има оптимално решение, то трябва да е в един от краищата или върховете на областта, където са възможни решения.
Така че, ако LP има оптимално решение, то има оптимално решение в крайна точка на осъществимото множество.
Освен това винаги има оптимален BFS, ако има оптимално решение.
Използване на симплексния метод за намиране на оптимален BFS
Симплексният метод е алгоритъм за решаване на проблеми в линейното програмиране.
Той се премества от един BFS към „съседен“ BFS чрез използване на процедурата на завъртане.
В процедурата на завъртане не-базова променлива се избира да стане основна променлива и след това текущият BFS се използва за решаване на новите основни променливи.
Когато никоя неосновна променлива не може да бъде променена, за да направи целевата функция по-добра, алгоритъмът е готов.
Защо основните осъществими решения са от решаващо значение за решаването на сложни инженерни проблеми
Все още трудно за разбиране? Да променя малко гледната точка:
Кой изобщо се нуждае от прости, работещи отговори? Просто хвърлете всичко заедно и се надявайте на най-доброто.
В крайна сметка, кой има нужда от оптимизация, когато хаосът е много по-забавен? Добре дошли в света на неотрицателните променливи, където всичко е само предложение и провалът е почти сигурен.
Или е така?
Нека проучим защо привидно основната концепция за основни осъществими решения е всичко друго, но не и основна и защо те може да са ключът към решаването дори на най-сложните инженерни проблеми.
Добре, това беше просто шега, направена да изглежда като телевизионна реклама.
Сега да се върнем към обяснението.
Намиране на основно осъществимо решение
Основно изпълнимо решение (BFS) е решение на проблем с линейна оптимизация, което отговаря на всички ограничения и има най-малък брой ненулеви променливи.
Всеки BFS е ъгъл на полиедъра на възможните решения от геометрична гледна точка.
Ако има най-добро решение, трябва да има и най-добра първа стъпка.
В тази статия ще говорим за това как да намерим първоначално основно осъществимо решение, как да намерим всички основни осъществими решения и как да намерим основно осъществимо решение без променливи.
Намиране на първоначално основно осъществимо решение
Можем да използваме различни методи, в зависимост от това как е поставен проблемът, за да намерим първоначално основно решение, което работи за проблем с линейна оптимизация.
Един от начините е да добавите слаби променливи към ограниченията върху неравенствата и да зададете всички останали променливи на нула.
Променливите за отслабване стават основни променливи, а останалите са неосновни променливи.
Двуфазният симплексен метод е друг начин за решаване на проблема.
Този метод включва решаване на допълнителен проблем с линейно програмиране, за да се намери първоначално основно решение, което е осъществимо.
След като бъде намерено първоначално основно осъществимо решение, симплексният метод може да се използва за преминаване от едно основно осъществимо решение към следващото и след това към най-доброто решение.
Намиране на всички основни осъществими решения
Може да има повече от едно основно решение, което работи за линейна програма.
Можем да променим системата, като добавим променливи за отслабване и след това да използваме новата система, за да намерим всички основни възможни решения за линейна програма.
След това тези основни осъществими решения се използват за намиране на основните осъществими решения за първоначалния проблем.
Намиране на основно осъществимо решение без променливи
Трябва да използваме забавени променливи, за да се отървем от по-малко от ограниченията, за да можем да намерим основно решение, което работи без забавени променливи.
Променливата за отслабване е просто разликата между дясната страна на ограничението и лявата страна.
Например, за първото ограничение, ние дефинираме променлива x4 = 14 - 2x1 - x2 - x3. От гледна точка на тази нова променлива, първото ограничение е еквивалентно просто на x4 ≥ 0, което е ограничение за положителност за x4.
Когато добавим тези забавени променливи, получаваме линейна програма, която е същата като оригиналната, с изключение на това, че всички ограничения са или уравнения, или ограничения, които казват, че нещо е положително.
Наборът от основни променливи, които имат стойности, различни от нула в основното решение, се нарича базис.
Променливи, които имат стойност нула в основното решение, не са основни променливи.
За да намерим най-доброто решение, трябва да намерим вектор x, който отговаря на всички правила и получава най-голямата или най-малката стойност за целта.
Но намирането на най-доброто решение изисква повече стъпки от намирането на решение, което работи и няма променливи.
Не винаги е възможно да се намери основно решение без променливи, особено за проблеми с по-малко от ограничения.
За да намерите основно осъществимо решение, трябва да използвате симплексния метод или друг алгоритъм за линейно програмиране, за да търсите решение, което отговаря на всички ограничения и има най-малко ненулеви променливи.
Свойства и значение на основното осъществимо решение
Свойства на основното осъществимо решение
Едно основно осъществимо решение има най-много m променливи, които не са нула, и поне nm променливи, които са нула, където n е броят на променливите за вземане на решение, а m е броят на ограниченията.
BFS е ъгъл на полиедъра на възможните решения и всеки BFS има n активни ограничения, които са линейно независими.
Ако има най-добро решение, трябва да има и най-добра първа стъпка.
Най-важното нещо за основните осъществими решения е, че те са краищата на набора от изпъкнали решения за проблем с линейно програмиране.
За да намери най-добрия отговор, симплексният алгоритъм преминава през серия от BFS.
Симплексният алгоритъм претърсва всички основни възможни решения по организиран начин, за да намери най-доброто.
Значение на основното осъществимо решение
Намирането на възможно основно решение е важно, защото помага да се намери най-добрият отговор на проблеми с линейното програмиране.
Той също така дава място за започване на сложни алгоритми и може да се използва, за да разберете дали линейна програма е възможна или не.
За да намерите всички основни осъществими решения за линейна програма, можете да промените системата, като добавите променливи за отслабване и след това да използвате променената система, за да намерите всички основни осъществими решения.
След това тези основни осъществими решения се използват за намиране на основните осъществими решения за първоначалния проблем.
Видео: Основни осъществими решения
Съвет: Включете бутона за надписи, ако имате нужда от него. Изберете „автоматичен превод“ в бутона за настройки, ако не сте запознати с говоримия език. Може да се наложи първо да щракнете върху езика на видеоклипа, преди любимият ви език да стане достъпен за превод.
Случаи на употреба
| Използвано в: | Описание: |
|---|---|
| Разпределение на ресурсите: | BFS може да се използва за разделяне на ограничени ресурси между няколко проекта, така че да може да се направи най-много с най-малко. Този метод може да се използва в много различни области, като транспорт, земеделие и финанси. |
| Оптимизация на мрежата: | BFS може да се използва за по-добра работа на комуникационните, транспортните и логистичните мрежи. BFS може да помогне в намирането на най-добрите маршрути за стоки и услуги, да намали времето и парите, изразходвани за транспорт, и да ускори и направи по-точни доставки. |
| Планиране на производството: | BFS може да се използва за планиране на производството, така че ресурси като труд, суровини и оборудване да се използват по възможно най-добрия начин, за да се извлече максимума от тях. BFS може да помогне за намаляване на производствените разходи, намаляване на отпадъците и подобряване на ефективността. |
| Финансово планиране: | Във финансовото планиране BFS може да се използва за оптимизиране на инвестиционни портфейли, намаляване на риска и връщане на най-много пари. BFS може да помогне да се намери най-добрият начин за разделяне на активи, намаляване на транзакционните разходи и печелене на повече пари. |
| Управление на веригата за доставки: | BFS може да се използва за подобряване на потока от стоки и услуги от доставчици към клиенти като част от управлението на веригата за доставки. BFS може да ви помогне да разберете кое е най-доброто количество наличност, което да поддържате под ръка, да съкрати времето за доставка и да подобри обслужването на клиентите. |
Заключение
Тъй като този поглед към основните осъществими решения приключва, става ясно, че те са важен инструмент за всеки инженер или студент по инженерство.
От намирането на най-добрия начин за изграждане на сложна система до максималното използване на наличните ресурси, основните осъществими решения осигуряват рамка за получаване на възможно най-добрия резултат.
Но не просто са полезни, те показват колко елегантна и красива може да бъде математиката.
Удивително е, че можете да сведете сложни проблеми до прост набор от уравнения и след това да използвате тези уравнения за решаване на проблеми в реалния свят.
Това е добро напомняне, че инженерството е свързано изцяло с решаването на проблеми и че като използваме силата на математиката, можем да намерим отговори, които някога са се смятали за невъзможни.
Така че, докато научавате повече за инженерството, имайте предвид това, което сте научили за прости решения, които работят и ги използвайте, за да направите света по-добро и по-ефективно място.
Връзки и препратки
Книги:
- Линейно програмиране: основи и разширения
- Линейно програмиране: теория и приложения
Сподели на…
