Особые случаи приведенной задачи.

1.Если матрица оценок (C_ij)_mn не является квадратной, то в модели следует записать ограничение:

              если работников > числа работ 

             если работников < числа работ 

 

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

Задача нелинейного программирования формулируется так же, как и общая задача оптимального программирования, но со следующими требованиями: целевая функция f(х_1,х₂,…,х_n) и (или) одна из функций g_i(х_1,х₂,…,х_n) являются нелинейными:

Min (max) f (х_1,х₂,…,х_n),

g_i(х_1,х₂,…,х_n) { ≤,=,≥} b_i, i=1,…, m,

х_j ≥ 0, j=1,…,n.

 

Задачи НЛП несравнимо сложнее ЛП и для них не существует универсального метода их решения (аналогично симплексному методу).

Есть целый ряд методов решения НЛП: метод Лагранжа, градиентный метод, метод штрафных функций, метод динамического программирования.

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

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

Метод динамического программирования. При решении задачи этим методом процесс решения делится на этапы, решаемые последовательно во времени.

 

Метод оптимизации Лагранжа

Метод оптимизации Лагранжа или метод разрешающих множителей применяют для решения задач типа:

Найти max (min) f (x ₁, x ₂,…, x_n) при ограничениях

        φ _i (x ₁, x ₂,…, x_n) = 0, i =1,…, m

Предполагают, что функции f и φ _i непрерывны вместе со своими частными производными.

1)    Для решения задачи составляют вспомогательную функцию (функцию Лагранжа), которая в области допустимых решений достигает максимума для тех же значений переменных x ₁, x ₂,…, x_n, что и целевая функция f:

              F (x ₁, x ₂,…, x_n, λ₁, λ₂,…, λ _m) = f (x ₁, x ₂,…, x_n) + Σ ^m _{i =1} λ _i φ _i (x ₁, x ₂,…, x_n)

2) Находят частные производные этой функции по переменным x ₁, x ₂,…, x_n  и множителям Лагранжа λ _i, приравнивают их к нулю и получают систему уравнений:

             всего (n+m)- уравнений и (n+m)- неизвестных

        Решают эту систему например методом Жордана-Гаусса.

 

3)  Получают решение (x ^* ₁, x ^* ₂,…, x ^* _n, λ^*₁, λ^*₂,…, λ ^* _m) и точка с координатами (x^*₁,x^*₂,…,x^*_n) является точкой экстремума (т.е. точкой минимума или максимума функции f).

4) Проверяют максимум это или минимум, для чего находят значение функции Лагранжа в окрестности экстремальной точки.

Если приращение функции ∆F = F(x+∆x) - F(x) отрицательно, то в данной точке достигается максимум.

Пример.

Найти экстремум функции f = х₁х₂ + х₂х₃ при ограничениях

х₁+х₂ =2

х₂+х₃ =2

Решение:

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

F (x ₁, x ₂, x ₃, λ₁, λ₂) = х₁х₂ + х₂х₃ + λ₁( х₁+х₂ -2) + λ₂( х₂+х₃ -2)

Дифференцируем ее по переменным x ₁, x ₂, x ₃, λ₁, λ₂ и полученные выражения приравниваем к нулю.

Решив систему, получаем x^*₁ = x^*₂ = x^*₃ =1, f^* = 2

 

Возьмем точку (0;2;0) из допустимой области, в ней f = 0, следовательно, точка (1;1;1) -точка глобального максимума.

 

Литература

1. Карасев А.И., Кремер Н.Ш., Савельева Т.И. Математические методы и модели в планировании.-М.: Экономика, 1987.

2. Лопатников Л.И. Экономико-математический словарь.-М.:Наука, 1987.

3. Федосеев В.В., Гармаш А.Н., Дайитбегов Д.М., Орлова И.В., Половников В.А. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В.Федосеева. – М.: ЮНИТИ, 1999. – 391 с.

4. Федосеев В.В. Экономико-математические методы и модели в маркетинге.-М.: Финстатинформ, 1996.

5. Экономико-математические методы и прикладные модели: Методические указания по выполнению контрольной работы, темы и задачи. Для студентов III курса по специальностям 060400 –«Финансы и кредит» и 060500 – «Бухгалтерский учет, анализ и аудит» /ВЗФЭИ.-М.:ВЗФЭИ, 2002.-104 с.