Название работы	Кол-во страниц	Размер
Решение задачи. Рассмотрим пример. Пусть имеется ряд предметов П1...	1	35.44kb.
Коллективное поведение роботов. Желаемое и действительное Карпов В.	1	20.56kb.
Проверочная работа «Решение задач» Учитель информатики Батракова Л.	1	126.86kb.
Решение задач оптимизации методом	1	53.98kb.
Решение. Возьмем на комплексной плоскости ℂ две различные точки и...	1	245.67kb.
Вопросы к экзамену Основные понятия, этапы и методы математического...	1	23kb.
Задача этих рекомендаций состоит в предложении вожатому некоторых...	4	1386.49kb.
Лабораторная работа №1. "Система" Указать пропущенные атрибуты системы...	1	29.92kb.
Решение задачи Коши для обыкновенных дифференциальных уравнений	1	33.74kb.
Конкурса "Юный программист-2006"	1	23.07kb.
Решение задачи получение результата с помощью программного	1	259.14kb.
Задача оптимизации туристических групп Поиск решения и сценарии.	1	171.42kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

9. МЕТОДЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ АНАЛИЗА СИСТЕМ

9.1. Математическое программирование как инструмент решения задач

выбора

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

Само наименование «математическое программирование» связано с тем, что целью решения задач является выбор программы действий.

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

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

К
(9.1)

ритерий эффективности W можно представить в виде целевой функции

W=Ф(х)

Н
(9.2)

а множестве X = {x: q_i(x)≥0, i = 1, 2, …..,k_j
h_j(x)=0, j = 1, 2, …., m}.

Здесь q_i(x) и h_j(x) – скалярные функции, определяющие ограничения на элементах х множества Х.

Решение задачи состоит в отыскании такой точки х*, которая обеспечивает оптимальное (минимальное или максимальное) значение целевой функции Ф(х), при заданных функциями q(x) и h(x) ограничениях.

Если целевая функция Ф(х) и функция ограничения q(x) и h(x) линейны, то соответствующая задача является задачей линейного программирования.

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

Задачи, решения которых достигаются в результате многих этапов, относятся к задачам динамического программирования.

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

Если в целевой функции Ф(х) и функциях q(x) и h(x), определяющих ограничения, содержатся параметры с элементами неопределённости, то такая задача относится к задаче стохастического программирования.

9.2. Линейное программирование

9.2.1. Постановка задачи линейного программирования

Как следует из определения, целевая функция имеет следующий вид:


(9.3)
W = C₁x₁ + C₂x₂ + … + C_jx_j + … + C_nx_n

В зависимости от существа решаемой задачи ищется максимум или минимум этой функции.

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

Пусть из общего числа m ограничений I заданы в виде равенств, а остальные m - 1 в виде неравенств.

Получаем следующую систему уравнений:

(9.4)

Ч
(9.5)

тобы закончить математическую формулировку задачи, необходимо записать, что
m n и что все неизвестные должны быть неотрицательными числами, т.е.

_Xj>0, j=l,2,...n

В системе (9.4) ограничений записаны только односторонние неравенства. В общем случае возможны такие случаи, когда в одной задаче имеются неравенства, направленные в разные стороны, т.е. неравенства противоположного смысла. В системе (9.4) все значения b_i положительны. Если какое – либо значение b_i будет отрицательным, то направление неравенства будет противоположным. Чтобы привести это уравнение к тому же направлению знака неравенства, достаточно все члены этого уравнения умножить на -1.

Совокупность значений x₁ ≥ 0, х₂ ≥ 0,...х_п ≥ 0, удовлетворяющих системе ограничений (9.4), образует многомерную область допустимых решений (ОДР). Значение же max (min) W (x₁, х₂,...x_n) может быть достигнуто (если оно существует) не при всех точках ОДР, а только при определенных, обеспечивающих условие max (min) целевой функции.

В случае, когда число переменных n равно числу ограничивающих уравнений m, то система (9.4) имеет единственное решение, которое может быть найдено с помощью матричной алгебры.

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

9.2.2. Геометрическая интерпретация линейного программирования.

Геометрическую интерпретацию задачи линейного программирования можно наглядно представить, когда n – m = 2, т.е. когда две из общего числа n переменных, например, х₁ и х₂ выбраны в качестве свободных. Тогда остальные m переменных можно выразить через х₁ и х₂. В общем виде это запишется следующим образом:

(9.6)

Условие неотрицательности всех n переменных запишется в этом случае в виде следующих неравенств

(9.7)

(9.8)

Поскольку все условия выражены через две переменные x₁ и x₂, то мы получили двумерную задачу, которую можно наглядно изобразить на плоскости.

Свободные переменные x₁ и х₂ будем откладывать по осям 0x₁ и 0х₂. (рис. 9.1).

Условия (9.7) означают, что допустимые переменные лежат правее оси 0х₂ и выше

оси 0х₁.

Р
ис. 9.1

Если положить величину х₃ равной нулю, то получим уравнение

₃₁  х₁ + ₃₂  х₂ + ₃ = 0,

которое является уравнением прямой линии. Штриховкой отметим ту сторону от прямой, где х₃> 0.

Аналогичную процедуру можно провести и с оставшимися переменными, получив, кроме осей координат n - 2 прямых, с обозначениями сторон, где каждая переменная x_i > 0.

Многоугольник, внутри которого расположена область, принадлежащая одновременно всем полуплоскостям, удовлетворяющим условиям x_i > 0, есть область допустимых решений (ОДР). На рис 9.1 ОДР помечена затемнениями. Заметим, что область допустимых решений представляет собой выпуклый многоугольник.

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

функции W =C₁x₁ + С₂х₂ +...+ C_jX_j +...+ С_nх_n

Д
(9.9)

ля тех же условий, т.е. когда n - m =2n в качестве свободных переменных выбраны x₁ и х₂. Так же как и раньше можно базисные переменные х₃, x₄, ..., х_n выразить через x₁ и х₂, и для целевой функции получим выражение

W = ₀ + ₁x₁ + ₂х₂

Здесь ₀ - свободный член, который появился при переходе к переменным x₁ и х₂.

Линейная функция (9.9) имеет угловой коэффициент и она достигает max(min) при тех значениях х₁ и х₂, что и функция


(9.10)
W¹ = ₁х₁ + ₂х₂ ,

Придавая величине W¹ различные значения С₁, С₂..., получим на плоскости x₁0x₂ различные прямые, параллельные между собой (рис. 9.2). Направление, в котором при параллельном перемещении прямой W¹ величина W¹ будет увеличиваться (уменьшаться), зависит от величины и знака величины ₁ и ₂.

На рис 9.2 показано направление, при котором величина W¹ уменьшается, т.е. для показанных положений прямых С_{2 1}. При этом ₁ и ₂ будут отрицательными, а следовательно, угловой коэффициент, равный , будет тоже отрицательным, что и соответствует положению прямой W¹.

Рассмотрим теперь взаимное расположение области допустимых решений и линейной функции W¹ , отражающей целевую функцию (рис. 9.3).

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

1. Решение задачи линейного программирования единственно и оно соответствует одной из вершин многоугольника ОДР (рис. 9.3a)

2. Решение соответствует любой точке отрезка АВ, которая является одной
из сторон многоугольника ОДР и она параллельна линейной целевой функции W¹ (рис. 9.3б).

3. ОДР незамкнута, именно неограниченна в направлении перемещения прямой W¹. В этом случае задача не имеет решения (рис. 9.3в).

Р
ис. 9.2

Р
ис. 9.3

9.3. Нелинейное и динамическое программирование

9.3.1. Задачи нелинейного программирования

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

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

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

Н
(9.13)

айти максимальное значение функции

W = x₂ – x₁² + 6x₁

При следующих ограничениях на переменные x₁ и х₂:

(9.14)

(9.15)

Строим линии уровней W = х₂ – x₁ + 6x₁ = h, где h - возможные значения функции W(x₁,x₂).

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

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

Функция W(x₁,x₂) принимает экстремальное значение в точке касания одной из парабол с границей многоугольника OABCD. В нашем случае эта точка Е. Координаты точки Е можно найти из системы уравнений

(9.16)

Решая эту систему, получаем x₁* = 3, х₂* = 4 и W_max = 13 при этих значениях переменных.

Как видим, в задаче этого примера решение не является вершиной многоугольника ОДР. Поэтому метод перебора вершин, который используется при решении задач линейного программирования, в данном случае неприемлем.

Рис. 9.4

9.3.2. Динамическое программирование

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

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

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

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

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

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

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

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

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

Пусть исходное состояние системы есть S₀, а конечное состояние системы, в которое необходимо перевести систему, есть S_k.

Предполагается, что система управляема, способ воздействия на систему - управление U, должен быть таким, чтобы перевод из состояния S₀ в состояние S_k был бы оптимальным (например, максимальным должен быть выигрыш). Поскольку выигрыш зависит от управления, то можно записать

(9.17)

Запись эта означает "максимальное" из всех значений W(U) при всех возможных управлениях U.

Для любого промежуточного i - го шага принцип оптимальности (принцип Беллмана) может быть записан в виде следующего функционального рекуррентного соотношения

(9.18)

W_i(S) = - условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i - го и до конца. Слово "условный" означает выигрыш при условии, что на i-м шаге система находится в состоянии S;

W_i(S₁U_i) - выигрыш на i-м шаге, который зависит от состояния S и принятого управления U_i;

Ф_i(S₁U_i) = S - состояние системы перед следующим i + 1 шагом, которое естественно зависит от предыдущего состояния S и управления, принятого на i-м шаге.

W_i+1{Ф_i(S₁U_i)} - условный оптимальный выигрыш, получаемый на всех шагах, начиная с (i + 1) - го шага. Отметим существующую особенность, заложенную в функциональном соотношении (9.18): функция W_i(S) i - го шага зависит от функции W_i+1(S¹) последующего шага, т.е. функцию W_i(S) можно определить, если известна следующая за ней по порядку функция W_i(S).

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

Одно за другим строится вся цепочка условных оптимальных управлений. Действительно, зная W_K(S), можно по общей формуле (9.18), полагая в ней i + 1 = m, найти функцию W_m-1(S) и соответствующее условное оптимальное управление U_m-1(S); затем
W_m-2(S) и U_m-2(S) и так далее вплоть до последнего от конца, т.е. до первого шага, для которого будут найдены функция W₁(S) и управление U₁(S).

На этом заканчивается первый этап оптимизации: найдены - условный оптимальный выигрыш и условное оптимальное управление для каждого шага.

Второй этап состоит в нахождении безусловного (окончательного) оптимального управления.

И
(9.19)

сходное состояние S₀ задано. Условный оптимальный выигрыш для первого шага был определен. Следовательно, для первого шага

W_max = W₁(S₀)

Одновременно находится и оптимальное управление на первом шаге

U₁ – U₁(S₀)

П
(9.20)

о исходному состоянию S₀ и управлению U₁ находят состояние после первого шага

S₁¹ = Ф₁(S₀,U₁)

П
(9.21)

о состоянию S₁¹ находим оптимальное управление на втором шаге U₂=U₂(S₁¹), затем S₂¹ = Ф₂(S₁¹,U₂) и т.д. Образуется цепочка

S₀  U₁(S₀)  S₁¹  U₂(S₁¹)  …  S_k-1¹  U_k(S_k-1¹)  S_k¹