Математическое программирование

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

Государственное образовательное  учреждение высшего  профессионального  образования.

Воронежский Государственный  Архитектурно-строительный Университет.   
 
 
 

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

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

по  дисциплине « Математическое программирование»  
 
 
 
 
 
 

Выполнила: Гончарова Оксана Сергеевна.

Руководитель: Мещерякова Татьяна  Вячеславовна. 
 
 

Работа  защищена «     »____2009 г.

С оценкой ____ (____). 
 
 
 
 
 
 
 
 
 
 
 

Воронеж 2009 г.

Введение. 

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

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

Вариант 7 

Лабораторная  работа 5.

Геометрический  метод решения  задачи оптимизации  себестоимости продукции. 

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

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

                                   

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

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

                                                                (1)

при условиях     ;      ( ),                                (2)

                                       ( ),                                  (3) 

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

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

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

                                                                        (4) 

при условиях                       ( ),              (5)

                                                .                                    (6)

     Будем считать, что .

     Чтобы найти решение задачи (4)-(6), сначала  находим многоугольник решений, определяемый ограничениями (5) и (6).Предполагая, что этот многоугольник не пуст, полагаем значение функции равным некоторому числу h, так что прямая

                                                  ,                       (7)

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

     Итак, процесс нахождения решения задачи (4) – (6) включает следующие этапы:

1. В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.
2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи.
3. Находят многоугольник решений задачи.
4. Строят прямую (7), уравнение которой получается, если принять значение целевой функции (4) равным некоторому постоянному числу.
5. Определяют точку максимума или устанавливают неразрешимость задачи.
6. Находят значение целевой функции в точке максимума.

 

  Задание. Для производства двух видов изделий А и В предприятие использует три типа технологического оборудования. Каждое изделие должно пройти обработку на трех типах оборудования. Время обработки и траты, связанные с производством 1-го изделия каждого вида приведены в таблице:

                                          Определим, сколько изделий каждого вида следует изготовить,

                               что бы себестоимость 1 изд. была минимальной.            

      Построим по этим ограничениям график и определим область

   допустимых решений. Это будет многоугольник ABCDE.                                                                     

     Значит, функция принимает свое min значение в одной из точек

     A,B,C,D или E. 
 

Что бы определить точку, в которой целевая функция принимает минимальное значение. Возьмем F, равное произвольному числу, например, 42/5.

(*)

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

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

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

(2;0).

Т.о. оптимальным планом, будет производство 1вида изделия А, производство же изделий вида В будет для нас невыгодно.

В точке (2;0),

При таком оптимальном  плане, себестоимость изделий будет минимальна и равна: . 
 
 
 
 
 
 
 
 

                                                   Лабораторная работа 6.

Оптимизация себестоимости продукции.

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

                                                               (1)

при условиях     ;      ( ),                            (2)

                                       ( ),                              (3)

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

     Задача (1) – (3) может быть сведена к задаче линейного программирования. Для этого следует обозначить

                                                                 (4) 

и ввести  новые  переменные

                                             ( ).                (5) 

     Используя введенные обозначения, исходную задачу (1) – (3) сведем к следующей: найти максимум функции

                                                                       (6) 

при условиях                       ( ),       (7) 

                                   ,                                       (8) 

                                       ( )  и .           (9) 

     Задача (5) – (9) является задачей линейного  программирования, а следовательно, её решение можно найти известными методами. Зная оптимальный план этой задачи, на основе соотношений (5) получаем оптимальный план исходной задачи (1) – (3).

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

     

1. Сводят  задачу (1) – (3) к задаче линейного  программирования (6)– (9).
2. Находят решение задачи (6) – (9).
3. Используя соотношения (5), определяют оптимальный план задачи (1) – (3) и находят максимальное значение функции (1).

 

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

 
 
 
 
 
 

 Сведем нашу задачу к линейной форме. Для этого введем новые переменные.

Обозначим, , , и получим:

 

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

Результаты вычислений приведены ниже, в таблице.