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

 

 

 

 

 

 

 

 

 

 

 

 

Реферат

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича «Математические методы организации и планирования производства», вышедшая в 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|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)   

 

 

Он содержит два положительных  элемента. Применяя рекомендацию алгоритма, получаем λ₁=4/(1/3)=12, λ₂=14/3, и, стало быть r=2. Следовательно, столбец с номером N₂(β⁽¹⁾)=2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи N(β⁽²⁾) = {5, 4, 3}. Элемент a_2,3(β⁽¹⁾)  является ведущим (обведен кружком). Переходим к симплекс-таблице, соответствующей второй итерации T⁽²⁾, и полагаем индекс текущей итерации q = 2. 

 

 

 

В ходе выполнения второй итерации опять-таки определяются вводимый столбец а¹, выводимый а⁴ и ведущий элемент a_2,1(β⁽²⁾). Перейдя к итерации q = 3, имеем таблицу T⁽³⁾. 

 

 

 

Как видно из T⁽³⁾, строка оценок содержит только неотрицательные значения, поэтому достигнутый базис N(β⁽³⁾) = {5, 1, 3} является оптимальным. В итоге мы получаем, что вектор х^* = (7, 0, 31/3, 0, 5/3) является оптимальным планом (точкой максимума) задачи (11)-(12), максимальное значение целевой функции равно f*=f(х*)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362). 

 

3. Вычислительная схема, основанная на преобразовании обратных матриц.  Пример решения ЗЛП модифицированным симплекс-методом.

Анализируя вычислительную процедуру симплекс-метода с позиций  оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является этап пересчета значений А и b при переходе от одного базисного плана к другому. Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n, можно добиться существенной «экономии», выполняя на очередной итерации q преобразование  Жордана—Гаусса   не  над   матрицей А(β^(q)),   а   над   матрицей Δ^-1(β^(q)). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А(β^(q)) целиком. Реально в ней использовались только строка оценок a₀(β^(q))  и ведущий столбец a^l(β^(q)). Данные соображения положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

Приведем решение рассмотренной  ранее задачи (11)-(12), основанное на использовании процедуры модифицированного симплекс-метода. Оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5,2,3}. Для него уже были вычислены Δ^-1(β^(q)) и b(β^(q)), поэтому заполнение начальных таблиц T₁ и Т₂⁽¹⁾ не представляет труда.

На первой итерации мы переписываем нулевую строку 

 

 

из Т₂⁽¹⁾ в T₁ и, умножив ее на матрицу A, получаем строку оценок 

 

 

 

Так как a₀(β⁽¹⁾) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β⁽¹⁾, и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец 

 

 

 

из таблицы T₁ в Т₂⁽¹⁾ и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ^-1(β^(q)), расположенную в таблице Т₂⁽¹⁾  слева, на а⁴. 

 

 

 

 

 

После заполнения таблицы Т₂⁽¹⁾ данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов b_i(β⁽¹⁾)  и a_i,l(β⁽¹⁾)  для {iÎ1:m| a_i,l(β⁽¹⁾)>0} и определив минимальное из них, находим, что r = 2. Следовательно, столбец с номером N₂(β^(q))=2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N(β⁽²⁾) = {5, 4, 3}. Элемент a_2,3(β⁽¹⁾)  является ведущим (обведен кружком). Переходим к симплекс-таблице, соответствующей второй итерации Т₂⁽²⁾, и полагаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т₂⁽²⁾ и Т₂⁽³⁾, на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т₂⁽³⁾.

 

 

4. Понятие двойственной задачи ЛП. Экономическая интерпретация.

Пусть задана КЗЛП (10). Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то

 

 

 

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х ≥ 0 справедливо неравенство

(13)

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

Если задана каноническая задача ЛП

(14)

     то задача ЛП

(15)

    называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к (D*,f*) называется прямой (или исходной). 

Традиционная экономическая  интерпретация двойственной задачи ЛП базируется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (j-й) элемент вектора х рассматривается как план выпуска продукции данного вида в натуральных единицах, с_j — цена единицы продукции j-го вида, а^j — вектор, определяющий технологию расходования имеющихся m ресурсов на производство единицы продукции j-го вида, b — вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых  значений A, b и с найден оптимальный план х*, максимизирующий суммарный доход max{cx}=cx*. Достаточно естественным представляется вопрос: как будет изменяться оптимальный план х* при изменении компонент вектора ограничений b и, в частности, при каких вариациях b оптимальный план х* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчивости х* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов b_i; могут существенно колебаться после принятия планового решения х*.

Когда вектор ограничений b изменяется на Δb или, как еще говорят, получает приращение Δb, то возникают соответствующие вариации для оптимального плана х*(b+Δb) и значения целевой функции f(х*(b+Δb)). Допустим, приращение Δb таково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+Δb)≥ 0. Определим функцию F(b), возвращающую оптимальное значение целевой функции задачи (D(b), f) для различных значений вектора ограничений b 

 

(16)

Рассмотрим отношение  ее приращения F(b+Δb)-F(b) к приращению аргумента Δb. Если для некоторого i устремить Δb_i 0, то мы получим 

 

(17)

 

Учитывая, что

(18)

и подставив (18) в (17), приходим к выражению 

 

(19)

 

 Из формулы (19) вытекает экономическая интерпретация оптимальных переменных двойственной задачи. Каждый элемент u_i* может рассматриваться как предельная (мгновенная) оценка вклада i-го ресурса в суммарный доход F при оптимальном решении х*. Грубо говоря, величина u_i* равна приросту дохода, возникающему при увеличении ресурса i на единицу при условии оптимального использования ресурсов. 

 

5. Двойственный симплекс-метод. Пример решения ЗЛП двойственным симплекс-методом.

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

В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (14). На рис. 2 изображен конус К положительных линейных комбинаций расширенных векторов условий а^j для случая m = 2, n = 6, а на рис. 3 — (для большей наглядности) — поперечное сечение данного конуса некоторой плоскостью L, проходящей параллельно оси аппликат.

С каждым планом и задачи, двойственной по отношению к (14), можно взаимно однозначно связать гиперплоскость, проходящую через начало координат и перпендикулярную вектору (-1,и). Допустимые планы двойственной задачи (15) должны удовлетворять условиям иА ≥ с, которые можно переписать в виде (1, и) А ≥ 0 . Последнее означает, что всякий расширенный вектор условий а^j лежит «ниже» плоскости, определяемой вектором (-1, и). Таким образом, любому допустимому плану двойственной задачи в рассматриваемом примере соответствует некоторая плоскость, расположенная выше всех расширенных векторов, а стало быть, и конуса К. На рис. 3, где изображено поперечное сечение, конусу К отвечает многогранник, а «гиперплоскостям двойственных планов» — пунктирные линии, являющиеся их следами.

Рис. 2                                   Рис. 3

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

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

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

 

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

Рассмотрим на конкретном, примере процесс решения КЗЛП двойственным симплекс-методом. Для этого вернемся к задаче (11)-(12). Предположим, что произошли изменения в векторе ограничений b в результате которых

 

Содержание исходной симплекс-таблицы T⁽¹⁾ (за исключением столбца b(β⁽¹⁾)) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного ранее. Для вычисления значений b(β⁽¹⁾) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации:

 

В результате имеем:

 

Как видно из таблицы Т⁽¹⁾, в столбце b(β⁽¹⁾) содержатся отрицательные элементы b₁(β⁽¹⁾) = - 1/3<0), то есть базис β⁽¹⁾ ={ ⁵, ¹, ³} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β⁽¹⁾) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r = 1 и N₁(β⁽¹⁾)=5. Далее рассматриваем строку a₁(β⁽¹⁾) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ₂ =42:(-(-1/6))=252, λ₄ =38:(-(-1/6))=228. λ₂> λ₄, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T⁽²⁾.

 

Поскольку b(β⁽²⁾) >0, то достигнутый базис N(β⁽²⁾) = {4,1,3} является оптимальным. Из Т⁽²⁾ можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции f(x*)= 444.