Основная задача линейного программирования. Различные формы записи задачи

Рассмотрим следующую задачу.

На предприятии производится продукция n видов. Для этого используются ресурсы m видов, запасы которого на предприятии составляют, соответственно, b₁, b₂, …, b_m единиц. Известно, что на изготовление единицы j-й продукции требуется затратить a_ij единиц i-го ресурса, а также, что прибыль от реализации единицы j-й продукции равна c_j. Требуется найти план производства, при котором прибыль предприятия будет максимальной.

Пусть x_j – планируемое к выпуску количество j-й продукции. Тогда прибыль от реализации этой продукции составит z = c₁x₁+…+ c_nx_n. При этом 1-го ресурса для производства продукции 1-го вида потребуется a₁₁x₁, для производства продукции 2-го вида – a₁₂x₂ и т.д. Всего для претворения в жизнь выбранного производственного плана необходимо иметь 1-й ресурс в количестве a₁₁x₁+…+ a_1nx_n, которое по условию задачи не должно превышать имеющихся запасов в размере b₁ единиц. Аналогичные рассуждения справедливы по отношению ко всем видам ресурсов.

Таким образом, поставленную задачу можно записать в следующем виде:

z = c₁x₁+…+ c_nx_n → max (максимизировать общую прибыль)

a_i1x₁+…+ a_inx_n ≤ b_i, i=1,…,m; (ограничения на ресурсы) (1.1.1)

x_j ≥ 0, j=1,…,n. (количество не может быть отрицательным)

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

Для теоретических выкладок в задаче линейного программирования удобно использовать матричные обозначения. Пусть x^T = (x₁,…,x_n), c^T = (c₁,…,c_n), b^T = (b₁,…,b_m), A = (a_ij),

тогда задачу (1.1.1) можно записать в виде

z=c^Tx→max,Ax ≤b, (1.1.2),x ≥ 0.

Если ввести дополнительные переменные по правилуx_n+i = b_i - (a_i1x₁+…+ a_inx_n) ≥ 0, i=1,…,m,то задача примет вид

z=c^Tx→maх,Ax =b, (1.1.3),x ≥ 0,

где x^T = (x₁,…,x_n, x_n+1,…,x_n+m), c^T = (c₁,…,c_n,0,…,0), b^T = (b₁,…,b_m), A = ((a_ij)|E) – матрица А из (1.1.2) дополняется справа единичной матрицей Е.

Задача (1.1.2) называется основной задачей линейного программирования (ЛП). При этом (1.1.3) называется канонической формой записи задачи ЛП, ее характерный признак – среди ограничений задачи встречаются только простейшие неравенства, выражающие неотрицательность переменных. Задача (1.1.2) называется задачей ЛП в нормальной форме. В этой форме задачи среди ограничений нет равенств. Если в задаче есть и равенства, и неравенства, говорят о задаче в общей форме.

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

Покажем, что верно и обратно, т.е. задачу в канонической форме можно свести к задаче в нормальной форме. Это не только дает возможность рассматривать (1.1.2) и (1.1.3) не как две разные задачи, а как различные формы записи одной и той же задачи, но и, как будет видно в дальнейшем, позволит найти алгоритм ее решения.

Система ограничений Ax = b – это обычная система уравнений. А раз так, с ней можно делать все стандартные для систем уравнений действия: умножать обе части уравнений на ненулевые числа, заменять одно из уравнений линейной комбинацией уравнений.

При переходе к нормальной форме задачи наша цель – привести при помощи стандартных преобразований матрицу А системы уравнений Ax = b к такому виду, чтобы из ее столбцов можно было бы составить единичную матрицу (см. предыдущий пример). Другими словами, нужно выразить из системы максимально возможное число переменных (в большинстве случаев равное числу уравнений). После этого подставим найденные выражения для этих переменных в целевую функцию и в условия вида x_i ≥ 0, после чего в системе ограничений уменьшится количество переменных, и не останется ни одного равенства, т.е. задача будет приведена к нормальной форме.

Рассмотрим указанную процедуру более подробно.

Предположим, что в задаче (1.1.3) система Ax = b имеет бесконечное число решений, причем ранг матрицы А равен m < n, т.е. у матрицы А существует m линейно независимых столбцов. (Если же система Ах=b имеет единственное решение, то оно же будет и оптимальным, т.е. задача (1.1.3) перестает быть интересной с точки зрения оптимизации).

Обозначим матрицу, составленную из этих столбцов, через A_Б, матрицу, составленную из оставшихся столбцов, через А_Н. Тогда равенство Ax=b можно записать в виде

A_Бx_Б+A_Hx_H=b, (1.1.4),где x=(x_Б,x_Н) – координаты вектора x, умножающиеся на столбцы из матрицы A_Б, составляют его базисную часть x_Б, а остальные координаты вектора x (соответствующие столбцам из матрицы A_Н) составляют его небазисную часть x_Н.

Матрица A_Б по построению является невырожденной (т.к. ее столбцы линейно независимы), поэтому равенство (1.1.4) можно записать так:

x_Б+A_Б^-1A_Hx_H=A_Б^-1b. (1.1.5)

Заметим, что мы фактически выразили из системы уравнений переменные x_Б.

Базисные координаты вектора x (как и все остальные) неотрицательны, поэтому из (1.1.5) получаем условие

x_Б= A_Б^-1b – A_Б^-1A_Hx_H ≥ 0, или A_Б^-1A_Hx_H ≤ A_Б^-1b. (1.1.6)

Исключим базисные координаты и из целевой функции задачи (1.1.3):

z = c_Б^Tx_Б + c_Н^Tx_Н = c_Б^T(A_Б^-1b – A_Б^-1A_Hx_H) + c_Н^Tx_Н = c_Б^TA_Б^-1b +(c_Н^T– c_Б^TA_Б^-1A_H)x_H.

В результате получаем задачу в нормальной форме:

z = c_Б^TA_Б^-1b +(c_Н^T– c_Б^TA_Б^-1A_H)x_H → max

(A_Б^-1A_H)x_H ≤ A_Б^-1b, (1.1.7),x_H ≥ 0.

Если матрица A_Б является единичной, то задача (1.1.7) будет иметь следующий вид:

z = c_Б^T b +(c_Н^T– c_Б^TA_H)x_H → max,A_H x_H ≤ b, (1.1.8),x_H ≥ 0.

Заметим, что

1) выполнения условия A_Б = Е можно добиться как при помощи матричных методов, так и при помощи тождественных преобразований исходной системы уравнений Ax=b, например, методом Гаусса (при этом мы сохраняем за матрицей преобразованной системы обозначение А).

2) если известно, какие из переменных являются небазисными и чему равны их значения, то значения базисных переменных восстанавливаются из системы ограничений однозначно.

Таким образом:

-Задача в нормальной форме содержит ограничения только в виде неравенств. Для перехода к канонической форме используют дополнительные переменные (которые можно считать и называть базисными).

-Задача в канонической форме содержит ограничения только в виде равенств (если не учитывать условия неотрицательности переменных). Для перехода к нормальной форме часть переменных из задачи исключается. Эти переменные тоже называются базисными так же, как и добавляемые переменные в канонической форме задачи.

-Перечень базисных переменных определяется неоднозначно.

Поиск по сайту: