Решение задачи многомерной оптимизации при помощи компьютера

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

математический программирование дискретный оптимизация

Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшими могут быть совершенно разные решения. Все зависит от выбранного или заданного критерия. На практике оказывается, что в большинстве случаев понятие «наилучший» может быть выражено количественными критериями - минимум затрат, минимум времени, максимум прибыли и т.д. Поэтому возможна постановка математических задач отыскания оптимального результата, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются задачами оптимизации. Оптимальный результат, как правило, находится не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. Чтобы решить практическую задачу надо перевести ее на математический язык, то есть составить ее математическую модель.

Математическая модель представляет собой стройную и глубокую совокупность знаний о математических моделях со своими проблемами, с собственными путями развития, обусловленными внутренними и внешними причинами и задачами. Математика дает удобные и плодотворные способы описания самых разнообразных явлений реального мира и тем самым выполняет в этом смысле функцию языка. Эту роль математики прекрасно осознавал Галилей, сказавший: «Философия написана в грандиозной книге - Вселенной, которая открыта нашему пристальному взгляду. Но понять эту книгу может лишь тот, кто научился понимать ее язык и знаки, которыми она изложена. Написана же она на языке математики».

Математика - это область человеческого знания, в которой изучаются математические модели.

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

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

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

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Наилучшие в определенном смысле решения задач принято называть оптимальными. Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

Составной частью методов оптимизации является линейное программирование.

1.1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Пусть задана функция n действительных переменных n f(x1, x2, x3, ..., xn) = f(x), определенная на множестве X ? R , где x - вектор- столбец, обозначающий точку в n-мерном евклидовом пространстве с координатами x1, x2, x3, ..., xn .

Функция f(x) имеет локальный минимум в точке x*? X, если существует окрестность точки x* такая, что f(x*) ? f(x) во всех точках этой окрестности. В n случае глобального минимума в точке x* для всех x ? R справедливо неравенство f(x*) ? f(x).

Далее будем рассматривать задачу отыскания точек минимума функции n

f(x), т.е. f(x) > min , x ? R . Для приведения же задачи максимизации к задаче минимизации достаточно изменить знак целевой функции.

1.2 АНАЛИЗ МЕТОДОВ РЕШЕНИЯ

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

Решается задача минимизации функции (x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности {x_k}. В качестве начального приближения выбирается любая точка x₀E_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

в точке x_k выбирают направление спуска - S_k;

находят (k+1)-е приближение по формуле

x_k+1=x_k-h_kS_k.

Направление S_k выбирают таким образом, чтобы обеспечить неравенство f(x_k+1)<f(x_k) по крайней мере для малых значений величины h_k. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число h_k определяет расстояние от точки x_k до точки х_k+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины h_k - это обеспечить выполнение неравенства (x_k+1)<(x_k).

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

x_k+1=x_k-h_k cos

где - cos=

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

Наибольшее распространение получили следующие алгоритмы:

1. (без коррекции);

2. если ; если

3. , если ; , если ; , если ,

где -угол между градиентами на предыдущем и текущем шаге;

и - заданные пороговые значения выбираются субъективно (например, ).

Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).

1.2.1 МЕТОД ПОКООРДИНАТНОГО СПУСКА

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

u=f(M)=f(x₁, x₂, . . . ,x_n).

Здесь через М обозначена точка n-мерного пространства с координатами x₁, x₂, . . . ,x_n: M=(x₁, x₂, . . . ,x_n). Выберем какую-нибудь начальную точку М_{_}=(x₁^_, x₂^_, . . . ,x_n⁰) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x₁, x₂^_,x₃^_, . . . ,x_n⁰ ). Тогда она превратится в функцию одной переменной x₁ . Изменяя эту переменную, будем двигаться от начальной точки x₁=x₁^_ в сторону убывания функции, пока не дойдем до ее минимума при x₁=x₁¹, после которого она начинает возрастать. Точку с координатами ( x₁¹, x₂^_,x₃^_, . . . ,x_n⁰) обозначим через М₁, при этом f(M₀) >= f(M₁).

Фиксируем теперь переменные: x₁=x₁¹, x₃= x₃^_, . . . ,x_n=x_n⁰ и рассмотрим функцию f как функцию одной переменной x₂: f(x₁¹, x₂², x₃^_ . . . ,x_n⁰). Изменяя x₂ , будем опять двигаться от начального значения x₂=x₂⁰ в сторону убывания функции, пока не дойдем до минимума при x₂=x₂¹ .Точку с координатами {x₁¹, x₂¹, x₃^_ . . . x_n⁰} обозначим через М_?, при этом f(M₁) >=f(M₂).

Проведем такую же минимизацию целевой функции по переменным x₃, x₄, . . . ,x_n. Дойдя до переменной x_n, снова вернемся к x₁ и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М_{_},М₁,М₂,--. . . , которой соответствует монотонная последовательность значений функции f(M₀) >=--f (M₁)>=--f(M₂)-->=----Обрывая ее на некотором шаге k можно приближенно принять значение функции f(M_k) за ее наименьшее значение в рассматриваемой области.

Проведем такую же минимизацию целевой функции по переменным x₃, x₄, . . . ,x_n. Дойдя до переменной x_n, снова вернемся к x и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М_{_},М₁,М₂, . . . , которой соответствует монотонная последовательность значений функции

f(M₀)>=--f(M₁)>=--f(M₂) >=--...--Обрывая ее на некотором шаге k можно приближенно принять значение функции f(M_k) за ее наименьшее значение в рассматриваемой области. Отметим , что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x₁, x₂, ... ,x_n) задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов. В противном случае, когда явной формулы для целевой функции нет, одномерные задачи следует решать с помощью одномерных методов

На рис.изображены линии уровня некоторой функции двух переменных u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода.

Пусть требуется решить задачу (2):

f(x) min, х ОRⁿ. (2)

В двумерном пространстве R². Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.

Выбирают произвольно начальную точку х⁽⁰⁾ из области определения функции f(х). Приближения х^(k) определяются соотношениями

(3): x^(k+1)=x^(k)+t^(k)S^(k) (k=0,1,2, ...),

где вектор направления спуска s^(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S^(k) параллелен х₁, то S^(k)= {1,0,0,...,0}, если он параллелен x₂, то S^(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t^(k) является решением задачи одномерной минимизации:

f(x^(k)+ts^(k)) min, t ОR¹, (k=0,1,2, ...), и может определяться, в частности, методом сканирования. Детальная реализация общей схемы в двумерном случае R² дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х^(k), x₁~^(k) x^(k+1) (k=0, 1, 2,) . При k=0, исходя из начальной точки х⁽⁰⁾=(x₁⁽⁰⁾,x₂⁽⁰⁾), находят точку х~⁽⁰⁾= (x₁~⁽⁰⁾,x₂⁽⁰⁾), минимума функции одной переменной f(x₁,x₂⁽⁰⁾); при этом f(x~⁽⁰⁾)<=f(x⁽⁰⁾).Затем находят точку минимума x⁽¹⁾ функции f (x₁~⁽⁰⁾,x₂) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х⁽¹⁾. Фиксируя вторую координату точки х⁽¹⁾, находят точку минимума х~⁽¹⁾= (x₁~⁽¹⁾,x₂⁽¹⁾), функции f(x₁,x₂⁽¹⁾) одной переменной x⁽¹⁾; при этом f(x~⁽¹⁾)<=f(x⁽¹⁾)<=f(x⁽⁰⁾). Точку х⁽²⁾ получают, минимизируя целевую функцию f(x₁~⁽¹⁾,x₂), вновь по коорданате х₂, фиксируя координату x₁~⁽¹⁾ ,точки x⁽¹⁾ , и т.д.

Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство

||x^(k+1) - x^(k) ||<e----(4)

1.2.2 МЕТОД ГРАДИЕНТНОГО СПУСКА

Рассмотрим функцию f, считая для определенности, что она зависит от трех переменных x,y,z. Вычислим ее частные производные дf/дх, дf/ду, дf/дz и образуем с их помощью вектор, который называют градиентом функции:

grad f(x, у, z) = дf (х, у,z) /дх*i+дf( x, у, z)/ду*j+дf(x, y,z)/дг*k.

Здесь i, j, k - единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции f по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (х, у,z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента

grad (х, у,z)|--=Ц--(дf/дх (х, у,z))² +(дf/ду( x, у, z))²+(дf/дг(x, y,z))².

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

Перейдем к описанию метода градиентного спуска. Основная его идея состоит в том, чтобы двигаться к минимуму в направлении наиболее быстрого убывания функции, которое определяется антиградиентом. Эта идея реализуется следующим образом.

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

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

Для оценки частных производных используются разностные методы:

1.Алгоритм с центральной пробой

------------------------------------------------------------------------------

2. Алгоритм с парными пробами

----------------------------------------------------------------------------------

где g_i - пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

Отметим, что при таких расчетах g_i ,нельзя брать слишком малым, а значения функции нужно вычислять с достаточно высокой степенью точности, иначе при вычислении разности

Df(x₁, ...,x_i+ g_i, ..., x_n) - f(x₁, ..., x_i, ..., x_n)

Df(x₁, ...,x_i+ g_i, ..., x_n) - f(x₁, ..., x_i- g_i,..., x_n)

будет допущена большая ошибка.

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

На рис1. изображены линии уровня функции двух переменных u= f (х, у), , и приведена траектория поиска ее минимума с помощью метода градиентного спуска.



Рис1.

1.2.3 МЕТОД НАИСКОРЕЙШЕГО СПУСКА

При использовании метода наискорейшего спуска на каждой итерации величина шага а_k выбирается из условия минимума функции f(x) в направлении спуска, т. е.

f(x[k] -a_kf'(x[k])) = f(x[k] - af'(x[k])).

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции

j(a) = f(x[k] - af'(x[k])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f'(x[k]).

3. Определяется величина шага a_k, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

4. Определяются координаты точки х[k+1]:

х_i[k+1] = x_i[k] - а_kf'_i(х[k]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f'(x[k+1]f'(x[k]) = 0.

Рис. 2.9. Геометрическая интерпретация метода наискорейшего спуска

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения



Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными.Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2.10. Овражная функция

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

1.2.4 МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ

Рассмотрим теперь совершенно иной подход к решению систем линейных уравнений, при котором к искомому точному решению x* системы Ax=b строится последовательность приближенных решений x0, x1, ..., xk,... При этом процесс вычислений организуется таким способом, что каждое очередное приближение дает оценку точного решения со все уменьшающейся погрешностью, и при продолжении расчетов оценка точного решения может быть получена с любой требуемой точностью. К преимуществам подобных итерационных методов можно отнести меньший объем (по сравнению, например, с методом Гаусса) необходимых вычислений для решения разреженных систем линейных уравнений, возможность более быстрого получения начальных приближений искомого решения, наличие эффективных способов организации параллельных вычислений.

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

Напомним, что матрица А является симметричной, если она совпадает со своей транспонированной матрицей, т.е. А=АТ. Матрица А называется положительно определенной, если для любого вектора x справедливо: xTAx>0.

Известно, что после выполнения n итераций алгоритма (n есть порядок решаемой системы линейных уравнений) очередное приближение xn совпадает с точным решением.

Последовательный алгоритм:

Если матрица А симметричная и положительно определенная, то функция



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

Итерация метода сопряженных градиентов состоит в вычислении очередного приближения к точному решению в соответствии с правилом:

Тем самым, новое значение приближения xk вычисляется с учетом приближения, построенного на предыдущем шаге xk-1, скалярного шага sk и вектора направления dk.

Перед выполнением первой итерации вектора x0 и d0 полагаются равными нулю, а для вектора g0 устанавливается значение равное -b. Далее каждая итерация для вычисления очередного значения приближения xk включает выполнение четырех шагов:

Шаг 1. Вычисление градиента:

Шаг 2. Вычисление вектора направления:

где есть скалярное произведение векторов.

Шаг 3. Вычисление величины смещения по выбранному направлению:



Шаг 4. Вычисление нового приближения:

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

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

и, тем самым, сложность алгоритма имеет порядок O(n3).

1.3 АНАЛИЗ СРЕДСТВ ПРОГРАММИРОВАНИЯ

Язык программирования С++ задумывался как язык, который будет:

- лучше языка С;

- поддерживать абстракцию данных;

- поддерживать объектно-ориентированное программирование.

С++ - язык общего назначения и задуман для того, чтобы настоящие программисты получили удовольствие от самого процесса программирования. За исключением второстепенных деталей он содержит язык С как подмножество. Язык С расширяется введением гибких и эффективных средств, предназначенных для построения новых типов. Программист структурирует свою задачу, определив новые типы, которые точно соответствуют понятиям предметной области задачи. Такой метод построения программы обычно называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. С такими объектами можно работать надежно и просто даже в тех случаях, когда их тип нельзя установить на стадии трансляции. Программирование с использованием таких объектов обычно называют объектно-ориентированным. Если этот метод применяется правильно, то программы становятся короче и понятнее, а сопровождение их упрощается.

Ключевым понятием С++ является класс. Класс - это определяемый пользователем тип. Классы обеспечивают упрятывание данных, их инициализацию, неявное преобразование пользовательских типов, динамическое задание типов, контролируемое пользователем управление памятью и средства для перегрузки операций. В языке С++ концепции контроля типов и модульного построения программ реализованы более полно, чем в С. Кроме того, С++ содержит усовершенствования, прямо с классами не связанные: символические константы, функции-подстановки, стандартные значения параметров функций, перегрузка имен функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены все возможности С эффективной работы с основными объектами, отражающими аппаратную "реальность" (разряды, байты, слова, адреса и т.д.). Это позволяет достаточно эффективно реализовывать пользовательские типы.

Объектно-ориентированное программирование - это метод программирования, способ написания "хороших" программ для множества задач. Если этот термин имеет какой-то смысл, то он должен подразумевать: такой язык программирования, который предоставляет хорошие возможности для объектно-ориентированного стиля программирования.

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

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

В 1998 году язык Си++ был стандартизован Международной организацией стандартизации под номером 14882:1998 -- Язык Программирования Си++. В настоящее время рабочая группа МОС работает над новой версией стандарта под кодовым названием C++09 (ранее известный как C++0X), который должен выйти в 2009 году.

Стандарт Си++ на 1998 год состоит из двух основных частей: ядра языка и стандартной библиотеки.

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

Стандарт Си++ содержит нормативную ссылку на стандарт Си от 1990 года и не определяет самостоятельно те функции стандартной библиотеки, которые заимствуются из стандартной библиотеки Си.

Кроме того, существует огромное количество библиотек Си++, не входящих в стандарт. В программах на Си++ можно использовать многие библиотеки Си.

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

РАЗДЕЛ 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 ПОСТАНОВКА ЗАДАЧИ И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

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

Алгоритм выполнения программы приведем в виде блок-схемы на рисунке1.

Рисунок1. Блок схема решения алгоритма задачи

Блок №1 «Главная форма» - форма, отображения при запуске программы.

Блок №2 «Выбор функции для исследования» производиться выбор функции.

Блок №3 «Нахождение точки минимума и значения функции» осуществляется расчет по введенным данным.

Блок №4 «Вывод min значения функции» выводится результат, содержащий значение функции, точки минимума и графическое представление.

2.2 ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА

Программный продукт реализован в среде С++ . Интерфейс программы реализован в виде окна, в котором расположено несколько объектов:

1. Поля для ввода начальных точек;

2. Поля для ввода дополнительных ограничений;

3. Поле для вывода конечного результата;

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

2.3. Инструкция пользователя

Для запуска программы выполните следующие действия: MinS.exe

После чего на экране запуститься главная форма программы (Рисунок 2)

Рисунок 2. «Главная форма»

На данной форме имеются поле выбора функции для исследования

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.

2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.

3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.

4. Банди Б. Методы оптимизации. Вводный курс / Б. Банди. - М.: Радио и связь, 1988.

5. Реклейтис Г. Оптимизация в технике: в 2 кн. / Г. Реклейтис, А. Рейвиндран. - М.: Мир, 1986.

Размещено на Allbest.ru

...