Оптимизационные задачи в экономике и математический аппарат их решения

МИНИСТЕРСТВО  ПО ОБРАЗОВАНИЮ И НАУКЕ РФ

Государственное образовательное учреждение

высшего профессионального  образования

«Ивановская государственная текстильная академия»

(ИГТА)

 

 

 

Кафедра банковского  дела, учета и аудита

 

 

 

 

Курсовая  работа

по дисциплине «Математическое моделирование экономических систем»

на тему: 

«Оптимизационные  задачи в экономике и математический аппарат их решения»

 

 

 

 

Выполнила:

студентка  4 курса,

группы 4э7а

Котова  И.И.

Проверила:

Щеглакова А.К.

 

 

 

Иваново 2010

Содержание

 

Введение…………………………………………………………....…... 3

Глава 1. Теоретическое обоснование

1. Оптимизационные методы решения задач…..……....4-11

1.2.   Многокритериальная оптимизация……………..….12-14

Глава 2. Анализ оптимизационных методов на примере решения транспортной и производственной задач................................ ..15-23

Заключение…………………………………………………………. 24-25

Библиографический список……………………………………………26

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Под термином «оптимизация» в научной литературе понимают процесс или последовательность операций, позволяющих получить уточнённое решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением уже известных решений, а не доведением их до идеала. Поэтому под оптимизацией понимают, скорее, стремление к поиску наиболее точного и выгодного в заданных условиях решения, которое, возможно, и не будет найдено [8].

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

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

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

Глава 1. Теоретическое обоснование

1. Оптимизационные методы решения задач

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

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

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

Математический  инструментарий, позволяющий решать экономические задачи оптимального типа, называется программированием. Различают  линейное и нелинейное программирование [5].

На практике наибольшее распространение получило линейное программирование. Методы линейного программирования в математике известны под названием общей задачи линейного программирования. Аналитическая формулировка общей задачи линейного программирования.

 Общая  задача линейного программирования  формулируется следующим образом:  найти решение {Х₁,Х₂,….Х_n}, позволяющее максимизировать или минимизировать целевую функцию

F = C₁X₁+C₂X₂+…+ C_nX_n

при условиях

Х₁≥0; Х₂≥0; …; Х_n≥0.

Это развернутая  запись общей задачи линейного программирования, а сокращенная запись этой модели имеет вид: найти решение {X_j}, позволяющее максимизировать (минимизировать) функцию

при условиях

 , i = 1,2,…,n;

X_j ≥ 0, j = 1,2,…,n.

Вышеприведенные записи общей задачи линейного программирования называют аналитической формой записи.

Любое решение, удовлетворяющее условиям, называется допустимым решением. Допустимое решение  систем неравенств, удовлетворяющее  целевой функции, называется оптимальным  решением. Такое решение единственно  при заданных условиях [9].

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

при ограничениях AX≤B    и   X≥0, 

где С = (с₁, с₂,…, с_n);

 

где С  – матрица-строка;

А – матрица  системы;

Х – матрица-столбец  переменных;

В – матрица-столбец  свободных членов.

Симплекс-метод

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

(1)

 

где - некоторое подмножество индексов     и 

 и матрица, составленная из строк-векторов аⁱ, неособенная. Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют и такие, что для    Поскольку для то, очевидно, что . В силу единственности решения (3) .  С другой стороны, если - крайняя точка, то можно обозначить через   множество равенств

Обозначим через  матрицу, составленную из строк Если предположить, что , то существует нетривиальное нуль-пространство

(2) Выбирая достаточно малым по норме, можно добиться того, что для вектор или для и для достаточно малых .    Аналогично можно показать, что при этом и .

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

Основная  идея метода заключается в разбиении  множества переменных x = x₁, x₂, . . ., x_n на базисные и небазисные . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (x^B, x^N ) [1].

Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде:

                                                         (3)

Предположим, что матрица  имеет полный ранг, т.е. - невырожденная. Тогда из равенства (5) следует

                                                                       (4)

Целевая функция задачи ЛПР также  может быть разбита на базисную и  не базисную части:

Подстановка (6) дает

                                      (5)

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

Каким образом можно уменьшить далее значение целевой функции?

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

сохраняя  при этом неотрицательность базисных переменных .

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

Здесь будет рассмотрена простейшая:

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

Поскольку при  увеличении -й компоненты вектор приобретает вид:

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

Максимально возможное значение    определится при этом как

                                                                               (6)

Пусть - номер , на котором достигается минимум (6). Очевидно, что при этом     Говорят, что переменная выводится из базиса (обращается в нуль), а переменная вводится в базис. Целевая функция при этом уменьшается на величину [4].

Важную  роль в теории симплекс-метода играет условие невырожденности, в котором  предполагается полный ранг A_B и строгая положительность базисного решения в. При этом л > 0 и дcx < 0, то есть целевая функция уменьшается при переходе к новому базису.

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

В силу выпуклости задачи любое другое оптимальное решение будет иметь  также значение целевой функции, т.е. будет в этом смысле эквивалентно [7].

Геометрический метод

Рассмотрим задачу линейного программирования в стандартной форме с двумя  переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений  является многоугольник ABCDE (Рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное (или минимальное) значение.

Рассмотрим  так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a,       т.е. F = a, или     c₁x₁+c₂x₂ = а (1)

Линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты [2].

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

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

Уравнение линии функции (1) есть уравнение  прямой линии. При различных уровнях, а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c₁ и c₂ и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

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

Пусть имеются  три линии уровня:

F=c₁x₁ + c₂x₂ = а₁ (I)

F=c₁x₁ + c₂x₂ = а₂ (II)

F=c₁x₁ + c₂x₂ = а₃ (III)

Причём  линия II заключена между линиями I и III. Тогда а₁ < а₂ < а_{3 и} а₁ > а₂ > а_3.

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

Для определения  направления возрастания рекомендуется  изобразить две линии уровня и  определить, на какой них уровень  больше. Например, одну из линий взять  проходящей через начало координат (если линия функция имеет вид  F=c₁x₁ + c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А) [3].

 

2. Многокритериальная оптимизация

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

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

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

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

 

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

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

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

   

при выполнении условия

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

Также применяется метод достижения цели. Данный метод включает в себя выражение для множества намерений разработчика , которое связано с множеством целей . Такая формулировка задачи допускает, что цели могут быть или «недо-» или «передостижимыми», и что дает разработчику возможность относительно точно выразить исходные намерения. Относительная «недо-» или «передостижимости» поставленных намерений контролируется посредством вектора взвешенных коэффициентов и её возможно представить как стандартную задачу оптимизации в виде:

при условии, что

Член  вносит в данную задачу элемент ослабления, что, иначе говоря, обозначает жесткость заданного намерения. Весовой вектор w дает исследователю возможность достаточно точно выразить меру взаимосвязи между двумя целями. Например, установка весового вектора w как равного исходному намерению указывает на то, что достигнут тот же самый процент недо- или передостижимости цели . Посредством установки в ноль отдельного весового коэффициента (т.е. ) можно внести жесткие ограничения в поставленную задачу. Метод достижения цели обеспечивает подходящую интуитивную интерпретацию поставленной исследовательской задачи, которая, в свою очередь, является вполне разрешимой с помощью стандартных процедур оптимизации [3].

 

 

 

 

 

 

Глава 2. Анализ оптимизационных методов на примере решения транспортной и производственной задач

Решение транспортной задачи

Дано: Пусть у нас имеются два склада с сырьём; ежедневно с первого склада вывозится 60 т сырья, а со второго – 80 т. Сырьё используется двумя заводами, причём первый завод получает – 50 т, а второй – 90 т. Необходимо организовать оптимальную (наиболее дешёвую) схему перевозок, если известно, что доставка 1т сырья с первого склада на первый завод стоит 7 рублей, с первого склада на второй завод – 9 рублей, со второго склада на первый завод – 10 рублей, со второго склада на второй завод – 8 рублей.

Решение:  Обозначим через х₁, х₂ количество сырья, который нужно доставить с первой базы соответственно на первый, второй заводы, а через х₃, х количество сырья, который нужно доставить со второй базы соответственно на первый, второй заводы. Составим выражения, которые в соответствии с исходными данными должны удовлетворять следующим условиям:

х₁ + х₂ = 60;

х₃ + х₄ = 80;                                     (1)

х₁ + х₃ = 50;

х₂ + х₄ = 90.

 

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

х_i ≥ 0, где i = 1, . ., 4          (2)

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

f = 7х₁ + 9 х₂ + 10 х₃ + 8х _4. (3)

Таким образом, мы пришли к типичной задаче линейного программирования: найти оптимальные значения проектных  параметров х_i (i = 1, . ., 4), удовлетворяющим условиям (2), (3) и минимизирующим стоимость перевозок (3).

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

х₁ + х₂ = 60;

х₃ + х₄ = 80;                                           (4)

х₃ = 50 - х₁;

х₄ = 90 - х₂.

Поскольку в соответствии с (2) все проектные параметры должны быть неотрицательны, то с учётом (4) получим следующую систему неравенств:

х₁ ≥ 0, х₂ ≥ 0, 50 - х₁ ≥ 0, 90 - х₂ ≥ 0

Эти неравенства  можно записать в более компактном виде:

0 ≤ х₁ ≤ 50, 0 ≤ х₂ ≤ 90        (5)

Данная система  неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных  параметров х₁ и х₂ нужно найти оптимальные, минимизирующие целевую функцию f. Формула (3) для неё с учётом соотношений (4) принимает вид

f = 7х₁ + 9 х₂ + 10(50 - х₁) + 8(90 - х₂);

f = -3х₁ + х₂ + 1220.

Отсюда следует, что стоимость перевозок уменьшается  с увеличением значений х₁, поэтому нужно взять его наибольшее допустимое значение. В соответствии с (5) х₁= 50, тогда получим, что х₂ = 60 - х₁ = 10. Тогда оптимальные значения остальных параметров можно найти по формулам (4):

х₃ = 50 - х₁ =50 – 50 = 0, х₄ = 90 - х₂ = 90 – 10 = 80.

В этом случае минимальная общая стоимость  перевозок равна:

f = 7*50 + 9*10 + 10*0 + 8*80 = 350 + 90 + 0 + 640 = 1080.

То есть, минимальная общая стоимость  перевозок f = 1080.

Покажем на рис.3 схему доставки сырья на заводы (числа указывают количество сырья в тоннах).

 

                     

Рис.3. Схема доставки сырья на заводы.

Решение производственной задачи

Дано: для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

 

Вид сырья	Нормы расхода сырья на одно изделие, кг A                 B	Общее количество сырья, кг
I	12                4	300
II	4                 4	120
III	3                12	252
Прибыль от реализации одного изделия, ден. ед.	30               40

 

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

Решение: Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х₁ +4 х₂) единиц ресурса I, (4х₁ +4х₂) единиц ресурса II, (3х₁ +12х₂) единиц ресурса III. Так как потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х₁ +4х₂ ≤ 300;                             3х₁ + х₂ ≤ 75;

4х₁ +4х₂ ≤ 120;    или                    х₁ + х₂ ≤ 30;          (6)

3х₁ +12х₂ ≤ 252.                             х₁ +4х₂ ≤ 84.

 

По смыслу задачи переменные х₁ ≥ 0, х₂ ≥ 0.                      (7)

Суммарная прибыль  А составит 30х₁ от реализации продукции А и 40х ₂ от реализации продукции В, то есть : F = 30х₁ +40х ₂                 (8)

Далее будем решать задачу двумя  методами:

1способ – симплексный метод

С помощью  дополнительных неотрицательных переменных перейдём к системе уравнений. В  данном случае все дополнительные переменные вводятся со знаком « + », так как  все неравенства имеют вид  « ≤ ».

Получим систему ограничений в виде:

3₁ +х₂ + х₃ ≤ 75;

х₁ +х₂ + х₄ ≤ 30;                                                            (9)

х₁ + 4х₂ + х₅ ≤ 84.

Для нахождения первоначального базисного решения  разобьём переменные на две группы – основные и не основные. Так  как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные  переменные: х₃, х₄, х_5.

Второстепенные  переменные: х₁, х_{2. .}

Выразим основные переменные через второстепенные:

х₃ = 75 - 3х₁ - х₂ ;

х₄ = 30 - х₁ - х₂;                                                                 (10)

х₅ = 84 - х₁ - 4х_2.

 

Положив основные переменные равными нулю, то есть х₁ = 0, х₂ = 0, получим базисное решение Х₁ = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные: