Общая задача линейного программирования, основные элементы и понятия.

Общая задача линейного программирования, основные элементы и понятия.

ЗЛП - задача об оптимальном использовании ограниченных пр-венных ресурсов. Оптимизационные модели в эк. возникают при практической реализации принципа оптимальности. Его суть состоит в стремлении выбрать такое управленческое решение X=(x₁, x₂, …, x_n), где x_j, j=1, …, n-его компоненты, которое наилучшим образом (эк. показатель, позволяющий сравнить эффективность управленческих решений) учитывало бы внутренние возможности и внешние условия пр-венной деят. (выбор X оскщ. из некоторой обл. возможных решений D) хоз-щего субъекта. Реализовать на практике принцип оптимальности это значит разработать и получить решение по модели: max (min) макс. или мин. ф-цию f(x) при ограничениях, где f(x₁, x₂, …, x_n) – математ. запись критерия оптимальности -ЦФ.

Max(min) f(x)=f(x₁, x₂, …, x_n), x є D.

Общая задача оптимального (математ.) программирования:

Max(min) f(x₁, x₂, …, x_n)

g₁(x₁, x₂, …x_n) {≤ , =, ≥ } b₁ (1)

g₂(x₁, x₂, …x_n) {≤ , =, ≥ } b₂ (2)

g_n(x₁, x₂, …x_n) {≤ , =, ≥ } b_n

x_i ≥ 0, i=1, ¯ n (3)

Область опред-ния – все мн-во допустимых решений. Вектор X - допустимое решение или план задачи. План X - оптимальный план.

Область допустимых решений - пустое мн-во (задача противоречива): некорректна поставлена эк. задача или разработана ЭММ. ЦФ явл. неограниченной на обл. определения: ЭММ разработана некорректно и некоторые сущ-ные ограничения в ней отсутствуют.

Графический метод решения задачи линейного программирования.

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

1. Стоится многоугольная область допустимых решений ЗЛП - мн-ик решений.

2. Строится вектор-градиент целевой функции. Начало в т.О(0, 0), а вершина в т.(df_/dx₁; df/dx₂)=(C₁; C₂).

3. Строим линию уровня c₁x₁+c₂x₂=a, a=const. Линия уровня это прямая перпендикулярная вектору-градиенту. Передвигаемся в направлении этого вектора. В случае максимизации ЦФ до тех пор, пока не покинет ОДР. Предельная точка ОДР при этом движении и является точкой max ЦФ.

4. Для нахождения координат указанной предельной точки, достаточно решить 2 уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку max. Значение ЦФ найденное в этой точке является max. При минимизации ЦФ линия уровня перемещается в направлении противоположном вектору-градиенту.

Особые случаи решения ЗЛП графическим методом.

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

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

1 max (3x₁+5x₂) ограничения: x₁+x₂ ≥ 2 4x₁+2x₂ ≤ 2 при x₁, ₂ ≥ 0

Задача неразрешима - противоречивость ограничений

2 max (3x₁+2x₂) x₁-x₂ ≤ 1 2x₁+x₂ ≥ 1 при x₁, ₂ ≥ 0

Задача неразрешима - неограниченность ЦФ на ОДР.

3 Случай не единственности решения max (8x₁+10x₂) 5x₁+x₂ ≤ 15 4x₁+5x₂ ≤ 40 при x₂ ≥ 3 x₁ ≥ 0

Линия уровня 8x₁+10x₂ =a параллельна одной из линий по границе ОДР. Это значит, что задача имеет бесконечное множество оптимальных решений (его задают координаты точек отрезка ВС).

Каноническая форма записи ЗЛП. Способы приведения ЗЛП к каноническому виду.

КЗЛП – запись с использованием знаков суммирования:

max (min) f(x₁, x₂, …, x_n)=Sc_jx_j,

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

Sa_ijx_j=b_i, i=1, 2, m; x_j≥ 0, j=1, 2, n; b_i≥ 0, i=1, 2, m

Векторная запись КЗЛП:

max (min) f(x₁, x₂, …, x_n)=f (X)=CX,

A₁x₁+A₂x₂+…+A_nx_n=B, X≥ 0,

Где: C=(c₁, c₂, c_n), X=(x₁, x₂, x_n);

CX-скалярное произведение векторов C и X;

A₁, A₂, A_n – вектор-столбцы.

Матричная запись:

max (min) f (X)=CX, AX=B, X≥ 0.

Где С=(c₁, c₂, c_n) – матрица-строка;

X, B – матрица-столбец;

A=(a_ij) – матрица размерности m*n, столбцами которой явл. Вектор-столбцы A₁, A₂, A_n.

Стандартная форма записи:

max (min) f (X)=CX, AX≥ (≤ )B (соотв. компонентов слева и справа), X≥ 0

Любую ЗЛП можно привести к КЗЛП путем введения в левую часть соотв. ограничения вида

k-й доп. (вспомогат.) переменной X_n+k≥ 0 со знаком «-», если «≥ » и «+», если «≤ ». Если на некоторую переменную X_p не накладывается условие неотр., то делает замену переменных X_p=X_1p-X_2p, X_1p≥ 0, X_2p≥ 0. В преобразованной задаче все переменные неотр.

Решение СЛУ методом Ж-Г. Общее решение, частное, базисное и опорное.

При решении СЛУ последовательно над строками матрицы выполняются элементарные преобразования, так что некоторое неизвестное искл. из всех ур-ий, кроме одного. В процессе решения могут встретиться сл. случаи:

1. X₁+0X₂+…+0X_n=B_i, (Bi≠ 0)

сист. несовместна – решений нет

2. 1 0 … B’1

0 1 …. B’2

…

0 0 … B’n

сист. имеет единственное решение Xn=Bn

3. 1 0 … A’_1r+1 … A’_1n | B’₁

0 1 … A’_2R+1 … A’_2n | B’₂

…

0 0 … 1 A’_rr+1 … A’_rn | B’_r

расширенная матрица – сист. имеет мн-во решений:

X_r=B’_r-A’_rr+1X_r+1-…-A’_rnX_n

Придавая каждой из стоящих в правых частях равенств переменных X_n произвольные значения получим частные решения. Неизвестные X_r – базисные (основные); соотв. линейно-независимым векторам A_r. Т.о. r переменные – базисные (основные), если определитель матрицы коэф. при них отличен от 0, а остальные (n-r) – свободные (неосновные). Базисное решение – частное решение, в котором неосновные переменные имеют нулевые значения. Каждому разбиению на основные и неосновные переменные соотв. одно базисное решение, а кол-во способов разбиения не превышает величины

_m n!

С =__________

ⁿ m! (n-m)!

Если все компоненты базисного решения неотр. – решение опорное.

Основные свойства задачи линейного программирования. Основы симплекс-метода

В основе математического метода получения оптимального решения лежат основные свойства ЗЛП:

1. Не существует локального экстремума отличного от глобального. Если экстремум есть, то он единственный.

2. Множествовсех планов ЗЛП является выпуклой многогранной областью (многогранником решения).

3. ЦФв ЗЛП достигает своего max (min) значения в угловой точке многогранника решения (в вершине). Если ЦФ принимает max решение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

4. Каждойугловой точке отвечает опорный план ЗЛП (не отрицательное базисное решение соответствующей КЗЛП).

Суть симплекс-метода состоит в том, что вначале получают допустимый вариант, удв. всем ограничениям, но обязательно оптимальный (начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за опред. число этапов. Нахождение начального опорного решения и переход к сл. проводятся на основе применения метода Жордана-Гаусса для сист. линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к др. выбирается при этом на основе критерия оптимальности ЦФ. Этапы:

1. опред-ние какого-либо первоначального допустимого базисного решения сист.

2. переход к нехудшему решению

3. проверка оптимальности допустимого базисного решения

Особые случаи решения ЗЛП симплексным методом.

1. решение не единственное (линия уровня параллельна одной из линий на границе области допустимых решений). Это означает, что задача имеет бесконечное множество оптимальных решений. Его задают координаты точек отрезка с угловыми точками.

2. задача не имеет решения, т.к. область решений не ограничена сверху.

3. задача не имеет решения, т.к множество планов пусто, нет ни одной общей точки.

Требования, предъявляемые к исходной информации при моделировании эк. процессов на основе временных рядов.

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

2. Однородность данных – отсутствие сильных изломов тенденций, а также аномальных наблюдений.

3. Представительность данных хар-ся их полнотой. Число наблюдений должно быть достаточным для постановки задачи.

4. Устойчивость – преобладание закономерности над случайностью.

Предварительный анализ временных рядов. Тренд.

Для определения наличия тренда во временном ряду применяется несколько методов.

1. Метод проверки разностей средних уровней. Состоит из 4х этапов:

I: Временной ряд разбивается на две примерно равные по числу уровней части (n₁+n₂=n).

II: Для каждой из этих частей вычисляются средние значения и дисперсии.

III: Проверка равенства (однородности) дисперсий обеих частей ряда с помощью F-критерия Фишера.

Если расчетное значение F меньше табличного Fα, то гипотеза о равенстве дисперсий принимается и переходят к 4му этапу.

IV: Проверяется гипотеза об отсутствии тренда с использованием t-критерия Стьюдента. Для этого определяется рассчетное значение критерия Стьюдента по формуле:

, где - среднекв. отклонение разности средних:

Если расчетное значение t меньше табличного значение статистики Стьюдента tα, тренда нет. Если больше – тренд есть.

2.Метод Фостера-Стьюарта.

Предварительный анализ временных рядов. Сглаживание.

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

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

Предварительный анализ временных рядов. Вычисление количественных хар-ик развития эк. процессов.

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