birmaga.ru
добавить свой файл

1 2 3 4
Словарь – СПРАВОЧНИК ОСНОВНЫХ терминов



ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ


1

ОПЕРАЦИЯ

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

2

ОПТИМИЗАЦИЯ

  1. Процесс приведения системы в наилучшее (оптимальное) состояние.

  2. Процесс нахождения экстремума функции, т.е. выбор наилучшего варианта из множества возможных.

3

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ

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

4

КРИТЕРИЙ ОПТИМАЛЬНОСТИ

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

5

ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ


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

6

ОПТИМАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Применение в экономике методов математического программирования.

7

ОПТИМИЗАЦИОННАЯ ЗАДАЧА

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


ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ


8

МАТРИЦА

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


,

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

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


9

ЕДИНИЧНАЯ МАТРИЦА

Квадратная матрица, на главной диагонали которой стоят единицы, а все остальные элементы нулевые.

10

ОПРЕДЕЛИТЕЛЬ (детерминант) -го порядка

Число, которое ставится в соответствие квадратной матрице-го порядка. Это число обозначается , , и вычисляется по определенному закону. Например, определитель второго порядка вычисляется по правилу:

.

11

МИНОР элемента определителя -го порядка

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


12

АЛГЕБРАИЧЕСКОЕ ДОПОЛНЕНИЕ элемента определителя -го порядка

Минор этого элемента, взятый со знаком . Обозначение: .

13

НЕВЫРОЖДЕННАЯ МАТРИЦА

Квадратная матрица с ненулевым определителем.

14

ОБРАТНАЯ МАТРИЦА к квадратной матрице

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

Обратная матрица существует только для невырожденных матриц.

15

МИНОР k-го порядка матрицы

Определитель, который состоит из элементов матрицы, расположенных на пересечении ее строк и столбцов.

16

РАНГ МАТРИЦЫ


Наивысший порядок минора матрицы, отличного от нуля.

17

УРАВНЕНИЕ

Равенство, в котором одна или несколько букв считаются (называются) неизвестными.

18

ЛИНЕЙНОЕ УРАВНЕНИЕ

Уравнение, содержащее неизвестные (переменные) только в первой степени. Например, уравнение является линейным уравнением с неизвестными , ,…..

19

СИСТЕМА ЛИНЕЙНЫХ УРАВНЕНИЙ

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

столбец — столбцом неизвестных, а столбец — столбцом свободных членов.

Если , то определитель матрицы системы называется определителем системы.

20


ФОРМУЛЫ КРАМЕРА

Формулы, позволяющие найти решение (единственное) системы линейных уравнений с неизвестными в случае, если определитель этой системы отличен от нуля. Решение такой системы по формулам Крамера имеет вид:

; ;……,

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

21

МАТРИЧНАЯ ЗАПИСЬ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ. МАТРИЧНЫЙ МЕТОД РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Представление системы линейных уравнений с неизвестными в виде матричного уравнения

,

где - матрица системы; - столбец неизвестных; - столбец свободных членов.

Если и матрица - невырожденная, то решение системы линейных уравнений определяется по формуле

, где - обратная матрица. (Матричный метод решения системы линейных уравнений).

22

МЕТОД ГАУССА

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


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


23

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП)

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

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

24

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП)

Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.

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

,

при ограничениях
где - неизвестные;

- целевая функция.


Матрица называется матрицей условий, а столбцы этой матрицы

- векторами условий задачи ЛП.

Вектор называется вектором неизвестных, а вектор - вектором ограничений.

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

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

Математическая модель задачи ЛП в более краткой записи имеет вид:

;

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

;



25

КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

26


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

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

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

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

Для задачи ЛП с двумя переменными

,

при ограничениях
алгоритм решения графическим методом имеет вид:

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

  • Построить вектор ;

  • Провести перпендикулярно вектору линию уровня функции так, чтобы она пересекала область ;

  • Прямую перемещать по направлению вектора для задач на максимум (и в противоположном направлении для задач на минимум) до тех пор, пока она не перестанет пересекать область;

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

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


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

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


  • Определить координаты точки экстремума (эта точка называется точкой оптимума) и значение целевой функции в ней.




27

ОПОРНОЕ РЕШЕНИЕ задачи ЛП

Допустимое решение задачи ЛП в канонической форме является опорным решением этой задачи, если в нем все свободные переменные равны нулю (базисные переменные при этом равны правым частям системы ограничений).


28

СИМПЛЕКС-МЕТОД решения задач ЛП

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


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


  • Используя каноническую форму задачи ЛП, определить начальное опорное решение, приравняв нулю свободные переменные. На этом шаге строится исходная симплекс-таблица и в нее заносятся все базисные переменные, коэффициенты при переменных в ограничениях, а также их правые части. Для целевой функции в таблице вводится отдельная строка (- строка). Для включения в симплекс-таблицу целевую функцию преобразуют путем переноса ее правой части влево от знака равенства: .

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

  • Из числа текущих базисных переменных выбирается исключаемая переменная, которая должна принять нулевое значение. на этом шаге проверяется условие допустимости: в задачах и максимизации, и минимизации целевой функции в качестве исключаемой выбирается та базисная переменная, для которой отношение значения в правой части соответствующего ограничения к положительному коэффициенту разрешающего столбца минимально. Переменная, исключаемая из состава базисных переменных, определяет разрешающую строку.
  • Находится новое опорное решение, соответствующее новым базисным и свободным переменным. Элемент симплекс-таблицы на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом. Очередная итерация проводится по схеме:


    1. все элементы разрешающей строки делятся на разрешающий элемент;

    2. все элементы разрешающего столбца заменяются нулями, а сам разрешающий элемент – единицей;

    3. все остальные элементы симплекс-таблицы вычисляются по правилу «прямоугольника»

, где разрешающий

элемент.





……….

…………

………..



…………






29

ДВОЙСТВЕННЫЕ ЗАДАЧИ

Взаимно двойственные задачи ЛП (двойственная пара) имеют следующий вид:



,

,





При этом задача максимизации называется прямой задачей, а задача минимизации – двойственной к ней.

Во взаимно двойственных задачах всегда выполняются следующие условия:

  • одна из задач является задачей максимизации, а другая – задачей минимизации; в системе ограничений задачи максимизации неравенства записаны со знаком , а в системе ограничений задачи минимизации – со знаком ;
  • каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения, при этом ограничению в виде неравенства соответствует переменная с условием неотрицательности;


  • матрица условий одной задачи получается из матрицы условий другой задачи путем транспонирования;

  • коэффициенты целевой функции одной задачи соответственно равны свободным членам системы ограничений другой задачи.


Из определения двойственной пары следует, что отношение двойственности взаимное, и задача, двойственная двойственной, совпадает с исходной задачей.

30

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

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

Применение двойственного симплекс-метода предусматривает выполнение следующих действий:

  • Преобразование всех ограничений задачи ЛП в ограничения типа , при этом часть ограничений будет иметь отрицательные правые части; для всех ограничений вводятся дополнительные переменные;

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


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

32

ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЦЛП)



следующая страница >>