Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Задачи оптимизации

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

  • Математика

Поделитесь материалом с коллегами:



Геометрия в задачах оптимизации

Содержание





1. Введение……………………………………………………………………с.2


2. Задание выпуклых многоугольников с помощью неравенств……..с.3


3. Задачи оптимизации на плоскости……………………………………с.4-6


4. Задание выпуклых многогранников с помощью неравенств……с.7


5. Задача оптимизации в пространстве………………………………..с.8-9


6. Заключение ………………………………………………………………...с.9


7. Список используемой литературы и Интернет-ресурсов……………c.10


Введение

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

- транспортная задача о составлении оптимального способа перевозок грузов;

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

- задача о наилучшем использовании ресурсов;

- задача о смесях, то есть о получении продукции с заданными свойствами при наименьших затратах;

- задача составления оптимального плана производства;

- задача рационального использования посевных площадей и т.д.

Несмотря на различные содержательные ситуации в этих задачах, математические модели, их описывающие, имеют много общего, и все они решаются одним и тем же методом, разработанным отечественным математиком Л. В. Канторовичем (1912 – 1986). Несколько слов о разработчике метода.

Леонид Витальевич Канторович (6 (19) января 1912, Санкт-Петербург — 7 апреля 1986, Москва) — советский математик и экономист, лауреат Нобелевской премии по экономике 1975 года «За вклад в теорию оптимального распределения ресурсов». Пионер и один из создателей линейного программирования.

hello_html_273400ed.jpg

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

Л. В. Канторович — представитель петербургской математической школы П. Л. Чебышева, ученик Г. М. Фихтенгольца и В. И. Смирнова. Канторович разделял и развивал взгляды П. Л. Чебышева на математику как на единую дисциплину, все разделы которой взаимосвязаны, взаимозависимы и играют особую роль в развитии науки, техники, технологии и производства. Л. В. Канторович выдвигал тезис взаимопроникновения математики и экономики и стремился к синтезу гуманитарных и точных технологий знания. Творчество Канторовича стало образцом научного служения, базирующегося на универсализации математического мышления.
















Задание выпуклых многоугольников с помощью неравенств

Пусть прямая задана уравнением hello_html_m3050f55b.gifи проходит через точку hello_html_m5edefd78.gif(hello_html_m34007a1c.gif. Ее вектор нормали hello_html_69bf56cc.gif имеет координаты hello_html_m7521e143.gif и определяет полуплоскость. Точка A(x; y) принадлежит этой полуплоскости в случае, если угол между векторами hello_html_69bf56cc.gif и hello_html_128833c3.gif не превосходит 90˚, т.е. в том случае, если скалярное произведение этих векторов больше или равно нулю, т.е. hello_html_m2b10a0cf.gif = a(x hello_html_m5c062083.gif hello_html_69b83015.gif) + b(yhello_html_m5c062083.gif hello_html_7e672011.gif) hello_html_m6d1256d7.gif 0. При этом hello_html_1776d760.gif Следовательно, точка A(x; y) принадлежит этой полуплоскости, если выполняется неравенство ax + by +c hello_html_m4b5fcb01.gif

Аналогично точка A(x; y) принадлежит другой полуплоскости по отношению к данной прямой, если выполняется неравенство ax + by +c hello_html_mabb22bc.gif.

Для того, чтобы определить, какой из двух полуплоскостей принадлежит точка A (x; y), достаточно подставить ее координаты в левую часть уравнения прямой и найти знак получившегося значения.

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

Действительно, пусть стороны выпуклого многоугольника лежат на прямых, задаваемых уравнениями:

hello_html_m673fa0a2.gif

……………………,

hello_html_4627d2d8.gif


Тогда сам многоугольник является пересечением соответствующих полуплоскостей, и, следовательно, для его точек должна выполняться система неравенств вида


hello_html_m355bee0a.gif


которая и определяет этот многоугольник.

Например, неравенства hello_html_m5d9b63d9.gif которые можно переписать в виде системы

hello_html_m31c1f7c5.gif


определяют единичный квадрат.


hello_html_m52b0a075.jpg


hello_html_m768a664f.jpg

hello_html_m7dd0f183.jpg

Если к этим неравенствам добавить еще одно неравенство

hello_html_3cc27488.gif

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

Задачи оптимизации на плоскости

В качестве примера задач оптимизации рассмотрим следующие задачи.

Задача 1. На трех складах хранится сырье одинакового вида в количестве соответственно 10 т, 20 т, 30 т. На завод нужно завести 35 т сырья. Найдите наиболее выгодный вариант перевозок, если расстояния от складов равны соответственно 7 км, 5 км, 8 км.

Р е ш е н и е. Составим математическую модель. Для этого обозначим через х и у количество тонн сырья, которое нужно перевезти соответственно с первого и второго складов на завод. Тогда с третьего склада нужно будет перевезти 35 – (x + y) тонн сырья. Занесем данные в таблицу, где hello_html_m35f1375e.gif склады.

Склад

hello_html_m3b33173b.gif

hello_html_m3af9773a.gif

hello_html_27846bad.gif

Количество сырья (т)

10

20

30

Расстояние до завода (км)

7

5

8

Количество сырья, перевезенное на завод (т)

x

y

35 – (x + y)

Все величины, входящие в эту таблицу, должны быть неотрицательны. Поэтому имеем систему неравенств:

hello_html_76777ada.gif

Систему можно переписать иначе:

hello_html_m1110cb4f.gifhello_html_19b57b3.jpg

Эта система определяет многоугольник ABCDE. Найдем на нем наименьшее значение функции

F = 7x + 5y + 8(35 – xy), или F = – x – 3y + 280.

Найдем координаты вершин многоугольника: А(5;0), В(0;5), С(0;20), D(10;20) , E(10;0). Тогда

hello_html_m1f97034b.gif

Таким образом, наименьшее значение функция принимает в точке D(10;20). Следовательно, наиболее выгодно с первого склада перевезти на завод 10 т сырья, со второго – 20 т и с третьего – 5 т.

Задача 2. Установка собирается из трех различных деталей – А, Б, В. На одном станке можно за смену изготовить либо 12 деталей типа А, 18 – Б, 30 –В. (первый режим), либо 20 деталей типа А, 15 – Б, 9 – В (второй режим). Хватит ли 100 станков, чтобы изготовить за смену детали для 720 установок? Какое наименьшее количество станков (и с какими режимами работы) нужно для выполнения заказа?

Режим

Кол-во станков

детали

А

Б

В

I

x

12

18

30

II

y

20

15

9



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

hello_html_3a8c9b7a.gif

Кроме того, поскольку количество деталей должно быть неотрицательно, нужно, чтобы выполнялись неравенства hello_html_m3b744391.gif Перепишем все эти неравенства в виде системы:

hello_html_m3e152883.gifhello_html_m6752fab0.jpg

Эта система неравенств определяет фигуру на плоскости.

Вершины A и D имеют координаты (60;0) и (0;80) соответственно. Для нахождения координат вершин B и C нужно решить системы уравнений

В:hello_html_m4ce13433.gif C:hello_html_20910449.gif

В результате имеем В(20;24), С(15;30).

Для нахождения наименьшего значения функции F = x + y, вычислим ее значения в вершинах: hello_html_2b053153.gif Наименьшее значение принимается в вершине В, и оно равно 44.

Таким образом, для выпуска 720 деталей достаточно 44 станка, из которых 20 работает в первом режиме, а 24 – во втором.

Задача 3. Для изготовления двух видов продукции используют три вида сырья: hello_html_58e0e0ee.gif Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице.

Вид сырья

Запас сырья

Количество единиц сырья, идущих на изготовление единицы продукции

hello_html_12999556.gif

hello_html_6e0474c0.gif

hello_html_30a36c6a.gif

20

2

5

hello_html_4c3e8dfc.gif

40

8

5

hello_html_54136dbd.gif

30

5

6

Прибыль от единицы продукции, руб.

50

40

Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Р е ш е н и е. Обозначим через x количество единиц продукции hello_html_12999556.gif, а через y - количество единиц продукции hello_html_6e0474c0.gif. Тогда количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:

hello_html_m3956787d.gif

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

Конечную цель решаемой задачи – получение максимальной прибыли – выразим как функцию переменных x и y. Реализация единиц продукции даст 50x и 40y руб. прибыли, суммарная прибыль Z = 50x + 40 y (руб.).

Неделимость продукции в условии не оговорена, поэтому переменные

могут быть и дробными числами.

Требуется найти такие х и y, при которых функция Z достигнет максимума, т.е. найти максимальное значение линейной функции

Z = hello_html_m788240e6.gif при ограничениях:

hello_html_3e4fa865.gif

Построим многоугольник решений. Для этого в системе координат hello_html_m6c58c22c.gif изобразим граничные прямыеhello_html_6d7af797.jpg

hello_html_m6b8fcaf2.gif

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

Для построения прямой 50x + 40 y = 0 строим радиус-вектор hello_html_m284767e2.gif hello_html_69bf56cc.gif и через точку О проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора hello_html_m7a7ae403.gif. Из рисунка следует, что опорной по отношению к многоугольнику решений эта прямая становится в точке С, где функция Z принимает максимальное значение. Точка С лежит на пересечении прямых hello_html_52781788.gif и hello_html_4a55f7c9.gif. Для определения ее координат решим систему уравнений

hello_html_6079a673.gifhello_html_3d98296a.gifhello_html_m20cde417.gif

Оптимальный план задачи: hello_html_11db053c.gif = 3,9; hello_html_4ed6b1a1.gif Подставляя значения в линейную функцию, получаем, что максимальная прибыль равна 260,3 руб., и чтобы ее заработать надо запланировать производство 3,9 ед. продукции hello_html_12999556.gif и 1,7 ед. продукции hello_html_m55019796.gif







Задание выпуклых многогранников с помощью неравенств

Плоскость в пространстве задается уравнением hello_html_2391fde5.jpg

ax + by + cz + d = 0, (*),

где a, b, c, d – действительные числа, причем a,b,c не равны нулю и составляют координаты вектора hello_html_69bf56cc.gif, перпендикулярного этой плоскости и называемого вектором нормали.

4 частных случая расположения плоскости:

  1. ax + by + cz = 0 (d = 0) – плоскость проходит через начало координат;

  2. ax + by + d = 0 (с = 0) – параллельно hello_html_m5f6786a.gif;

  3. ax + by = 0 (с = d = 0) – пересекает hello_html_m8a64c8d.gif;

  4. ax + d = 0 (b = с = 0) – hello_html_6de216a9.gif.

A(hello_html_588b7602.gif точки пересечения плоскости с осью абсцисс, осью ординат и осью аппликат соответственно. Если уравнение плоскости разделить на d, то получим уравнение плоскости в отрезках

hello_html_m713bedd1.gif.

Заметим, что если плоскость задана уравнением (*), то неравенства

ax + by + cz + d hello_html_m3316894e.gif ax + by + cz + d hello_html_mabb22bc.gif определяют полупространства, на которые эта плоскость разбивает пространство. Для того, чтобы определить, какому из двух полупространств принадлежит точка А (x; y. z), достаточно подставит ее координаты в левую часть уравнения плоскости и найти знак получившегося значения.

Поменяв знаки чисел a, b, c, d, второе неравенство всегда можно свести к первому.

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

Например, неравенства hello_html_m33ccef68.gif которые можно переписать в виде системыhello_html_m29b32bc.jpg

hello_html_1a763782.gif

определяют единичный куб в пространстве.



Если к этим неравенствам добавить еще одно неравенство

hello_html_m18478d99.gifhello_html_m4e0c23c6.jpg

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



Задача оптимизации в пространстве



Задача. Пусть на четыре завода hello_html_39bfa026.gif, hello_html_620465a1.gif hello_html_38e82c4a.gif hello_html_5cb64674.gif требуется завезти сырье одинакового вида, которое хранится на двух складах hello_html_m8be5179.gif, hello_html_m974317c.gif. Потребность данных заводов в сырье каждого вида указана в таблице , а расстояние от склада до завода – в таблице 2. Требуется найти наиболее выгодный вариант перевозок.

Таблица 1

Наличие сырья на складе (т)

Потребность завода в сырье (т)

С1

С2

З1

З2

З3

З4

20

25

8

10

12

15



Таблица 2

Склад

Расстояние от склада до завода (км)

З1

З2

З3

З4

С1

5

6

4

10

С2

3

7

3

7



Для решения этой задачи в первую очередь проанализируем ее условие и переведем его на язык математики, то есть составим математическую модель. Для этого количество сырья, которое нужно перевезти со склада С1 на заводы З1, З2, З3, обозначим через x, y, z. Тогда на четвертый завод с этого склада нужно перевезти 20 – xyz сырья в тоннах, а со второго нужно перевезти 8 – x, 10 – y, 12 – z, x + y + z – 5 сырья в тоннах. Запишем эти данные в таблицу 3.

Таблица 3

Склад

Количество сырья, перевезенное на завод (т)

З1

З2

З3

З4

С1

x

y

z

20 – x – y – z

С2

8 - x

10 - y

12 - z

x + y + z - 5



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

hello_html_65388afe.gif

hello_html_m1aec93f3.jpg

Эта система неравенств определяет некоторый многогранник. Для того чтобы его построить, изобразим сначала многогранник, определяемый первой и второй строкой данной системы. На рисунке это параллелепипед OABCO1A1B1C1. Уравнение 20 - x - y - z = 0 определяет плоскость D1D2D3, которая, пересекает параллелепипед, образуя многоугольник M1M2M3C1. Уравнение 
x + y + z - 5 = 0 определяет плоскость, которая пересекает параллелепипед и образует в нем треугольник E1E2E3. На многограннике M1M2M3C1CBAE1E2E3O1, где M1(8,10,2), M2(0,10,10), M3(0,8,12), C1(8,0,12), C(8,0,0), B(8,10,0), A(0,10,0), E1(5,0,0), E2(0,5,0), E3(0,0,5), O1(0,0,12), выполняются все условия данной системы. Назовем его многогранником ограничений. 


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

5x + 6y + 4z + 10(20 - x - y - z) + 3(8 - x) + 7(10 - y) + 
+ 3(12 -
 z) + 7(x + y + z - 5) = 295 - x - 4y - 2z.

Таким образом, задача сводится к отысканию наименьшего значения функции F = 295 - x - 4y - 2z на многограннике ограничений. Для этого достаточно найти наибольшее значение функции f = x + 4y + 2z. Тогда Fmin = 295 - fmax.

Вычислим значение функции f = x + 4y + 2z в вершинах многогранника ограничений: f(M1) = 52, f(M2) = 60, f(M3) = 56,f(C1) = 32, f(C) = 8, f(B) = 48, f(A) = 40, f(E1) = 5, f(E2) = 20, f(E3) = 10, f(O1) = 24. 
   

Легко видеть, что максимальное значение функции f равно 60. Тогда Fmin = 295 - 60 = 235. Это значение функция F принимает в точкеM2(0,10,10).  Таким образом, наиболее выгодный вариант перевозок задается таблицей 4.


Таблица 4

Склад

Количество сырья (в т), перевезенное на заводы

З1

З2

З3

З4

С1

0

10

10

0

С2

8

0

2

15


Заключение

Закончив работу над темой «Геометрия в задачах оптимизации», мы сделали следующие выводы:

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

- если число переменных равно 2-м, то в процессе решения задачи получится многоугольник, а если число переменных равно 3-м – многогранник;

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

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


Список используемой литературы и Интернет-ресурсов

  1. Ефимов Н.В. Краткий курс аналитической геометрии. Москва: Издательство «Наука», 1975 год

  2. Смирнова И.М., Смирнов В.А. Геометрия 7-9 классы. Москва: Издательство «Мнемозина», 2009 год

  3. Смирнова И.М., Смирнов В.А. Геометрия 10-11 классы. Москва: Издательство «Мнемозина», 2009 год

  4. Волков В.А. Элементы линейного программирования. Москва: Издательство «Просвещение», 1975 год

  5. Беляева Е.С., Монахов В.М. Экстремальные задачи. Москва: Издательство «Просвещение», 1977 год

  6. www.wikipedia.ru



12


Краткое описание документа:

Это проектная исследовательская работа учеников 11 класса, которая проводилась под моим руководством. Тема "Многогранники в задачах оптимизации" является дополнительной для базового уровня по учебнику И.М.Смирновой и В.А.Смирнова "Геометрия 10-11". Данная работа рассматривает кроме многогранников еще и многоугольники в задачах оптимизации. поэтому может быть интересна и понятна ученикам 9 класса.

Автор
Дата добавления 24.06.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров511
Номер материала 310854
Получить свидетельство о публикации
Похожие материалы

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