Алгоритмы оптимизации ИИ
Цель линейного программирования - минимизировать функцию стоимости, которая имеет некоторое количество переменных (x₁, x₂, x₃) вплоть до x𝑛. Эти переменные участвуют в вещах, значения которых я хочу знать, и их можно умножить на коэффициент, а затем сложить.
В линейном программировании мы имеем дело только с линейными уравнениями, поэтому мы не собираемся ничего возводить в квадрат или куб.
Также у нас будут некоторые линейные ограничения:
- a₁x₁ + a₂x₂ + … + a𝑛x𝑛 ≤ b
- a₁x₁ + a₂x₂ + … + a𝑛x𝑛 = b
Со следующей границей для каждой переменной:
- lᵢ ≤ xᵢ ≤ uᵢ
Пример
Это пример проблемы, которая возникает довольно часто. Вы можете начать замечать закономерности в подобных проблемах. И если вы будете следовать шагам, которые я опишу ниже, вы решите любые проблемы этого типа.
Эта проблема
В этой задаче у нас есть следующие ограничения:
- Две машины - X₁ и X₂. X₁ стоит 50 долларов в час, тогда как X₂ стоит 80 долларов в час.
- X₁ требует пяти единиц труда в час, а X₂ требует двух единиц труда в час. Нам нужно потратить в общей сложности 20 единиц рабочей силы.
- X₁ производит десять единиц продукции в час . X₂ производит 12 единиц продукции в час. Компании необходимо 90 единиц продукции.
Наша цель - выяснить, сколько часов у компании есть на работу оборудования, чтобы минимизировать общие затраты.
Учитывая ограничения проблемы, у нас есть следующая таблица с соответствующими значениями для X₁ и X₂. В первой строке мы рассматриваем стоимость часа работы двух машин. Во второй строке отображается, сколько единиц труда затрачено на каждую машину. В третьей строке у нас есть единицы производительности в час для каждой машины.
Примечание. Нельзя забывать, что компании необходимо 90 единиц продукции.
╔═══════════════╦═══════════════╗
║ X₁ ║ X₂ ║
╔═══════════╬═══════════════╬═══════════════╣
║ Cost/Hour ║ $50 ║ $80 ║
║ Labor ║ 5 ║ 2 ║
║ Units/Hour║ 10 ║ 2 ║
╚═══════════╩═══════════════╩═══════════════╝
Теперь давайте создадим уравнения для этой задачи.
Задача
Цель этой задачи - найти минимальное значение для этого уравнения:
TC = 50 X₁ + 80 X₂
X₁ - это переменная, показывающая, сколько часов мы работаем на машине X₁.
X₂ - это переменная, показывающая, сколько часов мы работаем на машине X₂.
Ограничения
Здесь мы покрываем уравнения для двух имеющихся ограничений:
- 5 X₁ + 2 X₂ ≤ 20
- 10 X₁ + 12 X₂ ≥ 90
Как я уже сказал, в линейном программировании мы имеем дело с ограничениями, равными (=) или меньшими или равными (≤). Мы видим, что второе уравнение не соответствует этому шаблону. Мы можем просто умножить уравнение на отрицательное и перевернуть его до значения меньше или равно (≤):
-10 X₁ + -12 X₂ ≤ -90
Изобразим это графически. Учитывая первое уравнение ограничения и когда X₂ = 0, мы будем иметь:
5 X₁ + 2 (0)≤ 20
5 X₁ ≤ 20
X₁ ≤ 4
Теперь, когда X₁ равно 0, мы можем вычислить значение X₂:
5 (0)+ 2 X₂ ≤ 20
2 X₂ ≤ 20
X₂ ≤ 10
Теперь мы можем провести линию между этими двумя точками:
Перейдем ко второму уравнению (- 10 X₁ + -12 X₂ ≤ -90). Проделываем тот же процесс:
- Если X₂ = 0
-10 X₁ = -90
X₁ = 9 - Если X₁ = 0
-12 X₂ = -90
X₂ = 7,5
Чтобы свести к минимуму стоимость и в то же время произвести 90 единиц продукции, решение будет в этой красной области:
Чтобы получить граничные точки, мы должны вычислить точку пересечения. Для этого просуммируем уравнения ограничений:
5 X₁ + 2 X₂ ≤ 20
-10 X₁ + -12 X₂ ≤ -90
Умножим первое уравнение на 2:
10 X₁ + 4X₂ ≤ 40
-10 X₁ + -12 X₂ = -90
— — — — — — —
0 X₁ + -8 X₂ = -50
-8 X₂ = -50
X₂ = 6.25
Теперь вычислим X₁, используя первое уравнение:
5 X₁ + 2 X₂ ≤ 20
5 X₁ + 2 (6.25) ≤ 20
X₁ = 1.5
При этом мы знаем значение точки пересечения (синим цветом):
Теперь, когда у нас есть все точки, давайте создадим сравнительную таблицу:
╔═══════════════╦═══════════════╦═══════════════╗ ║ X₁ ║ X₂ ║ TC ║ ║═══════════════╬═══════════════╬═══════════════╣ ║ 4 ║ 0 ║ ║ ║ 0 ║ 7.5 ║ ║ ║ 1.5 ║ 6.25 ║ ║ ╚═══════════════╩═══════════════╩═══════════════╝
Мы рассчитываем общую стоимость, используя наше объективное уравнение:
TC = 50 X₁ + 80 X₂
Единицы = 10 X₁ + 12 X₂
╔═══════════════╦═══════════════╦═══════════════╦═══════════════╗ ║ X₁ ║ X₂ ║ TC ║ Units ║ ║═══════════════╬═══════════════╬═══════════════╬═══════════════╣ ║ 4 ║ 0 ║ 200 ║ 40 ║ ║ 0 ║ 7.5 ║ 600 ║ 90 ║ ║ 1.5 ║ 6.25 ║ 575 ║ 90 ║ ╚═══════════════╩═══════════════╩═══════════════╩═══════════════╝
Результат
Мы отбросим первые значения, потому что мы должны учитывать ограничение, которое говорит, что нам нужно 90 единиц вывода. Итак, поскольку мы рассматриваем минимальную стоимость, мы получим всего 575, и компания должна запустить машину X₁ в течение 1,5 часа, а X₂ машина на 6,25 часа.
Решение этой проблемы с помощью Python
Для решения этой проблемы с Python воспользуемся библиотекой SciPy. Вы можете установить его, используя pip:
$ pip install scipy
Мы возьмем нашу целевую функцию и функции ограничений для вызова функции linprog пакета optimize:
У нас будет тот же результат, который мы рассчитали ранее:
X1: 1.5 hours X2: 6.25 hours
Заключение
В ИИ мы используем линейное программирование, когда нам не важен путь к решению, а только само решение.
