Общ.станд.и осн.формы записи задачи лин.прогр.правила перехода от одной формы записи к другой

Формы записи задач ЛП

Общей задачейЛПназыв.задача

кот.сост.вопред-ииmax(min)значен.фу-ии.

f=c1x1+c2x2+..+cnxn->max(n)

f=

при вып.усл.

,m)

Функция(1)назыв.целевой ф-ей,а условий 2,3 назыв.ограничениями данных задач

Лин-оепрограм-е — раздел матем-ого программ-я, прим-й при разработке методов отыскания экстремума линейных функций неск-х перем-ых при лин-х допол-х огранич-х, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

Особенностью задач линейного програм-я явл-я то, что экстремума целеваяфун-я достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений.

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

Теорема. Если система векторов содержит m линейно независимых векторов, то допустимый план

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

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

Общ.станд.и осн.формы записи задачи лин.прогр.правила перехода от одной формы записи к другой

Общей зад-й ЛП наз-ся задача кот.сост в опр-и max(min)знач-я фу-и

Ф-я наз-яцелев-й ф-ей или линейной формой задачи лп а усл.2,3 назыв.огранич-ми данных задач.Стандарт-и или симметр-и зад.лпназывзад.котсост.вотисканииmaxзн-я ф-ии при выпусл-й F=

xj≥0(j=1n)

канонич.зад.лп или осн.зад.лпявл.задача,кот.сост.в опр.min значения целевой ф-ии и вып.усл.f=

x

правила перехода если F

 

 

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

Опорным планом задачи лп f=c1x1+c2x2+..+cnxn->min

a11x1+a12x2+..+a1nxn=b1

a21x1+a22x2+..a2nxn=b2

..

 

планом или допустим.решением задачи Лпназ.х⃗кот.удовл.сист.огранич-й2*

Планом х наз.опорным,если векторы Аj(j=(1,n)) ̅входящ.вразлож 2*явл.линейнонезависим-и,если при них наход.+коэфф.хj>0

Замечание

Опорный план явл.невырожденным если он содержит ровно m+компонентов в противн.случае план вырожден

Оптимальным планом задачи лпназ.план при кот.целевая ф-я принимает min (max)значения

 

 

Методом северо-зап-ого угла и методом

Миним-о элемента.

методом северо-зап-ого угла

На каждом этапе максимально возможным

числом заполняют левую верхнюю клетку

оставшейся части таблицы. Заполнение таким

образом, что полностью выносится груз из

или полностью удовлетворяется потребность.

1) Полагают верхний левый элемент матрицы X

x 11 = min(a 1,b1)

Возможны три случая:

а)если a1 < b1, то х11=а1 и всю первую строку начиная со второго элемента заполняют нулями.

б)если a1 > b1, то Х11=b1, а все оставшиеся элементы первого столбца заполняют нулями.

в)если a1 = b1, то х11 = a 1 = b 1, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть уже проделано к шагов, кm-й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент хl, m.

Тогда полагают хl,m = min(аkl, bkm),

где аkl = al - Σxlj

bkm = bm - Σxim

Если аkl<bkm, то заполняют нулями l -ю строку начиная с (m + 1)-го элемента. В противном случае заполняют нулями оставшуюся часть m-го столбца.

Метод минимального элемента позволяет построить

начальный опорный план транспортной задачи и является

вариантом метода северо­западного угла, учитывающим

специфику матрицы С=(cij)m,n. В отличие от метода

северо-западного угла данный метод позволяет сразу

получить достаточно экономичный план и сокращает

общее количество итераций по его оптимизации.

Схема метода: элементы матрицы С нумеруют начиная

от минимального в порядке возрастания, а затем в этом

же порядке заполняют матрицу Х0.

Пусть элементом с минимальным порядковым номером

оказался элемент x0ij.

Тогда полагают x 0 ij = min (ai, bj)

Возможны три случая:

а) если min (ai, bj) = ai, то оставшуюся часть i-й строки

заполняют нулями; (a1, b1) = bj, то

оставшуюся часть j-ro столбца заполняют

нулями.

б) если min (a1, b1) = bj, то оставшуюся часть j-ro столбца заполняют нулями.

в) если ai = bj, то оставшуюся часть строки и столбца

заполняют нулями.

Далее этот процесс повторяют с незаполненной частью

матрицы.

Пусть элементом с k -м порядковым номером оказался

ХklmТогда хklm = min(akl, bkm),

гдеа k l = al - Σxglj, g = 1..l-1

bkm = bm - Σxuim, u = 1..k-1

Возможны три случая:

а) аkl<bkm, тогда хklm = аkl и оставшуюся часть строки l заполняют нулями;

б) аkl>bkm, тогда хklm = bkm и остаток столбца m заполняют нулями;

в) аk = bkm, тогда оставшуюся часть строки l и столбца m заполняют

нулями.

Формы записи задач ЛП

Общей задачейЛПназыв.задача

кот.сост.вопред-ииmax(min)значен.фу-ии.

f=c1x1+c2x2+..+cnxn->max(n)

f=

при вып.усл.

,m)

Функция(1)назыв.целевой ф-ей,а условий 2,3 назыв.ограничениями данных задач

Лин-оепрограм-е — раздел матем-ого программ-я, прим-й при разработке методов отыскания экстремума линейных функций неск-х перем-ых при лин-х допол-х огранич-х, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

Особенностью задач линейного програм-я явл-я то, что экстремума целеваяфун-я достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений.

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

Теорема. Если система векторов содержит m линейно независимых векторов, то допустимый план

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

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

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

Общей зад-й ЛП наз-ся задача кот.сост в опр-и max(min)знач-я фу-и

Ф-я наз-яцелев-й ф-ей или линейной формой задачи лп а усл.2,3 назыв.огранич-ми данных задач.Стандарт-и или симметр-и зад.лпназывзад.котсост.вотисканииmaxзн-я ф-ии при выпусл-й F=

xj≥0(j=1n)

канонич.зад.лп или осн.зад.лпявл.задача,кот.сост.в опр.min значения целевой ф-ии и вып.усл.f=

x

правила перехода если F

 

 

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

Опорным планом задачи лп f=c1x1+c2x2+..+cnxn->min

a11x1+a12x2+..+a1nxn=b1

a21x1+a22x2+..a2nxn=b2

..

 

планом или допустим.решением задачи Лпназ.х⃗кот.удовл.сист.огранич-й2*

Планом х наз.опорным,если векторы Аj(j=(1,n)) ̅входящ.вразлож 2*явл.линейнонезависим-и,если при них наход.+коэфф.хj>0

Замечание

Опорный план явл.невырожденным если он содержит ровно m+компонентов в противн.случае план вырожден

Оптимальным планом задачи лпназ.план при кот.целевая ф-я принимает min (max)значения