3.1.3 Градиентный алгоритм поиска оптимума с использование реверса (возврата назад)

Процедура опирается на следующие соотношения:

Алгоритм:

3.1.4 Поиск оптимума в многокритериальном пространстве.

Рассмотрим данный алгоритм на примере задачи проектирования технического объекта.

Дано:

1) Материальная модель системы, имеющая n параметров:

2) Ограничения на параметры:

3) Функциональные ограничения:

(рисунок)

4) Критерий качества проектируемой системы:

5) Критериальные ограничения:

Требуется:

Найти такое A, которое удовлетворяет всем ограничениям.

Рассмотрим укрупненную диалоговую процедуру решения данной задачи:

2 – 4 блоки — первый этап

5 блок – второй этап

Остальное - третий этап

Краткая характеристика первого этапа.

Он состоит в составлении таблиц испытаний для пространства D. Последовательно выбирается N-пробных точек, которые мы обозначили А₁, А₂,...,А_n . Эти точки равномерно распределены в пространстве G. В каждой точке A_i рассчитывается значения всех критериев оптимальности Ф_v(A₁), Ф_v(А₂)...Ф_v(А_n) (- таблица Δ). По каждому критерию составляется таблица испытаний, в которой записаны значения критериев в порядке возрастания: Ф_v(A_i1) <= Ф_v(A_ik) <= .... <= Ф_v(A_in), где i₁, i₂, ,.., i_n — номера пробных точек.

Кратка характеристика 2 этапа

ЛПР просматривает строки таблицы Δ и назначает (изменяет) ограничения по критериям.

Краткая характеристика 3 этапа

Проверка не пустоты множества D, если ....

3.2 Симплекс-алгоритм решения задачи линейного программирования

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

Ограничения:

Разделим множество переменных данной задачи на свободные и базисные, при этом свободные могут принимать любые значения > 0, а базисные вычисляются через свободные. Пусть в нашем дальнем рассмотрении x — свободные переменные, а y — базисные переменные

Построим симплекс-таблицу (СТ) на основе заданной надписи задачи

x	-x1	-x1	…	-xj	…	-xk	x
y1	a11	a12	…	aij	…	a1k	b1
y2	a21	a22	…	a2j	…	a2k	b2
…	…	…	…	…	…	…	…
ym	am1	am2	…	amj		amk	bm
Q	- а1	- a2	…	- aj	…	- ak	x

Рассмотрим укрупненную схему алгоритма, которая соответствует данному методу

П₄ – критерий оптимальности минимален, если в строке Q все элементы a_j – отрицательные.

П₁ — ограничения совместные, если на каждой итерации в каждой строке симплекс таблице, имеющей отрицательный свободный член “b”, есть хотя бы один отрицательный коэффициент “a”.

П₂ — решение допустимо если в СТ все свободные члены “b” неотрицательны

П₃ — критерий ограничен снизу, если на каждой итерации в каждом столбце СТ, содержащем положительный коэффициент a_j, имеется хотя бы 1 положительное a.

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

- определить разрешающий элемент в СТ

- разрешающий элемент заменить на

- остальные элементы разрешающей строки умножают на

- остальные элементы разрешающего столбца умножают на

- все другие СТ стоящие на пересеченной l-ой строки S-ого столбца вычисляем по формуле

Правило определения разрешающего элемента (РЭ) СТ состоит в следующем:

А) Выбрать i-ую строку с отрицательным коэффициентом

Б) Выбрать j-ый произвольный столбец с отрицательным коэффициентом

В) Вычислить отношение для всех

Г) Найти минимум отношения по всем найденным .

Д) Пересечения разрешающей строки (пункт 6) и разрешающего столбца (пункт г) дает разрешающий элемент.

В блоке 7 используется правило Б, которое включает в себя те же действия, что и правило А за исключением выбора разрешающего столбца.

Правило Б отличается от правила А тем, что разрешающий столбец выбирается тот, для которого коэффициент a_j – отрицателен.