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

α ₁₁x₁ + α₁₂x₂ + …+ α_1n x_n ≤ b₁,

α ₂₁x₁ + α₂₂x₂ + …+ α_2n x_n ≤ b₂,

α _k1x₁ + α_k2x₂ + …+ α_kn x_n ≤ b_k,

α _k +l,l + α_k+1,2x₂ + …+ α_k+1,n x_n = b_k+1

α _k+2,1x₁ + α_k+2,2x₂ + …+ α_k+2,n x_n = b_k+2

α _m1x₁ + α_m2x₂ + …+ α_mn x_n = b_m

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

F = c₁ x₁ + c₂ x₂ + …+ c_n x_n

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

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

Σ α_ijx_j ≤ b_i(i = 1,2,…,k),

Σ α_ijx_j ≤ b_i(i =k + 1, k + 2,…,m),

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

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

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

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

α₁₁ α_{12 …} α_1n

A = α₂₁ α_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

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

α₁₁ α₁₂ α₁₃

А = α₂₁ α₂₂ α₂₃

α₃₁ α₃₂ α₃₃

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

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

 α₁₁ x₁ + α₁₂ x₂ +…+ α_1nx_n  = b₁

 α₂₁ x₁ + α₂₂ x₂ +…+ α_2nx_n  = b₂

_{……………………………………………………..}

α _m1 x₁ + α_m2 x₂ +…+ α_mnx_n  = b_m

Матрица

α₁₁ α₁₂ … α_1n

А = α₂₁ α₂₂ … α_2n

………………….

α₃₁ α₃₂ …α_3n

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

α₁₁ α₁₂ … α_1n b₁

А = α₂₁ α₂₂ … α_2n b₂

……………………..

α_m1 α_m2 …α_mn b_m

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

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

r(A) = r(A₁) = r

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

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

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

F = CX → max (min)

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

АX = В,

X ≥ 0 

где

α₁₁ α_12… α_1n                      x₁                                    b₁

α₁₁ α_{11 …} α₁₁                     x₂                      b₂

С = (с₁,с₂,…,с_n); A = …………… ; X = …              B = …

α₁₁ α_{11 …} α₁₁                      x_n                      b_m 

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

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

F = CX → max (min)

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

p₁x₁ + p₂x₂ + …+ p_nx_n = p

x   ≥ 0

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

X = (x₁,x₂,…,x_n),  векторы

α₁₁                  α₁₁                 α_1n            b₁

P₁ = α₁₁ , P₂ = α₁₁ , P₁= α_2n    , P₁= b₁

…           …            …              …

α₁₁                 α₁₁           α_mn                    b₁

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

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

Х₁=(x₁, x₂,…, x_n) и Х₂=(x₁, x₂,…, x_n) – два допустимых решения задачи, заданной в матричной форме. Тогда АХ₁ = В и АХ₂=В

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

AX = A(α₁х₁+ α₂х₂) = α₁AX₁ + (1 — α₁) AX₂ = α₁B + (1 — α₁)B = B, т.е. решение Х удовлетворяет систему. Но так как х₁≥0, х₂ ≥0 , α₁ ≥0,

Α₂ ≥0, то и х ≥0, т.е решение Х  удовлетворяет и условно. Итак, доказано, что множество всех допустимых решений задачи линейного программирования выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которое в дальнейшем будет называть одним термином – многогранником решений. Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме. В этом разложении среди значений

 F(x_j)(j = 1,2,…,p) выберем максимальную. Пусть оно соответствует угловой точке  x_к (1≤ k ≤ p); обозначим его через M , т.е. F(x_к) = М.

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

F(x*) ≤ α₁M + α₂M + …+ α_pM = M Σ α_j =M.  Под  предположению оптимальное решение, поэтому, с одной стороны, F(x*)≥ F(x_к) = М,

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

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

 X₁, X₂,…,X_q 1≤ q ≤p ; F(X₁,) = F(X₂) = …= F(X_q) = M.

F(X) = F(α,X₁ + α₂X₂ + …+ α_qX_q) = α₁F(X₁) + α₂F(X₂) + …+ α_q F(X_q) = = α₁M + α₂M + …+ α_qM = MΣα_j = M,

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

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

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

Х₁=(x₁, x₂,…, x_m ;0,0,…,0) и

Х₂=(x₁, x₂,…, x_m ;0,0,…,0)

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

X = α₁ X₁ + α₂ X₂

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

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

Х₁ =  α₁ X₁ + α₂ X₂,

……………………..

Х₁ =  α₁ X_m + α₂ X_m,

0 = α₁ X_m+1 + α₂ X_m+1,

………………………

0 = α₁ X_n + α₂ X_n

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

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

Х =(x₁, x₂,…, x_m ;0,0,…,0) угловая  точка многогранника решений и первые ее m  координат  положительны. Покажем, что х – допустимое базисное решение. Если векторы P₁, P₂,…, P_m  линейно независимы, то ранг r матрицы А,  составленной из компонент этих векторов, равен m, т.е. определить |А| ≠ 0, следовательно, переменные x₁, x₂,…, x_m является основными, и  решение

Х =(x₁, x₂,…, x_m ;0,0,…,0) – базисное, допустимое, т.е. утверждение доказано.

Предположим противное, т.е. векторы P₁, P₂,…, P_m  линейно зависимы, тогда в равенстве α₁ P₁ + α_m P_m +…+ α_n P_n = 0

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

 μ α₁ P₁ + …+ μ α_m P_m +…+ μ α_n P_n = 0

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

р₁ х₁ + …+  р_m х_m +…+ р_n х_n = 0

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

P₁ (х₁ + μ α₁) + P_m (х_m + μ α_m ) + P_n (х_n + μ α_m )= P

P₁ (х₁ — μ α₁) + P_m (х_m — μ α_m ) + P_n (х_n — μ α_m )= P

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

х₁ = (х₁ + μ α₁,…, х_m + μ α_m; 0,0,…,0)

х₂ = (х₁ — μ α₁,…, х_m — μ α_m; 0,0,…,0)

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

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

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

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

x₁ = (x₁, x₂) и x₂ = (x₁, x₂) – точки плоскости  0_x·1X₂ а x = (x₁, x₂) – любая точка отрезка x₁x₂. Очевидно, что отношение α длин отрезков xx₂  и x₁x₂ удовлетворяет условию 0 ≤ α ≤ 1. Запишем это отношение α через координаты точек.

Получим

α = x₁ — x₁/ x₁ — x₁ = x₂ – x₂/ x₂ – x₂

откуда

x₁ = α x ₍₁₎ + (1 – α) x₁,

x₂ = α x ₂ + (1 – α) x₂

где

0 ≤ α ≤ 1

Пологая

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

x₁ = α₁x ₁ + α₂x₁ ,

 x₂ = α₁x ₂ + α₂x₂ ,

 α₁ ≥0, α ≥0, α₁ + α₂ = 1

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

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

x₁ = (x₁, x₂,…, x_n)   и x₂ = (x₁, x₂,…, x_n)

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

Точка Х называется выпуклой линейной комбинацией точек x₁, x₂,…, x_n, если выполнения условия

x = α₁x ₁ + α₂x₂ +…+ α_nx_n-n

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

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

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

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

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

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

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

α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

α ₂₁х₁ + α ₂₂х₂ + …+ α _2nх_n = b₂

_{……………………………………………………}

α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

α _m1х₁ + α _m2х₂ + …+ α _mnх_n = b_m 

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

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

 α₁х₁ + α ₁₂х₂ + …+ α _1n х_n = b₁

α ₂₁х₁ + α ₂₂х₂ + …+ α _2n х_n = b₂

_{……………………………………………………}

α₁х₁ + α ₁₂х₂ + …+ α _1nх_n = b₁

α _m1х₁ + α _m2х₂ + …+ α _mnх_n = b_m

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

α_{ij =} α_ij — α_ip· α_qj / α_qp

, i≠q

b_i = b_i  — α_ip∙ b_q / α_qp 

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

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

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

α_ij……………….α_ip

• _•
• _{………………………………•}

α_qj                   α_qp

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

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

к₁ x ₁ = l₁,

к₂ x ₂ = l₂,

…………

к_n x _n = l_n  

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