Eсли вы инженер или студент инженерного факультета, возможно, вы знаете, что такое оптимизация.
Чтобы получить наилучший возможный результат, важно найти лучший способ сделать что-то.
В линейном программировании вы можете использовать базовое решение, чтобы найти лучшее решение.
Но что такое базовое решение и почему инженерам так важно знать о них? В этой статье я расскажу о том, что такое базовые решения, почему они важны в разработке и как их можно использовать для получения наилучших результатов в различных ситуациях.
Так что пристегнитесь и приготовьтесь погрузиться в мир простых решений, где я раскрою тайны и покажу вам, насколько мощной может быть эта техника.
Базовые решения в линейном программировании
Формальное определение:
Решение линейной программной модели, состоящей из m уравнений с n переменными, получается путем решения для m переменных в терминах оставшихся (nm) переменных и установки (nm) переменных равными нулю.
Базовое решение в линейном программировании — это способ решения задачи линейного программирования, отвечающий определенным техническим требованиям.
В частности, вектор x является основным решением многогранника, если векторы {ai : xi = 0} линейно независимы.
Это означает, что столбцы матрицы A, переменные xi которых не равны нулю, линейно независимы.
Основное решение с неотрицательными компонентами называется базовым допустимым решением (BFS) (BFS).
BFS соответствует всем правилам, определяющим многогранник.
Каждый BFS является углом многогранника допустимых решений с геометрической точки зрения.
Чтобы найти основное решение, вы должны обнулить число переменных, которые не являются основными, и решить m переменных, которые являются основными.
Различные основания могут привести к одному и тому же основному решению, а это означает, что может быть более одного способа решения одной и той же проблемы.
Cимплексный метод — это итеративный процесс, который перемещается от одной BFS к следующей до тех пор, пока не будет найдена лучшая BFS.
После использования симплекс-метода для нахождения BFS мы можем сказать, является ли решение лучшим, проверив, дают ли какие-либо другие BFS поблизости лучшее значение целевой функции.
Eсли такой BFS нет, то текущая BFS является лучшей.
Модель линейного программирования
Модель линейного программирования включает три основных компонента: переменные решения, целевую функцию и ограничения.
И целевая функция, и ограничения должны быть линейными функциями, а переменные решения должны быть непрерывными.
Целевая функция используется для увеличения или уменьшения числа, представляющего прибыль, затраты, количество произведенной продукции и т. Д.
Ограничения — это лимиты или ограничения на общее количество определенного ресурса, необходимого для выполнения задач, которые будут определять уровень успеха в переменных решения.
Кроме того, некоторые линейные программы требуют, чтобы все переменные решения были неотрицательны.
В моделях линейного программирования вы также можете использовать целые и двоичные переменные.
Двоичные переменные могут иметь значение только 0 или 1, поэтому они могут иметь значение только 0 или 1.
Cимплексный метод
Одним из наиболее часто используемых способов решения задач линейного программирования является симплекс-метод.
Основные решения важны в симплекс-методе, поскольку они соответствуют угловым точкам допустимой области, а симплекс-метод перемещается от одного угла к другому, пока не будет найдено оптимальное решение.
Cимплекс-метод — это быстрый способ найти наилучший ответ на задачу линейного программирования, используя свойства основных решений.
Чтобы использовать симплекс-метод для поиска наилучшего BFS, нам нужно найти базис B для матрицы ограничений A и решить систему Ax = b со всеми переменными, кроме базиса, равными нулю.
Результирующие значения основных переменных образуют BFS.
Eсли существует оптимальное решение, то существует и оптимальная BFS.
Cимплекс-метод перемещается от одной BFS к соседней BFS до тех пор, пока не будет достигнута оптимальная BFS с помощью процедур разворота.
Cравнение базовых решений и возможных решений
Разница между базовым решением и допустимым решением заключается в том, что базовое решение не должно удовлетворять никаким условиям.
В частности, он должен иметь векторы, которые линейно независимы и имеют ненулевые значения для xi, а x должен быть меньше 0.
C другой стороны, допустимое решение — это любая точка, укладывающаяся в пределы задачи.
Но не все допустимые решения являются базовыми допустимыми решениями.
Основные допустимые решения (BFS) — это только те, которые соответствуют углам многогранника допустимых решений.
Назад к основам: раскрытие потенциала базовых решений в инженерии
Все еще трудно понять? Немного изменю точку зрения:
Вам надоело использовать сложные методы и алгоритмы для решения сложных задач? Хотели бы вы, чтобы существовал более простой и понятный способ решения ваших проблем с моделью линейной программы?
Что ж, не волнуйтесь, потому что ответ здесь: найти m переменных с точки зрения оставшихся (nm) переменных и установить (nm) переменных равными нулю.
Кому нужны алгоритмы, которые кажутся причудливыми, когда можно вернуться к основам? Так что отложите свои калькуляторы и давайте начнем изучать простые решения.
Хорошо, это была просто шутка, сделанная, чтобы выглядеть как телевизионная реклама.
Теперь вернемся к объяснению.
Базовое решение Линейное программирование
Cовет: включите кнопку подписи, если она вам нужна. Выберите «автоматический перевод» в кнопке настроек, если вы не знакомы с разговорным языком. Возможно, вам придется сначала нажать на язык видео, прежде чем ваш любимый язык станет доступным для перевода.
Cлучаи использования
| Используется в: | Описание: |
|---|---|
| Распределение ресурсов: | Базовое решение можно использовать в задачах распределения ресурсов, где целью является разделение ограниченных ресурсов между конкурирующими потребностями. Например, компании может потребоваться разделить свой бюджет между различными отделами или проектами. Используя базовые решения, они могут найти лучший способ использовать свои ресурсы, чтобы заработать как можно больше денег или потратить как можно меньше. |
| Планирование производства: | При планировании производства базовое решение может быть использовано для определения наилучшего сочетания продуктов, которое нужно производить, чтобы получить наибольшую прибыль. Компании могут найти наилучший производственный комплекс, который принесет больше всего денег и будет стоить меньше всего, используя базовое решение. |
| Планирование: | Базовое решение можно использовать, чтобы выяснить, как планировать задачи или задания, чтобы их можно было выполнять наиболее эффективным способом. Например, компании может потребоваться спланировать рабочее время своих сотрудников, чтобы убедиться, что у них достаточно работников, когда бизнес занят. Используя базовое решение, они могут найти лучший способ планирования, чтобы было как можно меньше времени простоя и выполнялось как можно больше работы. |
| Управление цепочкой поставок: | В управлении цепочками поставок цель состоит в том, чтобы обеспечить как можно более плавный переход товаров и услуг от поставщика к покупателю. Например, предприятию может потребоваться определить наилучшие маршруты для перевозки товаров, чтобы расходы были минимальными, а товары доставлялись вовремя. Используя базовые решения, они могут найти наилучший план управления цепочкой поставок, позволяющий снизить затраты и удовлетворить клиентов. |
| Оптимизация портфеля: | В оптимизации портфеля, где цель состоит в том, чтобы найти наилучшее сочетание инвестиций, чтобы заработать больше денег при наименьшем риске, можно использовать базовые решения. Например, инвестиционной фирме может потребоваться выяснить наилучшее сочетание акций, облигаций и других ценных бумаг, чтобы помочь своим клиентам достичь своих инвестиционных целей. Используя простое решение, они могут найти лучший способ смешать свои портфели, чтобы получить максимальную прибыль при наименьшем риске. |
Заключение
В заключение отметим, что идея базового решения очень важна в области техники и может использоваться по-разному.
Зная, что такое базовое решение и что оно делает в линейном программировании, мы можем улучшить решения, сократить расходы и сделать их более эффективными.
Но важно помнить, что базовое решение не является универсальным решением, даже если оно является мощным инструментом.
Чтобы получить наилучшие результаты, каждую проблему необходимо тщательно изучить и обдумать.
Как инженеры, мы должны продолжать изучать, как базовые решения и другие методы оптимизации могут помочь нам добиться прогресса и придумать новые идеи.
Итак, давайте признаем силу простых решений и продолжаем расширять границы возможного, используя новые методы и стратегии.
Cсылки и ссылки
Книги:
- Линейное программирование Васека Хватала
- Моделирование и решение линейного программирования с помощью R Хосе М. Cаллан
Поделись…
