Задачи оптимизации и методы их решения. Обзор
| Загрузить архив: | |
| Файл: ref-26211.zip (140kb [zip], Скачиваний: 362) скачать |
Введение. PAGEREF _Toc154915412 h 3
3. Многомерные задачи оптимизации. 13
3.1 Минимум функции нескольких переменных. 13
3.2 Метод покоординатного спуска. 14
3.3 Метод градиентного спуска. 14
4.1 Линейное Программирование. 16
Введение
Эта курсовая работа описывает задачи оптимизации и методы их решения необходимые для тех или иных видов деятельности, в частности в производстве.
Оптимизацией называют процесс выбора наилучшего варианта из всех возможных. В производстве необходимо знать какой из видов продукции наиболее оптимален для выпуска, и который принесет больше прибыли. В маркетинге тоже используется методы оптимизации.
Маркетинг – это комплексная система организации производства и сбыта товаров и услуг основанное на предвидении и удовлетворении спроса потребителей. В маркетинге необходимо изучать потребность покупателей в том или ином товаре, передача о потребностях на предприятие и производство наиболее выгодных товаров.
1. Основные понятия
1.1 Определения.
Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных. С точки зрения инженерных расчетов методы оптимизации позволяют выбрать наилучший вариант конструкции, наилучшее распределение ресурсов и т.д.
В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную задачу. При решении инженерных задач их принято называть проектными параметрами, а в экономических задачах их обычно называют параметрами плана. В качестве проектных параметров могут быть, в частности, значения линейных размеров объекта, массы, температуры и т.п. число n проектных параметров x1,x2,…,xn характеризует размерность ( и степень сложности) задачи оптимизации.
Выбор оптимального решения или сравнение двух альтернативных решений проводится с помощью некоторой зависимой величины (функции), определяемой проектными параметрами. Эта величина называется целевой функцией (или критерием качества). В процессе решения задачи оптимизации должны быть найдены такие значения проектных параметров, при которых целевая функция имеет минимум (или максимум). Таким образом, целевая функция – это глобальный критерий оптимальности в математических моделях, с помощью которых описываются инженерные или экономические задачи.
Целевую функцию можно записать в виде
U=F(x1, x2,…,xn). (1.1)
Примерами целевой функции, встречающимися в инженерных и экономических расчетах, являются прочность и масса конструкции, мощность установки, объем выпуска продукции, стоимость перевозок груза и т.п.
В случае одного
проектного параметра 
целевая функция (1.1)
является функцией одной переменной, и се график - некоторая кривая на
плоскости. При 
целевая функция
является функцией двух переменных, и ее график — поверхность в трехмерном
пространстве.
Следует отметить, что целевая функция не всегда может быть представлена в виде формулы. Иногда она может принимать только некоторые значения, задаваться в виде таблицы и т. п. Во всех случаях она должна быть однозначной функцией проектных параметров.
Целевых функций может быть несколько. Например, при проектировании изделий машиностроения одновременно требуется обеспечить, максимальную надежность, минимальную материалоемкость, максимальный полезный объем (или грузоподъемность). Некоторые целевые функции могут оказаться несовместимыми. В таких случаях необходимо вводить приоритет той или иной целевой функции.
1.2 Задачи оптимизации.
Можно выделить два типа задач оптимизации — безусловные и условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (1.1) при действительных переменных и определении соответствующих значений аргументов на некотором множестве σ n-мерного пространства. Обычно рассматриваются задачи минимизации; к ним легко сводятся и задачи на поиск максимума путем замены знака целевой функции на противоположный.
Условные задачи оптимизации, или задачи с
ограничениями, это такие, при формулировке которых задаются некоторые условия
(ограничения) на множестве 
Ограничения-равенства выражают зависимость между, проектными параметрами, которая должна учитываться при нахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т. п.
в результате ограничений
область проектирования , определяемая всеми проектными параметрами,
может быть существенно уменьшена в соответствии с физической сущностью задачи.
При наличие ограничений оптимальное решение может соответствовать либо локальному экстремуму в нутрии области проектирования, либо значению целевой функции на границе области. Если ограничения отсутствуют то ищется оптимальное решение на всей области проектирования, то есть глобальный экстремум.
2. Одномерная оптимизация
2.1 Задачи па экстремум.
Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=х, заданной на множестве σ, и определить значение проектного параметра х Є σ, при котором целевая функция принимает экстремальное значение. Существование решения поставленной задачи вытекает из следующей теоремы.
Теорема Вейерштрасса. Всякая функция F(х), непрерывная на отрезке [а, b], принимает на этом отрезке наименьшее и наибольшее значения, т.е. на отрезке [а, b] существуют такие точки х1 в х2, что для любого х Є [а, b] имеют место неравенства
Эта теорема не доказывает единственности решения. Не исключена возможность достижения равных экстремальных значений сразу в нескольких точках данного отрезка. В частности, такая ситуация имеет место для периодической функции, рассматриваемой на отрезке, содержащем несколько периодов.
Будем
рассматривать методы оптимизации для разных классов целевых функций. Простейшим
из них является случай дифференцируемой функции F(х) на отрезке [а, b], причем функция задана в виде аналитической
зависимости у = F(х), и
может быть найдено явное выражение для ее производной ‚
экстремумов таких функций можно проводить
известными из курса высшей математики методами дифференциального исчисления. Напомним
вкратце этот путь.
Функция
‚
может достигать своего
наименьшего и наибольшего значений либо в граничных точках отрезка [а, b], либо в точках минимума и максимума.
Последние точки обязательно должны быть критическими, т. е. производная в этих точках
обращается в нуль, — это необходимое условие экстремума. Следовательно, для
определения наименьшего или наибольшего значений функции ‚ на отрезке [а, b] нужно вычислить ее
значения во всех критических точках данного отрезка и в его граничных точках и
сравнить полученные значения; наименьшее или наибольшее из них и будет искомым
значением.
Случай, когда целевая функция задана в табличном виде или может быть вычислена при некоторых дискретных значениях аргумента, используются различные методы поиска. Они основаны на вычислении целевой функции в отдельных точках и выборе среди них наибольшего или наименьшего значений. Существует ряд алгоритмов решения данной задачи. Рассмотрим некоторые из них.
2.2 Методы поиска.
Численные
методы поиска экстремальных значений функции рассмотрим на примере нахождения
минимума функции на отрезке [а., b]. Будем предполагать, что
целевая функция унимодальна, т.е. на
данном отрезке она имеет только один минимум. Отметим, что в инженерной
практике обычно встречаются именно такие целевые функции.
Погрешность приближенного решения задачи определяется разностью между оптимальным значением x проектного параметра и приближение к нему х. Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения а:
(2.1)
Процесс
решения задачи методом поиска состоит в последовательном сужении интервала
изменения проектного параметра, называемого интервалом
неопределенности. В начале процесса оптимизации его длина равна 
Наиболее
простым способом сужения интервала является деление его на некоторое число равных
частей с последующим вычислением значений целевой функции в точках разбиения. Пусть
- число элементарных отрезков, 
- шаг разбиения. Вычислим
значения целевой функции 
в узлах 
Число 
на отрезке 
зависит от числа
точек, и для непрерывной функции
т. е. с увеличением числа точек разбиения погрешность минимума стремится к нулю.
В
данном методе, который можно назвать методом перебора, главная трудность
состоит в выборе 
и оценке погрешности. Можно,
например, провести оптимизацию с разными шагами и исследовать сходимость такого
итерационного процесса. Но это трудоемкий путь.
Более
экономичным способом уточнения оптимального параметра является использование
свойства унимодальности целевой функции, это позволяет построить процесс сужения
интервала неопределенности. Пусть, как и ранее, среди всех значений
унимодальной функции 
то его снова можно уменьшить путем нового разбиения. Получится интервал, равный двум длинам нового шага разбиения и т. д. Процесс оптимизации продолжается до достижения заданного размера интервала неопределенности.
Существует ряд специальных методов поиска оптимальных решений разными способами выбора узлов и сужения интервала неопределенности - метод деления отрезка пополам, метод золотого сечения и др. Рассмотрим один из них.
2.3 Метод золотого сечения.
При
построении процесса оптимизации стараются сократить объем вычислений и время
поиска. Этого достигают обычно путем сокращения количества вычислений (или
измерений — при проведении эксперимента) значений целевой функции достигается наилучшая
точность, является метод золотого сечения.
Он состоит в построении последовательности отрезков 
проводится лишь в
одной точке. Эта точка, называемая золотым
сечением, выбирается специальным образом.
Поясним
сначала идею метода геометрически, а затем выведем необходимые соотношения. Па
первом шаге процесса оптимизации внутри отрезка выбираем некоторые
внутренние точки 
и 
и
отрезков: 
или 
можно отбросить, сузив
тем самым первоначальный интервал неопределенности.
Второй
шаг проводим на отрезке
осталась из
предыдущего шага, поэтому достаточно выбрать лишь одну точку 
и провести сравнение.
Поскольку здесь 
не станет меньше
заданной величины
Теперь
рассмотрим способ размещения внутренних точек на каждом отрезке l, а точка деления разбивает
его на части 
(2.2)
Из этого соотношения можно найти точку деления, вычислив отношения
Преобразуем,
выражение (2.2) и найдем значения 
Поскольку пас интересует только положительное решение, то
Очевидно,
что интервал неопределенности можно разделить в соотношении золотого сечения
двояко: в пропорциях 
и 
и выбираются с учетом
этих пропорций. В данном случае имеем
(2.3)
Аналогично,
(2.4)
Начальная
длина интервала неопределенности составляет 
На втором шаге отрезок 
также делится в
соотношении золотого сечения. При этом одной из точек деления будет точка
Последнее
равенство следует из соотношения 
Вторая
точка деления выбирается так же, как
выбирается точка при деления отрезка 
По
аналогии с соотношениями (2.3), (2.4) можно записать координаты точек деления 
и 
на k-м шаге оптимизация 
Вычислению,
естественно, подлежит только одна из координат 
(2.5)
Как я в
общем случае метода поиска, процесс оптимизации заканчивается при выполнении
условия 
или 
(2.6)
Метод золотого сечения (как и, например, метод решения нелинейных уравнений делением отрезка пополам) относится к тем немногим численным методам, для которых можно гарантировать, что требуемая точность достигнута.
2.4 Метод Ньютона.
Как
было отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции сводится к нахождению
критических точек этой функции, определяемых уравнением
(2.7)
Когда уравнение (2.7) нельзя решить аналитически, для его решения можно применить численные методы, например метод Ньютона. В этом случае говорят о методе Ньютона решения задачи оптимизации.
Пусть 
- решение уравнения
(2.7), а 
некоторое начальное
приближение к 
подставим вместо производную и получим тем самым формулу
для
(2.8)
для использования этой
формулы необходимо, чтобы 
качестве критерия
окончания итерационного процесса можно применить условия близости двух
последовательных приближений
или близости значений целевой функции на этих приближениях
Достаточное условие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующая теорема.
Теорема. Пусть 
и
непрерывна. Тогда
существуют окрестность корня 
такая, что если
начальное приближение принадлежит этой
окрестности, то для метода Ньютона (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.3 Задача о ресурсах.
В
распоряжении бригады имеются следующие ресурсы:
Сначала
сформулируем задачу математически. Обозначим через и количество изделий А и
Б, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсы
сырья и рабочего времени зададим в виде
ограничений-неравенств:
(4.6)
Полная стоимость запланированной к производству продукции выражается формулой
(4.7)
Таким
образом, мы имеем задачу линейного программирования, которая состоит в
определении оптимальных значений проектных параметров 
являющихся целыми
неотрицательными числами, удовлетворяющих линейным неравенствам (4.6) и дающих
максимальное значение линейной целевой функции (4.7).
Вид сформулированной
задачи не является каноническим, поскольку условия (4.6) имеют вид неравенств,
а не уравнений. Как уже отмечалось выше, такая задача может быть сведена к
канонической путем введения дополнительных переменных 
по количеству
ограничений- неравенств (4.6). При этом выбирают эти переменные такими, чтобы
при их прибавлении к левым частям соотношений (4.6) неравенства превращались в
равенства. Тогда ограничения примут вид
(4.8)
При этом очевидно, что 
будут указывать остатки
ресурсов, не использованные в производстве. Здесь мы имеем задачу максимизации,
т. е. нахождения максимума целевой функции. Если функцию (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 тыс, р. При этом
все ресурсы стекла и рабочего времени будут использованы, а металла останется
5. Практическая часть.
Задача: на предприятии выпускается три вида изделий, используется при этом три вида сырья.
|
Тип сырья |
Нормы расхода сырья на одно изделие |
Запасы сырья, кг |
||
|
А |
Б |
С |
||
|
| |
1 |
2 |
1 |
430 |
|
|| |
3 |
0 |
2 |
460 |
|
||| |
1 |
4 |
0 |
420 |
|
Цена изделия |
3 |
2 |
5 |
1.
I вида увеличить на
2.
3. Какой из видов изделий исключить, чтобы затраты были минимальными?
Задача: На предприятии выпускают 3 вида изделий, при этом расходуется 3 вида сырья.
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения |
||
|
А |
Б |
В |
|||
|
I |
1 |
2 |
1 |
430 |
430 |
|
II |
3 |
0 |
2 |
460 |
460 |
|
III |
1 |
4 |
0 |
420 |
400 |
|
Цена |
3 |
2 |
5 |
||
|
Переменные х |
1 |
2 |
3 |
||
|
0 |
100 |
230 |
|||
|
Ц.Ф. |
1350 |
1. Как изменится общая стоимость выпускаемой
продукции и план ее выпуска, если запас сырья I вида увеличить
на
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения |
||
|
А |
Б |
В |
|||
|
I |
1 |
2 |
1 |
510 |
435 |
|
II |
3 |
0 |
2 |
450 |
450 |
|
III |
1 |
4 |
0 |
420 |
420 |
|
Цена |
3 |
2 |
5 |
||
|
Переменные х |
1 |
2 |
3 |
||
|
0 |
105 |
225 |
|||
|
Ц.Ф. 1 |
1335 |
Начальный вариант выгоднее
2. Целесообразно ли выпускать изделие Г ценой
7ед., если нормы затрат сырья составляют 2,4 и
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения, кг |
|||
|
А |
Б |
В |
Г |
|||
|
I |
1 |
2 |
1 |
2 |
430 |
430 |
|
II |
3 |
0 |
2 |
4 |
460 |
460 |
|
III |
1 |
4 |
0 |
3 |
420 |
400 |
|
Цена |
3 |
2 |
5 |
7 |
||
|
Переменные х |
1 |
2 |
3 |
4 |
||
|
0,00000 |
100 |
230 |
0 |
|||
|
Ц.Ф. 2 |
1350 |
Нецелесообразно: целевая функция (прибыль) не увеличивается.
3. Какой из видов изделий исключить, чтобы затраты были минимальными?
1) Если исключить Г, то это - исходный вариант.
2) Если исключить В:
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения, кг |
||
|
А |
Б |
Г |
|||
|
I |
1 |
2 |
2 |
430 |
267,5 |
|
II |
3 |
0 |
4 |
460 |
460 |
|
III |
1 |
4 |
3 |
420 |
420 |
|
Цена |
3 |
2 |
7 |
||
|
Переменные х |
1 |
2 |
3 |
||
|
0 |
18,75 |
115 |
|||
|
Ц.Ф. 3.2 |
842,5 |
3) Если исключить Б:
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения, кг |
||
|
А |
В |
Г |
|||
|
I |
1 |
1 |
2 |
430 |
230 |
|
II |
3 |
2 |
4 |
460 |
460 |
|
III |
1 |
0 |
3 |
420 |
0 |
|
Цена |
3 |
5 |
7 |
||
|
Переменные х |
1 |
2 |
3 |
||
|
0 |
230 |
0 |
|||
|
Ц.Ф. 3.2 |
1150 |
4) Если исключить А:
|
Три сырья |
Нормы расхода на одно изделие |
Запасы, кг |
Ограничения, кг |
||
|
Б |
В |
Г |
|||
|
I |
2 |
1 |
2 |
430 |
430 |
|
II |
0 |
2 |
4 |
460 |
460 |
|
III |
4 |
0 |
3 |
420 |
400 |
|
Цена |
2 |
5 |
7 |
||
|
Переменные х |
1 |
2 |
3 |
||
|
100 |
230 |
0 |
|||
|
Ц.Ф. 3.2 |
1350 |
Для того чтобы затраты были минимальными можно исключить изделие А и Г, так как их целевая функция равна одному и тому же числу, т.е. 1350.
Пояснения к задаче
Ц.Ф. - это целевая функция, по которой рассчитывается максимальная прибыль:
х1*(цена А)+х2*(цена Б)+...
х1, х2 ... - переменные, вводятся любые числа
Ограничения:
х1*Расход I А+...
х1*Расход II А+...
х1*Расход III А+...
Список литературы.
1.
2.