Приведение задач линейного программирования к каноническому представлению

Алгоритм – точное описание последовательности действий при решении задачи. Для определения первого (опорного) решения необходимо перейти к каноническому представлению задачи, в котором все ограничения имеют форму уравнений (т.е. относятся к типу “=”).

Развернутая математическая формулировка общей задачи линейного программирования.

Пример. В соответствии с исходными данными сформулируем группу основных переменных:

x₁ - площадь посева зерновых культур

x₂ - площадь посева кормовых культур

x₃ - поголовье коров

x₄ - привес свиней

На все переменные накладывается условие неотрицательности.

Построим систему ограничений:

1. По площади пашни

2. По трудовым ресурсам

3. По денежным ресурсам

4. По балансу кормов (20% зерна)

Целевая функция – максимум чистого дохода:

Приведение задачи к каноническому виду осуществляется за счет прибавления к левой части или вычитания из левой части дополнительной переменной.

В ограничениях типа “ ” вычитают из левой части дополнительную переменную, называемую избыточной, ее значение показывает, насколько левая часть ограничения превышает правую, а с экономической точки зрения означает сверхплановое производство.

В ограничения типа “ ” прибавляют к левой части дополнительную переменную, называемой остаточной, показывающей насколько левая часть ограничения меньше правой, а с экономической точки зрения означает недоиспользованный ресурс.

Помимо избыточных и остаточных переменных в левой части ограничений типа “ ” и “=” вводят со знаком “+” еще дополнительные неотрицательные переменные, называемыми искусственными. В правильном решении они в ответ не входят, поэтому они вводятся таким образом в целевую функцию, чтобы алгоритм решения приводил автоматически к «обнулению» искусственных переменных. В задачах на max искусственные переменные вводятся в целевую функцию с большим оптимальным коэффициентом, при решении на min – с большим положительным знаком «+»; например: