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

Лекция 1. Линейное программирование. Максим Бабенко // Лекториум [1:35:34]

Линейное программирование — это математический численный метод для оптимизации моделей, в которых целевые функции и ограничения строго являются уравнениями линейной алгебры.^:33 Модель линейного программирования включает целевую функцию, ограничения в виде линейных уравнений или неравенств и требование неотрицательности переменных. Термин был предложен Дж. Данцигу Т. Купмансом в 1951 году^:13 Метод применим в военной и экономической логистике для оптимизации доставки грузов и технологических процессов. Был расширен и далее исследован в пору Второй Мировой войны и после.^:19-37

Целевая функция

$f(x)=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}{\text{→}}min;$

Если функцию требуется обратить не в минимум, а в максимум, достаточно изменить знак коэффициентов $c_{i}$ на противоположный^:329

Ограничения

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1},\\a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}=b_{2},\\...\\a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}=b_{m};\end{cases}}$

Здесь a и b — постоянные числа, заданные условиями задачи. Если по условиям задачи вместо равенств предполагаются неравенства, то для неравенства вида «≤» для преобразования его в равенство надо добавить дополнительную переменную $x_{n+1}$ или несколько таких переменных ($x_{n+2}$ и т.д. по числу неравенств). Аналогично, для неравенств вида «≥» дополнительную неотрицательную переменную $x_{n+i}$ следует вычесть (или, что то же самое, прибавить с коэффициентом –1).^:34

Требования неотрицательности переменных

Переменные x принимают неотрицательные значения: $x_{j}\geq 0$, $j=1,{\text{…}},n$. Постоянные a, b и c, заданные условиями задачи, требований к неотрицательности не имеют (могут быть как положительными, так и отрицательными).

Запись в табличной форме

Предположим, что имеются запасы сырья, из которого производятся продукты разных видов, приносящие определенную прибыль. Требуется расчитать, какой объем продукции каждого вида следует выпустить, чтобы максимизировать прибыль.

Вид сырья	Продукт 1	Продукт 2	Продукт 3	Продукт 4	Запасы сырья
Сырье 1	a11 = 4 кг	a12 = 2 кг	a13 = 1 кг	a14 = 8 кг	b1 ≤ 1200 кг
Сырье 2	a21 = 2 кг	a22 = 10 кг	a23 = 6 кг	a24 = 0 кг	b2 ≤ 600 кг
Сырье 3	a31 = 3 кг	a32 = 0 кг	a33 = 6 кг	a34 = 1 кг	b3 ≤ 1500 кг
Прибыль (руб.)	c1 = 15	c2 = 6	c3 = 12	c4 = 24	max

Коэффициенты a_ij указывают, сколько сырья i уходит на изготовление одной единицы j-го продукта.

На выходе алгоритма расчета будут найдены переменные x_j, которые соответствуют оптимальному выпуску продукции при указанных ограничениях.^:57

Другим типом задач является задача на минимизацию издержек при составлении диеты или откорме животных. Коэффициенты a показывают содержание вещества в фунтах на фунт ингредиента. ^:174

Вид корма	Известняк	Зерно	Соевая мука	Ограничение
Кальций	a11 = 0,380	a12 = 0,001	a13 = 0,002	b1 ≥ 8 и b1 ≤ 12%
Белок	a21 = 0,00	a22 = 0,09	a23 = 0,50	b2 ≥ 22%
Клетчатка	a31 = 0,00	a32 = 0,02	a33 = 0,08	b3 ≤ 5%
Стоимость (долл./фунт)	c1 = 0,12	c2 = 0,45	c3 = 1,60	min

Симплекс-метод

Является основным методом для решения задачи линейного программирования. Основан на том, что область точек пространства, удовлетворяющих линейным ограничениям, является многогранником, и максимум линейной функции должен достигаться в одной из вершин этого многогранника. На каждом шаге симплекс-метода происходит переход в соседнюю вершину с не худшим значением целевой функции. При компьютерной реализации алгоритма на вход нужно подать одномерный массив коэффициентов целевой функции c (его размерность совпадает с числом столбцов), двумерный массив коэффициентов системы ограничений a (размерность m×n), одномерный массив свободных членов (размерность совпадает с числом строк) и знак ограничений (=, ≥, ≤), а также способ оптимизации (на минимум или на максимум). На выходе программа найдет значения переменных x (одномерный массив с размерностью, равной числу столбцов).

См. также

• Каноническая задача линейного программирования
• Задача о назначениях
• Задача о распределении ресурсов
• Производственная задача
• Транспортная задача