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

ОБЛАСТНАЯ НАУЧНО_ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ

 «В мир поиска, в мир творчества, в мир науки»»

Муниципальное бюджетное общеобразовательное учреждение

 «Средняя общеобразовательная школа № 2»

Исследовательская работа

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

Автор:  Кучков Кирилл, МБОУ СОШ №2, класс 9

Руководитель работы: Топчиева Ольга Николаевна, учитель математики

Колпашево  2012

Оглавление

1.Введение

 2. Решение задач

 3.Заключение

 4.Литература

Введение

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

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

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

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

      Цель:

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

Задача моей работы заключается в следующем:

1. Изучить данный тип задач
2. Научиться решать такие задачи геометрическим способом
3. Научиться разрабатывать электронные таблицы для решения таких задач.

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

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

Также сейчас в заданиях Единого Государственного Экзамена встречаются задачи на нахождение наименьшего и набольшего значений, которые легко решаются данным способом. И в своей работе я представлю решения некоторых подобных задач.

Задача №1.

Мастерская выпускает трансформаторы  2-х видов. В таблице №1 приведены: прибыль от реализации и количество необходимого сырья, для каждого трансформатора.

Таблица №1.

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

Пусть x,y – число трансформаторов первого и второго типа соответственно:

Геометрический способ решения.

Тогда 120x – прибыль от реализации трансформаторов первого вида, 100y - прибыль от реализации трансформаторов второго вида. Общая прибыль задается функцией F=120x+100y. Построим математическую модель:

прибыль от реализации трансформаторов первого вида

Построим графики:

Эта система определяет 4-х угольник OABC на плоскости.

Решим систему:

Это координаты вершины B. Остальные вершины O(0;0) ; A(96;0) ; C(0;150).

Вычислоим  значение функции F=120x+100y в этих точках.

F(O)=0;

F(a)=120*96=11520;

F(B)= 120*60+100*60=13200;

F(C)=100*150=15000;

Следовательно для получения наибольшей прибыли нужно выпустить 150 трансформаторов 2 вида.

Решение этой задачи в среде MS Exel.

 Решение

Доделать

Задача№2.

Для изготовления нужно вырезать из фонеры 1 заготовку для заднее стенки (детальА) две заготовки для боковинок (деталь Б) и 3 одинаковвых заготовок для верхней средней и нижней горизонтальных панелей (деталь В). Имеющиеся ина мебельном комбинате листы фанеры таковы, что при первом способе раскроя и- одного листа можно изготовит 1 деталь типа А 4 типа Б и 8 типа В. А при раскрое 2 способом 3 детали типа А 2 детали типа Б и 2 типа В. Можно ли имея 180 листов фанеры изготовить 200 полок? Ак осуществитьт раскрой материали, что бы было испольховано наименьшее число оистов фанеры.

Пусть x илстов необходимр для первого типа раскроя и y листов для 2 типа раскроя.

 Решение: геометрическом способом.

 Число фанеры задается выражением x+y < 180, а функции F=x+y.

Построим математическую модель:

Построим график.  Достроить 

Система определяется на плоскости 4х угольник ABCD. Найдем координаты вершин

A (80;40) B(50;100) c(40;140) D(170; 10) Вычислим значения функции в вершинах четырехугольника.

F(A) = 80+40=120

F(B)= 50+100+150

F(C)= 40+140=180

F(D)=170+10=180

Следовательно наименьшее число фанеры для изготовления 200 полок = 120, приэтом нужно 80 листов раскроить перым свпособом и 40 вторым.

Решение этой задачи в среде MS Exel.

Задача  №3.

Пусть в колхозе требуется распределить площадь пашни между двумя культурами в соответствии со следующими данными

Кроме того заданы ресурсы производства – земли – 1800 га. Человеко-дней – 8000.

Велечены x,y – неизвестные и подлежат определению.

Решение Геометрическом способом.

Построим математическую модель.

Построим график . 

Эта система определяется треугольником ABC решим систему

Следовательно, распределить площадь пашни между двумя культурами в соответствии с данными следует так 1250 культуре №1 и 550 культуре №2.

Решение этой задачи в среде MS Exel.

Задача на поиск оптимального планирования ресурсов предприятия.

Постановка задачи

Некоторое предприятие производит продукцию 5 видов, используя комплектующие детали 7 наименований А, В, С, D, E, F, G. запасы предприятия ограничены некоторым количеством комплектующих деталей. Известно, сколько требуется комплектующих деталей для производства единицы продукции каждого вида и прибыль от производства единицы продукции каждого вида. Определить, сколько требуется произвести продукции каждого вида, чтобы обеспечить предприятию наибольшую прибыль.

Данные по производству приведены в таблице.

Данные по производству продукции

Математическая модель рассматриваемой задачи:

При решении поставленной задачи с помощью надстройки «Поиск решения» необходимо предварительно ввести на рабочий лист электронных таблиц Excel известные исходные данные

Рис 1. Фрагмент рабочего листа Excel

Ячейки А1:А7, А9:А16 исходной области используются для хранения текста иллюстративно поясняющего характера. Блок ячеек В2:В6  искомые значения видов продукции.

 Ячейка В7 отводится для записи формулы, определяющая целевую функцию и ее максимальное значение (прибыль): =2*В2+3*В3+В4+5*В5+4*В6

Блок ячеек В10:В16  отводится для записи формул, определяющих ограничения по каждому комплектующему:

Для А ячейка В10 содержит формулу: =2*В2+2*В3+В6;

Для В ячейка В11 содержит формулу: =В2+2*В3+В5;

Для С ячейка В12 содержит формулу: =4*В2+В4;

Для D ячейка В13 содержит формулу: =4*В5;

Для Е ячейка В14 содержит формулу: =В4+2*В5+В6;

Для F ячейка В15 содержит формулу: =2*B2+B5;

Для G ячейка В16 содержит формулу: =2*B2+B5.

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

Для задания параметров поиска решения необходимо вызвать диалоговое окно Поиск решения с помощью команды Сервис, Поиск решения.

Моделирование задачи оптимального управления

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

Координаты населенных пунктов приведены в табл. 1.

Таблица 1

Решение.

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

Для решения задачи введем обозначения (табл. 2).

Таблица 2

Минимальное расстояние от железнодорожной станции до i-го населенного пункта (i = 1, …, 5) через аэропорт можно определить следующим образом:

Задачу решаем, используя приложение Microsoft Excel и надстройку «Поиск решения».

Для моделирования необходимо подготовить таблицу в Excel:

1. Введите необходимые заголовки, исходные значения координат населенных пунктов (рис. 1.)

Рис. 1.

2. В соответствующие ячейки Табл. 3) введите расчетные формулы.

Таблица 3

Компьютерное моделирование

Эксперимент № 1.

1. Применяя надстройку Excel «Поиск решения» (меню Сервис, Поиск решения), назначьте в качестве целевой ячейки В16 и установите переключатель Равной: равным минимальному значению. Укажите в качестве изменяемых ячеек ячейки $B$12:$C$12; $B$14:$C$14 (координаты аэродрома и станции).
2. Ограничения не вводите.
3. Щелкните по кнопке Выполнить.
4. Постройте диаграмму, выберите тип Точечная.
5. Проанализируйте результат.

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

Эксперимент № 2.

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

Таблица 4

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

3. Произведите  поиск решения.

Фрагмент рабочего листа (после ввода ограничений)

Некоторые задачи оптимизации.

1  Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

2. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м2(включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

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

4. В обработку поступила партия из 150 досок длиной по 7,5м каждая,для изготовления комплектов из 4 деталей. Комплект состоит из:

1.  1 детали длиной 3м.
2. 2 деталей длиной 2м.
3.  1 детали длиной 1,5м

5.Как распилить все доски. Получив наибольшее возможное число комплектов?

6.Окно имеет форму прямоугольника, завершенного полукругом. Периметр фигуры равен 6м. Каковы должны быть размеры окна, чтобы окно пропускало наибольшее количество света.

Заключение.

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

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

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

Литература.

1. Басова Л.Л Михайлова Н.И.Практикум по информатика и информационные технологии. М: Лаборатория Базовых Знаний.2002.
2. Башмаков М.И. Алгебра и начала анализа 10-11.: Просвещение,1992.
3. Гнеденко Б. В. Математика в современном мире .М: Просвещение, 1980
4. Семакин И.Г., Хенкер Е.К. Задачник-практикум 2 информатика М: Лаборатория Базовых Знаний.2000.
5.  Смирнов И.М.,  В. А. Смирнов, Геометрия 7-9 М:Мнемозина 2009
6. Попова О.Н. Статья «Моделирование процессов управления» Журнал «Информатика и образование» №3 2003
7. Перельман Я.И. Занимательная алгебра. М:АО»Столетие»»,1994
8. Угринович Н.Д. Учебник «Информатика и информационные технологии 10-11» М: Лаборатория Базовых Знаний.2002.
9. Шибасов Л.П., Шибасова З.Ф. За страницами  учебника математики. М: Просвещение, 1997
10. Шамгутдинова Т.М. Статья « Задачи линейного программирования» журнал « Информатика и образование» №8 2002.