Целью компиляции типичных задач линейного программирования является развитие изобретательского потенциала для формулирования задач оптимизации ресурсов.
Линейное программирование - общая проблема
Определение:
Учитывая набор из m линейных неравенств или линейных уравнений с n переменными, требуется найти неотрицательные значения этих переменных, которые удовлетворяют ограничениям, и максимизировать или минимизировать некоторую линейную функцию переменных, называемую целевой функцией.
Математически:
Найдите X J, J = 1, 2,.,,,, n для:
Максимизация
или Z = C 1 X 1 + C 2 X 2 +.,,,,, + C n X n
Свести к минимуму
Со следующими ограничениями:
в 11 х 1 +.,,,,, + a 1j X j +.,,,,, + a 1n X n ≤ или ≥ b1
а i1 X 1 +.,,,,, + а ij X j +.,,,, + a в X n ≤ или ≥ bi
а m1 X 1 +.,,,,, + a mj X j +.,,,,, + a mn X n ≤ или ≥ bm
X j = 0; j = 1, 2,.,,,,, N
Особенности линейного программирования
- Линейность предполагает, что не может быть таких терминов: X 1 X 2, X 3 от 2 до 14 Log X 4 Предполагает аддитивные и мультипликативные свойства.
- Если устройству типа E требуется 2 часа в машине A, а устройству типа F - 2½ часа, то им обоим нужно 4½ часа. Если устройству типа E требуется 1 час в машине B, то для 10 устройств требуется 10 часов.
- Оптимизируемая функция (максимизация или минимизация) называется целевой функцией, она не содержит никаких постоянных членов. В ограничениях m условия Xj = 0 (условие неотрицательности) не включены. Решения:
- Любое множество Xj, удовлетворяющее m ограничениям, называется решением задачи. Если решение удовлетворяет условию неотрицательности Xj = 0, оно называется допустимым решением. Допустимое решение, которое оптимизирует целевую функцию, называется оптимальным допустимым решением.
Обычно существует бесконечное количество возможных решений проблемы, из которых необходимо найти оптимальное.
Рекомендации и комментарии по моделированию
При преобразовании вербальных моделей в формальные будет очень полезно сначала описать словами модель, которая соответствует данной проблеме.
Вы можете действовать следующим образом:
- Обозначьте каждое ограничение словами; При этом обратите особое внимание на то, является ли ограничение требованием формы:
≥ (больше или равно, по крайней мере, по крайней мере, по крайней мере), ≤ (меньше или равно, не больше, не больше), или
= (равно, точно равно).
- Выразите цель словами. Устно определите переменные решения. Полезно задать себе вопрос:
какое решение необходимо принять для оптимизации целевой функции?, Ответ на этот вопрос поможет правильно определить переменные решения. Выразить целевую функцию через переменные решения. Проверить согласованность единиц. Например, если коэффициенты целевой функции Cj указаны в S. / кг, переменные решения Xj должны быть в килограммах, а не в тоннах или унциях. Выразите ограничения в терминах переменных решения. Убедитесь, что для каждого ограничения единицы на правой стороне такие же, как и на левой стороне.
Ограничения не могут иметь строгого неравенства со знаками <или>. Причина этого носит математический характер.
Формулировка моделей
Преобразуйте реальные проблемы в математические модели.
Не зацикливайтесь на проблеме больше, чем дано. Например, не вводите дополнительных ограничений, логических нюансов или воображаемых данных, которые, по вашему мнению, могут сделать модель более реалистичной.
Скачать оригинальный файл
