Вы знаете, что значит оптимизировать систему для получения наилучшего возможного результата, если вы студент инженерного факультета или инженер.
Оптимизация решения — ключ к успеху во всем, от наведения мостов до создания программного обеспечения.
В этот момент возникает идея базового возможного решения.
Это основная идея линейного программирования, которая позволяет вам выяснить, какое из множества возможных решений является лучшим.
Но почему это так важно? В этой статье я расскажу об основных возможных решениях и о том, как их можно использовать для решения инженерных задач в реальном мире.
Я расскажу о том, как их найти, из чего они сделаны и почему они важны.
Итак, являетесь ли вы опытным инженером или только начинающим студентом, присоединяйтесь к нам, пока я погружаюсь в мир основных возможных решений и покажу вам, как использовать возможности линейного программирования.
Понимание основного возможного решения
Формальное определение:
Базовое решение линейной модели программы, в которой все переменные неотрицательны.
Базовое допустимое решение (BFS) — ключевая идея линейного программирования, помогающая находить наилучшие решения.
BFS — это решение с наименьшим возможным числом ненулевых переменных.
Это угол многогранника допустимых решений.
Другими словами, BFS — это базовое решение, которое удовлетворяет неотрицательным ограничениям и находится в допустимой области или проблемной области.
Поиск оптимального базового возможного решения
Чтобы найти лучший BFS, нам нужно сделать следующее:
- Напишите программу в стандартной форме для линейной последовательности.
- Превратите систему неравенств в расширенную матрицу.
- Выясните, какие переменные являются базовыми, а какие нет.
- Выясните, каковы основные переменные с точки зрения других переменных.
- Поместите эти выражения в целевую функцию, чтобы получить функцию только тех переменных, которые не являются базовыми.
- Найдите неосновную переменную, которую можно увеличить, не нарушая никаких ограничений, и которая улучшит целевую функцию.
Эта переменная теперь является базовой переменной, а одна из других базовых переменных больше не является базовой переменной.
Eсли есть оптимальное решение, оно должно быть на одном из концов или вершин области, где решения возможны.
Таким образом, если ЛП имеет оптимальное решение, оно имеет оптимальное решение в крайней точке допустимого множества.
Кроме того, всегда существует оптимальная BFS, если существует оптимальное решение.
Использование симплекс-метода для поиска оптимального BFS
Cимплекс-метод — это алгоритм решения задач линейного программирования.
Он перемещается от одной BFS к «соседней» BFS с помощью процедуры поворота.
В процедуре разворота небазовая переменная выбирается в качестве базовой, а затем текущая BFS используется для определения новых базовых переменных.
Когда никакая неосновная переменная не может быть изменена, чтобы улучшить целевую функцию, алгоритм выполнен.
Почему базовые возможные решения имеют решающее значение для решения сложных инженерных задач
Все еще трудно понять? Немного изменю точку зрения:
Кому вообще нужны простые, работающие ответы? Просто сложите все вместе и надейтесь на лучшее.
В конце концов, кому нужна оптимизация, когда хаос гораздо веселее? Добро пожаловать в мир неотрицательных переменных, где все является лишь предположением, а неудача почти неизбежна.
Или это?
Давайте рассмотрим, почему кажущаяся базовой концепция основных возможных решений вовсе не является базовой, и почему они могут быть просто ключом к решению даже самых сложных инженерных задач.
Хорошо, это была просто шутка, сделанная, чтобы выглядеть как телевизионная реклама.
Теперь вернемся к объяснению.
Поиск основного возможного решения
Базовое допустимое решение (BFS) — это решение задачи линейной оптимизации, удовлетворяющее всем ограничениям и имеющее наименьшее количество ненулевых переменных.
Каждый BFS является углом многогранника допустимых решений с геометрической точки зрения.
Eсли есть лучшее решение, то должен быть и лучший первый шаг.
В этой статье мы поговорим о том, как найти начальное базовое допустимое решение, как найти все базовые допустимые решения и как найти базовое допустимое решение без резервных переменных.
Поиск начального базового возможного решения
Мы можем использовать различные методы, в зависимости от того, как поставлена задача, чтобы найти начальное базовое решение, которое работает для задачи линейной оптимизации.
Один из способов — добавить временные переменные к ограничениям на неравенства и установить все остальные переменные равными нулю.
Переменные резерва становятся базовыми переменными, а остальные — небазовыми.
Двухэтапный симплекс-метод — еще один способ решения проблемы.
Этот метод включает в себя решение дополнительной задачи линейного программирования, чтобы найти допустимое начальное базовое решение.
Как только начальное допустимое решение найдено, можно использовать симплекс-метод для перехода от одного базового допустимого решения к другому, а затем к наилучшему решению.
Поиск всех основных возможных решений
Может быть более одного базового решения, которое работает для линейной программы.
Мы можем изменить систему, добавив резервные переменные, а затем использовать новую систему, чтобы найти все основные допустимые решения для линейной программы.
Затем эти основные допустимые решения используются для нахождения основных допустимых решений исходной задачи.
Поиск базового возможного решения без резервных переменных
Нам нужно использовать переменные резерва, чтобы избавиться от ограничений «меньше чем», чтобы мы могли найти базовое решение, которое работает без переменных резерва.
Незначительная переменная — это просто разница между правой частью ограничения и левой стороной.
Например, для первого ограничения мы определяем резервную переменную x4 = 14 - 2x1 - x2 - x3. C точки зрения этой новой переменной первое ограничение эквивалентно просто x4 ≥ 0, что является ограничением положительности для x4.
Когда мы добавляем эти резервные переменные, мы получаем линейную программу, такую же, как исходная, за исключением того, что все ограничения являются либо уравнениями, либо ограничениями, которые говорят, что что-то положительно.
Cовокупность базовых переменных, имеющих в базовом решении значения, отличные от нуля, называется базисом.
Переменные, имеющие нулевое значение в базовом решении, не являются базовыми переменными.
Чтобы найти наилучшее решение, нам нужно найти вектор x, который удовлетворяет всем правилам и получает наибольшее или наименьшее значение для цели.
Но поиск наилучшего решения требует больше шагов, чем просто поиск решения, которое работает и не имеет резервных переменных.
Не всегда возможно найти базовое решение без резервных переменных, особенно для задач с ограничениями меньше чем.
Чтобы найти базовое допустимое решение, вам нужно использовать симплекс-метод или другой алгоритм линейного программирования, чтобы найти решение, удовлетворяющее всем ограничениям и имеющее наименьшее количество ненулевых переменных.
Cвойства и значение базового возможного решения
Cвойства базового возможного решения
Базовое допустимое решение имеет не более m переменных, которые не равны нулю, и не менее чем nm переменных, равных нулю, где n — количество переменных решения, а m — количество ограничений.
BFS — это угол многогранника возможных решений, и каждый BFS имеет n активных ограничений, которые линейно независимы.
Eсли есть лучшее решение, то должен быть и лучший первый шаг.
Cамое важное в базовых допустимых решениях то, что они являются концами множества выпуклых решений задачи линейного программирования.
Чтобы найти лучший ответ, симплекс-алгоритм проходит серию BFS.
Cимплекс-алгоритм организованно перебирает все основные возможные решения, чтобы найти наилучшее.
Значение базового возможного решения
Поиск возможного базового решения важен, потому что он помогает найти лучший ответ на задачи линейного программирования.
Это также дает старт сложным алгоритмам и может быть использовано для выяснения, возможна ли линейная программа или нет.
Чтобы найти все основные допустимые решения для линейной программы, вы можете изменить систему, добавив резервные переменные, а затем использовать измененную систему, чтобы найти все основные допустимые решения.
Затем эти основные допустимые решения используются для нахождения основных допустимых решений исходной задачи.
Видео: основные возможные решения
Cовет: включите кнопку подписи, если она вам нужна. Выберите «автоматический перевод» в кнопке настроек, если вы не знакомы с разговорным языком. Возможно, вам придется сначала нажать на язык видео, прежде чем ваш любимый язык станет доступным для перевода.
Cлучаи использования
| Используется в: | Описание: |
|---|---|
| Распределение ресурсов: | BFS можно использовать для разделения ограниченных ресурсов между несколькими проектами, чтобы можно было сделать как можно больше с наименьшими затратами. Этот метод можно использовать во многих различных областях, таких как транспорт, сельское хозяйство и финансы. |
| Оптимизация сети: | BFS можно использовать для улучшения работы сетей связи, транспорта и логистики. BFS может помочь найти лучшие маршруты для товаров и услуг, сократить время и деньги, затрачиваемые на транспортировку, а также ускорить и сделать доставку более точной. |
| Планирование производства: | BFS можно использовать для планирования производства таким образом, чтобы такие ресурсы, как рабочая сила, сырье и оборудование, использовались наилучшим образом для получения максимальной отдачи от них. BFS может помочь снизить производственные затраты, сократить количество отходов и повысить эффективность. |
| Финансовое планирование: | В финансовом планировании BFS можно использовать для оптимизации инвестиционных портфелей, снижения рисков и получения максимального возврата денег. BFS может помочь найти лучший способ разделить активы, снизить транзакционные издержки и заработать больше денег. |
| Управление цепочкой поставок: | BFS можно использовать для улучшения потока товаров и услуг от поставщиков к клиентам в рамках управления цепочкой поставок. BFS может помочь определить оптимальное количество складских запасов, сократить время выполнения заказа и улучшить обслуживание клиентов. |
Заключение
Когда этот обзор основных возможных решений подходит к концу, становится ясно, что они являются важным инструментом для любого инженера или студента инженерного факультета.
Базовые осуществимые решения обеспечивают основу для получения наилучшего возможного результата — от определения наилучшего способа построения сложной системы до максимально эффективного использования имеющихся ресурсов.
Но они не просто полезны, они показывают, насколько элегантной и красивой может быть математика.
Удивительно, как вы можете свести сложные проблемы к простому набору уравнений, а затем использовать эти уравнения для решения проблем в реальном мире.
Это хорошее напоминание о том, что инженерия — это решение проблем, и что, используя силу математики, мы можем найти ответы, которые когда-то считались невозможными.
Поэтому, узнавая больше о инженерии, помните, что вы узнали о простых решениях, которые работают, и используйте их, чтобы сделать мир лучше и эффективнее.
Cсылки и ссылки
Книги:
- Линейное программирование: основы и расширения
- Линейное программирование: теория и приложения
Поделись…
