Задачи оптимизации и методы их решения. Обзор

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

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

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

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

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

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

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

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

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

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

В случае одного проектного параметра целевая функция (1.1) является функцией одной переменной, и се график - некоторая кривая на плоскости. При целевая функция является функцией двух переменных, и ее график — поверхность в трехмерном пространстве.

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

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

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

Можно выделить два типа задач оптимизации — безусловные и условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (1.1) при действительных переменных и определении соответствующих значений аргументов на некотором множестве σ n-мерного пространства. Обычно рассматриваются задачи минимизации; к ним легко сводятся и задачи на поиск максимума путем замены знака целевой функции на противоположный.

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

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

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

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

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

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

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

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

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

Будем рассматривать методы оптимизации для разных классов целевых функций. Простейшим из них является случай дифференцируемой функции F(х) на отрезке [а, b], причем функция задана в виде аналитической зависимости у = F(х), и может быть найдено явное выражение для ее производной ‚. Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления. Напомним вкратце этот путь.

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

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

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

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

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

(2.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

(2.2)

Из этого соотношения можно найти точку деления, вычислив отношения

Преобразуем, выражение (2.2) и найдем значения ,

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

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

(2.3)

Аналогично,

(2.4)

Начальная длина интервала неопределенности составляет . После первого шага оптимизации получается новый интервал неопределенности — отрезок . Его длина с учетом (2.4) равна

На втором шаге отрезок также делится в соотношении золотого сечения. При этом одной из точек деления будет точка . Покажем это:

Последнее равенство следует из соотношения

Вторая точка деления выбирается так же, как выбирается точка при деления отрезка , т. е. аналогично (2.3): . И снова интервал неопределенности уменьшается до размера

По аналогии с соотношениями (2.3), (2.4) можно записать координаты точек деления и отрезка на k-м шаге оптимизация :

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

(2.5)

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

(2.6)

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

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 кг.

5. Практическая часть.

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

Тип сырья

Нормы расхода сырья на одно изделие

Запасы сырья, кг

430

460

|||

420

Цена изделия

1. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 80 кг, а II вида уменьшить на 10 кг?

2. Целесообразно ли выпускать изделие Г ценой 7ед., если нормы затрат сырья составляют 2,4 и 3 кг?

3. Какой из видов изделий исключить, чтобы затраты были минимальными?

Задача: На предприятии выпускают 3 вида изделий, при этом расходуется 3 вида сырья.

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения

430

460

III

420

400

Цена

Переменные х

100

230

Ц.Ф.

1350

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения

510

435

450

III

420

Цена

Переменные х

105

225

Ц.Ф. 1

1335

Начальный вариант выгоднее

2. Целесообразно ли выпускать изделие Г ценой 7ед., если нормы затрат сырья составляют 2,4 и 3 кг?

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения, кг

430

460

III

420

400

Цена

Переменные х

0,00000

100

230

Ц.Ф. 2

1350

Нецелесообразно: целевая функция (прибыль) не увеличивается.

3. Какой из видов изделий исключить, чтобы затраты были минимальными?

1) Если исключить Г, то это - исходный вариант.

2) Если исключить В:

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения, кг

430

267,5

460

III

420

Цена

Переменные х

18,75

115

Ц.Ф. 3.2

842,5

3) Если исключить Б:

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения, кг

430

230

460

III

420

Цена

Переменные х

230

Ц.Ф. 3.2

1150

4) Если исключить А:

Три сырья

Нормы расхода на одно изделие

Запасы, кг

Ограничения, кг

430

460

III

420

400

Цена

Переменные х

100

230

Ц.Ф. 3.2

1350

Для того чтобы затраты были минимальными можно исключить изделие А и Г, так как их целевая функция равна одному и тому же числу, т.е. 1350.

Пояснения к задаче

Ц.Ф. - это целевая функция, по которой рассчитывается максимальная прибыль:

х1*(цена А)+х2*(цена Б)+...

х1, х2 ... - переменные, вводятся любые числа

Ограничения:

х1*Расход I А+...Запасы I

х1*Расход II А+...Запасы II

х1*Расход III А+...Запасы III

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

1. Л.И. Турчак, П.В. Плотников «Основы численных методов» М.-Физматлит. 2003г.

2. www.referats.ru

Задачи оптимизации и методы их решения. Обзор

Задачи оптимизации и методы их решения. Обзор

Введение

Похожие работы на - Задачи оптимизации и методы их решения. Обзор