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

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

2 Транспортная задача Пусть на три завода З 1, З 2, З 3, требуется завезти сырье одинакового вида, которое хранится на двух складах С 1, С 2. Потребность в сырье каждого вида для данных заводов указана в таблице 1, а расстояние от склада до завода - в таблице 2. Требуется найти наиболее выгодный вариант перевозок, т.е. такой, при котором общее число тонно-километров наименьшее. Таблица 1 Таблица 2 Наличие сырья (в т) на складе Потребность в сырье (в т) на заводе С1С1 С2С2 З1З1 З2З2 З3З СкладРасстояние (в км) от склада до завода З 1 З 2 З 3 С С

3 Решение транспортной задачи 1 Для решения этой задачи в первую очередь проанализируем ее условие и переведем его на язык математики, т.е. составим математическую модель. Для этого количество сырья, которое нужно перевезти со склада С 1 на заводы З 1, З 2, обозначим через x и y соответственно. Запишем данные в виде таблицы 3. СкладыКоличество сырья (в т), перевезенное на заводы З 1 З 2 З 3 С 1 x y 20-x-y С 2 10-x 15-y x+y

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

5 Решение транспортной задачи 1 Общее число тонно-километров F выражается формулой: F = Воспользуемся тем, что для нахождения наименьшего значения линейной функции на многоугольнике достаточно вычислить значения функции в вершинах многоугольника и выбрать из них наименьшее. Вершины многоугольника имеют координаты: =5x + 7y + 10(20 - x - y) + 3(10 - x) +4(15 - y) + 6(x + y) = x - y. Наименьшее значение функции F достигается в точке С(10,10) и оно равно260. Значения функции в этих вершинах соответственно равны: O(0, 0), A(0, 15), B(5, 15), C(10, 10), D(10, 0). F(O) = 290, f(A) = 275, f(B) = 265, f(C) = 260, f(D) = 270.

6 Решение транспортной задачи 1 В соответствии с этим наиболее выгодный вариант перевозок задается таблицей. СкладКоличество сырья (в т), перевезенное на заводы З 1 З2З2 З3З3 C1C C2C2 0520

7 Упражнение 1 Ответ: а), б) Нарисуйте фигуру, координаты точек которой удовлетворяют системе неравенств: а) б)

8 Упражнение 2 Ответ: 3,5; 1. Найдите наибольшее и наименьшее значения функции F = x + y при условии

9 Упражнение 3 Ответ: 4, -5. Пусть математическая модель некоторой задачи представляется следующей системой ограничений На множестве решений этой системы найдите наибольшее и наименьшее значения функции F = y - 2x.

10 Задача 2 Мастерская выпускает трансформаторы двух видов. На один трансформатор первого вида расходуется 5 кг трансформаторного железа и 3 кг проволоки, а на один трансформатор второго вида - 3 кг железа и 2 кг проволоки. От реализации одного трансформатора первого вида мастерская получает 150 руб. прибыли, а от реализации одного трансформатора второго вида руб. Сколько трансформаторов каждого вида нужно выпустить, чтобы получить наибольшую сумму прибыли, если мастерская располагает 480 кг железа и 300 кг проволоки?

11 Решение задачи 2 Пусть x – число трансформаторов первого вида, y – число трансформаторов второго вида. Тогда общая прибыль от продажи трансформаторов выражается функцией F(x, y) = 150x + 100y. Аргументы x и y имеют ограничения, выражаемые системой неравенств: Эти неравенства задают многоугольник OABC, изображенный на рисунке.

12 Решение задачи 2 Вершины многоугольника имеют координаты: Наибольшее значение функции F равно и достигается в вершинах A(0, 150) и B(60, 60). Значения функции F(x, y) в этих вершинах соответственно равны: O(0, 0), A(0, 150), B(60, 60), C(96, 0). F(O) = 0, f(A) = 15000, f(B) = 15000, f(C) = Ответ: Трансформаторов первого вида можно выпускать 2k штук, трансформаторов второго вида 150 – 3k штук, k = 0, …, 30. При этом прибыль будет одинаковой, равной руб. Следовательно, это значение принимается и во всех точках отрезка AB.