2.2. Метод решения задачи

2..2.1. Выбор метода решения задачи

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

Пусть - заданное множество элементов x произвольной природы, – заданное отображение множества в множество Y чисел (натурального ряда, рациональных, действительных, неотрицательных, и т. д.).

Тогда задача минимизации (максимизации) может быть сформулирована следующим образом: либо найти элемент , , который минимизирует функцию f(x), либо установить его отсутствие. Если существует такой элемент , то для всех .

Класс задачи оптимизации определяется:

• свойствами множества Х;

• видом ограничений;

• видом целевой функции.

Множества Х может быть:

• непрерывное (н), дискретное (д)- [ ] , целочисленное (ц) - ;

• отрицательное (о), неотрицательное (н);

• бесконечное (б), конечное (к) ;

• бинарное (B) – [0,1], не бинарное (N).

Классы задач при учете свойств множества X представлены в табл. 3.2.:

Таблица 3.2

1

2

3

4

5

6

7

8

9

10

11

12

13

1

Непрерывность

н

н

н

н

д

д

д

д

ц

ц

ц

ц

ц

2

Отрицательность

о

о

н

н

О

о

н

н

о

о

н

н

н

3

Бесконечность

б

к

б

к

Б

к

б

к

б

к

б

к

к

4

Бинарность

N

N

N

N

N

N

N

N

N

N

N

N

B

Все ограничения относят к следующим видам:

• линейные - , или нелинейные , где нелинейная функция;

• логически связанные:

,

где - множество Н дизъюнктивных уравнений

Виды целевой функции может быть следующим:

• однокритериальные - , или многокритериальные - , где n- количество критериев.

• линейные или нелинейные.

Для определения класса задачи математического программирования необходимо воспользоваться источником: «Хохлюк В.И. Параллельные алгоритмы целочисленной оптимизации. -М.: Радио и связь, 1987.».

При установленном классе задачи можно воспользоваться методом решения задачи (см. Венцель Е.С. Исследование операций - М., «Советское радио», 1972).

2.2.2. Эвристические методы принятия решений

Приведем описание эвристического метода решения задачи в качестве примера.

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

На практике чаще всего используют эвристические методы решения задачи, так как точные методы невозможно применить из-за «проклятия размерности».

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

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

, (1)

при условии:

, (2)

где xÎ {0, 1}, j = 1, 2, …, n, c_j > 0, a_j > 0, b_j > 0. Не умаляя общности, можно предположить, что переменные занумерованы так, что c₁/a₁ ≥ c₂/a₂ ≥ ≥ c_n/a_n. Будем пытаться максимизировать f(x) за счет самых больших значений c_j/a_j, полагая последовательно x₁, x₂, и т. д. равными единице до тех пор, пока не нарушится ограничение (2).

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

С=c₁x₁+c₂x₂+c₃x₃+c₄x₄ ® min;

x_i ≥ 0, i = 1,2,3,4;

а₁₁х₁+а₂₁х₂+а₃₁х₃+а₄₁х₄≥b₁;

а₁₂х₁+а₂₂х₂+а₃₂х₃+а₄₂х₄≥b₂:

а₁₃х₁+а₂₃х₃+а₃₃х₃+а₄₃х₄≥b_3.

Воспользуемся пожирающим алгоритмом (можно также найти точное решение задачи, используя симплекс метод):

1. Найдем список коэффициентов:

H={ h_11, h_12, h_13, h_21, h_{22 ,}h₂₃, …, h₄₁, h₄₂, h₄₃,} ,

где h₁₁=c₁/a_11, h₁₂=c₁/a₁₂, h₁₃=c₁/a_13,.

h₂₁=c₂/a₂₁, h₂₂=c₂/a_22, h₂₃= c₂/a₂₃ …,

h₄₁= c₄/a₄₁, h₄₂=c₂/a₄₂, , h₄₃= c₄/a₄₃,

H={c_j/a_ji i=1,4; j=1,3}.

2. Присвоим s (номер витка цикла) значение равное единице

3. Найдем минимальное значение h*_ij, h*_ij Î H и исключим из списка H все значения h_kj (k=1,4).

4. Назначим максимально возможное значение x*_i (s):

x*(s)_i = b_j/a_ij.

5. Удалим из дальнейшего рассмотрения ограничение:

а_1jх₁+а_2jх₂+а_3jх₃+а_4jх₄≥b_j:

6. Используя найденное значение x*_i (s) изменим ограничения задачи:

а_1jх₁+а_2jх₂+а_3jх₃+а_4jх₄≥b_j - a_ij ´ x*_i(s).

7. Если список H не пустой, то увеличим s на единицу и перейдем к пункту 2. В противном случае завершим решение и найдем значение целевой функции и искомых переменных:

, i=1,4; ,

где S – множество номеров витков цикла алгоритма (шаги 2-6).