Многомерные задачи оптимизации

СОДЕРЖАНИЕ: Содержание: Содержание: 2 1. Основные понятия 3 1.1 Визначення. 3 1.2 Задачі оптимізації. 4 2.1 Задачи па экстремум. 5 2.3 Метод золотого сечения. 8 2.4 Метод Ньютона. 9

Содержание:

Введение. 3

1. Основные понятия. 4

1.1 Определения. 4

1.2 Задачи оптимизации. 5

2. Одномерная оптимизация. 6

2.1 Задачи па экстремум. 6

2.2 Методы поиска. 7

2.3 Метод золотого сечения. 8

2.4 Метод Ньютона. 11

3. Многомерные задачи оптимизации. 13

3.1 Минимум функции нескольких переменных. 13

3.2 Метод покоординатного спуска. 14

3.3 Метод градиентного спуска. 14

4. Задачи с ограничениями. 16

4.1 Линейное Программирование. 16

4.2 Геометрический метод. 17

4.3 Задача о ресурсах. 19

Список Литературы

1. Основные понятия

1.1 Визначення.

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

В процесі розв’язку задачі оптимізації,як звичай,необхідно знайти оптимальне значеннядеяких параметрів,які визначають дану задачу.При розвязку інженерних задачїх прийнято називати проектн ими параметрами , а в задачах економікиїх называютьпараметрами плана . В якості проектних параметрів можуть бути,зокрема,значення лінійних розмірів обєкта, маси, температурий інше число n проектних параметрів x₁ ,x₂ ,…,x_n які характеризують розмірність ( й степінь складності) задачі оптимізації.

Вибір оптимального рішення абопорівняння двох альтернативних розв’язків проводиться за допомогою деякої залежної величини (функції),обумовленої проектними параметрами.Ця велечина називаєтьсяцвілевою функцією (абокритерієм якості).В процесі розв’язку задачі оптимізації повинні бути знайдені такі значення проектних параметрів, при яких цілева функціямає мінімум (або максимум). Таким чином, ц ілева ф ункц ія – це глобальний критерій оптимальності в математичих моделях, за допомогою яких описуються инженерніабо экономичні задачі.

Цілеву функцію можно записатиу вигляді:

U=F(x₁ , x₂ ,…,x_n ). (1.1)

Прикладами цвілевої функції,які зустрічаються у інженерних та економічних розрахунках,є міцність й маса конструкції,потужність установки, обєм випуску продукції,вартість перевезеньвантажута шнше.

У випадку одного проектного параметра цілева функція (1.1) є функцією однієї змінної,аїї графік - деяка крива на площині.Прицілевафункціяє функцією двохзмінних, її графік — поверхня у тривимірному просторі.

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

Цілевих функцій може бути декілька.Наприклад,при проектуванні виробівмашино- будівництваодночасно потребується забезпечитимаксимальну надійність, мінімальну матеріалоємкість,максимальний корисний об’єм (або вантажопідємність).Деякі цілеві функціїможуть здатися несумісними.В таких випадкахнеобхідно вводитипріоритет тієї чи іншої цвілевої функції.

1.2 Задачі оптимізації.

Можно виділити два типи задач оптимізації — безумовні та умовні. Безу мовна задача оптимізаціїскладаєтьсяу відшуканні максимумуабо мінімумудійсної функції (1.1) при дійсних зміннихйвизначеннізначеньаргументів на деякіймножині n-мірногопростору. Звичайно розглядаютьсязадачі мінімізації, що до них легкозводятьсяі задачінапошукмаксимумушляхомзамінизнакацільовоїфункціїнапротилежний. Условные задачи оптимизации , или задачи с ограничениями, это такие, при формулировке которых задаются некоторые условия (ограничения) на множестве . Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих уравнениям или неравенствам.

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

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

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

2.1 Задачи па экстремум.

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

Методы поиска экстремума функции f (x ) (одномерной оптимизации)

К числу наиболее популярных численных методов одномерной оптимизации относятся: метод Больцано (деления интервала пополам), метод «золотого сечения» и пошаговый метод. Первые два метода ориентированы на поиск ext f (x ) внутри фиксированного интервала (а,b ) оси х , последний - на поиск ext f (x ) в окрестности заданной точки х₀ .

Метод Больцано при поиске минимума функции f (x ) предусматривает следующие действия:

1) определяется средняя точка интервала (а,b ): с = (a+b )/2;

2) выбирается число 0d (b-a )/2 (наиболее популярная рекомендация: d =(b-a )/4) и определяются точки: x₁ =c- d и x₂ =c+ d ;

3) вычисляются значения функции в этих точках: f (x₁ ) и f (x₂ );

4) если f (x₁ )f (x₂ ), то интервал (а,b ) стягивается в свою левую половину: b=c , в противном случае - в правую: а=с .

Для нового интервала (а,b ) вновь выполняются действия п.п. 1)-4). Процесс деления интервала продолжается до тех пор, пока его длина не станет меньше заданной точности: b-а e . При завершении процесса поиска за точку минимума f (x ) принимается середина последнего отрезка: x^* =(а+b )/2.

Достаточные условия сходимости алгоритма метода Больцано:

а) функция f (x ) непрерывна внутри интервала;

б) f (x ) унимодальна на интервале (а,b ), т.е. имеет внутри него единственный экстремум;

в) в некоторой окрестности искомой точки х* f (x ) является монотонной

(с одной стороны возрастает, с другой - убывает).

При тех же условиях сходится алгоритм метода «золотого сечения».

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

Следовательно, для отрезка единичной длины: 1/t = t /(1-t ) ®t² + t -1=0 ®

Пошаговый метод применяется в тех случаях, когда интервал (а,b ) оси х , содержащий точку экстремума функции f (x ) неизвестен, но известно, что экстремум находится в окрестности экспериментально найденной точки х₀ . Этот метод применяется на практике значительно чаще методов Больцано и «золотого сечения», т.к. условие сходимости его алгоритма намного проще: для этого достаточно, чтобы функция f (x ) была непрерывна в окрестности т. х₀ .

При поиске минимума функции метод заключается в

следующем:

1) выполняется пробный шаг от точки х₀ с целью выбора направления поиска:

x = x₀ + x (x ~ 0.5e ) и вычисляются значения f (х₀ ), f (х );

2) если f (х ) f (х₀ ), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h 0), в противном случае - отрицательна (h 0);

3) движение в выбранном направлении с шагом h : x_k+1 = x_k +h , k =0,1,2 ...

осуществляется до тех пор, пока f (x_k+1 ) f (x_k );

4) если f (x_k+1 ) f (x_k ), то при выполнении условия h процесс поиска заканчивается, а если h , то шаг дробится: h =|h |/p , p 1 и осуществляется возврат

к п. 1) с начальной точкой х₀ = x_k .

В качестве коэффициента дробления шага p используют 2, 3, 5, но чаще всего p = e = 2.71828. По завершении процесса поиска за точку экстремума принимается значение x* =(x_k+1 + x_k )/2.

2.2 Методы поиска.

Численные методы поиска экстремальных значений функции рассмотрим на примере нахождения минимума функции на отрезке [а., b]. Будем предполагать, что целевая функция унимодальна , т.е. на данном отрезке она имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции.

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

(2.1)

Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения проектного параметра, называемого интервалом неопределенности . В начале процесса оптимизации его длина равна , а к концу она должна стать меньше , т. е. оптимальное значение проектного параметра должно находиться в интервале неопределенности – на отрезке , причем . Тогда для выполнения (2.1) в качестве приближения к оптимальному значению можно принять любое .

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

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

т. е. с увеличением числа точек разбиения погрешность минимума стремится к нулю.

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

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

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

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

2.3 Метод золотого сечения.

Метод золотого сечения состоит в построении последовательности отрезков [ a₀ , b₀ ], [a₁ , b₁ ], …,стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление значения функции f(x) проводится лишь один раз. Эта точка, называемая золотым сечением, выбирается специальным образом.

На первом шаге процесса оптимизации внутри отрезка [a₀ , b₀ ] выбираем две внутренние точки x₁ и x₂ и вычисляем значения целевой функции f(x₁ ) и f(x₂ ). Поскольку в данном случае f(x₁ ) f(x₂ ), очевидно, что минимум расположен на одном из прилегающих к x₁ отрезков [a₀ , x₁ ] или [x₁ , x₂ ]. Поэтому отрезок [x₂ , b₀ ] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [a_1, b₁ ], где a₁ = a₀ , b₁ = x₂ . Нужно снова выбрать две внутренние точки, но одна из них (x₁ ) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку x₃ , вычислить значение f(x₃ ) и провести сравнение. Поскольку здесь f(x₃ ) f(x₁ ), ясно, что минимум находится на отрезке [x₃ , b₁ ]. Обозначим этот отрезок [a₂ , b₂ ], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [a_n , b_n ] не станет меньше заданной величины .

Теперь рассмотрим способ размещения внутренних точек на каждом от резке [a_k , b_k ]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l₁ , l₂ : l₁ l₂ , l = l₁ + l₂ . Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезк к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка: (1)

Из этого соотношения можно найти точку деления, определив отношение l₂ /l₁ . Преобразуем выражение (1), и найдем это значение:

l=l₂ l₁ , l=l₂ (l₁ + l₂ ),

l+l₁ l₂ - l=0,

² + - 1 =0,

=.

Поскольку нас интересует только положительное решение, то

.

Отсюда l₁ k₁ l, l₂ k₂ l.

Поскольку заранее неизвестно, в какой последовательности делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления. Точки деления x₁ и x₂ выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

x₁ – a₀ = b₀ – x₂ = k₂ d₀ ,

b₀ - x₁ = x₂ – a₀ = k₁ d₀ ,

d₀ = b₀ – a₀ .

После первого шага оптимизации получается новый интервал неопределенности – отрезок [a_1, b₁ ].

Можно показать, что точка x₁ делит этот отрезок в требуемом отношении, при этом

b₁ – x₁ = k₂ d₁ , d₁ = b₁ – a₁ .

Для этого проведем очевидные преобразования:

b₁ – x₁ = x₂ – x₁ = (b₀ – a₀ ) – (x₁ – a₀ ) – (b₀ – x₂ ) = d₀ – k₂ d₀ - k₂ d₀ = k₃ d₀ ,

d₁ = x₂ – a₀ = k₁ d₀ ,

b₁ – x₁ = k₃ (d₁ /k₁ ) = k₂ d₁ .

Вторая точка деления x₃ выбирается на таком же расстоянии от левой границы отрезка, т.е. x₃ – a₁ = k₂ d₁ .

И снова интервал неопределенности уменьшается до размера

d₂ = b₂ – a₂ = b₁ – x₃ = k₁ d₁ = kd₀ .

Используя полученные соотношения, можно записать координаты точек деления y и z отрезка [a_k , b_k ] на k +1 шаге оптимизации (y z):

y = k₁ a_k + k₂ b_k ,

z = k₂ a_k + k₁ b_k .

При этом длина интервала неопределенности равна

d_k = b_k – a_k = kd₀ .

Процесс оптимизации заканчивается при выполнении условия d_k . При этом проектный параметр оптимизации составляет a_k x b_k . Можно в качестве оптимального значения принять x = a_k (или x = b_k , или x = (a_k + b_k )/2 и т.п.).

2.4 Метод Ньютона.

Как было отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции сводится к нахождению критических точек этой функции, определяемых уравнением: (2.7)

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

Пусть - решение уравнения (2.7), а некоторое начальное приближение к . Применим для решения (2.7) метод Ньютона решения уравнения , которое эквивалентно уравнению (2.7) при . Для этого в формулу для -го приближения метода Ньютона подставим вместо производную и получим тем самым формулу для -го приближения к решению уравнения (2.7):

(2.8)

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

или близости значений целевой функции на этих приближениях

.

Достаточное условие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующая теорема.

Теорема. Пусть - корень уравнения (2.7), т.е. , а и непрерывна. Тогда существуют окрестность корня такая, что если начальное приближение принадлежит этой окрестности, то для метода Ньютона (2.8) последовательность значений сходится к при .

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

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

(2.9)

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

что совпадает с (2.8). Разложение (2.9) в окрестности точки , на котором график функции заменяется параболой графиком функции .

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

3. Многомерные задачи оптимизации

3.1 Минимум функции нескольких переменных.

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

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

(3.1)

Рассмотренный метод можно использовать лишь для дифференцируемой целевой функции. Но и в этом случае могут возникнуть серьезные трудности при решении систем нелинейных уравнений (3.1).

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

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

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

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

3.2 Метод покоординатного спуска.

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

(3.2)

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

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

На любом k-том шаге этот процесс можно прервать. И значение функции в точке kпринимается в качестве наименьшего значения целевой функции в рассматриваемой области.

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

3.3 Метод градиентного спуска.

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

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

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

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

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

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

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

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

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

4. Задачи с ограничениями

4.1 Линейное Программирование.

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

Стандартная (каноническая) постановка задачи линейного программирования формулируется следующим образом: найти значения переменных, которые

1) удовлетворяют системе линейных уравнений

(4.1)

2) являются неотрицательными, т. е.

(4.2)

3) обеспечивают наименьшее значение линейной целевой функции

(4.3)

Всякое решение системы уравнений (4.1), удовлетворяющее системе неравенств (4.2), называется допустимым решением . Допустимое решение, которое минимизирует целевую функцию (4.3), называется оптимальным решением .

4.2 Геометрический метод.

Областью решения линейного неравенства с двумя переменными

(4.4)

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

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

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

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

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

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

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

(4.5)

При параллельном переносе этой прямой в положительном направлении вектора нормали линейная функция будет возрастать, а при переносе прямой в противоположном направлении — убывать.

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

Поскольку

Если вектор сонаправлен с вектором , то и , а если направлен противоположно, то .

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

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

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

4.3 Задача о ресурсах.

В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м² стекла, 160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовить два наименования изделий: А и Б. Цена одного изделия А -1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м² стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1,2 тыс. для его изготовления необходимо 5 кг металла, 1 м² стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.

Сначала сформулируем задачу математически. Обозначим через и количество изделий А и Б, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени зададим в виде ограничений-неравенств:

(4.6)

Полная стоимость запланированной к производству продукции выражается формулой

(4.7)

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

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

(4.8)

При этом очевидно, что . Заметим, что введение дополнительных неизвестных не повлияло на вид целевой функции (4.7), которая зависит только от параметров . Фактически будут указывать остатки ресурсов, не использованные в производстве. Здесь мы имеем задачу максимизации, т. е. нахождения максимума целевой функции. Если функцию (4.7) взять со знаком минус и принять целевую функцию в виде

(4.9)

то получим задачу минимизации для этой целевой функции.

Примем переменные в качестве базисных и выразим их через свободные переменные из уравнений (4.8). Получим

(4.10)

В качестве опорного решения возьмем такое, которое соответствует пулевым значениям свободных параметров:

Этому решению соответствует нулевое значение целевой функции (4.9):

(4.11)

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

Положим и будем увеличивать переменную до тех пор, пока базисные переменные остаются положительными. Из (4.10) следует, что можно увеличить до значения , поскольку при большем его значении переменная станет отрицательной (отношение 100/(-2) является наименьшим по модулю среди отношений 300/(-4),100/(-2),160/(-2)).

Таким образом, полагая , , получаем новое опорное решение (значения переменных найдем по формулам (4.10)):

(4.12)

Значение целевой функции (4.9) при этом будет равно

(4.13)

Новое решение (4.12), следовательно, лучше, поскольку значение целевой функции уменьшилось по сравнению с (4.11).

Следующий шаг начнем с выбора нового базиса. Примем ненулевые переменные в (4.12) в качестве базисных, а нулевые переменные в качестве свободных. Из системы (4.8) найдем

(4.14)

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

(4.15)

Отсюда следует, что значение целевой функции по сравнению с (4.13) можно уменьшить за счет увеличения поскольку коэффициент при этой переменной в (4.15) отрицательный. При этом увеличение недопустимо, поскольку это привело бы к возрастанию целевой функции; поэтому положим .

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

(4.16)

При этом значение целевой функции (4.15) равно

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

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

Таким образом, ответ на поставленную задачу об использовании ресурсов следующий: для получения максимальной суммарной стоимости продукции при заданных ресурсах необходимо запланировать изготовление изделий А в количестве 35 штук и изделий Б в количестве 30 штук. Суммарная стоимость продукции равна 71 тыс, р. При этом все ресурсы стекла и рабочего времени будут использованы, а металла останется 10 кг.

Скачать архив с текстом документа