Линейное программирование

Контенус

В исследованиях операций (OR), таких как линейное программирование, моделирование проблемы состоит из определения:

внутренние (неизвестные) переменные
различные ограничения, которым подчиняются эти переменные
целевая цель (оптимизация) называется функцией цели.

В задаче линейного программирования (ЛП) ограничения и цель являются линейными функциями переменных. Также называется линейной программой. Они обозначаются следующим образом (каноническая форма явный):

Максимизировать	против^Т Икс
При условии	ах ≤ б
	х ≥ 0

где x - вектор переменных (Икс₁, …, Икс_нет), против и б – векторы коэффициентов, В матрица размерных коэффициентов м*н, а также ^Т транспонирование (например, вектор-столбец вместо вектора-строки). Неравенства ах ≤ б и х ≥ 0 (положительность переменных) являются ограничениями. в поле определения образует выпуклый многогранник. Говорят, что линейная программа находится в стандартной форме, если она включает ограничения равенства.

Положительность переменных. Если в контексте у нас есть ненулевая нижняя граница х ≥ к, просто поставь у=хк и у ≥ 0. Если нижней границы нет, всегда можно положить х = yz с у ≥ 0 и г ≥ 0.

Любую стандартную задачу можно записать канонически и наоборот. Ограничение равенства разбивается на два ограничения неравенства. Ограничение неравенства записывается в форме равенства путем добавления резервная переменная.

Решение x' называется допустимым, если оно удовлетворяет всем ограничениям.

Подводя итог, линейное программирование состоит из четырех элементов:

переменные решения;
целевая функция;
ресурсные ограничения;
ограничения типа.

Чтобы сформулировать проблему из спецификации, необходимо выполнить четыре предыдущих пункта по порядку.

Пример. Рассмотрим фабрику, производящую два типа клавиатур, каждая из которых стоит 50 и 70 фунтов стерлингов. Для изготовления изделия типа 1 требуется 40 мин труда и 20 мин механической обработки. Для изготовления узла типа 2 требуется 30 минут труда и 30 минут механической обработки. Персонал работает 6 часов в день, а машина доступна 8 часов в день. Сколько единиц каждого типа необходимо произвести, чтобы максимизировать прибыль?

Линейная программа. Эта задача моделируется в соответствии со следующим PL:

макс 50x + 70y
СК 40x +30y ≤ 360
20x + 30y ≤ 480
х, у≥ 0

Возможные решения

Могут возникнуть только четыре случая:

Если область определения пуста, проблема не реализуема;
иначе: оптимума не существует, задача не ограничена;
или: задача имеет единственное оптимальное решение, совпадающее с крайней точкой (вершиной) области определения;
или: задача имеет бесконечное множество решений, образующих грань или край области определения.