ЭКОНОМИКО- МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

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

Постановка задачи и основные понятия

Определение 1.1. Будем называть задачей математического программирования следующую задачу оптимизации где множество х, на котором ведется поиск оптимального вектора может быть задано с помощью ограничений в виде равенств и (или) неравенств:.

Определение 1.2. Функция называется линейной, если она представима в виде:, где произвольные константы.

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

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

Модель поведения потребителя

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

Задача о формировании штата фирмы

unix.mcs.anl.gov/otc/Guide/faq/linear- programming-faq.html#free (июль 2001); survey.html (июль 2001); (июль 2001). Последний сайт содержит подробный обзор программ по линейному программированию на русском языке.

Задача о смеси

Транспортная задача

Модель рационального использования посевных площадей

Составление плана производства

а) Планирование по валу. б) Планирование по номенклатуре.

Модель межотраслевого баланса

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

Модель динамического межотраслевого баланса

Задания на построение моделей линейного программирования

Оптимизация оперативно- производственного планирования.

Составление оптимального плана перевозки угля.

Планирование транспортного хозяйства.

Расчет оптимальной производственной программы

Линейная распределительная задача

Регрессионные модели

Определение вида функциональной зависимости. Метод наименьших квадратов

Задачей регрессионного анализа будем называть задачу нахождения (восстановления) конкретного вида функциональной зависимости

Вектор коэффициентов регрессии обычно находят методом наименьших квадратов (МНК)

Экономический смысл коэффициентов регрессии

Решение задач регрессионного анализа на компьютере в пакетах EUREKA, MAPLE и STATISTICA

avasta2.html (апрель 2001).

EUREKA: The Solver.

tware/maths.htm#Mercury (апрель 2001)

Verify – проверка правильности полученного результата. А именно: полученные в окне Solution значения подставляются в соотношения, записанные в окне Edit, и в окне Verify выводятся отдельно значения левых и правых частей. По величине погрешности (difference и max error) можно судить о близости найденных значений к истинному решению.

Find other – попытка найти другое решение данной задачи (например, если требуется найти корни квадратного или любого другого нелинейного уравнения.

Iterate – уточнение найденного решения.

Решение регрессионных задач в пакете Maple

Решение регрессионных задач в пакете STATISTICA

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейные неравенства и область решений системы линейных неравенств

Определение 2.1. Совокупность точек плоскости, координаты которых удовлетворяют неравенству (2.1) называют областью решений данного неравенства.

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

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

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

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

Решение задач линейного программирования на компьютере

Решение задач в пакете EUREKA

Решение задач в пакете MAPLE

Решение задач в пакете EXCEL

Задача линейного программирования в стандартной форме

Общий вид стандартной формы

Преобразование неравенств

Преобразование неограниченных по знаку переменных

Основы симплекс-метода

Система ограничений в каноническом виде

Определение 2.8. Элементарное преобразование представляет собой последовательность элементарных операций над строками, в результате которой коэффициент при некоторой переменной становиться равным единице в одном из уравнений и нулю в остальных уравнениях.

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

Определение Базисное решение называется допустимым, если значения входящих в него переменных неотрицательны.

Алгоритм симплекс-метода

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

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

Обозначим через приращение величины, получающееся при увеличении на единицу. Тогда Новое значение - Старое значение

(2.9)

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

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

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

Правило минимального отношения

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

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

Приведение задачи к стандартной форме при помощи дополнительных переменных дает:

Базисом называется совокупность базисных переменных текущей симплексной таблицы.

Постоянные Базис строка32000

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

Для определения переменной, выводимой из базиса применяют правило минимального отношения.

Не единственность оптимума.

Итак, если в оптимальной таблице имеется небазисная переменная с нулевой относительной оценкой, то оптимальное решение не единственно.

Основные шаги вычислительного процесса

Записать задачу в стандартной форме.

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

Вычислить вектор относительных оценок (строка ) при помощи правила скалярного произведения.

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

Определить при помощи правила минимального отношения переменную, выводимую из базиса.

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

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

Задачи минимизации

Подход первый. Преобразование задачи минимизации в эквивалентную задачу максимизации путем умножения целевой функции на (-1) и последующего применения симплекс-метода к задаче максимизации.

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

Модифицированный шаг 4.

Неограниченный оптимум

Вырожденность и зацикливание

Определение. Допустимое базисное решение, в котором одна или более базисных переменных равны нулю, называется вырожденным допустимым базисным решением. Допустимое базисное решение, в котором все базисные переменные положительны, называется невырожденным.

Правило для устранения зацикливания

Метод искусственных переменных

Двухэтапный симплекс-метод.

I этап. Цель этого этапа – найти начальное допустимое базисное решение исходной задачи.

Этап II. Цель второго этапа – найти решение исходной задачи

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