Размещено на http://www.allbest.ru/

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОБЛАСТНОЙ

УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА

ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра прикладной математики и информатики

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

По дисциплине

Основы математического моделирования социально-экономических процессов

Тема: Разработка модели и решение задачи линейного программирования (на примере задачи о выборе оптимальных проектов для финансирования)

Выполнила

студентка 26 группы

Кожухова Анастасия Андреевна

Москва 2012г

Содержание

Введение

1. Теоретическая глава

1.1 Общая математическая формулировка решаемой экономико-математической задачи

1.2 Методы решения задачи

2. Расчетная глава

2.1 Вербальная постановка конкретной решаемой задачи

2.2 Разработка экономико-математической модели решаемой задачи (прямой и двойственной)

2.3 Решение поставленной задачи в упрощенном варианте одним из методов «вручную» (геометрическим, симплексным и др.)

2.4 Решение поставленной задачи с помощью средств EXСEL (надстройки «Поиск решения», «Анализ данных»).

2.5 Интерпретация результатов расчетов и выработка управленческого решения (с учетом решения двойственной задачи)

Заключение

Литература

Введение

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

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

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

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

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

1. Теоретическая глава

1.1 Общая математическая формулировка решаемой экономико-математической задачи

Предположим, что проект требует инвестиций , , в конце n периодов времени.

Рисунок 1 - Зависимость времени и инвестиций

Для финансирования проекта фирма в начальный момент времени создает инвестиционный фонд, размером денежных единиц. Инвестиционный фонд должен обеспечить выплату требуемых денежных сумм , , в моменты времени 1, 2, …, n. (Причем вкладывает деньги в инвестиционный фонд только в начальный момент времени.) При этом фирма имеет возможность вкладывать деньги из инвестиционного фонда в m видов финансовых инструментов (облигации, банковские депозиты, ссуды и др.).

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

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

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

. (1)

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

Перенеся суммы из правых частей этих неравенств в левые, получим

 (2)

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

(3)

Здесь через обозначен вес вложений в финансовые инструменты вида i в k-м периоде. Причем будем считать, что определяется следующим образом:

(4)

Приведем ограничение (3) к линейному виду. Подставив (4) в (3) после несложных алгебраических преобразований, получим:

(5)

Итак, математическая постановка задачи оптимального финансирования проекта - следующая: минимизировать целевую функцию (1) при ограничениях (2), (5) и условии неотрицательности переменных , т.е.

 (6)

, (7)

, (8)

. (9)

1.2 Методы решения задачи

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

Алгебраический метод решения задач ЛП называется симплекс-методом.

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

1. Все ограничения записываются в виде равенств с неотрицательной правой частью;

2. Значения всех переменных неотрицательны;

3. Целевая функция подлежит максимизации или минимизации.

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

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

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

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

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

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

Пусть модель содержит m-уравнений и n неизвестных, тогда (n - m) переменных должны быть равны нулю.

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

Вычислительные процедуры симплекс-метода:

0. определить начальное допустимое базисное решение, приравнивая к нулю (n-m) небазисных переменных.

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

2. из числа переменных текущего базиса выбрать исключаемую переменную.

3. найти новое базисное решение и перейти к шагу 1.

математический экономический линейный программирование

2. Расчетная глава

2.1 Вербальная постановка конкретной решаемой задачи

Промышленная организация заключила контракт со строительной компанией о строительстве нового цеха. В условиях контракта сказано, что промышленная организация должна выплатить строительной организации 60 д.е. в конце первого квартала и 100 д.е. в конце второго квартала. Для финансирования этого проекта промышленная организация создает фонд. (Причем промышленная организация вкладывает деньги в инвестиционный фонд только в начале первого квартала.) При этом существует возможность вкладывать деньги в бескупонные облигации сроком на один квартал в начале первого квартала и в начале второго квартала. Эффективная доходность таких вложений составляет 3%, а уровень риска - 1. Также можно вкладывать деньги в бескупонные облигации в начале первого квартала сроком на пол года. Эффективная доходность таких вложений - 10%, уровень риска - 3. Требуется минимизировать начальные вложения в инвестиционный фонд. При этом средневзвешенный уровень риска в течение каждого из двух кварталов не должен превышать 2.

2.2 Разработка экономико-математической модели решаемой задачи (прямой и двойственной)

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

Тогда , , , ,

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

Это ограничение легко привести к линейному виду: . Так как в течение второго квартала деньги вложены в финансовые инструменты второго и третьего видов, ограничение, связанное с риском, для второго квартала имеет вид: , или .

Таким образом, математическая модель задачи - следующая:

(10)

, (11)

, (12)

, (13)

, (14)

(15)

Подставив в (11) - (14) известные значения параметров, получим:

, (15)

, (16)

, (17)

, (18)

, (19)

2.3 Решение поставленной задачи в упрощенном варианте одним из методов «вручную» (геометрическим, симплексным и др.)

Решим прямую задачу линейного программирования симплекс-методом.

Определим минимальное значение целевой функции F(X) = x1+x2 при следующих условиях-ограничениях.

1.03x1-x3?60

1.1x2+1.03x3?100

-x1+x2?0

x2-x3?0

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x5 со знаком минус. В 3-м неравенстве смысла (?) вводим базисную переменную x6. В 4-м неравенстве смысла (?) вводим базисную переменную x7.

1.03x1 + 0x2-1x3-1x4 + 0x5 + 0x6 + 0x7 = 60

0x1 + 1.1x2 + 1.03x3 + 0x4-1x5 + 0x6 + 0x7 = 100

-1x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = 0

0x1 + 1x2-1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 0

Введем искусственные переменные x: в 1-м равенстве вводим переменную x8; в 2-м равенстве вводим переменную x9;

1.03x1 + 0x2-1x3-1x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 60

0x1 + 1.1x2 + 1.03x3 + 0x4-1x5 + 0x6 + 0x7 + 0x8 + 1x9 = 100

-1x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 0

0x1 + 1x2-1x3 + 0x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 0

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = Mx8+Mx9 > min

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

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

Из уравнений выражаем искусственные переменные:

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1x2-1.03x3+x5

которые подставим в целевую функцию:

F(X) = M(60-1.03x1+x3+x4) + M(100-1.1x2-1.03x3+x5) > min

Или

F(X) = (-1.03M)x1+(-1.1M)x2+(-0.03M)x3+(M)x4+(M)x5+(160M) > min

Введем новую переменную x0 = -1.03x1-1.1x2-0.03x3.

Выразим базисные переменные <8, 9, 6, 7> через небазисные.

x0 = 160-1.03x1-1.1x2-0.03x3+x4+x5

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1x2-1.03x3+x5

x6 = 0+x1-x2

x7 = 0-x2+x3

Переходим к основному алгоритму симплекс-метода.

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

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(-1.03,-1.1,-0.03,1,1,0,0,0,0) = -1.1

x0 = 160-1.03x1-1.1x2-0.03x3+x4+x5

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1x2-1.03x3+x5

x6 = 0+x1-x2

x7 = 0-x2+x3

В качестве новой переменной выбираем x2.

3. Определение новой свободной переменной.

Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2 и из них выберем наименьшее

Вместо переменной x6 в план войдет переменная x2.

4. Пересчет всех уравнений.

Выразим переменную x2 через x6

x2 = 0+x1-x6

и подставим во все выражения.

x0 = 160-1.03x1-1.1(0+x1-x6)-0.03x3+x4+x5

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1(0+x1-x6)-1.03x3+x5

x7 = 0-(0+x1-x6)+x3

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

x0 = 160-2.13x1-0.03x3+x4+x5+1.1x6

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1x1-1.03x3+x5+1.1x6

x2 = 0+x1-x6

x7 = 0-x1+x3+x6

Полагая небазисные переменные x = (8, 9, 2, 7) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (2.13, 0, 0.03, -1, -1, -1.1, 0, 0, 0), x0 = 160

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(-2.13,0,-0.03,1,1,1.1,0,0,0) = -2.13

x0 = 160-2.13x1-0.03x3+x4+x5+1.1x6

x8 = 60-1.03x1+x3+x4

x9 = 100-1.1x1-1.03x3+x5+1.1x6

x2 = 0+x1-x6

x7 = 0-x1+x3+x6

В качестве новой переменной выбираем x1.

3. Определение новой свободной переменной.

Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1 и из них выберем наименьшее

Вместо переменной x7 в план войдет переменная x1.

4. Пересчет всех уравнений.

Выразим переменную x1 через x7

x1 = 0+x3+x6-x7

и подставим во все выражения.

x0 = 160-2.13(0+x3+x6-x7)-0.03x3+x4+x5+1.1x6

x8 = 60-1.03(0+x3+x6-x7)+x3+x4

x9 = 100-1.1(0+x3+x6-x7)-1.03x3+x5+1.1x6

x2 = 0+(0+x3+x6-x7)-x6

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

x0 = 160-2.16x3+x4+x5-1.03x6+2.13x7

x8 = 60-0.03x3+x4-1.03x6+1.03x7

x9 = 100-2.13x3+x5+1.1x7

x2 = 0+x3-x7

x1 = 0+x3+x6-x7

Полагая небазисные переменные x = (8, 9, 2, 1) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 2.16, -1, -1, 1.03, -2.13, 0, 0), x0 = 160

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.

2. Определение новой базисной переменной.

max(0,0,-2.16,1,1,-1.03,2.13,0,0) = -2.16

x0 = 160-2.16x3+x4+x5-1.03x6+2.13x7

x8 = 60-0.03x3+x4-1.03x6+1.03x7

x9 = 100-2.13x3+x5+1.1x7

x2 = 0+x3-x7

x1 = 0+x3+x6-x7

В качестве новой переменной выбираем x3.

3. Определение новой свободной переменной.

Вычислим значения Di по всем уравнениям для этой переменной: bi / ai3 и из них выберем наименьшее

Вместо переменной x9 в план войдет переменная x3.

4. Пересчет всех уравнений.

Выразим переменную x3 через x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

и подставим во все выражения.

x0 = 160-2.16(46.95+0.47x5+0.52x7-0.47x9)+x4+x5-1.03x6+2.13x7

x8 = 60-0.03(46.95+0.47x5+0.52x7-0.47x9)+x4-1.03x6+1.03x7

x2 = 0+(46.95+0.47x5+0.52x7-0.47x9)-x7

x1 = 0+(46.95+0.47x5+0.52x7-0.47x9)+x6-x7

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

x0 = 58.59+x4-0.0141x5-1.03x6+1.01x7+1.01x9

x8 = 58.59+x4-0.0141x5-1.03x6+1.01x7+0.0141x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

x2 = 46.95+0.47x5-0.48x7-0.47x9

x1 = 46.95+0.47x5+x6-0.48x7-0.47x9

Полагая небазисные переменные x = (8, 3, 2, 1) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, -1, 0.0141, 1.03, -1.01, 0, -1.01), x0 = 58.59

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(0,0,0,1,-0.0141,-1.03,1.01,0,1.01) = -1.03

x0 = 58.59+x4-0.0141x5-1.03x6+1.01x7+1.01x9

x8 = 58.59+x4-0.0141x5-1.03x6+1.01x7+0.0141x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

x2 = 46.95+0.47x5-0.48x7-0.47x9

x1 = 46.95+0.47x5+x6-0.48x7-0.47x9

В качестве новой переменной выбираем x6.

3. Определение новой свободной переменной.

Вычислим значения Di по всем уравнениям для этой переменной: bi / ai6 и из них выберем наименьшее:

Вместо переменной x8 в план войдет переменная x6.

4. Пересчет всех уравнений.

Выразим переменную x6 через x8

x6 = 56.88+0.97x4-0.0137x5+0.98x7-0.97x8+0.0137x9

и подставим во все выражения.

x0=58.59+x4-0.0141x5-1.03(56.88+0.97x4-0.0137x5+0.98x7-0.97x8+0.0137x9)+1.01x7+1.01x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

x2 = 46.95+0.47x5-0.48x7-0.47x9

x1 = 46.95+0.47x5+(56.88+0.97x4-0.0137x5+0.98x7-0.97x8+0.0137x9)-0.48x7-0.47x9

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

x0 = 0+0x4-0x5+0x7+1x8+1x9

x6 = 56.88+0.97x4-0.0137x5+0.98x7-0.97x8+0.0137x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

x2 = 46.95+0.47x5-0.48x7-0.47x9

x1 = 103.83+0.97x4+0.46x5+0.5x7-0.97x8-0.46x9

Полагая небазисные переменные x = (6, 3, 2, 1) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, -0, 0, 0, -0, -1, -1), x0 = 0

Выражение для x0 не содержит отрицательных элементов.

Найден оптимальный план.

x0 = 0+0x4-0x5+0x7+1x8+1x9

x6 = 56.88+0.97x4-0.0137x5+0.98x7-0.97x8+0.0137x9

x3 = 46.95+0.47x5+0.52x7-0.47x9

x2 = 46.95+0.47x5-0.48x7-0.47x9

x1 = 103.83+0.97x4+0.46x5+0.5x7-0.97x8-0.46x9

На этом первый этап симплекс-метода завершен.

Переходим ко второму этапу.

Удаляем переменные с искусственными переменными.

x6 = 56.88+0.97x4-0.0137x5+0.98x7

x3 = 46.95+0.47x5+0.52x7

x2 = 46.95+0.47x5-0.48x7

x1 = 103.83+0.97x4+0.46x5+0.5x7

Выразим базисные переменные:

x2 = 46.95+0.47x5-0.48x7

x1 = 103.83+0.97x4+0.46x5+0.5x7

которые подставим в целевую функцию:

F(X) = (103.83+0.97x4+0.46x5+0.5x7) + (46.95+0.47x5-0.48x7)

или

F(X) = 150.78+0.97x4+0.93x5+0.0178x7

Получаем новую систему переменных.

x0 = 150.78+0.97x4+0.93x5+0.0178x7

x6 = 56.88+0.97x4-0.0137x5+0.98x7

x3 = 46.95+0.47x5+0.52x7

x2 = 46.95+0.47x5-0.48x7

x1 = 103.83+0.97x4+0.46x5+0.5x7

Переменных для включения в новый базис не найдено.

Выражение для x0 не содержит отрицательных элементов.

Найден оптимальный план.

Окончательный вариант системы уравнений:

x0 = 150.78+0.97x4+0.93x5+0.0178x7

x6 = 56.88+0.97x4-0.0137x5+0.98x7

x3 = 46.95+0.47x5+0.52x7

x2 = 46.95+0.47x5-0.48x7

x1 = 103.83+0.97x4+0.46x5+0.5x7

Оптимальный план можно записать так:

x6 = 56.88

x3 = 46.95

x2 = 46.95

x1 = 103.83

F(X) = 1*103.83 + 1*46.95 = 150.78

2.4 Решение поставленной задачи с помощью средств EXСEL (надстройки «Поиск решения», «Анализ данных»)

Вводим данные задачи в ячейки (рисунок 1).



Рисунок 2 - Ввод данных в ячейки

Записываем необходимые формулы для решения задачи

Рисунок 3 - Ввод формул

Вызываем окно Сервис> Поиск решения

Рисунок 4 - Надстройка поиск решения

Полученный результат приведен ниже

Рисунок 5 - Результат решения задачи

2.5 Интерпретация результатов расчетов и выработка управленческого решения (с учетом решения двойственной задачи)

Составим двойственную задачу к прямой задаче.

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

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

Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj.

1.03y1-y3?1

1.1y2+y3+y4?1

-y1+1.03y2-y4?0

60y1+100y2 > max

y1 ? 0

y2 ? 0

y3 ? 0

y4 ? 0

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

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

Из первой теоремы двойственности следует, что Y = C*A-1.

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

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A-1 =

Оптимальный план двойственной задачи равен:

y1 = 0.97

y2 = 0.93

y3 = 0

y4 = -0.02

Z(Y) = 60*0.97+100*0.93+0*0+0*-0.02 = 150.78

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

1.03*103.83 + 0*46.95 + -1*46.95 = 60 = 60

0*103.83 + 1.1*46.95 + 1.03*46.95 = 100 = 100

-1*103.83 + 1*46.95 + 0*46.95 = -56.88 < 0

0*103.83 + 1*46.95 + -1*46.95 = 0 = 0

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ой ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).

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

Неиспользованный экономический резерв ресурса 3 составляет 56.88 (0--56.88).

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

4-ое ограничение прямой задачи выполняется как равенство. Это означает, что 4-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y4>0).

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

Обоснование эффективности оптимального плана.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

1.03*0.97 + 0*0.93 + -1*0 + 0*-0.02 = 1 = 1

0*0.97 + 1.1*0.93 + 1*0 + 1*-0.02 = 1 = 1

-1*0.97 + 1.03*0.93 + 0*0 + -1*-0.02 = -0 = 0

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).

3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).

Влияние запасов ресурсов на оптимальное решение прямой задачи.

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

Анализ устойчивости оптимального плана.

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

Чувствительность решения к изменению коэффициентов целевой функции.

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

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

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

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

?c3- = min [yk/d3k] для d3k>0.

?c3+ = |max [yk/d3k]| для d3k<0.

Таким образом, 3-параметр может быть уменьшен на 1.97 или увеличен на 0.03

Интервал изменения равен:

(c3 - ?c3-; c3 + ?c3+)

[0-1.97; 0+0.03] = [-1.97;0.03]

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

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

?c2- = min [yk/d2k] для d2k>0.

?c2+ = |max [yk/d2k]| для d2k<0.

Таким образом, 2-параметр может быть уменьшен на 0.04 или увеличен на 0

Интервал изменения равен:

(c2 - ?c2-; c2 + ?c2+)

[1--0.04; 1+0] = [1.04;1]

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

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

?c1- = min [yk/d1k] для d1k>0.

?c1+ = |max [yk/d1k]| для d1k<0.

Таким образом, 1-параметр может быть уменьшен на 1 или увеличен на 0.04

Интервал изменения равен:

(c1 - ?c1-; c1 + ?c1+)

[1-1; 1+0.04] = [0;1.04]

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

Чувствительность решения к изменению запасов сырья.

Из теоремы об оценках известно, что колебание величины bi приводит к увеличению или уменьшению f(X).

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

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

Найдем интервалы устойчивости ресурсов.

1-ый запас может изменяться в пределах:

?b1- = min [xk/dk1] для dk1>0.

?b1+ = |max [xk/dk1]| для dk1<0.

Таким образом, 1-ый запас может быть уменьшен на 58.59 или увеличен на 0

Интервал изменения равен:

(b1 - ?b1-; b1 + ?b1+)

[60-58.59; 60+0] = [1.41;60]

2-ый запас может изменяться в пределах:

?b2- = min [xk/dk2] для dk2>0.

?b2+ = |max [xk/dk2]| для dk2<0.

Таким образом, 2-ой запас может быть уменьшен на 100 или увеличен на 4160

Интервал изменения равен:

(b2 - ?b2-; b2 + ?b2+)

[100-100; 100+4160] = [0;4260]

4-ый запас может изменяться в пределах:

?b4- = min [xk/dk4] для dk4>0.

?b4+ = |max [xk/dk4]| для dk4<0.

Таким образом, 4-ый запас может быть уменьшен на 97.09 или увеличен на 57.75 Интервал изменения равен:

(b4 - ?b4-; b4 + ?b4+)

[0-97.09; 0+57.75] = [-97.09;57.75]

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

3-ий запас может изменяться в пределах:

0 ? ?b3 ? 46.95

[0-46.95; 0] = [-46.95;0]

Заключение

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

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

Во второй главе была непосредственно решена задача о выборе оптимальных проектов для финансирования (исходные данные взяты условно) симплекс-методом линейного программирования и с помощью прикладного программного пакета MS Excel.

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

Литература

1. Вилкас Э.И. Оптимальность в играх и решениях. - М.: Наука,1990.-256 с.

2. Зайцев М.Г. Методы оптимизации управления для менеджеров. - М.: Дело, 2002.

3. Информатика. Учебник. /Под ред. И.В.Макаровой. - 3-е изд.перераб. М.:Финансы и статистика, 2005-768 с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -- М.: МЦНМО, 2000.-960 с.

5. Кремер Н.Ш. Исследование операций в экономике. - М.: ЮНИТИ, 2010.

6. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22.-368 с.

7. Мищенко А.В., Джамай Е.В. Динамическая задача определения оптимальной производственной программы, Менеджмент в России и за рубежом №2 / 2002

8. Мищенко А.В., Попов А.А. Некоторые подходы к оптимизации инвестиционного портфеля , "Менеджмент в России и за рубежом", №2 / 2002

9. Орлова И.В. Экономико-математическое моделирование.- М.: ВЗФИ, 2004.

10. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

11. Шикин Е.В. Чхартишвили А.Г. Математические методы и модели в управлении: Учебник для ВУЗов. - М.: Дело, 2000.-440 с.

Размещено на Allbest.ru

...