Общая ЗЛП.
Дана линейная функция
(1)
и дана система линейных ограничений:
(2)
(3) , j:= 1…n, где - заданные постоянные величины.
Найти такие неотрицательные значения , где j:= 1…n, которые удовлетворяют системе ограничений (2) и доставляют линейной функции (1) минимальные значения. Это и есть общая задача.
В системе ограничений (2) все можно считать неотрицательными.
Векторная форма ЗЛП:
(1) , где
(2*) ,
где и т.д.
(3)
Матричная формулировка:
AX=B и
Df: Планом, или допустимым решением ЗЛП называется вектор , удовлетворяющий условиям (2) и (3).
Df: План (X) называется опорным, если векторы , входящие в разложение (2*) с положительными коэффициентами , являющиеся линейно независимыми.
Так как являются n-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать n.
Df: Опорный план называется невырожденным, если он содержит m положительных компонент, в противном случае он вырожденный.
Df: Оптимальным планом, или оптимальным решением ЗЛП называется план, доставляющий наименьшее (наибольшее) значение линейной целевой функции, т.е. функции Z.
Там, где надо найти максимум значения Z достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней.
Геометрическая интерпретация задачи линейного программирования:
Рассмотрим задачу:
(1)
(2)
(3) , j:= 1…n
Совокупность удовлетворяет (2) – (3) является решением, если система (2) при условии (3) имеет хотя бы одно решение, то она совместная.
Рассмотрим на плоскости Х1ОХ2 совместную систему линейных неравенств:
, то есть n = 2.
Каждое неравенство этой системы определяет полуплоскость с граничными прямыми вида:
ai1 + ai2 bi (i = 1…m) и x1 = 0 , x2 = 0.
Система совместна, поэтому полуплоскости, пересекаясь образуют общую совокупность точек, координаты которой являются решением данной системы. Совокупность этих точек (решение) называется многоугольником решений.
Он может быть точкой, отрезком, лучом в неограниченном многоугольнике, областью.
Если n = 3, то речь пойдет о пространствах, многогранниках, плоскостях.
Если n > 3, то будут гиперплоскости и т.д.
Значит геометрическая ЗЛП представляет собой отыскание такой точки многогранника решений, координаты которого доставляют линейной функции min значение. При чём допустимым решением являются все точки многогранника решений.
Свойства решений ЗЛП:
Теорема 1.
Множество всех планов ЗЛП выпукло, т.е. если X1 и X2 - планы ЗЛП ((1) - (3)), то их выпуклая линейная комбинация так же есть план ЗЛП, т.е. X = λ1X1 + λ2X2,
λ1,2 0, λ1 + λ2 = 1.
Доказательство.
Т.к. X1 и X2 - планы, то выполняется следующее
A X1= A0, X1 0
A X2= A0, X2 0
AX = A(λ1X1 + λ2X2) = λ1A X1 + λ2A X2 = λ1 A0 + λ2 A0 =
= (λ1 + λ2) A0 = A0
Т.е. AX = A0, значит X – тоже решение, а значит удовлетворяет (2), т.к. X1 и X2 0,
λ1,2 0, то и X > 0, отсюда следует, что выполняется (2), а т.к. X > 0, т.е. выполняется (3),
то X - X > план ЗЛП. Теорема доказана.
Теорема 2.
1. Линейная целевая функция ЗЛП достигает своего min(max) в угловой точке множества решений.
2. Если линейная функция принимает min(max) в угловой точке m, то она достигает того же значения в любой другой точке, является выпуклой линейной комбинацией этих точек.
Доказательство.
1. Предположим, что многогранник решений ограниченный, имеющий конечное число угловых точек, обозначим его K . В двухмерном пространстве K имеет вид многоугольника. Обозначим угловые точки K через x1,x2,…,xp. x0 – оптимальный план.
Тогда
Z(x0) Z(x) для любых точек принадлежащих K.
Если x0 – угловая точка, то первая часть теоремы доказана.
Предположим, что x0 – не угловая точка, тогда на основе Теоремы(*)(о замкнутом ограниченном выпуклом многограннике) можно представить её как линейную комбинацию угловых точек., т.е.
x0 = , i := 1..p, =1
Т.к. Z(x) - линейная функция, то (▲)Z(x0) = Z() =
В (▲) среди чисел Z(xi) i=1…p выбираем наименьшее значение.
Пусть это происходит в т. xk, 1kp, т.е. Z(xk) =m
Заменим в (▲) каждое значение Z(xi) через m.
Тогда , т.к. и =1, то Z(x0)= = m() = m
Z(x0)m
Значит Z(x0)m, с другой стороны Z(x0) m
Это может быть, когда Z(x0) = m = Z(xk), существует угловая точка xk, в которой линейная целевая функция принимает min значение.
2. Для доказательства допустим, что Z(x) принимает min значение, более чем в одной точке, а именно в точках x1,x2,…,xq, 1qp, тогда Z(x1) Z(x2) Z(xq) = m
Если ч – выпуклая линейная комбинация этих угловых точек, т.е.
x = , =1, то
Z(x) = = m() = m
Т.е. Z принимает min значение в произвольной точке x является выпуклой линейной комбинацией угловых точек.
Замечание: Если многогранник решений является неограниченной областью, то не каждую точку области можно представить выпуклой линейной комбинацией угловых точек. В этом случае ЗЛП с неограниченной областью можно привести к задаче с ограниченной областью введением системы дополнительных ограничений. Х1+ Х2Q, где Q – достаточно большое. Введение этого ограничения равносильно отсечению гиперплоскостью Х1+ Х2Q от многогранника неограниченного ограниченного многогранника. И изменяя Q значение функции можно сделать как угодно малым, а это означает, что линейная функция неограниченна.
Теорема 3. Если известно, что система векторов А1,А2,…,Аk (kn) в разложении
(*),, j:= 1…n, то X(x1 ,…, xk ,0…0) является угловой точкой многогранника решений.
Доказательство.
Предположим, что x – не угловая точка, значит существуют x1 , x2 , принадлежащие многограннику решений, такие что x= x1+, где
λ1,2 0, λ1 + λ2 = 1
n-k компонент векторов x1 и x2 то же =0, т.е.
x1=(, 0…0) и
x2=(,0…0) планы и удовлетворяют (*)
Вычитаем x1 подставляем в (*) x2 подставляем и вычитаем
(-,-,…,-,0…0) = x1- x2
(-)А1+-А2+…+-Аk = (**)
По предложению А1… Аk – линейно независимы, значит(**) выполняется, когда все коэффициенты равны нулю, .те. =…=
Подставляем в (*)
Значит x не может быть представлена выпуклой линейной комбинацией двух различных точек, отсюда следует, что x – угловая точка. Теорема доказана.
Теорема 4. Если X=(x1,…, xn) есть угловая точка многогранника решений, то векторы в (*) А1… Аk соответствующие положительным xi являются линейно независимыми.
Доказательство.
Без ограничений общности можно предположить неравными нулю первые k компонент вектора X, тогда
Допустим , что А1… Аk – линейно независимы, тогда существуют такие l1…lk не все равные нулю, такие что
(1)
По условию
(2)
Зададим некоторое ε > 0 и умножим на него соотношение (1), сложим с (2)
(3)
но x1,…, xk >0, но можно взять ε настолько малым, что все коэффициенты в (3) будут положительными.
Поскольку x1 и x2 будут иметь положительные компоненты, тогда это планы, при этом
x1=( ,…, ,0…0)
x2=( ,…, ,0…0)
кроме того , т.е. - выпуклая линейная комбинация x1 и x2, что противоречит тому, что - угловая точка А1… Аk – линейно независимы. Теорема доказана.
Следствие 1: т.к. векторы А1…Аn в (*) имеют размерность m, то угловая точка многогранника решений имеет m положительных компонент.
Следствие 2: каждой угловой точке многогранника решений соответствует km линейно независимых векторов А1… Аk системы А1… Аn
Итак, если линейная функция задачи линейного программирования ограничена на многограннике решений, то существует такая угловая точка многогранника решений, в которой целевая функция достигает своего оптимума. Каждый опорный план соответствует угловой точке многогранника решений, поэтому для решения ЗЛП необходимо исследовать только угловые точки многогранника решений, т.е. исследовать только опорные планы.
Графические методы решений (ГМР).
ГМР основан на геометрической интерпретации ЗЛП. Применяется при решении задач двухмерного пространства, иногда трёхмерного пространства. При большом числе не представляется возможным.
Пусть ЗЛП задача в двухмерном пространстве.
ЛП. на геометрической интерпритерпритации (1)
(2)
(3)
Пусть система (1) при имеющихся условиях совместна и многогранник ограничен, каждое из неравенств (2)-(3) определяет полуплоскость с ограничивающимися прямыми:
, =0, =0.
Т.е. функция Z из (1) при фиксированном значении Z является уравнением прямой линии:
=const
Построим многоугольник решений и график Z, при Z=0.
ЗЛП получаем интерпретацию: найти точку многоугольника, в k-ом применении Z будет опорная и при этом Z достигает min. Строим N(C1,C2) – части производной. Z возрастает в направлении вектора N. Передвигая прямую Z параллельно самой себе в направлении N будем иметь, что т.А – является min, продолжая движение т.C – является max, т.е. доставляет max Z.
Многоугольник решений не ограничен.
Z передвигаясь в направлении N( или против) постоянно пересекает многоугольник решений никакого оптимума не получаем. Но это не всегда так, поэтому что область может располагаться по-разному.
С помощью графического метода может быть решена ЗЛП, система ограничений содержит n неизвестных и m линейно независимых уравнений, в таком случае, когда n-m=2. с помощью преобразований Гаусса система ограничений может быть приведена к следующему виду:
и решение можно представить в плоскости.
Основные Идеи Симплекс-Метода:
Существует такая угловая точка многогранника решений, в которой линейная функция достигает своего наименьшего (наибольшего) значения. Каждой угловой точке соответствует опорный план. Каждый опорный план определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1…Аn .
Для отыскания оптимального плана необходимо исследовать только опорные планы. Верхняя граница количества опорных планов, содержащихся в данной задаче определяется числом сочетаний , что при больших m и n делает нахождение плана методом перебора очень трудоёмким, (эти задачи относятся к классу NP) поэтому необходимо иметь схему, позволяющую осуществить упорядоченный переход от одного опорного плана к другому. Такой схемой является симплекс-метод, который позволяет исходя из известного опорного плана за конечное число шагов получить оптимальный план. Каждый из шагов итерации состоит в нахождении нового плана, которому соответствует меньшее значение, чем в предыдущем плане. Процесс продолжается до получения оптимального плана. Если задача не обладает оптимальным планом или линейная форма не ограничена на многограннике решений, то симплекс-метод позволяет установить это в процессе решения.
(1)
(2)
, для любых i и j
Содержит m единичных векторов (а именно первые m векторов). Тогда необходимо минимизировать (1). При следующих ограничениях:
(3) , j:= 1…n
Запишем (3) в векторной форме:
(4)
, , . . . ,, , . . . ,
А1…Аn – линейно независимые единичные векторы m-мерного пространства.
Они образуют базис, поэтому в (4) за базис можно взять именно их, а свободные неизвестные ,…, приравниваем к нулю и получаем первичный опорный план.
(5)
Плану (5) соответствует следующее разложение
(6)
в разложении (6) вектора (А1…Аm) линейно независимы построенный первоначально план является опорным.
Рассмотрим как исходя из плана (5) можно построить следующий опорный план. А1…Аm образуют базис, значит каждый из векторов (4) можно разложить по базису.
, j = m+1,..,n
Для некоторого вектора не входящего в базис, например для Am+1 положителен хотя бы один из коэффициентов разложения (xi,m+1). Тогда имеем:
(7)
Зададим некоторую величину θ>0 (пока неизвестную). Умножим на её обе части (7) и вычтем из (6), тогда получим:
Таким образом получим вектор:
(8)
будет являться планом, если его компоненты не отрицательны. Так как θ больше нуля, то все компоненты , в которые входят не положительные xi,m+1 ( i =1..m ), будут неотрицательными. Поэтому надо будет рассмотреть только компоненты, включающие положительные xi,m+1. Надо определить такое θ > 0 в котором для любых xi,m+1 вектор будет планом задачи для любого θ, удовлетворяющего условию θ>0, θ
Опорный план не может содержать m+1 положительную компоненту, поэтому в необходимо обратить в ноль по крайней мере одну из его компонент.
Положим θ = θ0 = min тогда та компонента плана (8), для которой достигается min обратится в нуль. Без ограничений общности можно считать, что она стоит на первом месте, т.е. θ0=, т.е. мы получили разложение:
Исключение первого вектора из базиса и включение в него другого с помощью θ0 соответствует переходу от одного базиса к другому по методу Жордана-Гауса. Поэтому вектора A2,…,Am+1 линейно независимы и являются новым базисом. Для определения следующего опорного плана необходимо любой вектор, не входящий в базис A2,…,Am+1 разложить по векторам этого базиса, а затем определить θ0, при котором исключался бы один из векторов этого базиса.
Т.о. процесс получения новых опорных планов заключается в выборе вектора, который подлежит включению и вектора для исключения. Критерий используемый для определения включаемого вектора является основным элементом симплекс-метода.
Если вектор Am+1 подлежит включению в базис, а в его разложение все xi,m+1 , то очевидно нельзя найти θ > 0, которое исключало бы один из векторов в разложении вектора . В этом случае план содержит m+1 положительных компонент, а система векторов A1,…,Am+1 линейно зависима, то план определяет не угловую, а внутреннюю точку многогранника решений, в котором линейная форма не достигает min, т.е гиперплоскость не может стать опорной, а линейная форма не ограничена на многограннике решений. Т.о. если система ограничений ЗЛП при неотрицательных свободных членах содержит единичный базис, то без дополнительных вычислений можно получить первоначальный опорный план, а так же коэффициенты разложения вектора по векторам базиса.
Условия оптимальности:
Пусть ЗЛП обладает планами и каждый её опорный план невырожден. В этом случае для опорного плана (5) мы будем иметь
(9)
(10) , >0, - значение линейной формы, соответствующей этому плану.
Разложение любого вектора по векторам базиса А1…Аm будет:
(11) , для j =1…n
(12)
Значение линейной формы, если в неё вместо неизвестных подставить соответствующие коэффициенты разложения j-вектора по векторам базиса.
Обозначим через коэффициенты линейной формы соответствующие вектору . Тогда справедлива следующая теорема.
Теорема. Если для некоторого вектора выполняется условие , то план не является оптимальным и можно построить такой оптимальный план x, для которого выполняется неравенство .
Доказательство. Возьмём и умножая (11) на (12) на и соответственно вычтем эти соотношения из (9) и (10). Получим
(13)
(14)
В (13) - положительные, поэтому всегда можно выбрать такое , чтобы все коэффициенты при А1…Аm , были неотрицательны, т.е. в этом случае получили новый план:
, который соответствует (согласно (14)) значению линейной формы (15) – условие оптимальности.
если для некоторого плана разложению всех векторов (j =1…n), удовлетворяющих условию (15), то план - оптимальный. Теорема доказана.
(15) – условие оптимальности плана задачи на отыскание min значения линейной формы, а значение называется оценкой плана. В решении задачи на max .
