Глава 4. Задача линейного программирования и ее оптимальное решение

4.1. Определение линейности функций

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

Линейной называется комбинация скаляров или векторов, обычно обозначаемых Х_i, если она может быть записана в виде:

с₁Х₁+с₂Х₂+…+с_nХ_n

где c_i – const. Например, функция:

4х₁+3х₂+5х₃+2

линейна относительно переменных х₁, х₂, х₃ , тогда, как функция

2х₁²+х₁х₂+3

нелинейна относительно тех же переменных

Величины Х₁, Х₂, …, Х_n – называются линейно зависимыми, если для некоторого набора коэффициентов c_i в предположении, что не все они равны 0, имеет место следующее равенство:

c₁Х₁+c₂Х₂+ … +c_nХ_n=∑c_iХ_i=0.

Например, линейно зависимыми будут Х₁ и Х₂, если Х₁ – цена единицы товара, а Х₂ – выручка от продажи партии этого товара.

С другой стороны, если ∑c_iX_i=0 только тогда, когда все коэффициенты c_i =0, то Х₁, Х₂, …, Х_n называются линейно независимыми..

К ЗЛП относят планирования промышленного производства, системы оплаты контрактов, распределение кадров, получение мах прибыли и др.

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

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

Хотя задача линейного программирования может быть сформулирована по разному, запишем ее в следующей форме :

максимизировать функцию

n

Y

i=1

=∑ c_ix_i (4.2.1)

при ограничениях

a_ijx_i - b_j ≥ 0, (j=1,...,m); (4.2.2)

x_i ≥ 0, (i=1,...,n); (4.2.3)

где а, b, c – постоянные коэффициенты, а x_i – искомые переменные.

Отметим, что задача максимизации Y легко превращается в задачу минимизации при смене знака в целевой функции (4.2.1.):

n

Y

i=1

= –∑ c_ix_i . (4.2.4)

Пример. Приведем пример постановки типичной ЗЛП.

Определить неотрицательные значения х₁, х₂ и х₃, соответствующие максимуму функции у=3х₁+5х₂+4х₃ при наличии следующих ограничений:

2х₁+3х₂≤8,

2х₂+5х₃≤10,

3х₁+2х₂+4х₃≤15.

Задача линейного программирования, представленная в виде (4.2.1), (4.2.2), (4.2.3) называется стандартной формой ЗЛП. Особенность данной формы состоит в том, что в ней система функциональных и прямых ограничений состоит из одних неравенств, переменные x_i ≥ 0 являются положительными, а целевая функция может стремиться как к минимуму, так и к максимуму. Вектор Х = (х₁, х₂,…,х_n), удовлетворяющий системе ограничений (4.2.2), (4.2.3) называется допустимым решением, или планом ЗЛП, т.е. ограничения (4.2.2), (4.2.3) определяют область допустимых решений, или планов (область определения ЗЛП)

Если математическая модель ЗЛП имеет вид

n

Y

i=1

=∑ c_ix_i → min; (4.2.5)

n

∑

i=1

a_ijx_i = b_j,_, (j=1, ..., m); (4.2.6)

b_j, ≥ 0;

x_i ≥ 0, (i=1, ..., n); (4.2.7)

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

Любую задачу линейного программирования можно свести к ЗЛП в канонической форме. Общее правило приведения ЗЛП к каноническому виду состоит в следующем:

1. если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум на этой функции;

2. если в ограничениях правая часть отрицательна, то следует умножить это ограничение на –1;

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

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

х_k = х^'_k – х^''_k , х^'_k ≥ 0, х^''_k ≥ 0.

В преобразованной задаче все переменные неотрицательные.

Переход от стандартной формы ЗЛП к канонической. Разнообразие форм ЗЛП затрудняет исследование их общих особенностей и создание общих методов и вычислительных алгоритмов для их решения. Поэтому естественно рассмотреть способ сведения любой ЗЛП к наиболее простой и удобной для исследования форме — канонической.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (4.2.2) k-й дополнительной переменной x_n+k ≥ 0 со знаком «–» в случае ограничения типа ≥ и со знаком «+» в случае ограничения типа ≤. Дополнительные переменные x_n+k называются выравнивающими балансовыми переменными. Добавив эти выравнивающие переменные в неравенства, превращаем их в уравнения.

Пример. Пусть задача линейного программирования задана в стандартной форме: Y = 2х₁+3х₂ → max

при ограничениях:

х₁+3х₂ ≤ 18,

2х₁+х₂ ≤ 16,

х₂ ≤ 5,

3х₁ ≤ 21,

х₁ ≥ 0, х₂ ≥ 0.

Запишем эту задачу в каноническом виде, для чего обратим имеющуюся систему неравенств в равенства, вводя для этого в каждое из них соответствующую неотрицательную выравнивающую переменную:

х₁+3х₂ + х₃ =18,

2х₁+ х₂ + х₄ =16,

х₂ + х₅ =5,

3х₁ + х₆ =21.

В данном примере все дополнительные переменные введены со знаком «+», так как рассматриваемые неравенства имеют знак « ≤ ».