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

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

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

кот.сост.вопред-ии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)значения