Лекции Методы оптимальных решений. Методы оптимальных решений
 Скачать 466.5 Kb.
|
|
6. МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 6.1. Постановка задачи нелинейного программирования В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом: f (x1, x2, ..., xn) max (min) (6.1) gi (x1, x2 ..., xn bi, i=1, m1 gi (x1, x2 ..., xn bi, i=m1+1, m2 (6.2) ... ... ... ... ... ... ... ... ... ... ... gi (x1, x2 ..., xn bi, i=m2+1, m2 где xj - управляющие переменные или решения ЗНП, j=1, n; bi- фиксированные параметры, i=1, m; f, gi, i=1, n - заданные функции от n переменных. Если fи giлинейны, то (6.1), (6.2) проходит в задачу линейного программирования. Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных xj, j=1, n, которые удовлетворяют системе ограничений (6.2) и доставляют максимум или минимум функции f. Для задачи нелинейного программирования, в отличие от линейных задач, нет единого решения. В зависимости от вида целевой функции (6.1) и ограничений (6.2) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям. 6.2. Постановка задачи динамического программирования. Основные условия и область применения. В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения указанных задач используется метод динамического планирования (программирования). Этот метод более сложен по сравнению с методами расчета статических оптимизационных задач. Также не простым делом является процесс построения для реальной задачи математической модели динамическою программирования. Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах - через i, i=1, m. Если W обладает свойством аддитивности, т.е.:  (6.3)можно найти оптимальное решение задачи методом динамического программирования. Таким образом, динамическое программирование - это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (6.3). В задачах динамического программирования критерий эффективности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша. Переменная хi, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называются шаговым управлением i=1, m. Управлением процесса в целом (х) называется последовательность шаговых управлений х=(х1, х2, ..., хi, ..., хm). Оптимальное управление х - это значение управления х, при котором значение W(x) является максимальным (или минимальным, если требуется уменьшить проигрыш) W=W(x)=max W(x) xX, (6.4) где X - область допустимых управлений. Oптимальное управление xопределяется последовательностью оптимальных шаговых управлений: x = (x1, x, ..., xi, ..., xm). В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом: управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Поясним это правило. При решении задач динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники взамен устаревшей, на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать, с учетом его будущих воздействий на весь процесс. Другой момент, который следует учитывать при выборе управления на данном шаге, - это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств в i-ом году, необходимо знать, сколько средств осталось в наличии к этому году, и какая прибыль получена в предыдущем (i-1)-ом году. Таким образом, при выборе шагового управления необходимо учитывать: возможные исходы предыдущего шага. влияние управления на все оставшиеся до конца процесса шаги. В задачах динамическою программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага, и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления хm, на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, для каждого из них проводят условную оптимизацию m-го шага и определяют условное оптимальное управление хm. Аналогично поступают для (m-1)-го шага, делая предположение об исходах окончания (m-2)-го шага, и, определяя условное оптимальное управление на (m-1)-ом шаге, приносящее оптимальный выигрыш на двух последних шагах - (m-1)-ом и m-ом. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, т.к. состояние системы перед первым шагом обычно известно. Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является, безусловно, оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех ее шагах. 6.3. Многокритериальная оптимизация задачи, в которых оптимизацию проводят по нескольким параметрам, называют задачами многокритериальной или векторной оптимизации. Как и при линейном программировании задачи многокритериальной оптимизации включают в себя три основные части. три основные части задачи многокритериальной оптимизации: целевую функцию, ограничения, граничные условия. Наиболее часто целевая функция представляется обобщенными показателями эффективности, которые представляют собой взвешенную сумму частных показателей, в которую каждый из них входит с определенным весом, отражающим его важность: W= 1 .1 + 2 .2 + ... + n .n Для тex показателей, которые желательно увеличить, веса берутся положительные, а для тex, которые желательно уменьшить - отрицательные. Назначение коэффициентов весов проводят с помощью экспертных оценок. Методы экспертных оценок достаточно широко распространены. Математических методов определения экспертных оценок достаточно много. Рассмотрим некоторые из них. Математические методы определения экспертных оценок: Непосредственное назначение коэффициентов весов. Согласно этому методу каждый i-й эксперт для каждого k-ого параметра должен назначить коэффициент веса ik таким образом, чтобы сумма коэффициентов веса, назначенная одним экспертом для различных параметров, равнялась 1.  i=1, n, где n - число экспертов. В качестве коэффициента веса k-ого параметра kпринимают среднее значение по результатам экспертизы всех экспертов:  Oценка важности параметров в баллах. В этом случае каждый эксперт назначает каждому параметру оценку по десяти бальной системе. Наиболее важный параметр оценивается более высоким баллом. В результате экспертизы заполняется таблица, и находятся коэффициенты веса. |