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

 

 

 

 

 

 

 

 

 

 

 

 

Реферат

 

 

На тему: «Математические  методы исследования операций в экономике. Симплекс-метод».

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

1. Постановка задачи.

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

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

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

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

6. Реализация полученного  решения на практике.

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

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

Управление портфелем  активов. Рассмотрим проблему принятия инвестором решения о вложении имеющегося у него капитала. Набор характеристик потенциальных объектов для инвестирования, имеющих условные имена от А до F, задается следующей таблицей. 

 

Название	Доходность (в%)	Срок выкупа (год)	Надежность (в баллах)
А	5,5	2001	5
В	6,0	2005	4
С	8,0	2010	2
D	7,5	2002	3
Е	5,5	2000	5
F	7,0	2003	4

Предположим, что при принятии решения о приобретении активов  должны быть соблюдены условия:

a) суммарный объем капитала, который должен быть вложен, составляет $ 100 000;

b) доля средств, вложенная в один объект, не может превышать четверти от всего объема;

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

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

Приступим к составлению  экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как х_А, х_В, х_C, х_D, х_Е, х_F. Тогда суммарная прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде

(1)

На следующем этапе  моделирования мы должны формально  описать перечисленные выше ограничения  a-d на структуру портфеля.

a) Ограничение на суммарный  объем активов: 

 

 

хA + хB + хC + хD + хE + хF ≤ 100 000.

(2)

 

 b) Ограничение на размер доли каждого актива:  

хA ≤ 25 000, xB ≤ 25 000, xC ≤ 25 000,          xD ≤ 25 000,  xE ≤ 25 000, xF ≤ 25 000.

(3)

 

 c) Ограничение, связанное с необходимостью  вкладывать половину средств в долгосрочные активы:

xB + xC ≥ 50 000.

(4)

 

 d) Ограничение на долю ненадежных активов:

хC + хD ≤ 30 000.

(5)

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

хA ≥ 0, хB ≥ 0, хС ≥ 0, хD ≥ 0, хE ≥ 0, хF ≥ 0.

(6)

 

 Выражения (1)-(6) образуют математическую модель поведения инвестора. В рамках этой модели может быть поставлена задача поиска таких значений переменных х_A, x_B, x_C, x_D, x_E, x_F, при которых достигается наибольшее значение прибыли (т. е. функции (1)) и одновременно выполняются ограничения на структуру портфеля активов (2)-(6).

Перейдем теперь к рассмотрению более общих моделей и задач.  

 

1. Линейное программирование. Симплекс-метод.

 

 

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

(7)

на некотором множестве ^{, где} удовлетворяют системе ограничений

(8)

и, возможно, ограничениям      

(9)

Задачу линейного программирования, записанную в форме (7)-(9), называют общей задачей линейного программирования (ОЗЛП).

Если все ограничения  в задаче линейного программирования являются уравнениями и на все  переменные _{наложены усло}вия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:

(10)

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

Планом ЗЛП называется всякий вектор из пространства .

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

. 

Величина называется оптимальным значением целевой функции.

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

Рассмотрим следующий  пример. Пусть дана задача максимизации линейной целевой функции

 

на множестве 

 

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

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

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

Рис. 1

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

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

На рис. 1 изображен некоторый  частный случай, для которого решение ЗЛП достигается в угловой точке области .

 

2. Симплекс-метод. Пример решения ЗЛП симплекс-методом.

 

Классическим методом  решения ЗЛП стал симплекс-метод, получивший также в литературе название метода последовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом.

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

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

Рассмотрим на конкретном примере процесс решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:

			(11)
	(12)

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по данным столбцам вектора ограничений с положительными коэффициентами. Последнее означает, что столбцы {5, 2, 3} образуют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица Δ(β⁽¹⁾) и обратная по отношению к ней Δ^-1(β⁽¹⁾):

 

Используя их, получаем

 

 

 

 

Используя полученные значения A(β⁽¹⁾) и b(β⁽¹⁾), заполняем симплекс-таблицу T⁽¹⁾, соответствующую первой итерации (q=1). 

 

 

 

Поскольку строка оценок a₀(β⁽¹⁾)  в первом и четвертом столбцах содержит отрицательные элементы (a_0,1(β⁽¹⁾) = -84, a_0,4(β⁽¹⁾) = -88), план х(β⁽¹⁾) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f(x(β⁽¹⁾)) = -226 может быть улучшено. Следуя рекомендации алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)