Eng | Rus | Ukr
Исследование операций
21.01.2005

<< prev | ^up^ | next >>

2.1. ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИССЛЕДОВАНИЯ ИХ СТРУКТУРЫ.

Большинство задач,  решаемых методами исследования операций, может быть сформулировано так:

   максимизировать                   F (x1, x2, ., xn)

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

g1(x1, ., xn) £ b1;

g2(x1, ., xn) £ b2;

.   .   .   .   .   .   .   .

gm(x1, ., xn) £ bm;

где f (x1, x2, ., xn)  - целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п.); X={x1,.,xn}-варьируемые параметры; g1(x),.,gm(x)-функции, которые задают ограничения на имеющиеся ресурсы.

Среди разных разделов математического программирования наиболее развитым и законченным  является линейное программирование (ЛП).

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

Рассмотрим некоторые из них. 

Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b1,  b2, . , bi, bm  и  n видов изделий. Задана матрица A=|| aij ||, i=1 ,.,m, j=1,.,n ,где aij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Эффективность производства j-го вида изделий характеризуется показателем Cj, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через xk,  Тогда математическая модель этой задачи будет иметь такой вид:

                                          максимизировать                     (2.1.1)

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

 ,                                 (2.1.2)

 i=, 2, ., m.

Кроме ограничений на ресурсы (2.1.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции     x j³ xj0 ,   xi : :xj : xk = bi : bj : bk  для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а1, а2, ., аm,  используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b1,  b2, . , bi, bn единиц. Заданы числа lij, указывающие, сколько единиц j-й работы можно получить из единицы і-го ресурса, а также   Cij - затраты на производство   j-й работы из единицы   i-го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты - минимальными).

Данная задача называется общей распределительной задачей. Количество единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через xij.

Математическая модель рассматриваемой задачи такова:

               минимизировать                                                    (2.1.3)

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

 j=1, 2, ., n,                       (2.1.4)

 i=1, 2, ., m .                          (2.1.5)

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

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

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k-го вещества

k = 1, 2, ., q, входящее в состав единицы і-го компонента и в состав единицы смеси, обозначим через аik и аk соответственно.

Предположим, что аk зависит от аik линейно, то есть если смесь состоит из x1 единиц первого компонента, x2 - единицу второго компонента и т.д., то

 .

Задано р величин Ci , характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин bk , указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через x1, x2,.,xр значение компонента р-го вида, входящего в состав смеси.

Математическая модель этой задачи имеет такой вид:

             минимизировать                                                                  (2.1.6)

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

 k=1, 2, ., q ,                    (2...1.7)

              

Ограничение (2.1.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше bk.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.

Задача о раскрое материалов. Пусть поступает в раскрой m различных материалов. Требуется изготовить из них k разных комплектующих изделий (комплектов) в количествах, пропорциональных величинам b1, b2, . , bk (условия комплектности). Пусть каждую единицу j-го материала j=1, ., m можно раскроить n различными способами, так что при использовании i-го способа раскроя, i=1, ., n получим аij единиц k-го изделия. Нужно определить такой план раскроя материалов, обеспечивающий максимальное количество комплектов, если имеющийся запас j-го материала составляет аj единиц.

Обозначим через xij количество единиц j-го материала, раскраиваемых i способом, а через x-общее количество изготавливаемых комплектов.

Математическая модель этой задачи имеет такой вид:

                                                 максимизировать х                       (2.1.8)

при условиях

                                    (2.1.9)

, .             (2.1.10)

Условие (2.1.9) означает ограничение на запас j-го материала, а (2.1.10) - условие комплектности.

Оптимальные балансовые модели. Рассмотрим n-отраслевую балансовую модель со постоянными технологическими коэффициентами, задаваемыми матрицей затрат  A=||aij||, где aij затраты продуктов i-й отрасли на производство единицы продукции j-й отрасли. Производственные мощности i-й отрасли ограничивают ее валовой выпуск величиной di (i = 1, ...,n), и пусть цена конечного продукта i-й отрасли составляет ci единиц.

Нужно определить оптимальный валовой выпуск продукции каждой отрасли, при котором будет достигнут максимальный суммарный выпуск конечного продукта в денежном выражении.

Обозначим вектор валовой продукции всех отраслей через x=[x1,.,xn],а вектор конечного продукта y=[y1,.,yn]. Тогда yi - объем продукции i-й отрасли, идущего на накопление.

Между векторами x и y существует следующая связь:

x = Ax+y,

где Ax -продукт, расходуемый на потребление. Отсюда

y=x [E-А], x=[E-A]-1y

Математическая модель этой задачи имеет вид

максимизировать cTy=

при условиях

x=[E-A]-1y £ d , y³0;

Кроме того, в этой задаче можно дополнительно использовать такие, например, ограничения на конечные продукты:

а) y1:y2:.:yn=b1:b2:.:bn-условие комплектности;

б) di ³ yi³ bi - условие ограниченности выпуска конечного продукта.

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

                                  максимизировать                                (2.1.11)

при условиях

a11x1 + a12x2 + . + a1nxn £ b1 ;

a21x1 + a22x2 + . + a2nxn £ b2 ;

. . . . . . . . . . . . .

am1x1 + am2x2 + . + amnxn £ bm ;                 (2...1.12)

x1 ³ 0, x2 ³ 0, ., xn ³ 0,                        (2...1.13)

Ограничения (2.1.13) называют условиями неотрицательности переменных.

В рассматриваемом случае все ограничения имеют вид неравенств.

Иногда они могут быть смешанными, то есть неравенства и равенства:

a11x1 + a12x2 + . + a1nxn £ b1 ;

a21x1 + a22x2 + . + a2nxn £ b2 ;

. . . . . . . . . . . . .

am1x1 + am2x2 + . + amnxn £ bm ;

am+1,1x1 + am+1,2x2 + . + am+1,nxn = bm+1 ;             (2.1.14)

ak1x1 + ak2x2 + . + aknxn = bk .

Если все ограничения задачи ЛП имеют вид строгих равенств

a11x1 + a12x2 + . + a1nxn = b1 ;

a21x1 + a22x2 + . + a2nxn = b2 ;

. . . . . . . . . . . . .

am1x1 + am2x2 + . + amnxn = bm ;                 (2...1.15)

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

В матричной форме задача ЛП записывается следующим образом:

                                         максимизировать cTx                                         (2.1.16)

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

Ax £ b ;

x ³ 0,                                          (2.1.17)

где А - матрица ограничений размером (т x п); b(m*1) - вектор-столбец свободных членов; x(n*1) - вектор переменных; с=[c1, c2,.,cn]-вектор (строка) коэффициентов целевой функции

В векторной форме ограничения (2.1.14) записывают так:

A1x1 + A2x2 + . + Anxn £ b,                    (2...1.18)

Допустимым множеством решений задачи (2.1.11)-(2.1.13) назвается множество R(х) всех векторов x, удовлетворяющих условия (2.1.12) и (2.1.13).

Множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Решение x0 называется оптимальным, если он удовлетворяет условию

cTx0³cTx,

для всех х Î R (х).

Поскольку поиск min f(х) эквивалентен поиску мах[-f(х)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.

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

Рассмотрим такой пример:

максимизировать (4Х1 + 3Х2 ) = Z

при условиях

Х1 £ 4000; Х2 £ 6000; Х1 + 2/3Х2 £ 6000; Х1, Х2 ³ 0

Х1

 

Х2

 
 

Z1

 

Zmax

 
 
 
 

А

 

В

 

С

 
 

Рис. 2.1.

Каждое из этих неравенств определяет полуплоскости, пересечение которых дает многоугольник, заштрихованый на рис. 2.1. Этот многоугольник (выпуклый многогранник) и представляет собой допустимое множество решений R(x1, x2) задачи ЛП. Теперь рассмотрим целевую функцию

f (x1, x2) = 4х1 + 3х2,

пусть ее значения

f (x1, x2) =12000=Z1.

График уравнения 4х1 + 3х2=12000 - прямая с отрезками на осях x1=3000; x2=4000.

 .

При f(x1,x2) =24000 получим прямую z2,

Прямая z2 параллельная прямой z1, но расположена выше от нее. Передвигая прямую z вверх параллельно самой себе, приходим к такому ее положению, когда прямая и множество R будут иметь только одну общую точку А.

Очевидно, что точка А ( x1=2000; x2=6000) - оптимальное решение, так как она лежит на прямой с максимально возможным значением zmax . Заметим, что эта точка оказалась крайней точкой множества R.

При векторной форме ограничения задачи ЛП записываются так:

A1x1 + A2x2 + . + Anxn £ b,                     (2...1.18)

где

.;

 
  .,  

Рассмотрим допустимое множество A1, A2,.,An в пространстве данных векторов. Поскольку в формуле (2.1.18) хі³0, i = 1,2, ..., n,  то  все  положительные комбинации векторов  A1, A2,.,A образуют конус ( см.  приложение 1 ).Поэтому  вопрос о существовании допустимых решений равнозначен вопросу о принадлежности вектора b этому конусу. Поскольку A1, A2,.,A m-мерные векторы (n > m), то среди них всегда обнаружится m линейно-независимых векторов, образующих базис m-мерного пространства и содержащих конус, образованный векторами A1, A2,.,An...

Поэтому справедливо следующее утверждение. Если задача ЛП содержит n переменных и m ограничений, записанных в форме неравенств (n > m), не считая ограничений неотрицательности переменных xi³0, то в оптимальное решение входит не более чем m ненулевых компонент вектора x.

Расширенная форма задачи ЛП. Для решения задач ЛП необходимо переходить от ограничений - неравенств к ограничениям в форме уравнений. Для этого в каждое неравенство вводят по одной свободной переменной xn+1³0, xn+2³0,.,xn+m³0,чтобы превратить его в равенство. В таком виде задачу ЛП называют расширенной и записывают так:

максимизировать

f(x1, x2, ., xn)=c1x1+c2x2+.+cnxn+0xn+1+.+0xn+m                 (2...1.19)

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

a11x1 + a12x2 + . + a1nxn + 1xn+1 + 0xn+2 + . +0xn+m= b1 ;

a21x1 + a22x2 + . + a2nxn + 0xn+1 + 1xn+2 + . +0xn+m= b2 ;

. . . . . . . . . . . . . . . . . . . . . . . . . .

am1x1 + am2x2 + . + amnxn + 0xn+1 + 0xn+2 + . +1xn+m= bm ...

В матричной форме эта задача имеет следующий вид:

                                          максимизировать cTx

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

Am×nx1 + Em×mx2 =b;

где

X2

 
                         (2.1.20)

Наконец, векторная форма записи расширенной задачи ЛП:

                                     максимизировать cTx

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

A1x1 + A2x2 + . + Anxn +An+1xn+1 +.+ An+nxn+m= b.           (2.1.21)

                .

               

Text Box: 
Рис. 2.1.
Text Box: 
Рис. 2.2.

               Рис.2.2                                               Рис.2.3

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

Установим отношение между элементами R и R1:

исходная задача           расширенная задача

       x1 + x2 £ 500                   x1 + x2 + x3 = 500.

На рис. 2.2 и 2.3 изображены допустимые множества решений обеих задач. Очевидно, что треугольник ОСА (рис. 2.2) - допустимое множество R - есть проекция допустимого множества R1 (рис.2.3) на подпространство x1 È x2.

В общем случае допустимое множество решений исходной задачи R есть проекция допустимого множества решений расширенной задачи R1на подпространство исходных переменных x1 È x2.

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

1x1 + 1x2 £ 5; 1x1 + 1x2 + 1x3 = 5;

3/2x1 + 1x2 £6; 3/2x1 + 1x2 + 0x3 + 1x4 =6;

x1, x2, x3, x4 ³0;

Обозначим

 ; ; ; ; .

Из векторов A1,A2,A3,A4 можно образовать шесть базисов:

{A1, A2}; {A1, A3}; {A4, A3} и т. д.

Для каждой из этих матриц найдем обратную матрицу B-1.

Умножив B-1 на A0, получим решения, назваемые базисными:

(x1=2, x2=3);

(x1=4, x3=1);

(x1=5, x4=-3/2);

(x2=6, x3=-1);

(x2=5, x4=1);

(x3=5, x4=6).

Допустимые базисные решения

Пусть ограничения задачи ЛП задан в форме равенств (уравнений)

A(m´n)x(n´1) = b(m´1) ,                                                                 (2.1.22)

Предположим, что m<n и ранг матрицы А равен m. Выберем из матрицы A=[A1,.,An] m линейно-независимых столбцов, которые обозначим через B(m*m). Матрица В образует базис системы. Совокупность оставшихся столбцов матрицы А обозначим через D. Тогда А = [В, D]. Совокупность переменных, связанных с матрицей В, обозначим через xВ, а связанных с матрицей D - через xD. Тогда

Ax = BxВ + DxD .                                                             (2.1.23)

Поскольку В - невырожденная квадратная матрица, то существует обратная к ней B-1. Умножив обе части (2.1.23) на B-1, получим

B-1BxВ + B-1DxD = B-1b .

Отсюда

xВ = B-1b - B-1DxD .                                (2.1.24)

Переменные xВ- базисные, а xD - небазисные.

Соотношения (2.1.24) определяют полное множество решений системы линейных уравнений (2.1.22). В развернутом виде эти соотношения можно записать так:

 xj = αj,  jÎJнеб,                                                    (2.1.25)

где Iб - множество индексов базисных векторов; Jнеб - множество индексов небазисных векторов; ai0 - i - тая компонента векторов B-1b; aij (j Î Jнеб) - строка матрицы B-1D, αj - произвольный скаляр. Если положить для всех небазисных переменных нулевые значения, то получим базисное решение системы уравнений (2.1.22).

Очевидно, в этом случае xi=ai0, iÎІб. Если базисное решение удовлетворяет условию неотрицательности, то оно называется допустимым (ДБР).

Если среди компонент xi, иÎIб нет нулевых, то базисное решение называется невырожденным.

Основные теоремы линейного программирования.

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

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

Теорема 2.1. Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R1, то она принимает это значение в крайней точке R1. Если целевая функция принимает максимальное значение более, чем в одной крайней точке, то она принимает это же значение в любой их выпуклой комбинации.

Доказательство. Будем считать, что R1- выпуклый многогранник. Доказательство основано на следующей лемме.

Лемма. Если R1- запертое ограниченное выпуклое множество, имеющее конечное число крайних точек, то любая точка xÎR1 может быть представлена в виде выпуклой комбинации крайних точек R1. (доказательство см. в приложении І).

Обозначим крайние точки через x1, x2,.,xm  ,а точку, в которой f(х) достигает максимума, через xопт.

Предположим, что xопт- не крайняя точка. Тогда в соответствии с леммой 1.1(см. приложение 1)

  ki³0, и=1, 2, ., m.

Так как xопт- оптимальной решение, то сTxопт³cTx.

Функция - f(х) линейная, поэтому

f( ) =

Поэтому

cTxопт= cTxr,  (2.1.26)

где через сTxr обозначено {сTxi}. Итак

cTxопт£ cTxr                                   (2.1.27)

Однако xопт - оптимальное решение, и потому

cTxопт³ cTxr                                   (2.1.28)

Сравнив (2.1.28) с (2.1.27), получим cTxr = cTxопт, то есть существует ,по крайней мере, одна крайняя точка xr, где целевая функция принимает  максимальное значение. Итак, первая часть теоремы доказана.

Докажем вторую часть теоремы. Допустим, что оптимальные решения находятся в крайних точках x1,.,xs. Тогда их произвольная выпуклая комбинация определяется как:

                                (2.1.29)

где

    , ki³0 .

Найдем значения целевой функции

f(x*) = cTx* = .                      (2.1.30)

Так как точки xi, i=1,.,s   отвечают оптимальным решениям, то

cTxi = cTxопт ,                                                                                               

для всех                                     i=1,.,s.                                                (2.1.31)

Подставляя (2.1.31) в (2.1.30), получим

f(x*) = cTxопт =cTxопт .                                                             (2.1.32)

Итак, теорема доказана.

Из теоремы 2.1 следует, что для поиска оптимального решения достаточно просмотреть только крайние точки допустимого множества решений.

Докажем, что всегда можно найти крайние точки, выделяя только допустимые базисные решения.

Теорема 2.2. Если существует такое независимое множество m - мерных векторов A1, A2, ., Ak (K £ m) , что A1x1 + A2x2 +.+Akxk=A0 ,  

xi ³ 0, i=1, 2, ., m, то n-мерный вектор х=(x1,.,xk,)есть крайняя точка допустимого множества R1.

Иными словами каждое допустимое базисное решение соответствует некоторой крайней точке R1.

Доказательство проводим от противного, то есть предположим, что х - не крайняя точка R1. Тогда x=kx1+(1-k)x2, 0 < k <1, где x1 и x2 - крайние точки R1.

Поскольку последние (n-К) компоненты х в соответствии с условиями теоремы равны нулю, то эти же компоненты векторов x1 и x2 также равны 0. Поэтому

A1x11+A2x21+.+Akxk1=A0 ;                         (2.1.33)

A1x12+A2x22+.+Akxk2=A0.                          (2.1.34)

       Вычитая из уравнения (2.1.33) уравнение (2.1.34), получим

A1(x11-x12) + A2(x21-x22) +.+Ak(xk1-xk2)=0.               (2.1.35)

Так как векторы A1, A2,.,Ak-линейно независимы, то x11-x12=0, x21-x22=0, xk1-xk2=0, что возможно только в том случае, если x1=x2. Это противоречит предположению, что x1 и x2 разные крайние точки множества R1.

Справедлива следующая теорема, обратная теореме 2.2.

Теорема 2.3. Если х0T=(x1(0),.,xk(0),0,.,0)-крайняя точка допустимого множества решений R, то соответствующее решение x0 является допустимым базисным решением системы ограничений (2.1.22).

Доказательство теоремы простое и приводится в [23].

Вывод. Используя результаты теорем 2.1 - 2.3, можно сделать вывод, что для нахождения оптимального решения задачи ЛП достаточно просмотреть (перебрать) лишь ее допустимые базисные решения. Этот вывод лежит в основе многих методов решения задач линейного программирования.

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

Если общее число переменных задачи ЛП  n = 2 или она может быть сведена к соответствующей задаче с числом независимых переменных

k = 2, то такую задачу легко решить графическим методом.

Итак, пусть задача ЛП имеет вид

   максимизировать  f(x1,x2)=(c1x1 + c2x2)                (2.1.36)

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

g1(x1, x2) £ b1;

g2(x1, x2) £ b2;

. . . . .

                                                   gm(x1, x2) £ bm;                         (2.1.37)

                                                   x1 ³ 0, x2 ³ 0 .                          (2.1.38)

Графический метод решения состоит из следующих шагов.

1. Строим допустимое множество решений R, определяемое (2.1.37) и (2.1.38).

2. Далее строим вектор нормали N к целевой функции f(x1,x2). Его проекция на ось  Ox равна  kc1,  и  на  ось  Ox -  kc2,  где  k  - произвольный  положительный скаляр.

      

                                                            Рис.2.4

3. Перемещаем прямую f(x1,x2)=const в направления N так, чтобы она оставалась перпендикулярной  N до тех пор, пока эта прямая не выйдет на границу множества R.

При этом возможен один из следующих случаев:

а) f(x1,x2) и R имеют лишь одну общую точку (которая обязательно является крайней); эта точка определяет единое оптимальное решение;

б) f(x1,x2) и R имеют целое множество общих точек - это будет в том случае, когда вектор N окажется нормален к соответствующей грани множества R, а данное множество общих точек представляет собой множество оптимальных решений задачи;

в) прямая f(x1,x2) = const не выходит на границу множества R, сколько бы мы ее не перемещали - это будет в том случае, если множество R -неограниченно, тогда целевая функция f(x1,x2) оказывается также неограниченной.

Соответствующие случаи иллюстрируются рис. 2.4 а, б, в.

Заметим, что при решении задачи минимизации прямую f(x1,x2) перемещают в направлении, противоположном  N.

Рассмотрим теперь общий случай задачи ЛП:

                                максимизировать

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

 i=1, 2, ., m, xj³0 .

Если k = п-r = 2, где r - ранг матрицы А, то эту задачу также можно решить графическим методом.

Действительно, на основании общих соотношений (2.1.25) все базисные переменные xj можно выразить через две небазисные переменные xj1 и xj2:

x1 = j1(xj1, xj2) ³ 0;

x2 = j2(xj1, xj2) ³ 0;

. . . . . . . .

xr = jr(xj1, xj2) ³ 0.                                  (2.1.39)

Подставляя в целевую функцию выражения (2.1.39), приходим к следующей задаче:

             максимизировать  f(x1,.,xn)=f(ji(xj1,xj2)iÎ, xj1, xj2)               (2.1.40)

                        при ограничениях (2.1.39) и xj1 ³ 0; xj2 ³ 0.                     (2.1.41)

Как видим, задача (2.1.40) легко решается графически.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004