шпоргалка. Шпоры_4семестр. 1 Мат методы, модели

• Название: 1 Мат методы, модели
• Анкор: шпоргалка
• Дата: 03.03.2023
• Размер: 0.52 Mb.
• Имя файла: Шпоры_4семестр.doc
• Тип: Закон; #966516
• страница: 1 из 5

1-4. Мат методы, модели

Экономико-математическая модель — мат описание исследуемого экономич процесса или объекта. Эта модель выра­жает закономерности экономич процесса в абстрактном виде с помощью матем соотношений. Использование матем моделирования в экономике позволяет углубить количе­ственный экономич анализ, расширить область экономич инфы, интенсифицировать экономич расчеты.

Можно выделить 3 осн этапа проведения экономико- матем моделирования. На 1 этапе ставятся цели и задачи исследования, проводится качественное описание объекта в виде экономич модели. На 2 этапе формируется мате­матич модель изучаемого объекта, осуществляется выбор (или разработка) методов исследования, проводится программирование модели на ЭВМ, подготавливается исходная инфа. Далее про­веряются пригодность машинной модели на основании правильно­сти получаемых с ее помощью результатов и оценка их устойчивости. На 3, основном, этапе экономико-математич моде­лирования осуществляются анализ математич модели, реализо­ванной в виде программ для ЭВМ, проведение машинных расчетов, обработка и анализ полученных результатов.

Процедура экономико-математич моделирования заме­няет дорогостоящие и трудоемкие натуральные эксперименты расчетами. Действительно, при использовании экономико-математич методов достаточно быстро и дешево производится на ЭВМ сравнение многочисл вариантов планов и управ­ленческих решений. В результате отбираются наиболее оптим варианты.
5. Классификация задач оптимизации

Класс оптимизацион­ных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономич системами. Оптимизационную задачу можно сформулировать в общем виде: найти переменные X1, X2, ..., Xn, удовлетворяющие системе неравенств (уравнений): φi (X1, X2, X3, …, Xn) <= bi, i=1,2,…,m

и обращающие в max/min целевую функцию, т.е. Z = f (x1, x2, ..., xn) -> mах (min).

(Условия неотриц переменных, если они есть, вхо­дят в ограничения )

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

Если критерий эффективности Z = f(x1, х2, ..., xn) пред­ставляет лин функцию, а функции φi (x1, х2, х3,...,xn) в сис­теме ограничений также линейны, то это задача лин программирования. Если, исходя из содержатель­ного смысла, ее решения должны быть целыми числами, то это задача целочисл лин программирования. Если критерий эффективности и (или) система ограничений задаются нелин функциями, то это задача нелин программирования. В частности, если указанные функции обладают свойствами вы­пуклости, то это задача выпуклого про­граммирования.

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

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

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

8. Функция цели и типы уравнений-ограничений

9. Условные обозначения в задачах лин программирования

15. Типы уравнений-ограничений в эконом-мат моделях, приведение к канонич виду

Оптимизационную задачу можно сформулировать в общем виде: найти переменные X1, X2, ..., Xn, удовлетворяющие системе неравенств (уравнений)

φi (x1, x2, x3, …, xn) <= bi, i =1,2,…,m

и обращающие в максимум (или минимум) целевую функцию, т.е.

Z = f (X1, X2, ..., Xn) -> mах (min).

(Условия неотриц переменных, если они есть, вхо­дят в ограничения)

Если критерий эффективностиZ = f(x1, х2, ..., xn) пред­ставляет линейную функцию, а функции фi, (x1, х2, х3,..., Xn)в сис­теме ограничений также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержатель­ного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования.

Общая задача лин про­граммирования: дана система m линейных уравнений и неравенств с n перемен­ными:

A11X1 + A12X2 + … + A1nXn <= B1,

A21X1 + A22X2 + … + A2nXn <= B2,

………………………………………

Ak1X1 + Ak2X2 + … + AknXn <= bk,

Ak+1,1X1 + Ak+1,2X2 + … + Ak+1,nXn = Bk+1,

Ak+2,1X1 + Ak+2,2X2 + ... + Ak+2,nXn = Bk+2

..............................................................

Am1X1 + Am2X2 + ... + AmnXn = Bm

(Это всё в системе!!)

и линейная функция: F = C1X1 + C2X2 + … + CnXn.

Надо найти такое решение системы Х= (X1, X2, ..., Xj, ..., Xn), где Xj >= 0 (j=l,2,..., L; L <= n), при котором лин функция F принимает оптим (max/min) значение.

Система называется системой ограничений, а функция F — лин функцией, лин формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде: F = ∑ CjXj -> max (или -> min) при ограничениях:

{∑AijXj ≤ Bi (i = 1,2,…,k),

{∑AijXj = Bi (I = k+1,k+2,…, m),

(это в системе!!)

Xj ≥ 0 (j = 1,2,…,L; L ≤ n).

Оптим решениезадачи ли­н программирования – решениеХ = (X1, X2, …, Xj, …, Xn) системы ограничений, удовлетворяющее условию, при котором лин функция принимает опти­м (max/min) значение.

При условии, что все переменные неотрицательны (Xj ≥ 0, j =1, 2, ..., n), система ограничений состоит лишь из одних неравенств, — такая задача линейного программирования называется стандарт­ной; если система ограничений состоит из одних уравнений, то зада­ча называется канонической. Любая задача линейного программирования может быть сведе­на к канонической, стандартной или общей задаче.

Представим стандартную задачу в каноническом виде, введя в каждое из m неравенств системы ограничений доп неотриц переменные Xn+1, Xn+2, …, Xn+m, получим:

A11X1 + A12X2 + … + A1nXn + Xn+1 = B1,

A21X1 + A22X2 + … + A2nXn + Xn+2 = B2,

……………………………………………..

Am1X1 + Am2X2 + … + AmnXn + Xn+m = Bm.

(Это всё в системе!!!)
7. Понятие, критерий оптимальности и тд

См. вопрос 6 +

Если задача лин программирования имеет оптим решение, то лин функция принимает max/min значение в одной из угловых точек многогранника решений. Если лин функция принимает max/min значение более чем в 1 угловой точке, то она принимает его в любой точке, являющейся выпуклой лин комбинацией этих точек.

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

Критерии оптимальности (для симплекс-метода?):

Критерий оптим решения при отыскании max (min) лин функции: если выражении лин функции через неосновные переменные отсутствуют положительные (отрицательные) коэффициенты при неосновных переменных, то решение оптимально.
10. Графо-аналитич метод решения лин программирования

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

Необходимо среди то­чек этого многоугольника найти такую точку, в которой лин функцияF = C1X1 + C2X2 принимает max/min значение.

Рассмотрим линию уровня лин функции F, т.е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение а, т.е. F = а, или C1X1 + C2X2 = a.

На многоугольнике решений следует найти точку, через которую проходит линия уровня функ­цииF с наибольшим (если линейная функция max) или наименьшим (если она min) уровнем. Линии уровня функцииF — это своеобразные "параллели", распо­ложенные обычно под углом к осям координат. Далее, определив направление возрастания лин функции (обозначим как вектор С), найдём точку, в которой функция принимает max/min значение.

При геометрическом решении подобных за­дач возможно совпадение линии уровня с границей многоугольника решений. Так будет происходить, если линия уровня и граничная прямая параллельны, т.е. их коэффициенты при переменных пропорциональны. Напр коэффициенты при переменных линии уровняF = 3X1 + 3X2 пропорциональны соответствующим коэффициентам гранич­ной прямой X1 + X2 =6.

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

11. Краткая характеристика симплекс метода, его графич интерпретация

Идея последовательного улучшения решения легла в основу универсального метода решения задач лин программирова­ния —симплексного метода.

Геометрический смысл симплексного метода состоит в последо­вательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой лин функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптим решение — вершина, где достигается оптим значение функции цели (если задача имеет конечный оптимум).

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

Для реализации симплексного метода — последовательного улучшения решения — необходимо освоитьтри основных элемента: способ определения какого-либо первоначального допустимого базисного решения задачи; правило перехода к лучшему (точнее, не худшему) решению; критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача лин программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений.
12. Этапы вычисления симплексным методом

17. Алгоритм решения симплекс методом

Смысл дополнит переменных это разность (например между между содержанием и необходимым минимумом каждого из пит веществ).

Для использования симплексного метода задача лин программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений.

Если расчеты осуществляются без ЭВМ, то удобно использовать симплекс таблицы. Да­лее мы рассмотрим алгоритм их составления (для max).

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

2. Исходную расширенную систему заносим в первую сим­плекс таблицу. Последняя строка таблицы, в которой приве­дено уравнение для лин функции цели, называетсяоценоч­ной. В ней указываются коэффициенты функции цели с противо­положным знаком: Bi = - Ci. В левом столбце таблицы записыва­ем основные переменные (базис), в 1 строке таблицы — все переменные (отмечая при этом основные), во втором столбце — свободные члены расширенной системы B1, B2, …, Bm. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы зане­сены коэффициентыAij при переменных из расширенной системы.

3. Проверяем выполнение критерия оптим при ре­шении задачи на max — наличие в последней строке отри­ц коэффициентов. Если таких нет, то ре­шение оптимально, достигнут maxF = C0 (в левом нижнем углу таблицы), основные переменные принимают значения Ai0 (второй столбец), основные переменные равны 0, т.е. получаем оптималь­ное базисное решение.

4. Если критерий оптимальности не выполнен, то наиболь­ший по модулю отрицательный коэффициент в последней строке определяет ключевой столбец s.

Определяем min {Bi/Ais} (если Ai0 b Ais имеют одинаковые знаки). Затем выбираем ключевую строку, где получен конечный минимум. На пересечении ключевых строки и столбца находится ключевой элемент Aqs.

5. Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной Xq — переменную Xs.

б) в столбцах, соответствующих основным переменным, про­ставляем нули и единицы: 1 — против "своей" осн пере­менной, 0 — против "чужой" осн переменной, 0 — в последней строке для всех осн переменных;

в) новую строку с номеромq получаем из старой делением на ключ элемент

г) все остальные элементыA’ijвычисляем поправилу прямо­угольника.

Дальше опять переходим к пункту 3.
13. Правила составления исходной матрицы и 1-ого плана

Для использования симплексного метода задача лин программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений.

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

Алгоритм получения первоначального допустимого базисного решения:

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

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

3. Если базисное решение недопустимое, а в уравнении, со­держащем отриц свободный член, отсутствует неоснов­ная переменная с положит коэффициентом, то допустимое базисное решение получить нельзя, т.е. условия задачи противоречивы.

+ см. вопрос 12.
14. Экономич смысл доп и искусственных переменных при М-методе

Для решения М-задачи можно воспользоваться симплекс-методом, поскольку указан допустимый базис.

При решении М-задачи могут представиться две возможности:

1. М-задача имеет решение, т.е. min F существует.

2. М-задача не имеет решения, min F =¥.

Решая М-задачу, мы стремимся получить оптимальное решение, в котором значения искусственных неизвестных равны нулю. Для того чтобы этого достичь, необходимо выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, т.е. стали свободными. Тогда в базисном решении значения этих неизвестных и будут как раз нулями.

Таким образом, переходя при решении М - задачи от одного базиса к другому, мы стараемся в первую очередь выводить из базиса одно искусственное неизвестное за другим. Возможны, впрочем, и такие (досадные) случаи, когда в процессе решения приходится заменять одно искусственное неизвестное на другое (выбор разрешающего элемента по-другому не получается). Но общим направлением вычислительного процесса во всех случаях остается постепенный вывод искусственных неизвестных из базиса.

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

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

Смысл дополнит переменных это разность (например между между содержанием и необходимым минимумом каждого из пит веществ).

16. Геометрическая интерпретация этапов решения задачи симплексным М-методом.

19. Алгоритм решения задач симплексным методом и искусственным базисом. Расчет коэффициентов целевой строки исходной матрицы

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

Геом. Интерпретация

Путь решения любой задачи лин программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них те, на котором функция цели принимает оптим решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптим решению (если оно сущ), однако его практич осуществление связано с огромными трудностями, тк для реальных задач число допустимых базисных решений хотя и конечно, но Мб чрезвычайно велико. Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было «лучше» (или не хуже), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F->max, уменьшение – при отыскании минимума F->min). Такой перебор позволяет сократить число шагов при отыскании оптимума.