Как следует из вышеприведенных примеров в рамках задач линейного программирования (ЗЛП) могут быть формализованы самые различные по своему содержанию задачи. Поэтому целесообразно более подробно рассмотреть основные свойства и алгоритм решения таких задач
В общем случае задача линейного программирования (ЗЛП) может содержать произвольное количество n переменных (элементов решения) и также произвольное количество m ограничений, т. е. равенств или неравенств. Рассмотрим такую задачу с ограничениями- неравенствами для случая отыскания max целевой функции.
(4.7)
………………………. (4.8)
(4.9)
Отметим, что в задачах линейного программирования должно выполняться соотношение
m<n,
т.е. количество ограничений должно быть меньше или равно количеству переменных.
Выражение (4.7) является целевой функцией модели, выражения (4.8)- ее ограничениями. Выражение (4.3) является стандартным (тривиальным) ограничением на неотрицательность переменных. В результате решения задачи (4.7- (4.9) должны быть найдены такие неотрицательные
Очень часто для решения задач линейного программирования используются стандартные программные средства, которые предназначены для ЗЛП определенной стандартной формы. Например, программа «RASKR 1» предназначена для решения задач линейного программирования для случая, когда ищется максимум целевой функции, а все ограничения являются равенствами. Если решается, например, задача оптимального раскроя древесно-стружечных плит на мебельные заготовки, в качестве критерия оптимальности используется выход заготовок и требуется точное выполнение спецификации по выпуску заготовок, то соответствующая этой задаче математическая модель будет удовлетворять сформулированным требованиям: целевая функция будет максимизироваться, а все ограничения по количеству получаемых заготовок запишутся в виде равенств. В общем же случае, например при работе по критерию минимума отходов, вид математической модели не будет соответствовать стандартной форме, необходимой для корректного ввода исходных данных в компьютер. Поэтому на этапе подготовки исходных данных для ввода в компьютер необходимо привести исходную математическую модель к стандартной форме. Для этого необходимо использовать следующие правила:
1. Чтобы перейти от минимизируемой целевой функции (типа «min») к максимизируемой (типа «max»), или наоборот, необходимо умножить все коэффициенты целевой функции на “–1”.
2.Чтобы перейти от ограничений-неравенств типа «>» к ограничениям неравенствам типа «<» (или наоборот), необходимо левую и правую части этого ограничения умножить на –1.
Прежде чем перейти к формулировке правил, позволяющих переходить от ограничений в виде неравенств к ограничениям в виде равенств, рассмотрим пример.
Пусть имеется ограничение
3+ 4≥ 10 , (4.10)
которое необходимо преобразовать в равенство. Очевидно, что выражение ( 4.10 ) можно записать следующим образом:
3+ 4= 10 + , (4.11)
где – новая дополнительная переменная, введение которой позволяет представить ограничение (4.12) в виде равенства. Физический смысл переменной прост: она показывает насколько левая часть ограничения (4.11) больше его правой части. Если левая часть равна 10, то = 0.
В моделях линейного программирования переменные всегда находятся в левой части ограничений, а в правой всегда записываются константа. С учетом этого перенесем переменную в левую часть. В результате выражение (4.11) примет следующий вид:
3+ 4– = 10 (4.12)
Таким образом, чтобы перейти от ограничения типа “≥” к ограничению типа “=” необходимо ввести еще одну, дополнительную переменную. Эта переменная включается в ограничение с коэффициентом “–1”, и имеет индекс на единицу больший чем, наибольший индекс исходного ограничения. Если имеется несколько ограничений, то дополнительны переменные необходимо ввести в каждое ограничение. При этом индекс дополнительной переменной, введенный в какое- либо ограничение должен быть на единицу больше чем индекс дополнительной переменной в предыдущем ограничении.
Аналогичным образом осуществляется переход от ограничений типа “≤” к ограничениям типа “=”. Однако в этом случае дополнительные переменные включаются в исходные ограничения с коэффициентом “1”.
Рассмотрим пример. Пусть имеется задача линейного программирования вида:
2+ 3– 1→ min (4.13)
1+ 5+ 4≤ 80 (4.14)
2– 4+ 5≥ 5 (4.15)
которую необходимо преобразовать к модели с ограничениями в виде равенств.
Введем дополнительные переменные: в неравенстве ( 4.14 ) –, причем с коэффициентом “+1” (т.к. неравенство имеет вид “≤”), а в (4.15) – с коэффициентом “–1” (неравенство имеет вид “≥”).
Функция цели (4.13) стремится к минимуму. Поэтому для перехода к целевой функции типа “max” умножаем все коэффициенты на “–1”. Кроме того, в целевую функцию вводим и дополнительные переменных и , с коэффициентами равными нулю. В результате получаем выражение для целевой функции:
(4.7)
(4.9)
+ 4
≥ 10 , (4.10)
, (4.11)
, причем с коэффициентом “+1” (т.к. неравенство имеет вид “≤”), а в (4.15) – 
с коэффициентом “–1” (неравенство имеет вид “≥”).