Экономмико-математические методы и модели

      х₁/14 + х₂/4,666 1 

     х₁/8,33 + х₂/6,25  1

     х₁/6,143 + х₂/21,5 1

     х₁ 0, х₂ 0

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

     Тогда целевая функция:

      F₁ = х₁ + х₂       max

       Эту зависимость представим в виде х₂ = f - х₁. Из графика данного уравнения (рис.1.) следует, что tg = -1, при этом = 135⁰, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если эту величину перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно , что оптимальным решением будут координаты  точки   С = (х₁, х₂).

      На  основании рассмотренного, можно  сделать исключительно важный вывод: оптимальным решением являются координаты вершин ОДР. На этом базируется аналитический метод решения задач линейного программирования, который заключается в следующем:

• Найти вершины ОРД, как точки пересечения ограничений.
• Определить последовательно значения целевой функции в вершинах.
• Вершина, в которой ЦФ приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной.
• Координаты этой вершины и являются искомыми оптимальными значениями переменных.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Рис. 2.2. 

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

     Тот факт, что оптимальное решение  находится на вершине ОДР, дает ещё 2 очень важных вывода:

     - Если оптимальным решением являются  координаты вершин ОДР, значит, сколько вершин имеет ОДР, столько  оптимальных решений может иметь  задача.

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

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

      б)  F₂ = 6х₁ + 8х₂       max (максимизация прибыли)

          6х₁ = f – 8х_{2 .}         

     Из  графика уравнений следует, что tg = - , а величина f равна отрезку, отсекаемому прямой функцией цели на оси координат (рис.2.2.).

     Так же мы можем найти следующие функции:

      F₃ = х₁           max  (максимализация выпуска продукции П₁)

      F₄ = х₂       max (максимализация выпуска продукции П₂)    

      F₅ = (1+3+7) х₁ + (3+4+2) х₂ = 11х₁ + 9х₂         max (минимизация используемых ресурсов). 

     Для каждой целевой функции, так же как  и для F₁, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 2.

                                                                                                                                   Таблица 2.

 
 

2.3.Симплексный  метод

Для аналитического решения задач линейного программирования разработан специальный алгоритм направленного  перебора вершин ОРД (области допустимых решений). Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается. В геометрии есть такое понятие, как "симплекс". Симплексом тел в К-мерном пространстве называется совокупность (К+1) его вершин. Так, для плоскости при К=2 симплексом будут 3 вершины треугольника. При К=3 - 4 вершины четырехгранника и т.д. С учетом этого понятия аналитический метод решения задач линейного программирования называется симплекс-метод. Он основан на алгоритме направленного перебора вершин. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине называются итерацией.

     В настоящее время этот метод является одним из основных методов решения  задач линейного программирования. Более подробно симплексный метод  решения задач мы рассмотрим на примере этой же задачи.

      х₁ + 3х₂ 14

     3х₁ + 4х₂  25

     7х₁ + 2х₂ 43

а) Функция цели f = 6х₁ + 8х₂       max

х₁ 0, х₂ 0

     Симплексный метод предназначен для решения  задач в канонической форме. Что бы перевести наше неравенство в каноническую форму введем новые неотрицательные  переменные y₁, y₂, y₃ и перейдем от системы неравенств к системе уравнений.

       х₁ + 3х₂ + 1y₁ + 0y₂ + 0y₃ 14 

     3х₁ + 4х₂  + 0y₁ + 1y₂ + 0y₃ 25

     7х₁ + 2х₂  + 0y₁ + 0y₂ + 1y₃ 43

     f = 6х₁ + 8х₂ + 0y₁ + 0y₂ + 0y₃

     Для удобства составления симплекс таблицы  перепишем данную систему в виде              0-уравнения:

              0 = 14 - (х₁ + 3х₂  + 1y₁ + 0y₂ + 0y₃)

             0 = 25 - (3х₁ + 4х₂  + 0y₁ + 1y₂ + 0y₃)         

             0 = 43 - (7х₁ + 2х₂  + 0y₁ + 0y₂ + 1y₃)                       

             0 = f –( 6х₁ + 8х₂ + 0y₁ + 0y₂ + 0y₃)

     Данную  систему можно записать в виде одного векторного равенства:

        0 = В – (А₁х₁ + А₂х₂ + А₃у₁ + А₄у₂ + А₅у₃),

где, вектор-столбец  В имеет своими компонентами свободные члены, а вектор А_1, А_{2, ….} А₅ – коэффициенты при соответствующих переменных х₁, х₂ , у₁ , у₂ , у_3. Иными словами:

                  14             1              3              1              0             0                                                        

           В=  25  , А₁=   3  , А₂ =  4   , А₃ =  0  ,  А₄=  1  ,  А₅=  0  .                                                                                          

           43              7             2              0              1             1                                                       

     Линейная  форма имеет вид:

     f = 6х₁ + 8х₂ + 0y₁ + 0y₂ + 0y₃.

     Векторы А_3,  А_4,  А₅ образуют базис. Это означает, что, присвоив х₁ = 0, х₂ = 0, получаем первое базисное решение: х₁=0; х₂=0; у₁=14; у₂=25; у₃ =43.

     При этом линейной формы f = 0. На этом основании строим первую симплексную таблицу 3.

     

                                                                                                                                            Таблица 3.

     Так как мы решаем задачу на максимализацию прибыли, то из выражения линейной формы  видно, что имеет смысл увеличить х₁ или х₂ (так как коэффициенты при этих переменных отрицательны в скобках).  Если мы предположим что х₁ 0 или х₂ 0, то значение f увеличится. Эти же коэффициенты с их знаками стоят в индексной строке. Из этого следует, что наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что оптимальное решение ещё не получено, и то, что от таблицы    надо перейти к следующей.

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

1. В индексной строке находим наибольшее по абсолютному значению отрицательное число. В нашем примере это будет – 8. Найденной число определяет ведущий или ключевой столбец.
2. Делим свободные члены на положительные элементы ведущего столбца и из полученных отношений выбираем наименьшее, это отношение и определит ведущую строку. В данной таблице мы проделали эту процедуру в последнем столбце, и из полученных результатов видно, что ведущей строкой является вторая строка А₄.
3. На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент. В данной задаче – это число 5.
4. Теперь преступаем к составлению второй таблицы:

а) Вместо единичного вектора А₄ мы в базис вводим  вектор А_2.

б) Переход  к новому базису, как это известно, эквивалентен элементарному преобразовании матрицы, элементами которой служат числа таблицы 4. А именно: в новой таблице элемент строки, соответствующий элементу ведущей строки прежне таблицы, равен этому элементу ведущей строки, разделенному на разрешающий элемент.

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

                                                                                                                                 Таблица 4.