Теория принятия решений

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

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

   Теорема Куна – Таккера утверждает: вектор Х является оптимальным вектором тогда и только тогда, когда существует такой вектор , что пара векторов ( ) - есть седловая точка функции . Из этой теоремы следует, что для того, чтобы решить ЗНП целесообразно искать седловую точку, соответствующую функции Лагранжа. Зная ее, находим решение ЗНП.

   Если  предположить, что f и g_i непрерывны и дифференцируемы, то теорема Куна – Таккера дополняется аналитическими  выражениями:

   

  
 

 
 

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

Математическая  постановка задачи квадратичного  программирования. 

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

   Матричная постановка задачи квадратического программирования имеет вид: 

min f(x)=C^Tx+x^TQx 

при выполнении системы ограничений:

   aTx b

   x  

где , ,  

   В алгебраической форме модель  ЗКП имеет вид:

определить оптимальное  значение (x₁, x₂,…,x_n) 

 

при выполнении системы ограничений: 

     

  
 

где - отрицательно полуопределенная квадратичная функция. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Метод решения задачи квадратичного  программирования. 

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

   

   Добавляя  дополнительные выражения по теореме  Куна – Таккера, имеем: 

        

      

      

        

        

        
 

   Введем  дополнительные переменные  ,

 

        Þ 

      

      

        Þ 

      

        

      Подставляя их значения получаем: 

 Þ   

 

   Чтобы найти решение ЗКП, необходимо определить неотрицательное решение системы линейных отношений: 
 

        

        

        

        
 

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

      при условиях:

      

      

      

        

где Z_i – искусственная переменная, введенная в уравнение.                 

   Используя этот метод после конечного числа шагов, получаем оптимальное решение ЗКП либо устанавливаем ее неразрешимость. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Решение:  

max

 

Составим функцию Лагранжа: 

 

   Составим  выражения необходимых и достаточных условий существования седловой точки построенной функции:

    

    

    

    

    

    

    

      

   Систему линейных неравенств перепишем в  виде:

    

    

      

   Введем  дополнительные неотрицательные переменные:

   

    

      

   Из  первого равенства находим: 

     

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

      

   Аналогично  для второй системы: 

        

   Тогда необходимо решить следующую задачу: max F при выполнении системы неравенств:

   

    

      

с учетом выполнения равенств: 

         

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

   Решим данную задачу методом искусственного базиса. Тогда модель такой ЗНП имеет вид:

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

    

    

      

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