Ако сте инженер или студент по инженерство, може би знаете какво означава да оптимизираш.
За да получите възможно най-добрия резултат, важно е да намерите най-добрия начин да направите нещата.
При линейното програмиране можете да използвате основно решение, за да намерите най-доброто решение.
Но какво е основното решение и защо е толкова важно за инженерите да знаят за тях? В тази статия ще говоря какво представляват основните решения, защо са важни в инженерството и как могат да се използват за постигане на най-добри резултати в различни ситуации.
Така че закопчайте коланите и се пригответе да се потопите в света на основните решения, където ще разбия мистериите и ще ви покажа колко мощна може да бъде тази техника.
Основни решения в линейното програмиране
Официална дефиниция:
Решение на линеен програмен модел, състоящ се от m уравнения в n променливи, се получава чрез решаване на m променливи по отношение на останалите (nm) променливи и задаване на (nm) променливи равни на нула.
Основно решение в линейното програмиране е начин за решаване на проблем с линейно програмиране, който отговаря на определени технически изисквания.
По-специално, вектор x е основно решение за полиедър, ако векторите {ai : xi = 0} са линейно независими.
Това означава, че колоните на A, които имат променливи xi, които не са нула, са линейно независими.
Базово решение с неотрицателни компоненти се нарича основно изпълнимо решение (BFS) (BFS).
BFS отговаря на всички правила, които определят полиедър.
Всеки BFS е ъгъл на полиедъра на възможните решения от геометрична гледна точка.
За да намерите основно решение, трябва да зададете nm променливи, които не са основни, на нула и да решите m променливи, които са основни.
Възможно е различни бази да водят до едно и също основно решение, което означава, че може да има повече от един начин за решаване на един и същи проблем.
Симплексният метод е итеративен процес, който преминава от един BFS към следващия BFS, докато намери най-добрия BFS.
След като използваме симплексния метод за намиране на BFS, можем да разберем дали решението е най-доброто, като видим дали други BFS наблизо дават по-добра стойност за целевата функция.
Ако няма такъв BFS, тогава сегашният BFS е най-добрият.
Модел на линейно програмиране
Моделът на линейно програмиране включва три основни компонента: променливи за вземане на решения, целева функция и ограничения.
Както целевата функция, така и ограниченията трябва да бъдат линейни функции, а променливите за вземане на решение трябва да са непрекъснати.
Целевата функция се използва за увеличаване или намаляване на число, което представлява печалба, разходи, брой произведени продукти и т.н.
Ограниченията са лимити или ограничения върху общото количество на определен ресурс, който е необходим за изпълнение на задачите, които ще определят нивото на успех в променливите за вземане на решение.
В допълнение, някои линейни програми изискват всички променливи за вземане на решение да са неотрицателни.
В моделите за линейно програмиране можете също да използвате цели числа и двоични променливи.
Двоичните променливи могат да имат само стойност 0 или 1, така че могат да имат само стойност 0 или 1.
Симплексният метод
Един от най-използваните начини за решаване на проблеми с линейното програмиране е симплексният метод.
Основните решения са важни в симплексния метод, тъй като те съответстват на ъгловите точки на осъществимата област, а симплексният метод се движи от един ъгъл в друг, докато се намери оптимално решение.
Симплексният метод е бърз начин за намиране на най-добрия отговор на проблем с линейно програмиране чрез използване на свойствата на основните решения.
За да използваме симплексния метод, за да намерим най-добрия BFS, трябва да намерим основа B за матрицата на ограничения A и да решим системата Ax = b с всички променливи, различни от основата, зададена на нула.
Получените стойности за основните променливи формират BFS.
Ако съществува оптимално решение, тогава съществува оптимален BFS.
Симплексният метод се премества от една BFS към съседна BFS, докато достигне оптимална BFS чрез използване на осеви процедури.
Сравнение между основни решения и осъществими решения
Разликата между основно решение и осъществимо решение е, че основното решение не трябва да отговаря на никакви условия.
По-специално, той трябва да има вектори, които са линейно независими и имат ненулеви стойности за xi, а x трябва да е по-малко от 0.
От друга страна, осъществимо решение е всяка точка, която се вписва в границите на проблема.
Но не всички осъществими решения са основни осъществими решения.
Основните осъществими решения (BFSs) са само тези, които съответстват на ъглите на полиедъра на осъществимите решения.
Обратно към основите: Отключване на силата на основните решения в инженерството
Все още трудно за разбиране? Да променя малко гледната точка:
Омръзна ли ви да използвате сложни методи и алгоритми за решаване на трудни проблеми? Искате ли да има по-прост, по-ясен начин за справяне с проблемите на вашия модел на линейна програма?
Е, не се притеснявайте, защото отговорът е тук: намерете m променливи по отношение на останалите (nm) променливи и задайте (nm) променливите на нула.
Кой се нуждае от алгоритми, които звучат фантастично, когато можете да се върнете към основите? Така че оставете калкулаторите си и нека започнем да учим за прости решения.
Добре, това беше просто шега, направена да изглежда като телевизионна реклама.
Сега да се върнем към обяснението.
Основно решение Линейно програмиране
Съвет: Включете бутона за надписи, ако имате нужда от него. Изберете „автоматичен превод“ в бутона за настройки, ако не сте запознати с говоримия език. Може да се наложи първо да щракнете върху езика на видеоклипа, преди любимият ви език да стане достъпен за превод.
Случаи на употреба
| Използвано в: | Описание: |
|---|---|
| Разпределение на ресурсите: | Базовото решение може да се използва при проблеми с разпределението на ресурси, където целта е да се разделят ограничените ресурси между конкуриращи се нужди. Например, една компания може да се наложи да раздели бюджета си между различни отдели или проекти. Използвайки основни решения, те могат да разберат най-добрия начин да използват своите ресурси, за да направят най-много пари или да харчат възможно най-малко. |
| Планиране на производството: | При планирането на производството основното решение може да се използва за определяне на най-добрия микс от продукти, които да направите, за да спечелите най-много пари. Компаниите могат да намерят най-добрия производствен микс, който носи най-много пари и струва най-малко, като използват основното решение. |
| Планиране: | Базовото решение може да се използва, за да разберете как да планирате задачи или работни места, така че да могат да бъдат изпълнени по най-ефективния начин. Например, една компания може да се наложи да планира работното време на своите служители, за да се увери, че имат достатъчно работници, когато бизнесът е натоварен. Като използват основно решение, те могат да измислят най-добрия начин да планират нещата, така че да има възможно най-малко време на престой и да се свърши възможно най-много работа. |
| Управление на веригата за доставки: | При управлението на веригата за доставки целта е да се гарантира, че стоките и услугите се движат възможно най-гладко от доставчика към клиента. Например, един бизнес може да трябва да намери най-добрите маршрути за транспортиране на стоки, така че разходите да бъдат сведени до минимум и стоките да бъдат доставени навреме. Използвайки основни решения, те могат да намерят най-добрия план за управление на веригата за доставки, който поддържа ниски разходи и поддържа клиентите доволни. |
| Оптимизация на портфолио: | При оптимизирането на портфейла, където целта е да се намери най-добрата комбинация от инвестиции, за да се направят най-много пари, като същевременно се поема най-малко риск, могат да се използват основни решения. Например, инвестиционен посредник може да се наложи да намери най-добрата комбинация от акции, облигации и други ценни книжа, за да помогне на своите клиенти да постигнат своите инвестиционни цели. Като използват просто решение, те могат да намерят най-добрия начин да комбинират своите портфейли, така че да получат най-добра възвръщаемост, като същевременно поемат най-малко риск. |
Заключение
В заключение, идеята за основно решение е много важна в областта на инженерството и може да се използва по много различни начини.
Като знаем какво е основно решение и какво прави в линейното програмиране, можем да подобрим решенията, да намалим разходите и да ги направим по-ефективни.
Но е важно да запомните, че основното решение не е универсално решение, въпреки че е мощен инструмент.
За да получите най-добри резултати, всеки проблем трябва да бъде внимателно разгледан и обмислен.
Като инженери трябва да продължим да търсим как основните решения и други техники за оптимизация могат да ни помогнат да постигнем напредък и да измислим нови идеи.
Така че, нека признаем силата на простите решения и да продължим да разширяваме границите на възможното, като използваме нови техники и стратегии.
Връзки и препратки
Книги:
- Линейно програмиране от Vasek Chvatal
- Моделиране и решаване на линейно програмиране с R от Хосе М. Салан
Сподели на…
