ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ

Примеры задач линейного программирования позволяют сформировать общую задачу линейного программирования. Дана система m  линейных уравнений и неравенств  с  n  переменными

α 11x1 + α12x2 + …+ α1n xn ≤ b1,

α 21x1 + α22x2 + …+ α2n xn ≤ b2,

α k1x1 + αk2x2 + …+ αkn xn ≤ bk,

α k +l,l + αk+1,2x2 + …+ αk+1,n xn = bk+1

α k+2,1x1 + αk+2,2x2 + …+ αk+2,n xn = bk+2

α m1x1 + αm2x2 + …+ αmn xn = bm

и линейная функция

F = c1 x1 + c2 x2 + …+ cn xn

F = Σcjxj → max (или min)

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

Σ αijxj ≤ bi(i = 1,2,…,k),

Σ αijxj ≤ bi(i =k + 1, k + 2,…,m),

Xj ≥0 (j = 1,2,…,l;l ≤ n).

Оптимальным решением задачи линейного программирования называется решения Х=(x1, x2,…,хj,…, xn) система ограничений удовлетворяющее условию, при котором линейная функция принимает оптимальное значение. Термины «решение» и «план» – синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй – о содержательной стороне (экономические интерпретации). При условии, что все переменные неотрицательны (Xj ≥0, j = 1,2,…,n), система ограничений состоит лишь из одних неравенств ,- такая задача линейного программирования называется стандартной, если система ограничений из одних уравнений, та задача называется канонической. Так, в приведенном выше примерах задач линейного программирования задачи 1 и 2 – стандартные, задача 4 – каноническая, а задача, а задача 3 – общая.

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

Ранг матрицы. Эквивалентные матрицы. Дана прямоугольная матрица.

α11 α12 … α1n

A = α21 α22… α2n

αn1αn2…. αnn

выделим в этой матрице к произведенных столбцов и к произведенных строк (k m, k n). Определитель которого порядка, составлений из элементов матрицы А, расположенных на пересечении выделенных строк и столбцов, называются минором которого порядка матрицы А. матрица А имеет

С · С миноров которого порядка.

Рассмотрим всевозможные миноры матрицы А,  отличные от нуля. Рангом матрицы А называется наибольший порядок минора этой матрицы принимают равным нулю. Всякий отличный от нуля минор матрицы, порядок которого равен рангу этой матрицы называется базисным минором матрицы. Ранг матрицы А будем обозначать через r(A). r(A) = r(B) , матрицы А и В называется эквивалентными. В этом случае записывают А ~ В. ранг матрицы не изменяется от элементарных приобретений. Под элементами преобразованиями понимается:

  1. замена строк столбцами, α столбцов соответственно строками;
  2. перестановка строк матрицы;
  3. вычеркните строки, все элементы которой равны нулю;
  4. умножение какой – либо строки на число не равно нулю;
  5. прибавление к матрицам одной строки соответствующих элементов другой строки.

Определить ранг матрицы

2 3 4

4 6 8

6 9 12

определитель матрицы второго и третьего порядка.

4 6                         1 2

М =      = 0;      М =          

6 9                          2 4

все миноры второго и третьего порядка равны нулю, следовательно, ранг матрицы  r (A) = 1

ПРИМЕР 2

1 0 0 0 5

0 0 0 0 0

2 0 0 0 11

Вычеркним строки и столбцы с нулевыми элементами, получим  матрицу эквивалентностью данной.

1 5

2 11     

 так как             1 5

= 0 = 1, то ранг матрицы r (A) = 2

2 11

Сколько миноров второго порядка имеет матрица

α11 α12 α13

А = α21 α22 α23

α31 α32 α33

С • С = 3·3 = 9 миноров второго порядка

Исследования систем  m линейных  уравнений с n неизвестными. Дана система m линейной уравнений с n неизвестными.

 α11 x1 + α12 x2 +…+ α1nxn  = b1

 α21 x1 + α22 x2 +…+ α2nxn  = b2

……………………………………………………..

α m1 x1 + αm2 x2 +…+ αmnxn  = bm

Матрица

α11 α12 … α1n

А = α21 α22 … α2n

………………….

α31 α32 …α3n

называется матрицей системы. Матрица

α11 α12 … α1n b1

А = α21 α22 … α2n b2

……………………..

αm1 αm2 …αmn bm

называется расширенной матрицей этой системы.

Для совместной системы необходимо и достаточно, чтобы ранг матрицы система равнялся рангу расширенной матрицы этой системы.

r(A) = r(A1) = r

Если  b = b2 = … bn = 0,  то система линейного уравнения называется однородной. Однородная система уровней всегда совместна. Если ранг совместной системы равен числу неизвестных (т.е. r = n), то система будет определенной. Если же ранг совместимой системы меньших числа неизвестных, то система неопределенная.

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

 Матричная форма записи:

F = CX → max (min)

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

АX = В,

X ≥ 0 

где

α11 α12… α1n                      x1                                    b1

α11 α11 … α11                     x2                      b2

С = (с12,…,сn); A = …………… ; X = …              B = …

α11 α11 … α11                      xn                      bm 

здесь С    матрица – строка, А – матрица систем, Х – матрица – столбец переменных, В – матрица – столбец свободных членов.

Векторная форма записи:

F = CX → max (min)

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

p1x1 + p2x2 + …+ pnxn = p

x   ≥ 0

где CX – скалярное произведение векторов С = (с12,…,сn) и

X = (x1,x2,…,xn),  векторы

α11                  α11                 α1n            b1

P1 = α11 , P2 = α11 , P1= α2n    , P1= b1

…           …            …              …

α11                 α11           αmn                    b1

состоят соответственно из коэффициентов при переменных и свободных членов. Векторное неравенство x ≥ 0 означает, что все компоненты вектора неотрицательны, т.е. x j≥ 0, j = 1,2,…,n.

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

Х1=(x1, x2,…, xn) и Х2=(x1, x2,…, xn) – два допустимых решения задачи, заданной в матричной форме. Тогда АХ1 = В и АХ2

Рассмотрим выпуклую линейную комбинацию решений Х1 и Х2, т.е. х = α1х1 + α2х2  при  α1≥0, α2 ≥0 и α1 + α2 = 1 и покажем, что она также является допустимым решением системы самом деле

AX = A(α1х1+ α2х2) = α1AX1 + (1 — α1) AX2 = α1B + (1 — α1)B = B, т.е. решение Х удовлетворяет систему. Но так как х1≥0, х2 ≥0 , α1 ≥0,
Α2 ≥0, то и х ≥0, т.е решение Х  удовлетворяет и условно. Итак, доказано, что множество всех допустимых решений задачи линейного программирования выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которое в дальнейшем будет называть одним термином – многогранником решений. Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме. В этом разложении среди значений
 F(xj)(j = 1,2,…,p) выберем максимальную. Пусть оно соответствует угловой точке  xк (1≤ k ≤ p); обозначим его через M , т.е. F(xк) = М.

Заменим в выражении каждое значение этим максимальным значением М. тогда, учитывая, что αj 0, Σ αj = 1,

F(x*) α1M + α2M + …+ αpM = M Σ αj =M.  Под  предположению оптимальное решение, поэтому, с одной стороны, F(x*)≥ F(xк) = М,

то с другой стороны, доказано, что F(x*) М, следовательно,

F(x*) = М = F(xк), где  xкугловая точка.  Итак, существует угловая точка xк , линейная функция принимает максимальное значение более чем в одной угловой точке, например, в точках

 X1, X2,…,Xq 1 q p ; F(X1,) = F(X2) = …= F(Xq) = M.

F(X) = F(α,X1 + α2X2 + …+ αqXq) = α1F(X1) + α2F(X2) + …+ αq F(Xq) = = α1M + α2M + …+ αqM = MΣαj = M,

т.е. линейная функция. F принимает максимальное значение в произвольной точке Х, является выпуклой линейной комбинацией угловых точек Х12,…,Хq.

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

Пусть Х1=(x1, x2,…, xm ;0,0,…,0) – допустимое базисное решение системных ограничений задачи, в котором первые m компонент – основные переменные, а остальные n – m компонент – не основанные переменные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х – угловая точка многогранника решений. Предположим противное, т.е. что Х не является угловой точкой. Точку Х можно представить внутренней точкой отрезка, соединяющего две различные не совпадающие с Х, точки

Х1=(x1, x2,…, xm ;0,0,…,0) и

Х2=(x1, x2,…, xm ;0,0,…,0)

другими  словами, — выпуклой линейной комбинацией точек x1 и x2 многогранника решений, т.е

X = α1 X1 + α2 X2

где α1≥0, α2≥0, α1 + α2 = 1 (полагаем, что α1 = 0, α2 = 0, ибо в противном случае точка Х  совпадает с точкой X1  или X2)

Запишим векторное равенство в координатной форме:

Х1 =  α1 X1 + α2 X2,

……………………..

Х1 =  α1 Xm + α2 Xm,

0 = α1 Xm+1 + α2 Xm+1,

………………………

0 = α1 Xn + α2 Xn

Поскольку xj≥0, xj≥0 (j = 1,2,…,n), x1>0, x2>0, то из последних n – m  равенств следует, что Xm+1 = 0,…, Xn = 0, Xn = 0, т.е. в решениях x1, x2 и х  система уравнений значения n – m компонент равны в данном случае нулю. Эти компоненты можно считать значениями не основных переменных. Но значения не основных переменных однозначно определяют значения основных, следовательно,

x1= x1 = x1,…, xm = xm = x2. Таким образом, все n  компонент в решениях х, x1 и x2 совпадают, и значит, точки x1  и x2 сливаются, что противоречит допущению. Следовательно, х – угловая точка многогранника решений. Докажем обратное утверждение. Пусть

Х =(x1, x2,…, xm ;0,0,…,0) угловая  точка многогранника решений и первые ее m  координат  положительны. Покажем, что х – допустимое базисное решение. Если векторы P1, P2,…, Pm  линейно независимы, то ранг r матрицы А,  составленной из компонент этих векторов, равен m, т.е. определить |А| ≠ 0, следовательно, переменные x1, x2,…, xm является основными, и  решение

Х =(x1, x2,…, xm ;0,0,…,0) – базисное, допустимое, т.е. утверждение доказано.

Предположим противное, т.е. векторы P1, P2,…, Pm  линейно зависимы, тогда в равенстве α1 P1 + αm Pm +…+ αn Pn = 0

Хотя бы один из коэффициентов α1,…, αm,…, αn  отличен от нуля. умножим почтенно равенство на множитель μ >0

 μ α1 P1 + …+ μ αm Pm +…+ μ αn Pn = 0

подставив координаты угловой точки Х  многогранника решений в системе ограничений, получим

р1 х1 + …+  рm хm +…+ рn хn = 0

Равенство  почтенно сложим с равенством, а затем вычтем его из равенства. Получим

P11 + μ α1) + Pmm + μ αm ) + Pn n + μ αm )= P

P11 — μ α1) + Pmm — μ αm ) + Pn n — μ αm )= P

Сравнивая полученные равенства с равенством, заключаем, что при любом μ система ограничений удовлетворяет решения

х1 = (х1 + μ α1,…, хm + μ αm; 0,0,…,0)

х2 = (х1 — μ α1,…, хm — μ αm; 0,0,…,0)

Поскольку xj≥0 (j = 1,2,…,n), то можно подобрать μ настолько малым, что все компоненты решений х1  и х2  будут неотрицательны.

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

½( х1 + х2) = (х1 ,х2,… хm; 0,0,…,0) = x, т.е.векторы Р1 , Р2 ,…, Рm линейно независимы и   x – допустимое базисное решение задачи. Из этого непосредственно вытекает важное следствие. Если задача линейного программирования имеет оптимальное решение, то оно совпадают, по крайней мере, с одним из ее допустимым базисных решений. Итак, оптимизм линейной функции задачи линейного программирования следует искать среди конечного числа и допустимых базисных решений.

Выпуклое множества точек определения как множество, которое вместе с любыми своими двумя точками содержит весь отрезок, их соединяющий. Однако в случае n переменных не ясно, что следует понимать под «отрезком» в n – мерном пространстве.  Очевидно, надо дать аналитическое определение этого понятия. Начнем с  n = 2 (двумерного пространства, плоскости). Пусть

x1 = (x1, x2) и x2 = (x1, x2) – точки плоскости  0x·1X2 а x = (x1, x2) – любая точка отрезка x1x2. Очевидно, что отношение α длин отрезков xx2  и x1x2 удовлетворяет условию 0 ≤ α ≤ 1. Запишем это отношение α через координаты точек.

Получим

α = x1 — x1/ x1 — x1 = x2 – x2/ x2 – x2

откуда

x1 = α x (1) + (1 – α) x1,

x2 = α x 2 + (1 – α) x2

где

0 ≤ α ≤ 1

Пологая

α1 = α и α2 = 1 – α, условия примут вид

x1 = α1x 1 + α2x1 ,

 x2 = α1x 2 + α2x2 ,

 α1 ≥0, α ≥0, α1 + α2 = 1

понимая, что в нем все операции выполняются покоординатное

(т.е. отдельно по переменной x1 и отдельно по переменной x2). Таким образом, отрезок x1x2  можно определить как множество  точек, удовлетворяющих условиям. В случае n – мерного  пространства определение отрезка будет таким же – множества точек, удовлетворяющих условиям если под x1 и x2 подразумевать  точки n – мерного пространства.

x1 = (x1, x2,…, xn)   и x2 = (x1, x2,…, xn)

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

Точка Х называется выпуклой линейной комбинацией точек x1, x2,…, xn, если выполнения условия

x = α1x 1 + α2x2 +…+ αnxn-n

αj ≥ 0 (j = 1,2,…,n), Σ αj = 1

Так, например, выражение (1/6) x 1 + (1/2) x 2 + ( 1/3) x 3 есть выпуклая линейная комбинация точек x 1, x 2, x 3, а выражения

(1/3) x 1 + (1/2) x 2 + ( 1/3) x 3 или (1/3) x 1 — (1/2) x 2 + ( 7/6) x 3 является линии, но не выпукление комбинации тех точек (в первом 1/3 + ½ + 1/3 ≠ 1, а во втором α2 = — 1/2 > 0).

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

Таким образом точка Х  есть выпуклая линейная комбинация угловая точек треугольника Х1Х2Х3. Из теоремы следует что выпуклой многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками множеством, не определяется однозначно своими условиями точками; любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

линии уровня широко используется, например, на картах прогнозы погоды, где извилистые линии – так называемые изо термы есть не что иное, как линии уровня температуры Т = с. Еще более простым примером линий уровня является параллель не географический карте. Это линии уровня широты. Предположим, надо найти самую северную точку какой – либо области, например страны или материка. Это будет точка, через которую проходит параллель с самой большой широтой. Именно так и надо поступать при геометрическом решении задач линейного программирования. На многоугольное решение следует найти точку, через которую проходит линия уровня функции F  с наибольшим или наименьшим уровнем. Уравнение линии уровня функции есть уравнение прямой линии. При различных уровнях α линии уровня параллельны, так как их угловые коэффициенты определения только соотношением между коэффициентами с1 и с2  и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные «параллели», расположенное обычно под углом к осям координат. Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении, в другую сторону – только убывает.

Дана система линейного уравнения

α1х1 + α 12х2 + …+ α 1nхn = b1

α 21х1 + α 22х2 + …+ α 2nхn = b2

……………………………………………………

α1х1 + α 12х2 + …+ α 1nхn = b1

α m1х1 + α m2х2 + …+ α mnхn = bm 

В матрице А  этой системы выберем отличий от нуля элемент αpq.  Этот элемент будет называется разрешающим элементом, р – й столбец разрешающий столбец, а q – я строка – разрешающая строка.

Рассмотрим новую систему уравнений

 α1х1 + α 12х2 + …+ α 1n хn = b1

α 21х1 + α 22х2 + …+ α 2n хn = b2

……………………………………………………

α1х1 + α 12х2 + …+ α 1nхn = b1

α m1х1 + α m2х2 + …+ α mnхn = bm

с матрицей А коэффициенты и свободные члены которой определяется по формулам.

αij = αij αip· αqj / αqp

, i≠q

bi = bi  — αipbq / αqp 

в частности   αip= 0,  если i ≠ q. Если же i = q,  то принимаем

 αqj = αqj, bq = bq. Таким образом q – е уравнение системе и одинаковы, а коэффициенты при хр  во всех уравнениях система, кроме  q – го уравнения, равны 0. Следует иметь в виду, что система и одновременно совместимы или несовместимы. В случае совместности система и равносильны. Для определения элемента

αij  матрицы А полезно иметь в виду так называется «правило прямоугольника». Рассмотрим 4 элемента матрицы А: αij(элемент, подлежащий преобразований) а  и элементы αip и αqj следует из элементов αij  вычесть произведение элементов αip  и αqj  расположенных  в противоположных вершинах прямоугольника, деленное на разрешающих элемент αqp :

αij……………….αip

  • ……………………………•

αqj                   αqp

Аналогичным  образом можно преобразовать система, приняв за разрешающий элемент матрицы А элемент asr ≠ 0, s ≠ 0, r ≠ p

После этого преобразования все коэффициенты при хr кроме asr будут равны нужно. Полученная система может быть слова преобразовано. Если  r = n,  то после ряда преобразований придем к системе уравнений вида:

к1 x 1 = l1,

к2 x 2 = l2,

…………

кn x n = ln  

из которой находятся значения неизвестных. Описанный способ решения, основанной на последовательном исключении неизвестных, называется способом Жордана – Гаусса.