Справочник основных терминов




Скачать 422.45 Kb.
НазваниеСправочник основных терминов
страница1/3
Дата конвертации22.07.2013
Размер422.45 Kb.
ТипСправочник
  1   2   3
Словарь – СПРАВОЧНИК ОСНОВНЫХ терминов




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


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

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

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

33

МЕТОД ГОМОРИ

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

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

34

МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

Процесс решения можно представить в виде следующих шагов:

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

  • Формирование ветвей исследования. Допустим, условию целочисленности не удовлетворяют переменные , . Тогда на основе дробного значения, например, формируются две не связанные между собой подзадачи:

а) ; б)

(- целая часть )

  • Решение подзадачи а).

  • Решение подзадачи б).

35

ТРАНСПОРТНАЯ ЗАДАЧА

Это одна из распространенных задач ЛП. Ее цель – разработка наиболее рациональных путей и способов транспортировки товаров.

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

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

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


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


,

,

.



36

ОТКРЫТАЯ И ЗАКРЫТАЯ транспортные задачи

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


  1. Если сумма запасов груза равна суммарной потребности в нем, т.е.

,

то транспортная задача называется закрытой.


Математическая постановка закрытой транспортной задачи имеет вид:


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


,

,

.

  1. Если сумма запасов груза не равна суммарной потребности в нем, т.е.

,

то транспортная задача называется открытой.

При этом:

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

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




  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

Справочник основных терминов iconСправочник основных терминов
Если число строк в таблице не совпадает с числом столбцов, т е., то матрица называется прямоугольной. Матрица, у которой число строк...
Справочник основных терминов iconКемеровский технологический институт пищевой промышленности т. В. Батурина С. В. Ивлев Основные понятия по политологии и социологии Краткий словарь и
Словарь-справочник раскрывает содержание основных политологических понятий и терминов, широко употребляемых в современной общественно...
Справочник основных терминов iconСправочник терминов Веб-сайт Редакция 1 Стр из Информация для сайта фабрики «Ренессанс»
Деталь, конструкция которой обеспечивает плавное, пружинистое соприкосновение элементов мебели в процессе эксплуатации
Справочник основных терминов iconМеждународные правила толкования торговых терминов
Целью Инкотермс является обеспечение комплекта международных правил толкования торговых терминов, наиболее часто используемых во...
Справочник основных терминов iconСправочник состоит из следующих разделов
Настоящий справочник включает полный перечень произведений Д. Б. Кабалевского и их библиографию
Справочник основных терминов iconСправочник составлен и подготовлен
...
Справочник основных терминов iconСправочник составлен и подготовлен
...
Справочник основных терминов iconСправочник составлен и подготовлен
...
Справочник основных терминов iconКомментарий к Международным правилам толкования торговых терминов "Инкотермс 2000" (под ред. Галенской Л. Н.)
Цель инкотермс установление ряда международных правил для толкования наиболее часто используемых торговых терминов во внешней торговле....
Справочник основных терминов iconСправочник укрупненных базовых цен на
Справочник предназначен для применения предприятиями (организациями) различных организационно-правовых форм, выполняющими изыскательские...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©kk.docdat.com 2013
обратиться к администрации
Библиотека
Главная страница