Линейное програннирование

 

     За  ведущий выберем столбец 1, так как -7 - наименьший элемент в строке Z*(y).

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

От элементов строки 2 отнимем соответствующие элементы строки 1, умноженные на -3. От элементов строки 3 отнимем соответствующие элементы строки 1, умноженные на -7.  

 

     За  ведущий выберем столбец 5, так  как -12 – наименьший элемент в  строке Z*(y). В разрешающем столбце все элементы отрицательные, поэтому решение данной задачи симплекс методом бесконечно. 
 

3. Согласно первой теореме двойственности, необходимо выполнение условия Z(x)= Z*(y).

Найдем с помощью  надстройки «Поиск решения» в электронной  таблице Excel решение исходной задачи. 

 

Получим, . Выполнилось условие первой теоремы двойственности. Таким образом, найденный оптимальный план исходной задачи является оптимальным. 

 

Задача  № 2

Дана задача линейного программирования:

Требуется:

1. Решить задачу графическим способом.
2. Используя условия Куна-Таккера, доказать, что найденная точка является седловой для функции Лагранжа.

 

Решение.

1. Построим в системе координат Ox₁x₂ прямые, соответствующие неравенствам системы:

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

    Полагая значение целевой функции Z равным некоторому числу h, получаем линии уровня, а именно окружности с центром E(8, 4) и радиусом . С увеличением (уменьшением) числа h значения функции Z соответственно увеличиваются (уменьшаются).

      
 
 
 
 
 
 
 
 
 
 
 
 

    Проводя из точки E окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке С, в которой окружность касается области решений. Для определения координат этой точки составим систему двух уравнений (2) и (3), точкой пересечения графиков которых точка С является:

      

    Таким образом,

.

2. Имеем условия Куна-Таккера в дифференциальной форме:

   

 

   

    Покажем, что существует Λ⁽⁰⁾≥0, при котором в точке оптимума выполняются условия Куна-Таккера для функции Лагранжа F(X,Λ).

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

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

 

Имеем:

 

Подставляя найденное  решение x₁=5, x₂=5 в последние три уравнения, получим:

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

Так как x₁=5, x₂=5 – не равны нулю, то из первых двух уравнений имеем:

Отсюда, при x₁=5, x₂=5, =0 получим:

16-10- -3 =0

8-10- +5 =0.

Отсюда

=3 ≥ 0

=1 ≥ 0.

Следовательно, в точке (X⁽⁰⁾, Λ⁽⁰⁾) выполняются условия Куна-Таккера и она действительно является точкой экстремума и седловой точкой функции Лагранжа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

1. Кузнецов Ю.Н. «Математическое программирование: учебное пособие для экономических специалностей вузов», М., 1980г.