Курсовая работа - Нелинейное программирование - файл n1.docx

Курсовая работа - Нелинейное программирование
скачать (1270.9 kb.)
Доступные файлы (1):
n1.docx1271kb.19.09.2012 22:42скачать

n1.docx

Федеральное агентство по образованию Российской Федерации

Филиал «СЕВМАШВТУЗ»

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

высшего профессионального образования «Санкт-Петербургский государственный морской технический университет»

в г. Северодвинске
Факультет второй

Кафедра «Бухгалтерский учет, анализ и планирование»

КУРСОВАЯ РАБОТА
по дисциплине “Математическая экономика”
Тема: _____Нелинейное программирование__________

(наименование темы)

Преподаватель _Плотицина И.В.

(фамилия и инициалы)

Студент _Бабаханова Н.Э.

(фамилия и инициалы)

Группа ____2201______________

(№ группы)
Дата сдачи на проверку_____________________
Оценка ______________________


Северодвинск

2009 г.

Задание на выполнение курсовой работы по дисциплине

« Математическая экономика»



ТЕОРЕТИЧЕСКАЯ ЧАСТЬ КУРСОВОЙ РАБОТЫ


на тему:___ Нелинейное программирование_____________




РАСЧЕТНАЯ ЧАСТЬ КУРСОВОЙ РАБОТЫ


на тему: «Линейное программирование»


Вариант № __2_____


Исходные данные:


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

Производственная мощность позволяет выпускать максимум 3500 деталей типа А.

Ресурсы

Нормы расхода ресурсов на производство детали

Лимит ресурсов

Трудозатраты, чел.-час.

4

3

8000

Листовой материал, кг

2

6

7500

Полимерные материалы, кг

5

2

6000

Доход от продажи 1 детали

11

13




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





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

«14» февраля 2009 г работы на кафедру:

«___» ________ 2009 г

Задание получил Руководитель работы

Студент_________________ Преподаватель_____________





Оглавление


Задание на выполнение курсовой работы по дисциплине 2

« Математическая экономика» 2

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ КУРСОВОЙ РАБОТЫ 2

на тему:___ Нелинейное программирование_____________ 2

РАСЧЕТНАЯ ЧАСТЬ КУРСОВОЙ РАБОТЫ 2

на тему: «Линейное программирование» 2

Вариант № __2_____ 2

Исходные данные: 2

Дата выдачи задания: Дата представления курсовой 2

«14» февраля 2009 г работы на кафедру: 2

«___» ________ 2009 г 2

Задание получил Руководитель работы 2

Студент_________________ Преподаватель_____________ 2

1.2. Критерии оптимальности в задачах с ограничениями. 6

1.2.1. Задачи с ограничениями в виде равенств 6

1.2.2. Множители Лагранжа 7

1.3. Условия Куна-Таккера 12

1.3.1. Условия Куна—Таккера и задача Куна—Таккера 13

1.3.2. Интерпретация условий Куна — Таккера 14

1.3.3. Теоремы Куна—Таккера 16

1.4. Функции нескольких переменных 23

1.4.1. Методы прямого поиска 24

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

2.1. Описание постановки задачи. 27

2.2. Формулировка экономико-математической модели. 27

2.3. Нахождение численного решения «Поиска решений». 28

29

2.4. Нахождение численного решения Simplex-метода. 31

Систему неравенств: 31

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

Список литературы. 34




Введение


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

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

1. Нелинейное программирование

1.1 Постановка задачи нелинейного программирования.
В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

, i=1,2,…,m (1)

а переменные , т.е. компоненты вектора х, неотрицательны:

(2)

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

1.2. Критерии оптимальности в задачах с ограничениями.



Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмотрения задач оптимизации, которые содержат только ограничения в виде равенств.

1.2.1. Задачи с ограничениями в виде равенств



Рассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств:

Минимизировать

при ограничениях , k=1,…,n

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

Пример 1

Минимизировать

при ограничении

Исключив переменную , с помощью уравнения , получим

оптимизационную задачу с двумя переменными без ограничений

min

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



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

1.2.2. Множители Лагранжа



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

Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства:

Минимизировать (3)

при ограничениях (4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x,u)=f(x)-u*h(x) (5)

Функция L(х;u) называется функцией Лагранжа, u — неизвестная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.

Пусть при заданном значении u=u0 безусловный минимум функции L(x,u) по х достигается в точке и удовлетворяет уравнению . Тогда, как нетрудно видеть, x0 минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4), и L(x,u)=min f(x).

Разумеется, необходимо подобрать значение u=u° таким образом, чтобы координата точки безусловного минимума х° удовлетворяла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать

при ограничении =0

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать L(x,u)= -u

Решение. Приравняв две компоненты градиента L к нулю, получим





Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,

,

которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х. Следовательно, координаты , определяют точку глобального минимума. Оптимальное значение u находится путем подстановки значений и в уравнение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается при и и равен min f(x)=4/5.

При решении задачи из примера 2 мы рассматривали L(х;u) как функцию двух переменных и и, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограничение. Если же решение системы

, j=1,2,3,…,n

в виде явных функций u получить нельзя, то значения х и u находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:

, j=1,2,3,…,n

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

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

Минимизировать f(x)

при ограничениях =0, k=1, 2, ..., К.

Функция Лагранжа принимает следующий вид:

L(x,u)=f(x)-

Здесь —множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:





………..



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






Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко.

1.3. Условия Куна-Таккера



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

Рассмотрим следующую общую задачу нелинейного программирования:

минимизировать (0)

при ограничениях (1)

(2)

Определение:

Ограничение в виде неравенства называется активным, или связывающим, в точке , если , и неактивным, или несвязывающим, если

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

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

1.3.1. Условия Куна—Таккера и задача Куна—Таккера



Найти векторы ,удовлетворяющие следующим условиям

(3)

(4)

(5)

(6)

(7)

Прежде всего проиллюстрируем условия Куна — Таккера на примере.

Пример 3

Минимизировать

при ограничениях

Решение.

Записав данную задачу в виде задачи нелинейного программирования (0)-(2), получим









Уравнение (3), входящее в состав условий Куна—Таккера, принимает следующий вид:



откуда



Неравенства (4) и уравнения (5) задачи Куна — Таккера в данном случае записываются в виде



Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид



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

Таким образом, этой задачи условия Куна—Танкера записываются в следующем виде:


1.3.2. Интерпретация условий Куна — Таккера



Для того чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейного программирования с ограничениями в виде равенств:

минимизировать

при ограничениях

Запишем условия Куна—Таккера

(8)

(9)

Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств



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



Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа.

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

минимизировать

при ограничениях

Запишем условия Куна—Таккера



Соответствующая функция Лагранжа имеет вид



Условия оптимальности первого порядка записываются как



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

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

Для того чтобы определить знак (неявной цены, ассоциированной с ограничением ), следует увеличить правую часть ограничения от 0 до 1. Ясно, что при этом область допустимых решений сужается, поскольку любое решение, удовлетворяющее ограничению , автоматически удовлетворяет неравенству . Следовательно, размеры допустимой области уменьшаются, и минимальное значение улучшить невозможно (так как вообще оно может только возрастать). Другими словами, неявная цена , ассоциированная с -м ограничением, должна быть неотрицательной, что соответствует условиям Куна—Таккера.

1.3.3. Теоремы Куна—Таккера



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

Теорема 1. Необходимость условий Куна—Таккера

Рассмотрим задачу нелинейного программирования (0)-(2). Пусть - дифференцируемые функции, а х* — допустимое решение данной задачи. Положим . Далее пусть линейно независимы. Если х* — оптимальное решение задачи нелинейного программирования, то существует такая пара векторов , что является решением задачи Куна—Таккера (3)—(7).

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

1. Все ограничения в виде равенств и неравенств содержат линейные функции.

2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства — линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что



Если условие линейной независимости в точке оптимума не выполняется, то задача Куна—Таккера может не иметь решения.

Пример 4

Минимизировать

при ограничениях

Решение.

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


Рис.1 Допустимая область в задаче 4
Так как

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

Запишем условия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид;

(11)

(12)

(13)

(14)

(15)

(16)

При из уравнения (11) следует, что , тогда как уравнение (14) дает , Следовательно, точка оптимума не является точкой Куна — Таккера.

Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна—Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией. При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна—Таккера (12) - (16) остаются неизменными, а уравнение (11) принимает вид



Нетрудно проверить, что точка является точкой Куна—Таккера, т. е. удовлетворяет условиям Куна—Таккера.

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

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

Теорема.2 Достаточность условий Куна—Таккера

Рассмотрим задачу нелинейного программирования (0) — (2). Пусть целевая функция выпуклая, все ограничения в виде неравенств содержат вогнутые функции , а ограничения в виде равенств содержат линейные функции . Тогда если существует решение , удовлетворяющее условиям Куна—Таккера (3) — (7), то х* — оптимальное решение задачи нелинейного программирования.

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

Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример:

Минимизировать

при ограничениях

С помощью теоремы 2 докажем, что решение является оптимальным. Имеем



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

чтобы показать, что функция является вогнутой, вычислим



Поскольку матрица отрицательно определена, функция является вогнутой. Функция входит в линейное ограничение в вяде равенства. Следовательно, все условия теоремы 2 выполнены; если мы покажем, что - точка Куна-Таккера, то действительно установим оптимальность решения . Условия Куна-Таккера для примера 2 имеют вид

(22)

(23)

(24)

(25)

, (26)

, (27)

(28)

(29)

Точка удовлетворяет ограничениям (24) — (26) и, следовательно, является допустимой. Уравнения (22) и (23) принимают следующий вид:



Положив ,получим и. Таким образом, решение х*=(1, 5), удовлетворяет условиям Куна—Таккера. Поскольку условия теоремы 2 выполнены, то оптимальное решение задачи из примера 3. Заметим, что существуют также и другие значения и , которые удовлетворяют системе (22) -(29).

Замечания

1.Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна—Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна—Таккера. (Здесь уместно провести аналогию со случаем безусловной оптимизации, когда соответствующие алгоритмы позволяют определить стационарную точку.)

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

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

1.4. Функции нескольких переменных



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

Сначала рассмотрим вопрос анализа «в статике» с использованием положений линейной алгебры и дифференциального исчисления, а также условия, которые (в достаточно общих возможных ситуациях) позволяют идентифицировать точки оптимума. Такие условия используются для проверки выбранных точек и дают возможность выяснить, являются ли эти точки точками минимума или максимума. При этом задача выбора указанных точек остается вне рамок проводимого анализа; основное внимание уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям многомерной задачи безусловной оптимизации, в которой требуется минимизировать f(x) x при отсутствии ограничений на x, где x — вектор управляемых переменных размерности n, f — скалярная целевая функция. Обычно предполагается, что xi (для всех значений i=1, 2, …, n) могут принимать любые значения, хотя в ряде практических приложений область значений x выбирается в виде дискретного множества. Кроме того, часто оказывается удобным предполагать, что функция f и ее производные существуют и непрерывны всюду, хотя известно, что оптимумы могут достигаться в точках разрыва f или ее градиента



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

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

1.4.1. Методы прямого поиска


Ниже рассматривается вопрос анализа «в динамике» для функций нескольких переменных, т. е. исследуются методы и алгоритмы, позволяющие на итерационной основе получать оценки х*— вектора управляемых переменных, которому соответствует минимальное значение функции f(x). Указанные методы применимы также к задачам максимизации, в которых целевую функцию следует заменить на -f(х). Методы, ориентированные на решение задач безусловной оптимизации, можно разделить на три широких класса в соответствии с типом используемой при реализации того или иного метода информации.

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

2. Градиентные методы, в которых используются точные значения первых производных f(x).

3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f(x).

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

Методы решения задач безусловной оптимизации отличаются относительно высоким уровнем развития по сравнению с другими методами нелинейного программирования. Ниже речь идет о методах прямого поиска, для реализации которых требуются только значения целевой функции; в следующем разделе рассматриваются градиентные методы и методы второго порядка. Здесь предполагается, что f(x) непрерывна, а может как существовать, так и не существовать, поскольку соответствующие числовые значения не используются. Однако следует отметить, что методы прямого поиска можно применять для решения задач, в которых существует, и они часто используются в тех случаях, когда представляет собой сложную векторную функцию управляемых переменных. Наконец, в этом и последующих разделах предполагается, что функция f(х) унимодальна в рассматриваемой области. Если же изучаемые методы применяются для анализа мультимодальных функций, то приходится ограничиваться идентификацией локальных минимумов.

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



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




2.1. Описание постановки задачи.


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

Производственная мощность позволяет выпускать максимум 3500 деталей типа А.

Ресурсы

Нормы расхода ресурсов на производство детали

Лимит ресурсов

Трудозатраты, чел.-час.

4

3

8000

Листовой материал, кг

2

6

7500

Полимерные материалы, кг

5

2

6000

Доход от продажи 1 детали

11

13




Табл. 1 Исходные данные
Определить, сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю через Simplex-метод и «Поиск решений» используя средства Microsoft Excel.

2.2. Формулировка экономико-математической модели.



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

Обозначим x1; x2- нормы расхода ресурсов на производство детали. Для их изготовления потребуется:

1+3х2 – трудозатраты

1+6х2 - листовой материал

5 х1+2 х2 - полимерные материал

Так как использование норм расхода ресурсов на производство детали не должно превышать лимит ресурсов то связь выразится следующей системой неравенств:



(1)


По смыслу задачи (2)

(3)

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

2.3. Нахождение численного решения «Поиска решений».



В MS Excel составляем таблицу с исходными данными:


В ячейки D2; D3; D4 вводим соответственно:

=СУММПРОИЗВ(B2:C2;$B$6:$C$6)

=СУММПРОИЗВ(B3:C3;$B$6:$C$6)

=СУММПРОИЗВ(B4:C4;$B$6:$C$6)

Затем заходим на вкладку Данные и выбираем «Поиск решений»; в появившемся окне последовательно выбираем изменяемые ячейки:



И добавляем необходимые нам ограничения:







В параметрах поиска решений выбираем «Линейная модель»:

безымянный3.bmp
И в результатах поиска решений сохраняем найденное решение:

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



2.4. Нахождение численного решения Simplex-метода.


Систему неравенств:




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




базисные неизвестные;

свободные члены;

целевая функция.
В MS Excel заполняем 1 Simplex-таблицу:





2 Simplex-таблица:




3 Simplex-таблица:


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

Результат: F(x)=21634,61

X1=807

X2=980,7

Данный результат почти идентичен результату, полученному при нахождение численного решения «Поиска решений», что подтверждает правильность решения данной задачи линейного программирования.

























Заключение


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

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

Список литературы.


  1. Волошин Г.Я., Методы оптимизации в экономике: Учебное пособие. — М.: «Издательство «Дело и Сервис», 2004. — 320 с.

  2. Данилов Н.Н. Курс математической экономики. – М.: Высшая школа, 2006.

  3. Замков О.О., Толстопятенко А.В., Чермных Ю.Н. Математические методы в экономике: учеб. пособие. Изд-во «ДИС», Москва. – 1998 г.

  4. Колемаев В. А. Математическая экономика: Учебник для вузов. – 2-е изд., перераб. и доп. – М.: ЮНИТИ-ДАНА, 2002. – 399 с.

  5. Коршунов Н.И., Плясунов В.С., Математика в экономике. - М.: Изд-во «Вита-Пресс», 2006. – 345 с.

  6. Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие/ Под науч. ред. Проф. Б. А. Суслакова. – М.: Издательско-торговая корпорация «Дашков и К?», 2004. – 352 с.




Федеральное агентство по образованию Российской Федерации
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации