Формы записи задач ЛП
Общей задачейЛП назыв.задача
кот.сост.в опред-ии max(min)значен.фу-ии.
f=c1x1+c2x2+..+cnxn->max(n)
f=j=1ncjxj→max(min)
при вып.усл.j=1naij*xj≤bi(i=1r)
j=1naij*xj=bi(i=x+1,m)
3xj≥0j=1,k,1≤n
Функция(1)назыв.целевой ф-ей,а условий 2,3 назыв.ограничениями данных задач
Лин-ое програм-е — раздел матем-ого программ-я, прим-й при разработке методов отыскания экстремума линейных функций неск-х перем-ых при лин-х допол-х огранич-х, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного програм-я явл-я то, что экстремума целевая фун-я достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений.
Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).
Теорема. Если система векторов содержит m линейно независимых векторов, то допустимый план
является крайней точкой многогранника планов.
Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.
Общ.станд.и осн.формы записи задачи лин.прогр.правила перехода от одной формы записи к другой
Общей зад-й ЛП наз-ся задача кот.сост в опр-и max(min)знач-я фу-и
Ф-я наз-яцелев-й ф-ей или линейной формой задачи лп а усл.2,3 назыв.огранич-ми данных задач.Стандарт-и или симметр-и зад.лп назыв зад.кот сост.в отискании maxзн-я ф-ии при вып усл-й F=j=1ncjxj→max
j=1naijxj≤bj(i=1m)
xj≥0(j=1n)
канонич.зад.лп или осн.зад.лп явл.задача,кот.сост.в опр.min значения целевой ф-ии и вып.усл.f=j=1ncjxj→min
j=1naijxj=bi(i=1,m)
x=0(j=1,n)
правила перехода если F→max f=F→min
4.векторная форма записи зад.лп.опорн.невырожденный и оптим.планы задач лп.
Опорным планом задачи лп f=c1x1+c2x2+..+cnxn->min
a11x1+a12x2+..+a1nxn=b1
a21x1+a22x2+..a2nxn=b2
..
планом или допустим.решением задачи Лп наз.х ⃗ кот.удовл.сист.огранич-й2*
Планом х наз.опорным,если векторы Аj(j=(1,n)) ̅входящ.в разлож 2*явл.линейнонезависим-и,если при них наход.+коэфф.хj>0
Замечание Аj-m-мерные
Опорный план явл.невырожденным если он содержит ровно m+компонентов в противн.случае план вырожден
Оптимальным планом задачи лп наз.план при кот.целевая ф-я принимает min (max)значения
Решение системы лин.неравенств.понятие о многоугольнике и многограннике.реш.зад.лп
Линейные неравенства и системы линейных неравенств с одним неизвестным
Под линейными неравенствами понимают неравенства вида
ax+b>0, ax+b<0, ax+b≥0, ax+b≤0,
где a и b - действительные числа (a/=0).
Линейные неравенства решают заменой исходного неравенства ему эквивалентным. При этом используются следующие преобразования неравенств, приводящие к эквивалентным неравенствам: прибавление к обеим частям неравенства одного и того же числа и умножение (деление) обеих частей неравенства на одно и то же число. Так, множество решений неравенства
ax+b>0 (1)
может быть найдено следующим образом:
Прибавим к обеим частям неравенства (1) число −b, в результате чего получим эквивалентное неравенство
ax>−b (2)
и разделим обе части неравенства на a. Тогда:
1) Если a>0, то получаем неравенство
x>−ab,
которое и дает множество решений исходного неравенства (1). Это множество решений также можно записать в виде
x∈(−ab;+∞)
2) Если a<0, то получаем неравенство
x<−ab
Множество действительных чисел, удовлетворяющих этому неравенству, и есть множество решений исходного неравенства (1):
x∈(−∞;−ab)
Аналогичным образом могут быть найдены решения любых линейных неравенств.
Множество решений системы двух линейных неравенств
ax+b>0, cx+d>0
находится как пересечение множеств решений этих неравенств.
Решить систему неравенств — значит найти множество всех значений неизвестного, при которых выполняется (справедливо) каждое неравенство системы. Для этого находят множество решений каждого неравенства системы в отдельности, а затем находят общую часть всех полученных множеств, т. е. все те числа, которые входят в каждое из этих множеств.
свойства решений зад.лп.пониятие о вып.лин-й комбинации и вып.множестве
Пусть имеется т-точек(векторов) n-мерного пространства,т.А явл.их выпуклой комбинацией если вып.усл-я
Множество точек наз-я выпукл-и если вместе с люб.двумя св.точками оно содерж.их произв-ю выпукл-ю комбин-ю.
Угловыми точками вып.множ-аназ.точки не явл.выпуклой комбинацией двух других точек множества
Т1.Множ-о всех планов задачей лп явл.выпуклым если оно не пусто
Т2.Целеваяфу-я задачи лп достигает своего min(max)знач-я в<точке многогранника решений,коорд.кот сост.опорн.план задач.
.7.
Симплекс-метод подразумевает последовательный перебор всех вершин области допустимых значений с целью нахождения той вершины, где функция принимает экстремальное значение. Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).
Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):
В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.