Разработка модели и решение задачи линейного программирования

 

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

УНИВЕРСИТЕТ

 

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

 

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

 

 

 

КУРСОВАЯ РАБОТА по дисциплине  
«ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ»

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

 

Выполнил: студент ___ группы __________________ (ФИО)

 

 

 

 

 

 

 

 

 

 

 

Москва 2012

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ 3

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

1.1. Общая математическая формулировка задачи линейного программирования…………………………………………………………………...5

1.2. Методы решения задачи линейного программирования…………………...7

2. РАЗРАБОТКА МОДЕЛИ И РЕШЕНИЕ ЗАДАЧИ О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ ДЛЯ ФИНАНСИРОВАНИЯ 15

2.1. Вербальная постановка задачи о выборе оптимальных проектов для финансирования…………………………………………………………………….15

2.2. Разработка экономико-математической модели задачи о выборе оптимальных проектов для финансирования…………………………….………15

2.3. Решение поставленной задачи симплекс-методом………………………...17

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

2.5. Интерпретация результатов расчетов и выработка управленческого решения……………………………………………...……………………………...28

ЗАКЛЮЧЕНИЕ 29

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 31

 

ВВЕДЕНИЕ

 

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

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

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

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

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

Данная цель обусловила решение в работе следующих задач:

1. Изучить понятие  и методы линейного программирования.

2. Рассмотреть основные  методы решения задач линейного  программирования.

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

4. На основе решения  принять управленческое решение  и обосновать его.

5. Сделать выводы.

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

Объектом исследования выступает решение задачи о выборе оптимальных проектов для финансирования.

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

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

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

 

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ  ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Общая математическая формулировка задачи линейного программирования

 

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

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

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

Формулировка  задачи линейного программирования

Естественной формой задачи линейного программирования является задача об определении максимума линейной целевой функции, обычно называемой линейной формой. Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных:

 

 

которая носит название целевой функции. Ставится задача: найти  экстремум (максимум или минимум) целевой функции f(x) при условии,

,

при i = 1, 2, 3, . . . , m.

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

Такую задачу называют "основной" или "стандартной" в линейном программировании.

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

Переменные двойственной задачи называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция  исходной задачи формулируется  на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум - вид ³;

2) матрица А, составленная  из коэффициентов при неизвестных  в системе ограничений исходной  задачи и аналогичная матрица А^т в двойственной задаче получаются друг из друга транспонированием;

3) число переменных  в двойственной задаче равно  числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче;

4) коэффициентами при  неизвестных в целевой функции  двойственной задачи являются  свободные члены в системе  ограничений исходной задачи, а  правыми частями в ограничениях  двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению  одной задачи соответствует переменная  другой задачи: номер переменной  совпадает с номером ограничения;  при этом ограничению, записанному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

Решая ЗЛП симплексным  методом, одновременно решается двойственная ЗЛП. Переменные двойственной задачи называют объективно обусловленными оценками.

1.2. Методы решения задачи линейного программирования

 

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

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

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

0-этап – нахождение  первоначально допустимого базисного  решения:

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

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

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

Пример исходной симплекс-таблицы для задачи ЛП:

Таблица 1

Симплекс-таблица

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

 

Нам известно, что x₁, x₂, x_n − исходные переменные, x_n+1, x_n+2, x_n+m − дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы, а исходные в первую строку).

Алгоритм применения симплекс-метода

• Подготовительный этап

Приводим задачу ЛП  к каноническому виду:

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

В случае, если в исходной задаче необходимо найти минимум  − знаки коэффициентов целевой функции F меняются на противоположные a0,n= −a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае, если условие содержит знак "≤" − коэффициенты запишутся без изменений.