Предмет история и перспективы развития методов оптимальных решений.

Предмет история и перспективы развития методов оптимальных решений.

1 Предмет «МОР–изучает экстремальные задачи. «МОР» – изучает математические модели задач принятия решений. Поэтому областью применения данного предмета являются математические модели экономических, технических, социальных и других задач принятия решений.

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

Хинчин и Гнеденко в середине тридцатых годов начали изучать класс вероятностных задач. Во время войны оптимизационные методы получили широкое развитие в Англии и США.

В послевоенные годы были созданы первые ЭВМ и неизмеримо обогатился вычислительный арсенал математики. Это не могло не сказаться на развитии всех теорий, связанных с конкретными задачами практики.

Появление ЭВМ, стимулировало объединение разнообразных задач, связанных с проблемами принятия решений, , которая получала название «МОР» или еще один вариант название дисциплины «Исследование операций».

Главным содержанием дисциплины были сложные проблемы принятия решений.

огромную роль играет математическая культура исследователя. Надо уметь не только понять смысл задачи, но и сформулировать ее так, чтобы она была доступна для анализа математическими средствами.

Дисциплина «МОР» опирается на математический анализ, линейную алгебру и программирование.

Основные понятия: модель, моделирование, экономико-математическая модель.

Модель – условный образ объекта управления.

Модель должна соответствовать следующим требованиям:

1) адекватность структуре и свойствам объекта управления;

2) соответствие модели системе ценностей и предпочтений лица,

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

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

Модели могут иметь различную природу:

- материальную;

- знаковую (математическая, графическая);

- вербальную (словесную).

Моделирование – это процесс построения, изучения и применение модели.

Цель моделирования – это изучение объектов познания через их модели, при условии, что между объектом и моделью существует некоторое подобие

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

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

Задача линейного программирования – оптимизация линейной функции в области, задаваемой линейными ограничениями

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

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

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

Теорема.Всякому решению неравенства соответствует определенное решение уравнения , в котором

И, наоборот, каждому решению уравнения (и неравенства соответствует определенное решение неравенства .

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

Для решения задачи в Excel необходимо правильно поместить математическую модель по ячейкам электронной таблицы

В ячейках, содержащих формулы чаще всего используется функция СУММПРОИЗВ

Все сведения о модели заносят в окно «Поиск решения»

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

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

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

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

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

Задача о назначениях.

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

Метод потенциалов.

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

Если система содержит уравнение неизвестных, то один из потенциалов можно задать произвольно. После этого остальные неизвестные определяются однозначно.

12. Целочисленные переменные в задачах экономического планирования.

могут возникать различными путями.

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

2. Задачи линейного программирования, в которых переменные представляли физически неделимые величины.

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

Целочисленная задача линейного программирования (задача с неделимостями). К данному классу принадлежат задачи распределениякапиталовложении

Нелинейные задачи оптимизации.

Такие задачи возникают, когда, затраты растут не пропорционально количеству закупленных или произведённых товаров.

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

Общая формулировка нелинейных задач:

Найти переменные х₁ , х₂ , …, х_n , удовлетворяющие системе уравнений

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

Свойства выпуклых множеств

· Пересечение выпуклых множеств является выпуклым.

· Линейная комбинация точек выпуклой множества выпуклая.

· Выпуклая множество содержит любую выпуклую комбинацию своих точек.

· Любую точку n -мерного евклидова пространства с выпуклой оболочки множества можно представить как выпуклую комбинацию не более n +1 точек этого множества.

Теория игр

Игра — это совокупность правил, описывающих сущность кон­ фликтной ситуации. Эти правила устанавливают:

•выбор образа действия игроков на каждом этапе игры;

•информацию, которой обладает каждый игрок п

•плату для каждого игрока после завершения любого этапа

игры.

Игру можно определить следующим образом:

•имеются п конфликтующих сторон (игроков), , интересы которых не совпадают;

•определен набор возможных конечных состояний

•всем игрокам (участникам игры) заранее известны платежи, соответствующие каждому возможному конечному состоянию.

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

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

сненулевой суммой.

Решение игры состоит в определении наилучшей стратегии каждым игроком

Предмет история и перспективы развития методов оптимальных решений.

1 Предмет «МОР–изучает экстремальные задачи. «МОР» – изучает математические модели задач принятия решений. Поэтому областью применения данного предмета являются математические модели экономических, технических, социальных и других задач принятия решений.

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

Хинчин и Гнеденко в середине тридцатых годов начали изучать класс вероятностных задач. Во время войны оптимизационные методы получили широкое развитие в Англии и США.

В послевоенные годы были созданы первые ЭВМ и неизмеримо обогатился вычислительный арсенал математики. Это не могло не сказаться на развитии всех теорий, связанных с конкретными задачами практики.

Появление ЭВМ, стимулировало объединение разнообразных задач, связанных с проблемами принятия решений, , которая получала название «МОР» или еще один вариант название дисциплины «Исследование операций».

Главным содержанием дисциплины были сложные проблемы принятия решений.

огромную роль играет математическая культура исследователя. Надо уметь не только понять смысл задачи, но и сформулировать ее так, чтобы она была доступна для анализа математическими средствами.

Дисциплина «МОР» опирается на математический анализ, линейную алгебру и программирование.

Основные понятия: модель, моделирование, экономико-математическая модель.

Модель – условный образ объекта управления.

Модель должна соответствовать следующим требованиям:

1) адекватность структуре и свойствам объекта управления;

2) соответствие модели системе ценностей и предпочтений лица,

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

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

Модели могут иметь различную природу:

- материальную;

- знаковую (математическая, графическая);

- вербальную (словесную).

Моделирование – это процесс построения, изучения и применение модели.

Цель моделирования – это изучение объектов познания через их модели, при условии, что между объектом и моделью существует некоторое подобие

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