Нелинейного программирования

=================== =============================== ======

4. Методы решения задач нелинейного программирования

================================================== ======

Наиболее известными методами решения задач нелинейного программирования являются:

1. Градиентный метод.

2. Метод штрафных функций.

3. Метод выпуклого анализа.

4. Метод обобщенных градиентов.

5. Метод негладких штрафных функций.

6. Прямой градиентный метод.

7. Метод отсекающих гиперплоскостей.

8. Двойной градиентный метод.

9. Метод Эрроу-Гурвица.

10. Итерактивни методы декомпозиции.

11. Метод возможных направлений.

12. Метод линераризации.

13. Метод покампонентного спуска.

14. Метод множителей Лагранжа.

15. Метод потенциалов.

4.1. Решение нелинейных транспортных задач по правилу потенциалов

([1]- ст.142-143)

---------------------------------------------- ---- ---------------------------------------------

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

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

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

F = S Э_st(Г_st)®min (4.1)

где Э_st(Г_st) - затраты по участку s-t, которые являются некоторой нелинейной функцией потока по данному участку.

Г _st - общий поток всех грузов.

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

Для проверки оптимальности распределения потоков может быть использовано правило потенциалов, причем в нелинейном случае вместо длин участков c_st используют дифференциальные затраты по участкам, то есть производные расходов по потоку при данной ее величине. так, для базовых участков s-t

u_t – u_s = dЭ_st / dГ_st; (4.2)

для пустих

u_t – u_s £ dЭ_st / dГ_st; (4.3)

для насичених

u_t – u_s ³ dЭ_st / dГ_st; (4.4)

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

Предположим, что при оптимальном распределении потоков по каждой линии не превысит пропускной способности. Тогда обе линии базисные и соответственно (4.2)

u_Б – u_А= dЭ₁ / dГ₁; = dЭ₂ / dГ₂.

Пример 1. Распределить по двум параллельным ходам суммарный грузопоток 50 млн.т. между станциями А и Б. Затраты при потоках больших 60% пропускной способности составляют: на 1-линии Е₁=3Г₁+0,01Г₁²; на 2-й лінии Е₂=2Г₂+0,03Г₂^2.

При этом пропускная способность 1-линии - 27 млн.т, 2-линии - 30 лн. т.

Решение

Задачу решаем связываем методом потенциалов.

1. Найдем дифференциальные затраты.

на 1-й линии dЕ₁/dГ₁ = 3+ 0,02Г₁;

на 2-й линии dЕ₂/dГ₂ = 2 + 0,06Г₂.

2. Так, при оптимальному распределению потока дифференциальные затраты на параллельных линиях должны быть равны. Пользуясь этим, составляем систему уравнений

Решив которую, получим Г₁=25, Г₂=25.

Если бы оказалось, что один из потоков превысит пропускную способность (Г_k>d_k),, то приняли бы Г_k=d_k, а остаток общего потока пропустили бы по другой линии.

4.2. Решение нелинейных транспортных задач по принципу кусочно-линейных приближений.

([1]- ст.144-146)

-------------------------------------------------- ---------------------------------------------

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

1. Сначала весь грузопоток разбивается на n интервалов с шириной интервала DГ=(Г₁+Г₂)/n.

2. Затем вычисляются: а) расходы на границах интервалов Е_і; б) прирост затрат на каждом интервале DЕ_і ; в) удельный прирост DЕ_і /DГ_і.

3. Груз направляют по тому пути где удельный прирост меньше. Если удельный прирост по двум направлениям одинаковый, то груз распределяют пропорционально.

4. Суммируют груз по направлениям и получают решения данной задачи.

Точность решения тем больше, чем меньше интервалы линейности. Но при малых интервалах увеличивается число участков мульмережи, а соответственно и объем расчетов.

Пример 2. Распределить по двум параллельным ходам суммарный грузопоток 50 млн.т. между станциями А и Б. Затраты при потоках больших 60% пропускной способности составляют: на 1-линии Е₁=3Г₁+0,01Г₁² на 2-й линии Е₂=2Г₂+0,03Г₂².

При этом пропускная способность 1-линии - 27 млн.т, 2-линии - 30 лн. т.

Решение

Задачу решаем связыванием по принципу кусочно-линейных приближений. Расчеты делаем в виде таблицы.

1. Весь грузопоток разбиваем на 5 интервалов с шириной интервала DГ=(Г₁+Г₂)/n.=50/5=10 (млн.т) /табл.1, Кол.2, 3 /.

2. Высчитываем:

2.1. Расходы на границах интервалов Е и / табл.1, кол.4, 5, 6, 7 /;

2.2. Прирост расходов на каждом интервале D Еи /табл.1, кол.8, 9 /.;

2.3. Удельный прирост D Е и / D Г и / табл.1, кол.10, 11 /.

3. Груз направляем по тому пути где удельный прирост меньше. Если удельный прирост по двум направлениям одинаковый, то груз распределяется пропорционально / табл.1, кол.12, 13 /.

4. Суммируем груз по направлениям и получаем решения данной задачи / т.1-кол.14, 15 /.

Таблица 1.

№ п / п

Интер. шага

Витр.1-линии

Витр.2-линии

Пит. расх.

Диф.витрат

Накл.поток

Печаль. поток

ниж

вер.

ниж

вер.

ниж

вер.

D Г1

D Г 2

1лин

2лин

1лин

2лин

1лин

2лин

3,1

2,3

3,3

2,9

3,5

3,5

9сентября

3,7

4,1

3,9

4,7

25

25

Если бы оказалось, что один из потоков превысит пропускную способность (Г _{k> d} k), то приняли бы Г _k = _d k, а остаток общего потока пропустили бы по другой линии.

4.3. Метод множителей Логранжа

([8] - ст.166-171, [7] - ст.257-262;)

-------------------------------------------------- ---------------------------------------------

дано:

- Функции ограничений

g(x₀, x₁, x₂, …, x_n)= åa_ijx_ij =b_іj (4.3.1)

- Целевая функция.

z= f(x₀, x₁, x₂, …, x_n) Þmin(max) (4.3.2)

Найти: f(x_і) для которых z=åС_ijx_ij Þmin(max).

Чтобы найти решение задачи вводят набор переменных l_1,l_2,...,ln, которые называют множителями Лагранжа, а затем составляют функцию Лагранжа

(4.3.3)

После этого находят частные производные

(4.3.4)

и

(4.3.5)

Затем решают систему с(m + n) уравнений

(4.3.6)

Всякое решение системы уравнений (4.3.6) определяет точку Х = (x_0,x_1,x_2,...,x_n), в которой может иметь место экстремум функции f(x₀, x₁, x₂, …, x_n)

Итак, решив систему уравнений (4.3.6) получаем все точки, в которых функция (4.3.2) может иметь экстремальные значения. Дальнейшие исследования найденых точек проводят также, как и в случае безусловного экстремума.

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

1. Составление функции Лагранжа;

2. Нахождение частных производных от функции Лагранжа по переменным х_і, l_і и приравнивания их к нулю.

3. Решая систему (4.3.6) находят точки, в которых целевая функция задачи может иметь экстремум.

4. Вычисляют значение функции (4.3.2) в найденных точках.

Метод множителей Лагранжа имеет ограниченное использование, ибо система (4.3.6), как правило, имеет несколько решений.

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

Пример 3. По плану производства продукции завода необходимо изготовить 180 деталей. Эти детали могут быть изготовлены двумя технологическими способами. При производстве деталей І способом затраты равны Е₁=4х₁+х₁² а при изготовлении ІІ способом они равны Е₂=8х₂+х₂².

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

Решение

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

f= 4х₁+х₁²+8х₂+х₂² (1)

при условиях

х₁+х₂=180 (2)

х₁, х₂ ³ 0 (3)

Задачу решаем методом множителей Лагранжа.

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

2. F(x₁, x₂, l)= 4х₁+х₁²+8х₂+х₂²+l(180-x₁-x₂), (4)

2. Вычислим частные производные по x_1,x_2, l и приравняем их к нулю:

(5)

3. Решения "связав систему уравнений (5) получаем

================================================== ==============

Пример 4

дано:

n - количество видов запчастей;

d- общая сумма денег, выделенная на закупку всех запчастей;

b_j- стоимостьj-ой детали,j= 1, ... n;

Y_j -необходимость в j-й детали. Необходимость имеет показательное закон распределения с параметром a j;

a_j - параметр показательного закона распределения нужностиj-ой детали;

C_j- прибыль, который будет получен в результате использования j-ой детали;

r_j- убытки, которые будут получены в результате отсутствия j -ой детали;

q_j-убытки, Которые будут получены в результате неиспользования j-ой детали.

Распределить деньги d так, чтобы общая прибыль была максимальной.

Таблица 1 - Исходные данные.

i	aj	bj	Cj	Rj	qj	d	n
	0,25
	0,15
	0,10

Решение

1. обозначим

x_j - Сумма, которая выделяется на закупку j-ой детали,

x _j/b_j- количество купленных j-ых деталей.

2. Примем, что все переменные непрерывные.

3. определим:

- Получаемый доход, Р;

- убытки от отсутствия детали, З_1;

- убытки от неиспользования детали, З_2.

Результаты сведем в таблицу 2.

Таблица 2 - прибыль от использования деталей.

интервал	Прибыль, Р	Убытки, З1	Убытки, З2
Yj< xj/bj	CjYj		qi(xj /bj- Yj)
Yj= xj/bj	Cj xj/bj
Yj> xj/bj	Cj xj/bj	ri(Yj -xj /bj)

4. Определим суммарный доход по j-й детали:

4. (1)

5. Суммарная прибыль по n -Детали:

6. (2)

6. Математическая постановка задачи состоит в определении максимального значения функции

7. (3)

при условиях

или х₁+х₂+х₃ =820 (4)

х₁, х₂ , х₃ ³ 0 (5)

7. Задачу решим методом множителей Лагранжа.

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

(6)

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

, (7)

(8)

9. Вычислим частные производные по x _1, x _2, l и приравняем их к нулю получаем систему уравнений

10. (9)

11.

12. (10)

10. : Решивши систему уравнений (…) получаем

11. х₁ = 120; х₂ = 250; х₃ = 450;

11. Найдем суммарную прибыль

Z₁ = 42.45; Z₂ = 38.95; Z₃ = 88.43;

Z₁ + Z₂ + Z₃ = Z₁ = 42.45 + 38.95 + 88.43 = 169.83 (единиц стоимости);