3.5 Анализ полученных результатов

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

Искомая погрешность для целевой функции будет равна:

Если сравнить полученные решения, то можно сделать вывод о том, что мы при выборе точек аппроксимации удачно попали в значения для переменных x₁, x₂ и x₃, полученных при использовании для решения задачи методом Била.

Сравнивая ход решения задачи методом Била и методом сепарабельного программирования, очевидна гораздо большая трудоемкость решения во втором случае. Это объясняется большим количеством переменных и ограничений. Кроме этого, была выполнена достаточно грубая аппроксимация – 10 точек. Увеличение их количества привело бы к еще большему усложнению задачи.

Так или иначе задачи квадратичного программирования разумнее решать более конкретизированными методами, например, используемым выше методом Била.

3.6 Выводы к Главе 3

• В данной главе продемонстрированы основные этапы и приемы, используемые для решения нелинейных задач методом Била и сепарабельным симплекс-методом.

• Трудоёмкость решения задачи сепарабельным симплекс-методом намного выше трудоёмкости решения методом Била.

• Погрешность результатов сепарабельного симплекс-метода всецело зависит от сетки аппроксимации.

• Даже в задачах такого уровня уже весомую роль играет анализ решения и эмпирические выкладки. Всё это способно значительно упростить решение.

4 Разработка программного модуля

4.1 Теория решения двойственных задач

4.1.1 Переход от прямой задачи к двойственной

Общая задача линейного программирования формулируется следующим образом максимизировать (минимизировать) целевую функцию Y вида:

Y=c_jx_j → max

При ограничениях

a_ijx_j(<=, =, >=)b_i  i=[1,m]; j=[1,n]; x_j>=0

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

Y=с₁*x₁+…+с_n*x_n → max

При ограничениях

a₁₁*x₁+…a_1n*x_n<=b₁

a₂₁*x₁+…a_2n*x_n<=b₂

....

a_k1*x₁+…a_kn*x_n<=b_k

x_i>=0 , i=[1,n]

Двойственная задача:

S=b₁*y₁+…+b_m*y_m → min

При ограничениях

a₁₁*y₁+…a_m1*y_m>=c₁

a₁₂*y₁+…a_m2*y_m>=c₂

....

a_1n*x₁+…a_mn*y_m>=c_n

y_i>=0 , j=[1,m]

Правила образования двойственной задачи:

1. Целевая функция исходной задачи оптимизируется противоположно двойственной.

2. Матрица коэффициентов ограничений  двойственной задачи получается путём транспонирования матрицы коэффициентов прямой задачи и наоборот.

3. Число переменных в двойственной задаче равно числу ограничений прямой задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

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

5. Если переменная x_j прямой задачи может принимать только положительное значение, то j-е условие в системе ограничений двойственной задачи является неравенством вида >=. Если переменная  x_j может принимать любое значение, то j-е ограничение уравнение =. Аналогичное состояние имеется между ограничениями исходной задачи и переменными двойственной задачи.