Вход

1.основные понятия моделирования 2. методы линейного программирования 3. методы нелинейного и динамич. программир.

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 137156
Дата создания 2008
Страниц 29
Источников 8
Мы сможем обработать ваш заказ (!) 29 марта в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 580руб.
КУПИТЬ

Содержание

1. Основные понятия моделирования
2. Постановка задачи линейного программирования
2.1 Задачи линейного программирования
2.2. Основные свойства ЗЛП и ее геометрическая интерпретация
2.3. Базисные решения и вторая геометрическая интерпретация ЗЛП
2.4. Симплекс-метод
3. Нелинейное программирование
Практическая часть
Список литературы

Фрагмент работы для ознакомления

Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации.
Как и в ЗЛП, вектор называется допустимым планом, а если для любого x(D выполняется неравенство , то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.
С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП
Задача (3.2) является весьма общей, т. к. допускает запись логических условий, например:
или запись условий дискретности множеств:
Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:
либо, добавив фиктивные переменные у, к системе уравнений:
Перечислим свойства ЗИП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:
1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).
3. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).
3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа.
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения.
Одним из наиболее общих подходов к решению задачи поиска экстремума (локального максимума или минимума) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Многим читателям он должен быть известен из курса дифференциального исчисления. Идея данного метода состоит в сведении задачи поиска условного экстремума целевой функции
(3.3)
на множестве допустимых значения D, описываемом системой уравнений
(3.4)
к задаче безусловной оптимизации функции
Ф(x,u) = f(x1,x2,...,xn)+ulgl(xi,x2,...,xn)+...+ungm(xl,x2,...,xn), (3.5)
где — вектор дополнительных переменных, называемых множителями Лагранжа. Функцию Ф(х,и), где , , называют функцией Лагранжа. В случае дифференцируемое™ функций f и gi справедлива теорема, определяющая необходимое условие существования точки условного экстремума в задаче (3.3)-(3.4). Поскольку она непосредственно относится к предмету математического анализа, приведем ее без доказательства.
Теорема 3.1. Если х* является точкой условного экстремума функции (3.3) при ограничениях (3.4) и ранг матрицы первых частных производных функций
равен т, то существуют такие, не равные одновременно нулю, при которых
(3.6)
Из теоремы (3.1) вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.
1. Составление функции Лагранжа Ф(х,и).
3. Нахождение частных производных
и
3. Решение системы уравнений
(3.7)
относительно переменных х и и.
4. Исследование точек, удовлетворяющих системе (3.7), на максимум (минимум) с помощью достаточного признака экстремума.
Присутствие последнего (четвертого) этапа объясняется тем, что теорема (3.1) дает необходимое, но не достаточное условие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще говоря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и gi) и, как правило, трудноприменимы на практике. Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений (3.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (3.3)-(3.4). Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (3.7). Их применение объясняется необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретических выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итеративных процессах вычисления и сравнения значений оптимизируемых функций.
Градиентные методы решения задач безусловной оптимизации. Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.
Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х(1) перемещаться в направлении вектора , то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1). Следовательно, для точки , , лежащей в такой окрестности, справедливо неравенство . Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 3.1).
Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага (, в рекуррентной формуле
(3.8)
задающей последовательность точек, стремящихся к точке максимума.
В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее известных из них.
Метод наискорейшего спуска
Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее, по традиции такое название используется и при решении задачи на максимум.
Пусть f(x) = f(xl,xl,...xn) — дифференцируемая функция, заданная на Rn, а — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) x(0), не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось выше, если x(q) — нестационарная точка (т. е. ), то при движении в направлении функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя ( > 0 , полагая
(3.9)
или, в координатной форме,
(3.10)
Чтобы добиться наибольшего из возможных значений f при движении по направлению , нужно выбрать такое значение , которое максимизирует функцию . Для вычисления , используется необходимое условие экстремума . Заметим, что если для любого ( >0 , то функция f(x) не ограничена сверху (т. е. не имеет максимума). В противном случае, на основе (3.10) получаем
(3.11)
что, в свою очередь, дает
(3.12)
Если считать, что следующая точка соответствует оптимальному значению , то в ней должно выполняться условие , и следует находить из условия или

(3.13)
Условие (3.13) означает равенство нулю скалярного произведения градиентов функции f точках х(q+1) и х(q) Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рис. 3.3. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке х(q+1) вектор , будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку. Стало быть, вектор является касательным к этой линии. Итак, движение в направлении градиента следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции.
После того как точка х(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора должны быть близки к нулю.
Метод дробления шага
Для нахождения шага (, в методе наискорейшего спуска требуется решить уравнение (3.13), которое может оказаться достаточно сложным. Поэтому часто ограничиваются «подбором» такого значения (, что . Для этого задаются некоторым начальным значением (1 (например, (1 =1) и проверяют условие . Если оно не выполняется, то полагают
и т. д. до тех пор, пока не удается найти подходящий шаг, с которым переходят к следующей точке х(q+1). Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорейшего спуска.
Практическая часть
Решение задачи графическим методом
Каждое из неравенств в ограничениях определяет полуплоскость с соответствующей границей. Представим этот многоугольник на плоскости, предварительно выразив X2 в каждом из неравенств.
ОДР для каждого из неравенств находится под соответствующей линией. Совместная ОДР для всех неравенств находится на пересечении этих полуплоскостей.
Теперь достаточно проверить значение целевой функции в каждой из вершин ОДР и выбрать наибольшее.
F(0,0)=2*0+3*0=0
F(0,6)=2*0+3*6=18
F(2.76,4.15)=18
F(4.5,0)=2*4.5+3*0=9
Целевое значение функции равно 18
Решение транспортной задачи
Исходная таблица:
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1  
10
0
 
7
0
 
14
0
 
8
0
 
7
0
  35   A2  
10
0
 
8
0
 
10
0
 
8
0
 
16
0
  30   A3  
6
0
 
10
0
 
10
0
 
12
0
 
14
0
  35   A4  
14
0
 
10
0
 
8
0
 
10
0
 
12
0
  45 Потребность 28 30 22 35 30   Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу минимального элемента:
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
   
7
30
   
14
 
   
8
 
   
7
5
  35   A2    
10
 
   
8
 
   
10
 
   
8
30
   
16
 
  30   A3    
6
28
   
10
 
   
10
 
   
12
 
   
14
7
  35   A4    
14
 
   
10
 
   
8
22
   
10
5
   
12
18
  45 Потребность 28 30 22 35 30   Целевая функция F=1193
Решаем задачу методом потенциалов: Примем некоторые обозначения: i - индекс строки; j - индекс столбца; m - количество поставщиков; n - количество потребителей. Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V2=C1,2-U1= 7 V5=C1,5-U1= 7 U3=C3,5-V5=7 U4=C4,5-V5=5 V1=C3,1-U3= -1 V3=C4,3-U4= 3 V4=C4,4-U4= 5 U2=C2,4-V4=3 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток: S1,1= 11 S1,3= 11 S1,4= 3 S2,1= 8 S2,2= -2 S2,3= 4 S2,5= 6 S3,2= -4 S3,3= 0 S3,4= 0 S4,1= 10 S4,2= -2 Наиболее потенциальной является клетка (3,2). Для нее оценка равна -4. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
 - 
7
30
   
14
 
   
8
 
 + 
7
5
  35   A2    
10
 
   
8
 
   
10
 
   
8
30
   
16
 
  30   A3    
6
28
 + 
10
 
   
10
 
   
12
 
 - 
14
7
  35   A4    
14
 
   
10
 
   
8
22
   
10
5
   
12
18
  45 Потребность 28 30 22 35 30   Перемещаем по циклу груз величиной в 7 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
   
7
23
   
14
 
   
8
 
   
7
12
  35   A2    
10
 
   
8
 
   
10
 
   
8
30
   
16
 
  30   A3    
6
28
   
10
7
   
10
 
   
12
 
   
14
 
  35   A4    
14
 
   
10
 
   
8
22
   
10
5
   
12
18
  45 Потребность 28 30 22 35 30   Целевая функция F= 1165
Значение целевой функции изменилось на 28 единиц по сравнению с предыдущим этапом. Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V2=C1,2-U1= 7 V5=C1,5-U1= 7 U3=C3,2-V2=3 U4=C4,5-V5=5 V1=C3,1-U3= 3 V3=C4,3-U4= 3 V4=C4,4-U4= 5 U2=C2,4-V4=3 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток: S1,1= 7 S1,3= 11 S1,4= 3 S2,1= 4 S2,2= -2 S2,3= 4 S2,5= 6 S3,3= 4 S3,4= 4 S3,5= 4 S4,1= 6 S4,2= -2 Наиболее потенциальной является клетка (2,2). Для нее оценка равна -2. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
 - 
7
23
   
14
 
   
8
 
 + 
7
12
  35   A2    
10
 
 + 
8
 
   
10
 
 - 
8
30
   
16
 
  30   A3    
6
28
   
10
7
   
10
 
   
12
 
   
14
 
  35   A4    
14
 
   
10
 
   
8
22
 + 
10
5
 - 
12
18
  45 Потребность 28 30 22 35 30   Перемещаем по циклу груз величиной в 18 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
   
7
5
   
14
 
   
8
 
   
7
30
  35   A2    
10
 
   
8
18
   
10
 
   
8
12
   
16
 
  30   A3    
6
28
   
10
7
   
10
 
   
12
 
   
14
 
  35   A4    
14
 
   
10
 
   
8
22
   
10
23
   
12
 
  45 Потребность 28 30 22 35 30   Целевая функция F= 1129
Значение целевой функции изменилось на 36 единиц по сравнению с предыдущим этапом. Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V2=C1,2-U1= 7 V5=C1,5-U1= 7 U2=C2,2-V2=1 V4=C2,4-U2= 7 U3=C3,2-V2=3 U4=C4,4-V4=3 V1=C3,1-U3= 3 V3=C4,3-U4= 5 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток: S1,1= 7 S1,3= 9 S1,4= 1 S2,1= 6 S2,3= 4 S2,5= 8 S3,3= 2 S3,4= 2 S3,5= 4 S4,1= 8 S4,2= 0 S4,5= 2 Так как все оценки Si,j>=0, то полученный план является оптимальным. Транспортная задача решена.
Поставщик Потребитель Запасы груза     B1         B2         B3         B4         B5       A1    
10
 
   
7
5
   
14
 
   
8
 
   
7
30
  35   A2    
10
 
   
8
18
   
10
 
   
8
12
   
16
 
  30   A3    
6
28
   
10
7
   
10
 
   
12
 
   
14
 
  35   A4    
14
 
   
10
 
   
8
22
   
10
23
   
12
 
  45 Потребность 28 30 22 35 30   Целевая функция F= 1129
Список литературы
1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. - М.: Финансы и статистика, 2001.
2. Замков О.О., Толстопятенко А.В. Черемных Ю.Н. Математические методы в экономике: Учебник. - М.: «ДИС», 2001.
3. Исследование операций в экономике: Учеб. пособие/ Под. ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 1997.
4. Конюховский П. В. Математические методы исследования операций в экономике—СПб: Питер, 2000..
5. Пинегина М.В. Математические методы и модели в экономике. - М.: Изд-во «Экзамен», 2002.
6. Федосеев В.В.. Гармаш А.Н., Дайитбегов Д.М. Экономико-математические методы и прикладные модели: Учеб. пособие. -М.: ЮНИТИ, 1999.
7. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учеб. пособие. - М.: Финансы и статистика, 2005.
8. Хазанова Л.Э. Математическое моделирование в экономике: Учеб. пособие. - М.: БЕК, 1998.
Напомним, что l — номер столбца, вводимого в базис, а r — номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.
Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.
Настоящая структура, симплекс-таблиц строится на идеях и принципах их организации, предложенных в [1].
24
T(1)=
- 226 –84 0 0 –88 0
5 4 1/3 0 0 1/3 1
2 14 2 1 0 3 0
3 17/3 –2/3 0 1 –4/3 0
5
4
3
554/3
22/9
14/3
107/9
-76/3 88/3 0 0 0
1/9 -1/9 0 0 1
2/3 1/3 0 1 0
2/9 4/9 1 0 0
T(2)=
5
1
3
362
5/3
7
31/7
0 42 0 38 0
0 -1/6 0 -1/6 1
1 1/2 0 3/2 0
0 1/3 0 -1/3 0
T(3)=

Список литературы [ всего 8]

1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономиче-ских систем: Учеб. пособие. - М.: Финансы и статистика, 2001.
2. Замков О.О., Толстопятенко А.В. Черемных Ю.Н. Математические методы в эконо-мике: Учебник. - М.: «ДИС», 2001.
3. Исследование операций в экономике: Учеб. пособие/ Под. ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 1997.
4. Конюховский П. В. Математические методы исследования операций в экономике—СПб: Питер, 2000..
5. Пинегина М.В. Математические методы и модели в экономике. - М.: Изд-во «Экза-мен», 2002.
6. Федосеев В.В.. Гармаш А.Н., Дайитбегов Д.М. Экономико-математические методы и прикладные модели: Учеб. пособие. -М.: ЮНИТИ, 1999.
7. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учеб. пособие. - М.: Финансы и статистика, 2005.
8. Хазанова Л.Э. Математическое моделирование в экономике: Учеб. пособие. - М.: БЕК, 1998.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00532
© Рефератбанк, 2002 - 2024