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

 

 

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РФ

филиал  федерального  государственного бюджетного

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

высшего профессионального образования

«Воронежский  государственный

архитектурно-строительный университет»

в городе Борисоглебске

 

 

Кафедра экономики и управления строительством

 

 

 

 

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

 

по дисциплине «Оптимизационные задачи в экономике»

Тема «Решение оптимизационной задачи линейного  программирования»

 

 

 

 

 

                                                                                Выполнил: студентка группы 

                                                                                                         ФБ -811-У

направление «Менеджмент»                  

                                                                                                           Дунаева Е.Г.

                                                                                    Проверил: преподаватель                  

                                                                                                         Перегудова В.Н.

 

 

 

 

 

 

Борисоглебск 

2012

 

Содержание

Введение…………………………………………………………………………...3

I.Теоретическая часть……………………………………………………………6

1 Постановка  задач и оптимизации…………………………………………….6

2 Построение  аналитической модели…………………………………………..6

3 Обоснование  и описание вычислительной процедуры……………………..8

3.1 Приведение  задач линейного программирования  к стандартной форме….8

3.2 Основная  идея симплекс метода……………………………………………12

II Практическая часть………………………………………………………….22

Заключение……………………………………………………………………….30

Список используемой литературы……………………………………………..31

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 Оптимизация  - целенаправленная деятельность, заключающаяся  в получении наилучших результатов при соответствующих условиях.

 Поиски   оптимальных   решений   привели   к   созданию    специальных

математических  методов и уже в 18 веке были заложены  математические  основы оптимизации (вариационное исчисление, численные  методы  и  др).  Однако  до второй половины 20 века  методы  оптимизации  во  многих  областях  науки  и техники  применялись  очень  редко,  поскольку  практическое   использование математических  методов  оптимизации   требовало   огромной   вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде  случаев  - невозможно.

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

( количество  продукции - расход сырья

( количество  продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

1.  Наличие   объекта  оптимизации  и   цели   оптимизации.   При   этом

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

2. Наличие  ресурсов оптимизации,  под   которыми  понимают  возможность

выбора  значений некоторых параметров оптимизируемого  объекта.

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

4. Учет ограничений.

Обычно  оптимизируемая  величина  связана  с   экономичностью   работы

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

Критерием    оптимальности    называется     количественная     оценка

оптимизируемого качества объекта.

 На основании  выбранного критерия  оптимальности   составляется  целевая

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

Таким образом, задача оптимизации  сводится  к  нахождению  экстремума

целевой функции.

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

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

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

Итак, линейное программирование возникло  после  Второй  Мировой

Войны  и  стал   быстро   развиваться,   привлекая   внимание   математиков,

экономистов  и  инженеров  благодаря  возможности   широкого   практического применения, а так же математической «стройности».

Можно  сказать,  что  линейное  программирование  применимо  для

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

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

Линейное  программирование   представляет   собой   наиболее   часто

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

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

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

 

 

 

        1. Постановка задач оптимизации.

2.Построение аналитической модели.

Сама  по себе постановка задачи оптимизации  проста и естественна:

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

Условимся записывать   задачу на минимум в виде:

       ( 2.1.1 )

где

    - целевая функция;

         -  допустимое множество 

-  допустимая  точка задачи ( 2.1.1 ).

В основном мы будем иметь дело с конечномерными задачами оптимизации, то есть с задачами, в которых допустимое множество  лежит в евклидовом пространстве ().

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

Точка называется

1) точкой  глобального минимума функции  на множестве или глобальным решением задачи ( 2.1.1 ), если

( 2.1.2 )

2) точкой  локального минимума функции  на множестве или локальным решением задачи ( 2.1.1 ), если

,такое что для  ( 2.1.3 )

где

Если  неравенство в ( 2.1.2 ) или в ( 2.1.3 ) выполняется как строгое при то - точка строгого минимума (строгое решение) в глобальном или локальном смысле.

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

  

или эквивалентная  ей запись   

     Множество всех точек глобального  минимума на,   обозначают через

 

где - минимальное значение функции на множестве .

В этом случае - это просто произвольная точка из множества

По аналогии с ( 2.1.1 ) записывают задачу максимизации функции на множестве ,  в виде

,     ( 2.1.4 )

Заменяя в данных выше определениях слово  «минимум» на «максимум»  и заменяя  знак неравенств в ( 2.1.2 ), ( 2.1.3 ) на противоположный, получаем соответствующие понятия для задачи ( 2.1.4 ).

Решения задач ( 2.1.1 ), ( 2.1.4 ), то есть точки минимума и максимума функции на множестве ,  называются также точками экстремума, а сами задачи ( 2.1.1 ), ( 2.1.4 ) - экстремальными задачами.

Ясно, что  задача ( 2.1.4 ) эквивалентна задаче

,     ,

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

При изучении задач оптимизации в первую очередь  возникает вопрос о существовании  решения. Ответ на этот вопрос дает теорема Вейерштрасса.

Теорема Вейерштрасса.

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

Напоминание:

Компакт - замкнутое  ограниченное множество.

3 Обоснование и описание вычислительной  процедуры.

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

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

,  ( 6.1.1 )

где

,

- вектор  размерности , ,

- матрица  размера  ранга ,

- вектор  размерности , . ( 6.1.2 )

Скалярное произведение  называется целевой функцией. Коэффициенты целевой функции - это координаты вектора . 

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

Задача ( 6.1.1 ) - . ( 6.1.2 ) называется задачей линейного программирования в каноническом виде.

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

Теорема (условия оптимальности для задачи линейного программирования).  

Рассмотрим  задачу линейного программирования ( 6.1.1 ) - ( 6.1.2 ).

Пусть , - экстремальные (угловые) точки, - экстремальные направления множества .

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

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

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

То есть это перебор всех точек многогранного  множества. Но количество экстремальных  точек для реальных задач велико, и способ перебора неприемлем.