Разработка модели и решение задачи линейного программирования. 2
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОБЛАСТНОЙ
УНИВЕРСИТЕТ
ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ
И ПРАВА
ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ
Кафедра прикладной математики и информатики
КУРСОВАЯ РАБОТА по дисциплине
«ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ
СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ»
Тема: «Разработка модели и решение задачи
линейного программирования
(на примере задачи о выборе оптимальных
проектов для финансирования)»
Выполнил: студент ___ группы __________________ (ФИО)
Москва 2012
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 3
1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5
1.1. Общая математическая
формулировка задачи линейного программирования……………………………………
1.2. Методы решения задачи линейного программирования…………………...7
2. РАЗРАБОТКА МОДЕЛИ И РЕШЕНИЕ ЗАДАЧИ О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ ДЛЯ ФИНАНСИРОВАНИЯ 15
2.1. Вербальная постановка
задачи о выборе оптимальных проектов
для финансирования…………………………………………
2.2. Разработка экономико-математической
модели задачи о выборе оптимальных проектов
для финансирования…………………………….………1
2.3. Решение поставленной задачи симплекс-методом………………………...17
2.4. Решение поставленной
задачи с помощью средств EXСEL (надстройка
«Поиск решения»)………………………………………………………
2.5. Интерпретация
результатов расчетов и выработка управленческого
решения……………………………………………...………
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 31
ВВЕДЕНИЕ
При выполнении любых действий и при принятии решений в различных областях деятельности основополагающим желанием является получение наилучшего результата. Смысл действий и принятие решений определяются заинтересованностью в этих действиях и решениях в соответствии с имеющимися возможностями. Заинтересованность может выражаться в получении максимальной прибыли, минимальной себестоимости при заданной производительности, максимальной производительности при заданных затратах.
Современная экономическая наука существенно опирается на математическое моделирование экономических процессов и пронизана различным математическим аппаратом, а применяющийся в ней математический язык позволяет более определенно и однозначно формулировать экономические факты и законы. Формализация основных особенностей функционирования экономических объектов позволяет оценить возможные последствия воздействия на них и использовать такие оценки в управлении.
Для решения задачи оптимального
управления необходимо иметь в той
или иной форме математическое описание
оптимизируемого объекта и
Исследование экономических явлений математическими методами, в частности в финансово-экономической сфере и бизнесе, помогает лицу, принимающему решение, произвести критический анализ ситуации и в результате более обоснованно и последовательно проводить определенную политику или стратегию поведения при решении сложных, комплексных проблем.1
Целью данной курсовой работы является решение задач оптимизации методами линейного программирования на примере задачи о выборе оптимальных проектов для финансирования.
Данная цель обусловила решение в работе следующих задач:
1. Изучить понятие
и методы линейного
2. Рассмотреть основные
методы решения задач
3. Построить математическую модель задачи о выборе оптимальных проектов для финансирования.
4. На основе решения
принять управленческое
5. Сделать выводы.
Предметом исследования курсовой работы является применение линейного программирования для решения задачи о выборе оптимальных проектов для финансирования в среде Microsoft Excel.
Объектом исследования выступает решение задачи о выборе оптимальных проектов для финансирования.
Методологической базой исследования являются общенаучные методы анализ, синтез, сравнение, аналогия, описательные методы и методы решения задач линейного программирования.
Информационной базой исследования выступают труды ученых, изучающих методы линейного программирования, учебная и специальная литература по методам исследования операций, ресурсы сети Интернет.
Структурно работа состоит из введения, теоретической части, практической части, заключения и списка использованных в работе источников.
1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1.1. Общая математическая формулировка задачи линейного программирования
На практике постоянно встречаются такие ситуации, когда достичь какого-то результата можно не одним, а многими различными способами. Естественно, при большом количестве решений выбирается наилучшее. Математически это обычно сводится к нахождению наибольшего и наименьшего значения некоторой функции. В зависимости от характера целевой функций и функций ограничения, различают разные виды математического программирования.
Линейное программирование (ЛП) – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т. е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.
Линейность целевой функции и линейность условий связи варьируемых переменных являются основной особенностью задач линейного программирования.2
Формулировка задачи линейного программирования
Естественной формой задачи линейного программирования является задача об определении максимума линейной целевой функции, обычно называемой линейной формой. Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных:
которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии,
при i = 1, 2, 3, . . . , m.
Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).
Такую задачу называют "основной" или "стандартной" в линейном программировании.
Оптимальное решение задачи линейного программирования определяется теми значениями параметров модели, которые они имели в момент ее формирования и построения. В реальной экономике значения параметров, формирующих модель, с течением времени или под воздействием каких-либо обстоятельств могут меняться. В связи с этим особый интерес представляют методы, позволяющие определить изменения в оптимальном решении, обусловленные изменениями значений параметров модели. Одним из источников таких методов является теория двойственности, результаты которой позволяют также производить экономический анализ оптимальных решений экономико-математических моделей.
Переменные двойственной задачи называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум - вид ³;
2) матрица А, составленная
из коэффициентов при
3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче;
4) коэффициентами при
неизвестных в целевой функции
двойственной задачи являются
свободные члены в системе
ограничений исходной задачи, а
правыми частями в
5) каждому ограничению
одной задачи соответствует
Решая ЗЛП симплексным методом, одновременно решается двойственная ЗЛП. Переменные двойственной задачи называют объективно обусловленными оценками.
1.2. Методы решения задачи линейного программирования
В общем случае для
решения задач линейного
Сущность симплекс-метода состоит в том, что из исходного базиса переходят за один шаг в соседний с ним базис. Проверяют выполнение условий оптимальности в этом базисе. Если условие оптимальности не выполняется, то из этого базиса переходят в другой соседний с ним базис.
Алгоритм решения задачи симплекс-методом включает в себя однократно выполняемый 0-этап и повторяемый конечное число шагов 1-этап.
0-этап – нахождение
первоначально допустимого
- с помощью дополнительных неотрицательных переменных переходим к равенствам (каноническая форма задачи);
- все переменные разбиваются на две группы: основные и неосновные, при этом определитель матрицы, составленный из коэффициентов при основных переменных должен быть отличным от 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 |
Нам известно, что x1, x2, xn − исходные переменные, xn+1, xn+2, xn+m − дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы, а исходные в первую строку).
Алгоритм применения симплекс-метода
• Подготовительный этап
Приводим задачу ЛП к каноническому виду:
F=a0,1x1+a0,2x2+...a0,nxn +b0
a1,1x1+a1,2x2+...a1,nxn+xn+1=b
a2,1x1+a2,2x2+...a2,nxn+xn+2=b
..............................
am,1x1+am,2x2+...am,nxn+xn+m=b
В случае, если в исходной задаче необходимо найти минимум − знаки коэффициентов целевой функции F меняются на противоположные a0,n= −a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае, если условие содержит знак "≤" − коэффициенты запишутся без изменений.
• 0 этап
Составляем симплексную
Таблица 2
Симплекс-таблица
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 |
• Шаг 1. Проверка на оптимальность
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных, то найдено допустимое оптимальное решение (решение, соответствующее одной из вершин многогранника условий). Тогда мы переходим к шагу 2.
Если в столбце
свободных членов имеются
Если среди свободных членов есть отрицательные элементы , а в соответствующей строке нет, то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму.
• Шаг 2. Проверка на неразрешимость
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность. Если среди элементов симплексной таблицы, находившихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)
l − столбец, в котором находится этот элемент, будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
k − строка, для которой это отношение минимально − ведущая. Элемент ak,l − ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис. Пересчитываем симплекс − таблицу по формулам . Если в новой таблице после перерасчета в строке F остались отрицательные элементы, то переходим к шагу 2.
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена − алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положи-тельные, то найдено оптимальное решение.3
Правила преобразования симплекс-таблицы:
При составлении новой
симплекс-таблицы в ней
• вместо базисной переменной xk записываем xl; вместо небазисной пе-ременной xl записываем xk;
• ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l ;
• все элементы ведущего столбца (кроме ak,l) умножаются на −1/ak,l ;
- все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l ;
- оставшиеся элементы симплекс-таблицы преобразуются по формуле (2)
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого
базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Геометрический (графический) метод
Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
Рис. 1. Система ограничений на плоскости
Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.
Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.
Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или
c1x1+c2x2 = а
линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.
Предположим надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т. е. точка через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).
Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.
Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а.
Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели”, расположенные обычно под углом к осям координат.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении линии в другую сторону – только убывает.
Пусть имеются три линии уровня :
F=c1x1 + c2x2 = а1 (I)
F=c1x1 + c2x2 = а2 (II)
F=c1x1 + c2x2 = а3 (III)
Причём линия II заключена между линиями I и III. Тогда а1 < а2 < а3 и а1 > а2 > а3.
В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.
Для определения направления
возрастания рекомендуется
2. РАСЧЕТ ЗАДАЧИ О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ ДЛЯ ФИНАНСИРОВАНИЯ
2.1. Вербальная постановка конкретной решаемой задачи
Рассмотрим задачу выбора оптимальных проектов для финансирования. Управляющему банка были представлены предложения о четырех проектах, претендующих на кредиты банка. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов.
Доступная наличность банка, потребности проектов и прибыль по ним приведены в табл. 1.
Таблица 3
Доступная наличность банка, потребности проектов и прибыль по ним, в рассматриваемые периоды, тыс. долл.
Проект |
Период 1 |
Период 2 |
Период 3 |
Период 4 |
Прибыль |
А |
8 |
8 |
10 |
10 |
21 |
В |
7 |
9 |
9 |
11 |
18 |
С |
5 |
7 |
9 |
11 |
16 |
D |
9 |
8 |
7 |
6 |
17,5 |
Ресурс банка |
22 |
25 |
38 |
30 |
Какие проекты следует
финансировать и какое
2.2. Разработка экономико- математической
модели задачи о выборе оптимальных проектов
для финансирования
Построим экономико-
Пусть xi – логические переменные, равные 1, если проект принимается и равные 0, если проект не принимается. Тогда суммарная потребность в наличности в данные период будет равна сумме произведений Xi на столбец финансовых затрат по каждому проекту в данный период.
В принятых обозначениях ограничения по ресурсам примут вид:
8x1 + 7x2 + 5x3 + 9x4 ≤ 22,
8x1 + 9x2 + 7x3 + 8x4 ≤ 25,
10x1 + 9x2 + 9x3 + 7x4 ≤ 38,
10x1 + 11x2 + 11x3 + 6x4 ≤ 30,
x1,x2,x3,x4 ≥ 1,
где X(x1,x2,x3,x4) – координаты точки X в R4 (4-мерном пространстве).
Так как неизвестные могут принимать только целые значения, то задача является задачей целочисленного программирования и
В этой модели целевая функция - это математическая запись критерия оптимальности «максимум прибыли от финансирования проекта» Целевая функция равна
F(x1,x2,x3,x4) = 21x1+18x2+16x3+17,5x4 → max.
Двойственная задача: пусть имеется спонсор, который захочет профинансировать те же проекты в тех же потребностях проектов в финансировании, при условии, что он получит от использования этих ресурсов большую прибыль, чем планируется банком.
Тогда целевая функция – это функция ограниченности ресурсов
X(x1,x2,x3,x4) = 22x1+25x2+38x3+30x4→min,
а ограничения примут вид:
8x1 + 8x2 + 10x3 + 10x4 ≥ 21,
7x1 + 9x2 + 9x3 + 11x4 ≥ 18,
5x1 + 7x2 + 9x3 + 11x4 ≥ 16,
9x1 + 8x2 + 7x3 + 6x4 ≥ 17,5.
Какие периоды спонсор станет финансировать и в каких пределах, чтобы его вложения были минимальны?
2.3. Решение поставленной задачи симплекс-методом
Решим прямую задачу линейного программирования строчечным симплекс-методом. Определим максимальное значение целевой функции
F(X) = 21x1+18x2+16x3+17,5x4
при следующих условиях ограничений:
8x1+7x2+5x3+9x4≤22
8x1+9x2+7x3+8x4≤25
10x1+9x2+9x3+7x4≤38