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

Экономико-математическая модель (ЭММ). Понятие, пример, общая классификация ЭММ.

В основе всех совр.фин.расчетов лежат те или иные мат.модели исследуемых эк.процессов, т.е. основным методом является метод моделирования. Этот метод основан на принципе аналогии, т.е. возможности изучения не самого исходного объекта, а некоторого искусственного созданного объекта – модели. Модель вообще это некоторый объект способный заменить исследуемый с целью получения нового знания. Модели подразделяются на физические и абстрактные. Физические это макеты, конструкции и т.д. Абстрактные это словесно-описательные и мат.модели. Словесно-описательные это эк.сценарии, программы, пояснительные записки. ЭММ это мат.образ, мат.описание принципиальных сторон исследуемого эк.процесса, проблемы, задачи. ЭММ средствами экономики и мат-ки отражает существо исследуемой эк.проблемы. ЭММетоды это методы разработки, исследования и принятия решений по ЭММ. ЭММ подразделяют на макро- и микроэкономические, прескриптивные и дескриптивные. К макро относят модели, реализующие народно-хозяйственные пропорции, межотраслевые и межрегиональные пропорции и эк.взаимоотношения. К микро - модели на уровне взаимоотношений хозяйствующего субъекта, модели внутри фирменного планирования. Прескриптивные (нормативные) это модели отвечают на вопрос: Какой вариант управленческого поведения лучше? (оптимизационные модели). Дескриптивные это модели отвечают на вопрос: А что будет, если? (балансовые модели, производственные функции). Многим задачам в экономике отвечают оптимизационные (экстремальные) ЭММ.

Основные этапы применения математических методов в финансово-экономических расчетах (иллюстрация на конкретном примере).

В процессе решения эк.задач с применением мат.методов можно выделить 4 осн.этапа: 1.Постановка эк.задачи, проблемы. Здесь осуществляется описание экономико-организационной задачи. 2.Мат.моделирование. Здесь разрабатывается ЭММ задачи. 3.Получениерешения по модели. Здесь осуществляется реализация ЭММ. 4.Внедрениеполученного решения. Разработка рекомендаций, предложений в доступном и наглядном виде для работника. В процессе исследований и принятия решений с помощью ЭММ приходится возвращаться заново на те или иные этапы.

Общая запись оптимизационной ЭММ (задача оптимального программирования). Основные элементы и понятия.

Реализовать на практике принцип оптимальности это значит разработать и получить решение по модели: max(min) максимизировать или минимизировать функцию f(x) при ограничениях, где f(x1,x2,…,xn) – математическая запись критерия оптимальности -ЦФ. Max(min) f(x)=f(x1,x2,…,xn),x є D.

Обычно, приведенную модель записывают в виде:

Max(min) f(x1,x2,…,xn)

g1(x1,x2,…xn) {≤ , = , ≥ } b1 (1)

g2(x1,x2,…xn) {≤ , = , ≥ } b2 (2)

gn(x1,x2,…xn) {≤ , = , ≥ } bn

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

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

Если в задаче линейного программирования ограничения заданы в виде неравенств с двумя переменными, то задача может быть решена графически. Графический метод решения ЗЛП состоит из этапов: 1.Стоится многоугольная область допустимых решений ЗЛП. 2.Строится вектор-градиент целевой функции. Начало в т.О(0,0), а вершина в т.(df/dx1; df/dx2)=(C1;C2). 3.Строим линию уровня c1x1+c2x2=a, a=const. Линия уровня это прямая перпендикулярная вектору-градиенту. Передвигаемся в направлении этого вектора. В случае максимизации ЦФ до тех пор, пока не покинет ОДР. Предельная точка ОДР при этом движении и является точкой max ЦФ. 4.Для нахождения координат указанной предельной точки, достаточно решить 2 уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку max. Значение ЦФ найденное в этой точке является max. При минимизации ЦФ линия уровня перемещается в направлении противоположном вектору-градиенту.

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

ЗЛП имеет несколько форм записи: 1)векторная f(x)=cx A₁x₁+A₂x₂+…+A_nx_n≤ (= ≥)B с=(с₁,с₂…с_n) – вектор строка. х=(х₁,х₂..х_n), А_j вектор столбцы А_j= , В-вектор столбец св членов. 2)матричная Ах≤ (= ≥)В х≥0, А-матрица коэфф. А= . 3)стандартная (все знаки одинаковые) b_j≥0 х≥0. 4)каноническая Ах=В. Любую ЗЛП можно привести к каноническому виду. Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:1)если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;2)если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;3)если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;4)если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными.

8. Основы симплекс-метода: общая схема алгоритма метода. Понятие базиса системы векторов. Базисные и опорные решения системы линейных уравнений, переход от одного базисного решения к другому

Основное содержание симплексного метода заключается в следующем:

1. Указать способ нахождения оптимального опорного решения

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

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

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

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Базисные и опорные решения системы линейных уравнений, переход от одного базисного решения к другому.

В процессе решения системы уравнений на некотором этапе получилась расширенная матрица вида:

( 10…0А'1r+1…А'1n | B'1)

А'= ( 01…0A'2r+1…A'2n | B'2 )

(………………………|……)

(00….1A'rr+1…A'r n | B'r )

Система совместна и имеет бесчисленное множество решений. Общее решение системы записывают:

Х1= В'1-А'1r+1*Xr+1 ------A'1n*Xn

X2=B'2- A'2r+1*Xr+1-------A'2n*Xn

----------------------------------------------

Xr= B'r - A'rr+1*Xr+1--------A'r n*Xn

Придавая каждой из стоящих в правых частях равенств переменных Xr+1, Xr+2,……, Xn; произвольные значения, получаем частные решения системы. Неизвестные Х1, Х2,…., Хr; называют базисными или основными, они соответствуют линейно-независимым векторам А1, …, Аr. Любые r – переменных называют базисными, если определитель матрицы коэффициентов при них отличен от нуля, а остальные (n-r) переменных называют свободными или не основными. Базисным решением системы уравнений называют частное решение, в котором не основные переменные имеют нулевые значения. Каждому разбиению на основные и не основные переменные соответствует одно базисное решение, а количество способов разбиения не превышает величины Сⁿⁿn=n! /m!*(n-m)!

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