XIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Оптимизационные задачи
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Людям нередко приходиться решать, как оптимизировать свою деятельность, т. е. с помощью наименьших затрат сил, средств, материалов получить более лучшей результат. И на это люди тратят наибольшую часть своих усилий.
Одной из древнейших задач на оптимизацию является «задача Дидоны». Необходимо было шкурой быка охватить как можно больший участок земли. По легенде Дидона разрезала шкуру на узкие ремни, связала их. А затем получившимся канатом охватила прибрежный участок земли.
Представители разных специальностей решают такого рода задачи (технологи, экономисты, диетологи и т д.):
-Как минимизировать транспортные расходы предприятий, заводов для связи с источниками сырья и потребностями их продукции. -Как при небольших финансовых затратах создать сбалансированную диету для больных? -Где следует построить мост через реку, чтобы дорога, проходящая через него и соединяющая два города, была самой короткой? -Какие размеры должен иметь ящик, чтобы объём его был наименьшим при ограничении на расходные материалы?
Великий русский математик П. Л. Чебышев еще в 19 веке писал, что «особую возможность имеют те методы науки, которые позволяют решать задачу, общую для всей практической деятельности человека: как располагать своими средствами для достижения наибольшей выгоды». Задачи подобного типа имеют общее название - задачи на оптимизацию. Они тесно связаны с практической деятельностью человека. С их помощью можно получить ответ на вопрос: как добиться максимальной затраты времени, наименьших потерь.
Как решать задачи на оптимизацию? Существуют три этапа их решения:
Составление математической модели, постановка математической задачи.
Работа с математической моделью.
Ответ на вопрос задачи.
Совсем недавно единственным методом решения подобных задач была обыкновенная прикидка, решение «на глаз», или же путем перебора всех возможных вариантов находился лучший. Факторов, влияющих на решение становилось всё больше, так что возрос интерес к математическим методам в экономике. Развитие вычислительной техники так же способствовало «математизации экономики». Одним из видов задач на оптимизацию являются задачи линейного программирования
Линейное программирование
Линейное программирование - это метод математической оптимизации. Под методом “ оптимизации” подразумевается метод, который пытается максимизировать или минимизировать некоторую величину, например, максимизировать прибыль или минимизировать затраты. Линейное программирование-это часть более широкой области математических оптимизационных задач, называемых математическим программированием. Линейное программирование-это мощный и широко применяемый метод. Линейное программирование широко применяется в военной и нефтяной промышленности, а также в экономике.
В любой задаче линейного программирования необходимо принимать определенные решения. Эти решения представлены переменными решения xj, используемыми в модели линейного программирования. Основная структура задачи линейного программирования состоит в том, чтобы либо максимизировать, либо минимизировать целевую функцию, удовлетворяя при этом набору ограничивающих условий или ограничений.
Целевая функция представляет собой математическое представление общей цели, сформулированной как функция переменных принятия решения xj (линейная функция). Целевая функция может представлять цель, такую как уровень прибыли, общая выручка, общая стоимость.
Набор ограничений (система неравенств), также указанных в терминах xj, представляет условия, которые должны выполняться при принятии решения. Например, при попытке максимизировать прибыль от производства и продажи группы продуктов ограничения выборки могут отражать ограниченные трудовые ресурсы, ограниченное сырье и ограниченный спрос на продукцию.
Другие условия, которые необходимо выполнить, принимают форму требований. Например, при определении количества различных продуктов для производства могут быть указаны минимальные объемы производства. Ограничения задачи линейного программирования могут быть представлены уравнениями или неравенствами (типы≤ и / или ≥).
Формулировка задачи линейного программирования
Три основных шага в построении задачи линейного программирования заключаются в следующем:
Шаг 1. определите неизвестные переменные, которые необходимо определить ( переменные принятия решения), и представьте их в терминах алгебраических символов.
Шаг 2. определите все ограничения и выразите их в виде линейных уравнений или неравенств.
Шаг 3. определите целевую функцию в виде линейной функции переменных решения, которая должна быть максимизирована или минимизирована.
Эти задачи называются задачами линейного программирования, потому что целевая функция и ограничения являются линейными.
Примеры задач
Задача № 1
В компании есть два класса контролеров, 1 и 2, которые должны быть назначены для проверки качества. Требуется, чтобы в течение 8-часового рабочего дня проверялось не менее 1800 единиц продукции. Контролеры 1-го класса могут проверять детали со скоростью 25 штук в час, точность 98%. Контролеры 2-го класса проверяют со скоростью 15 штук в час с точностью 95%.
Ставка заработной платы контролера 1-го класса составляет 4,00 доллара в час, а контролера 2-го класса-3,00 доллара в час. Каждый раз, когда контролер допускает ошибку, стоимость для компании составляет 2,00 доллара. Компания имеет в своем распоряжении восемь контролеров 1-го класса и десять контролеров 2-го класса. Компания хочет определить оптимальное назначение контролеров, которое позволит минимизировать общую стоимость проверки. Решение:
Составим целевую функцию. Для этого выполним некоторые вычисления:
25·8=200(дет)-за 8 часов работы может проверить контролер 1 класса
100%-98%=2%-такой процент деталей может контролёр 1 класса проверить неправильно.
200·0,02=4(дет)- может контролер 1 класса проверить неправильно за 8 часов работы
2·4=8($)-ущерб для компании за 8 часов работы контролера 1 класса
4·8+8=40($)-денег потратит компания на одного контролера 1 класса за один день (з/п + ущерб).
15·8=120(дет) )-за 8 часов работы может проверить контролер 2 класса
100%-95%=5% такой процент деталей может контролёр 2 класса проверить неправильно.
120·0,05=6(дет)- может контролер 2 класса проверить неправильно за 8 часов работы
2·6=12($)-ущерб для компании за 8 часов работы контролера 2 класса
3·8+12=36($)-денег потратит компания на одного контролера 2 класса за один день (з/п + ущерб).
Итак, Минимизировать целевую функцию: Z =40x1 + 36x2 , x1 -число контролеров 1 класса, x2-число контролеров 2 класса.
При условии
x1 ≤8
x2≤10
200x1 +120x2 ≥1800
x1≥0, x2≥0
если разделить все коэффициенты на 40, то получим 5x1 +3x2 ≥45.
Графическое решение:
Когда модель линейного программирования сформулирована в терминах двух переменных решения, она может быть решена с помощью графических метода. Графический подход обеспечивает эффективную визуальную решения. На рисунке показана область допустимых значений функции (многоугольник АВСD)
Это приведено решение задачи с помощью программы Excel.
Оптимальное решение Z=380, при x1=8 и x2= 1.666667. Но так как x1 и x2 должны быть целыми числами, то оптимальным будет Z=392 при x1=8 и x2= 2
Вывод: Для того, чтобы расход средств на оплату труда контролеров был оптимальным, необходимо взять на работу 8 контролеров 1 класса и 2 контролера 2 класса, при общей затрате 392 $ в день.
Задача №2. Диетическое питание
Диетолог планирует меню для ужина в университетской столовой. Будут поданы три основных блюда, все с разным содержанием питательных веществ. Диетолог заинтересован в обеспечении по крайней мере минимальной суточной потребности каждого из трех витаминов в этом одном приеме пищи. В этой таблице приведены сведения о содержании витаминов на единицу каждого продукта, стоимости единицы каждого продукта питания и минимальных суточных потребностях (МСП) в трех витаминах. Можно выбрать любую комбинацию из трех продуктов, если общий размер порции составляет не менее 9 единиц. Сколько максимально будет стоить ужин, чтобы выполнились требования диетолога?
|
витамин |
||||||
|
цена |
3 |
2 |
1 |
продукты |
||
|
0.10$ |
10 мг |
20 мг |
50мг |
1 |
||
|
0.15$ |
50 мг |
10 мг |
30 мг |
2 |
||
|
0.12$ |
20 мг |
30 мг |
20 мг |
3 |
||
|
210 мг |
200 мг |
290 мг |
(МСП) |
|||
Решение:
Целевая функция Z=0.10 x1+0.15 x2+0.12x3 подлежит максимизации
x1 – количество единиц 1-го продукта
x2 - количество единиц 2-го продукта
x3 - количество единиц 3-го продукта
условия:
50 x1 +30 x2 + 20 x3 ≥ 290
20 x1 +10 x2 + 30 x3 ≥ 200
10 x1 + 50 x2 +20 x3 ≥ 210
x1 + x2 + x3 ≥ 9
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Поскольку в задаче три переменные решения x1 , x2 , x3 ,то решать будем только с помощью программы Excel.
Вывод: максимальная стоимость ужина будет составлять 1.12 $ при взятии 2,86 ед. 1-го продукта, 1,72 ед. 2-го продукта, 4,76 ед. 3-го продукта.
Задача №3 Ассортимент продукции
Компания хочет запланировать производство кухонного прибора, который требует двух ресурсов-труда и материалов. Компания рассматривает три различные модели, и ее производственный отдел предоставил следующие данные:
|
C |
B |
A |
Модель |
|
6 |
3 |
7 |
Рабочая сила (часов на единицу) |
|
5 |
4 |
4 |
Материал (фунтов на единицу) |
|
1 |
2 |
4 |
Прибыль ($ на единицу) |
Поставка сырья ограничена 200 кг в день. Ежедневная доступность рабочей силы составляет 150 часов. Необходимо определить какие модели и в каком количестве надо произвести ежедневно для получения максимальной прибыли. Решение:
Максимизировать Z= 4x1+2x2+ x3
При условии
7 x1+3 x2+6 x3≤150
4 x1+4 x2+5 x3≤200
x1≥0, x2≥0, x3≥0
Поскольку в задаче три переменные решения x1 , x2 , x3 ,то она была решена с помощью программы Excel.
Вывод: максимальную прибыль 100$ можно получить при изготовлении 50 моделей В ежедневно.
Задача №4. Выбор рекламных носителей
Рекламодатель желает спланировать рекламную кампанию в трех различных средствах массовой информации–на телевидении, радио и в журналах. Цель рекламной программы состоит в том, чтобы охватить как можно больше потенциальных клиентов. Результаты исследования рынка приведены ниже:
|
Телевидение |
||||||||
|
Журналы |
Радио |
основное время |
Дневное время |
|||||
|
15 000$ |
30 000 $ |
75 000 $ |
40 000$ |
СCтоимость рекламной единицы |
||||
|
200 000 |
500 000 |
900 000 |
400 000 |
Количество потенциальных клиентов, привлеченных на единицу |
||||
|
100 000 |
200 000 |
400 000 |
300 000 |
Количество клиентов-женщин, охваченных на единицу |
||||
Компания не хочет тратить на рекламу более 800 000 долларов. Также требует, чтобы:
по крайней мере 2 миллиона женщин подвергались воздействию;
реклама на телевидении должна быть ограничена 500 000 долл.;
по крайней мере 3 рекламных блока можно купить на дневном телевидении и два блока в основное время;
количество рекламных блоков на радио и в журналах должно составлять от 5 до 10.
Решение:
Максимизировать целевую функцию Z = 400 x1+900 x2+500 x3+200x4
При условии
40 x1 +75 x2 +30 x3+15x4 ≤800
30 x1 +40 x2 +20 x3+10 x4 ≥200
40 x1 +75 x2 ≤500
x1 ≥3, x2 ≥2, x3 ≥5, x3 ≤10, x4 ≥5, x4 ≤10
x1≥0, x2≥0, x3≥0, x4≥0
Поскольку в задаче четыре переменные решения x1 , x2 , x3 , x4 ,то решать будем только с помощью программы Excel
Вывод: 10960 потенциальных клиентов может быть максимально привлечены при 3-х рекламах по телевидению в дневное время, 3-х рекламах в основное время, 10-ти рекламах по радио, и 10-ти рекламах в журналах.
Заключение
В настоящее время пришло понимание того, что успех развития, большинства областей науки, техники, организации производства и экономики зависит от развития многих направлений математики. Математика становится средством решения проблем организации производства, поисков оптимальных решений. Она способствует повышению производительности труда, его эффективности, минимизации затрат.
Экстремальные задачи или задачи на оптимизацию позволяют связать реальные задачи экономики, транспорта, производства с методами математики. Их решение способствует углублению и обогащению математических знаний.
В результате этой работы я познакомился с задачами линейного программирования, использовал литературу по этой теме. А также изучил методы решение этих задач с помощью графиков и программы Excel.
Список литературы
Беляева Э. С., Монахов В.М. Экстремальные задачи. М.: Просвещение, 1997.
Виленкин Н. Л. Функции в природе и технике. – М.: Просвещение, 1978
Возняк Г. М., Гусев В. А. Прикладные задачи на экстремумы. М.: Просвещение, 1985.
Гейн А. Г. Земля Информатика. – Екатеринбург: Издательство Уральского университета, 1997
Гнеденко Б. В. Введение в специальность математика. – М: Наука, 1991
Гнеденко Б. В. Математика в современном мире. М: Просвещение, 1980.
Перельман Я. И. Занимательная алгебра. М: АО “Столетие”, 1994
Хургин Я. И. Ну и что? (Разговоры математика с биологами и радистами, врачами и технологами… о математике и ее связях с другими науками). М.: Молодая гвардия, 1987.