Линейное Программирование это

Декабрь 20, 2016 – 13:52

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

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

f(x)= c_1x_1 + c_2x_2 + ... + c_nx_n → 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 = b2, \\ ... \\ 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 \ge 0, j = 1, …, 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

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

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

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

Вид корма	Известняк	Зерно	Соевая мука	Ограничение

Source: cyclowiki.org

Похожие публикации