Научно-исследовательский проект

«Решение оптимизационных задач

методами линейного программирования»

2017 – 2018 учебный год

10 класс

 

Руководитель проекта: Бруханская Елена Александровна, учитель математики

 

Цель проекта: решение производственной и транспортной оптимизационных задач методами линейного программирования.

Задачи:

1. Теоретическая часть исследования

2. Постановка и решение задачи минимизации транспортных расходов

3. Постановка и решение задачи максимизации прибыли

 

1. Теоретическая часть

 

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

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

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

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

     Постановка задачи на оптимизацию и ее решение включает в себя ряд этапов:

- выбор и обоснование цели оптимизации;

- согласование цели с имеющимися возможностями, т.е. учет ограничений;

- реализация способа достижения цели при учете ограничений.

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

  В таких задачах, как правило, выделяют два аспекта:

     1) Ограничения - это то, что ограничивает наши решения. Как правило, ограничения записываются в виде равенств или неравенств.

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

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

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

     Задачи математического программирования делятся на два больших класса:

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

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

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

     Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

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

     Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

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

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

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

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

Основные этапы решения оптимизационной задачи:

1. Постановка задачи (сбор исходной информации, составление математической модели)
2. Решение задачи (выбор метода решения, выполнение вычислений)
3. Анализ решения

Заключение

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

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

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

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

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

      4)   Расширены знания о существующих видах оптимизационных задач и способах их решения..

      Практической значимостью данной работы является привлечение внимания к изучению методов задач на поиск оптимальных решений в общеобразовательной школе при подготовке к ЕГЭ по математике профильного уровня (задача №17).