Оптимизация

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

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

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

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

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

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

          Объект  исследования: процесс исследования задач оптимизационного моделирования.

    Предмет исследования: методы решения задач линейного программирования.

          Цель: освоить решения задач в Excel.

          Задачи: 

1. познакомиться с задачами оптимизации как разделом прикладной математики.
2. Освоить графический метод решения задач линейного программирования.
3. Освоить решения задач в Excel с использованием специального средства – поиск решения.
4. Разработать и оформить практические занятия для изучения.
5. Составить и оформить сборник задач.

    Линейное  программирование – это раздел методов  оптимизации. К числу задач линейного  программирования можно отнести  задачи:

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

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

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

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

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

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

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

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

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

    Рассмотрим  задачу и решим её графическим способом.

Задача 1:

    Предприятие электронной промышленности выпускает  две модели радиоприемников, причем каждая модель производится на отдельной  технологической линии. Суточный объем  первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

    Построение  математической модели:

    Переменные  задачи

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

      – суточный объем производства радиоприемников первой модели, [шт/сутки];

      – суточный объем производства радиоприемников второй модели, [шт/сутки];

    Целевая функция

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

• их объемы производства, т.е. и радиоприемников в сутки;
• прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

    Таким образом, доход от продажи суточного  объема производства радиоприемников  первой модели равен  $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

     [$/сутки]

    Ограничения

    Возможные объемы производства радиоприемников  и ограничиваются следующими условиями:

• количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;
• суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;
• объемы производства радиоприемников не могут быть отрицательными.

    Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

    1) расходом элементов электронных  схем;

    2) суточным объемом технологических  линий;

    3) неотрицательностью объемов производства.

    Запишем эти ограничения в математической форме:

1. Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

     [шт/сутки]

2. Ограничения по суточному объему первой и второй технологических линий имеют вид:

      [шт/сутки]

3. Неотрицательность объемов производства задается как

     .

    Таким образом, математическая модель этой задачи имеет вид

    

    

    Нахождение  оптимального решения  задачи с помощью  линейного метода.

       Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:

    

    

    Построим  прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).

    

    прямая (1) – точки (0;95) и (63,(3);0), прямая (2) проходит через точку  параллельно оси , прямая (3) проходит через точку параллельно оси .

    

    Рис.3.1. Графическое решение задачи о  производстве радиоприемников.

    Определим ОДР. Например, подставим точку (0;0) в  исходное ограничение (1), получим  , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

    Целевую прямую можно построить по уравнению:

    

    Точки пересечения с осями – (0;75) и (37,5;0)

    Строим  вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)