математика. Департамент образования города москвы государственное бюджетное профессиональное образовательное учреждение города москвы
 Скачать 1.12 Mb.
|
|
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГОРОДА МОСКВЫ «ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ №50» Графический метод решения задач линейного программирования Работу выполнил: Рибчинский Максим Русланович, студент группы ДЛ-206П Руководитель: Седова Елена Геннадьевна, преподаватель математики Москва 2016 2 Содержание Стр. Введение 3 Глава 1. Теоретические основы решения задач линейного программирования графическим методом 4 1.1. Основные понятия и определения линейного программирования 4 1.2. Теоретические основы графического метода решения задач линейного программирования 6 1.3. Примеры решения задач линейного программирования графическим методом 9 Глава 2. Практическое применение графического метода решения задач линейного программирования 15 Заключение 22 Список литературы 24 3 Введение В современной экономической науке математическая модель является инструментом исследования и прогноза экономических явлений. Математические модели в экономике – это формализованное описание управляемого экономического процесса, включающее известные параметры, неизвестные величины, объединенные между собой связями в виде математических зависимостей, формул. Математические модели представляют собой основу компьютерного моделирования и обработки информации. Линейное программирование сформировалось как отдельный раздел прикладной математики, в котором успешно решается проблема распределения ограниченных ресурсов между конкурирующими видами деятельности с тем, чтобы оптимизировать (максимизировать или минимизировать) некоторые численные величины. Большинство всех решаемых на практике задач оптимизации относится к задачам линейного программирования. Созданный математический аппарат в сочетании с компьютерными программами, производящими сложные и трудоемкие расчеты, позволяет широко использовать модели линейного программирования как в экономической науке, так и в хозяйственной деятельности. В представленной работе проводится исследование теоретических основ и практических результатов применения графического метода решения задач линейного программирования. Актуальность данного исследования заключается не только в приобретении новых математических знаний в процессе выполнении работы, но и в овладении определенными компетенциями, позволяющими использовать математический аппарат для решения прикладных экономических задач. Гипотеза: математическими методами можно решать экономические задачи. Цель работы: изучение графического метода решения задач линейного программирования и определение области его применения в решении экономических задач. Задачи: 1) изучить основные понятия и определения линейного программирования; 2) изучить теоретические основы графического метода решения задач линейного программирования; 3) рассмотреть примеры решения задач линейного программирования графическим методом; 4) определить область применения графического метода решения задач линейного программирования; 5) рассмотреть примеры практического применения графического метода для решения экономических задач оптимизации. Предмет исследования: графический метод решения задач линейного программирования. Методы исследования: изучение теоретического материала и практическое решение задач. 4 Глава 1. Теоретические основы решения задач линейного программирования графическим методом 1.1. Основные понятия и определения линейного программирования Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, то есть задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Математическое программирование применяется в области оптимизации экономических процессов для решения теоретических и практических задач планирования и организации производства, основная цель которого – это рациональная деятельность хозяйствующих субъектов при ограниченных ресурсах. Линейное программирование (ЛП) – раздел математического программирования, в котором изучаются методы решения задач на нахождение экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные которой наложены линейные ограничения. Линейная функция называется целевой, а ограничения, которые представляют количественные соотношения между переменными, выражающие условия и требования экономической задачи и математически записываются в виде уравнений или неравенств, называются системой ограничений. С помощью задач линейного программирования решается широкий круг вопросов планирования экономических процессов, где ставится цель поиска наилучшего решения. В качестве целевой функции могут рассматриваться, например, прибыль от реализации (должна быть максимальной) или издержки производства (должны быть минимальными). Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи и записывается в общем виде как при ограничениях: 5 где x j — неизвестные; a ij , b i , c j — заданные постоянные величины. Все или некоторые уравнения системы ограничений могут быть записаны также в виде неравенств. Математическая модель в более краткой записи имеет вид: при ограничениях: Совокупность значений неизвестных (x 1 , x 2, …, x n ), удовлетворяющих системе ограничений, называется допустимым решением, или планом задачи линейного программирования, аограничения определяют область допустимых решений (ОДР). Допустимое решение задачи линейного программирования называется оптимальным, если оно обеспечивает максимальное (минимальное) значение целевой функции. Если все ограничения заданы уравнениями и переменные x j неотрицательные, то модель называется канонической. Если хотя бы одно ограничение является неравенством, то модель называется неканонической. Для составления математической модели необходимо: 1) обозначить переменные; 2) составить целевую функцию исходя из цели задачи; 3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности. 6 1.2. Теоретические основы графического метода решения задач линейного программирования Наиболее простым и наглядным методом решения задач линейного программирования является графический метод. Он применяется для задач линейного программирования с двумя переменными, когда ограничения выражены неравенствами, и задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Графический метод основан на геометрическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости (x 1 , x 2 ) некоторую полуплоскость. Пересечение этих полуплоскостей задает область допустимых решений (ОДР), то есть любая точка из этой области является решением системы ограничений. В общем случае область допустимых решений может быть представлена одной из следующих фигур: выпуклым многоугольником, неограниченной многоугольной областью, лучом, отрезком, точкой или пустой областью. В последнем случае говорят, что ограничения не совместны. Если система ограничений включает равенства, то они определяют на координатной плоскости (x 1 , x 2 ) прямую линию. Область допустимых решений всегда представляет собой выпуклую фигуру. Рис.1. Геометрическая интерпретация ограничений и целевой функции задачи линейного программирования С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на которой достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста. 7 Целевая функция задачи линейного программирования при фиксированном значении L определяет на плоскости прямую линию L = c 1 x 1 + c 2 x 2 . Изменяя значения L, получим семейство параллельных прямых, называемых линиями уровня. Для нахождения экстремального значения целевой функции используют вектор 𝑔𝑟𝑎𝑑 ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗ 𝐿 = 𝐶 ⃗⃗ на плоскости X 1 OX 2 , который показывает направление наискорейшего изменения целевой функции, он равен: где e 1 и e 2 — единичные векторы по осям ОX 1 и ОX 2 . Таким образом, Координатами вектора 𝐶 являются коэффициенты целевой функции L(x). Алгоритм решения задачи ЛП графическим методом 1. Находим область допустимых решений системы ограничений задачи. Для этого каждое из неравенств системы заменяем равенством и строим соответствующие этим равенствам граничные прямые. Каждая из построенных прямых делит плоскость на две полуплоскости. Чтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержащая решения, удовлетворяющие рассматриваемому неравенству, достаточно проверить одну какую-либо точку, не лежащую на прямой (например (0,0)). Если при подстановке ее координат в левую часть неравенства оно выполняется, то надо заштриховать полуплоскость, содержащую данную точку. Если же неравенство не выполняется, надо заштриховать полуплоскость, не содержащую данную точку. Отмечаем общую область для всех неравенств. Таким образом, получим область допустимых решений рассматриваемой задачи ЛП. 2. Формируем графическое изображение целевой функции. Приравняем целевую функцию к постоянной величине L: L = c 1 x 1 + c 2 x 2 Это уравнение при фиксированном значении L определяет прямую, а при изменении L семейство параллельных прямых, каждая из которых называется линией уровня. Проводим линию уровня L 0. 3. Определяем направление возрастания целевой функции (вектор 𝐶 ). Для определения направления максимального возрастания значения целевой функции строим вектор-градиент целевой функции, который начинается в точке (0,0), заканчивается в точке (c 1 , c 2 ). Если линия уровня и вектор-градиент построены верно, то они будут перпендикулярны. 8 4. Находим оптимальное решение задачи ЛП. Линию уровня перемещаем по направлению вектора 𝐶 для задач на максимум и в направлении, противоположном 𝐶 , для задач на минимум. Перемещение линии уровня производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений (ОДР). Эта точка определяет единственное решение задачи ЛП и будет точкой экстремума. Если окажется, что линия уровня параллельна одной из сторон ОДР, то задача ЛП будет иметь бесчисленное множество решений. Если ОДР представляет неограниченную область, то целевая функция может быть неограниченна. Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми. 5. Находим координаты точки экстремума и значение целевой функции в этой точке. Для вычисления координат оптимальной точки решим систему уравнений прямых, на пересечении которых находится эта точка. Подставляя найденный результат в целевую функцию, получим искомое оптимальное значение целевой функции. 9 1.3. Примеры решения задач линейного программирования графическим методом Задача 1. Найти наибольшее значение функции L = x 1 + x 2 при ограничениях: x 1 + 3 x 2 ≤ 6, 2 x 1 + x 2 ≤ 8, x 1 ≥ 0 x 2 ≥ 0 . Решение: 1) Рассмотрим первое неравенство системы ограничений. x 1 + 3 x 2 ≤ 6. Построим прямую: x 1 + 3 x 2 = 6. Пусть x 1 =0 => 3 x 2 = 6 => x 2 = 2. Пусть x 2 =0 => x 1 = 6. Найдены координаты двух точек (0, 2) и (6, 0). Соединяем их и получаем необходимую прямую (1). Вернемся к исходному неравенству x 1 + 3 x 2 ≤ 6, 3 x 2 ≤ - x 1 + 6, x 2 ≤ - 1/3 x 1 + 2. Знак неравенства « ≤ », следовательно, решение неравенства – множество точек, расположенных ниже прямой (1), включая эту прямую. 2) Рассмотрим второе неравенство системы ограничений. 2 x 1 + x 2 ≤ 8. Построим прямую: 2 x 1 + x 2 = 8. Пусть x 1 =0 => x 2 = 8. Пусть x 2 =0 => 2 x 1 = 8 => x 1 = 4. Найдены координаты двух точек (0, 8) и (4, 0). Соединяем их и получаем необходимую прямую (2). Вернемся к исходному неравенству. 2 x 1 + x 2 ≤ 8, x 2 ≤ - 2 x 1 + 8. Знак неравенства « ≤ », следовательно, решение неравенства – множество точек, расположенных ниже прямой (2), включая эту прямую. 3) Строим вектор 𝐶 {1; 1}, координатами которого являются коэффициенты функции L. 4) Перемещаем линию уровня (красную прямую), перпендикулярно данному вектору, от левого нижнего угла к правому верхнему. В точке, в которой линия уровня в первый раз пересечет область допустимых решений, функция L достигает своего наименьшего значения. 10 В точке, в которой линия уровня в последний раз пересечет область допустимых решений, функция L достигает своего наибольшего значения. Функция L достигает наибольшего значения в точке A. (см. рисунок справа) Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений: x 1 + 3 x 2 = 6 => x 1 = 18/5 2 x 1 + x 2 = 8 x 2 = 4/5 Вычислим значение функции L в точке A (18/5; 4/5). L (A) = 1 ∙ 18/5 + 1 ∙ 4/5 = 22/5. Ответ: x 1 = 18/5; x 2 = 4/5; L max = 22/5. Задача 2. Найти наименьшее значение функции L = x 1 + x 2 при ограничениях: x 1 + 3 x 2 ≥ 6, 2 x 1 + x 2 ≥ 4, 2 x 1 + 3 x 2 ≤ 12, x 1 ≥ 0 x 2 ≥ 0 . Решение: 1) Рассмотрим первое неравенство системы ограничений. x 1 + 3 x 2 ≥ 6. Построим прямую: x 1 + 3 x 2 = 6. 11 Пусть x 1 =0 => 3 x 2 = 6 => x 2 = 2. Пусть x 2 =0 => x 1 = 6. Найдены координаты двух точек (0, 2) и (6, 0). Соединяем их и получаем прямую (1). Вернемся к исходному неравенству. x 1 + 3 x 2 ≥ 6, 3 x 2 ≥ - x 1 + 6, x 2 ≥ - 1/3 x 1 + 2. Знак неравенства « ≥ », следовательно, решение неравенства – множество точек, расположенных выше прямой (1), включая эту прямую. 2) Рассмотрим второе неравенство системы ограничений. 2 x 1 + x 2 ≥ 4. Построим прямую: 2 x 1 + x 2 = 4. Пусть x 1 =0 => x 2 = 4. Пусть x 2 =0 => 2 x 1 = 4 => x 1 = 2. Найдены координаты двух точек (0, 4) и (2, 0). Соединяем их и получаем прямую (2). Вернемся к исходному неравенству. 2 x 1 + x 2 ≥ 4, x 2 ≥ - 2 x 1 + 4. Знак неравенства « ≥ », следовательно, решение неравенства – множество точек, расположенных выше прямой (2), включая эту прямую. 3) Рассмотрим третье неравенство системы ограничений. 2 x 1 + 3 x 2 ≤ 12. Построим прямую: 2 x 1 + 3 x 2 = 12. Пусть x 1 =0 => 3 x 2 = 12 => x 2 = 4. Пусть x 2 =0 => 2 x 1 = 12 => x 1 = 6. Найдены координаты двух точек (0, 4) и (6, 0). Соединяем их и получаем прямую (3). Вернемся к исходному неравенству. 2 x 1 + 3 x 2 ≤ 12, 3 x 2 ≤ - 2 x 1 + 12, x 2 ≤ - 2/3 x 1 + 4. Знак неравенства « ≤ », следовательно, решение неравенства – множество точек, расположенных ниже прямой (3), включая эту прямую. 3) Строим вектор 𝐶 {1; 1}, координатами которого являются коэффициенты функции L. 4) Перемещаем линию уровня (красную прямую), перпендикулярно данному вектору, от левого нижнего угла к правому верхнему. В точке, в которой линия уровня в первый раз пересечет область допустимых решений, функция L достигает своего наименьшего значения. В точке, в которой линия уровня в последний раз пересечет область допустимых решений, функция L достигает своего наибольшего значения. 12 Функция L достигает наименьшего значения в точке A. Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений: x 1 + 3 x 2 = 6 => x 1 = 6/5 2 x 1 + x 2 = 4 x 2 = 8/5 Вычислим значение функции L в точке A (6/5; 8/5). L (A) = 1 ∙ 6/5 + 1 ∙ 8/5 = 14/5. Ответ: x 1 = 6/5; x 2 = 8/5; L min = 14/5. Задача 3. Найти наименьшее значение функции L =3 x 1 + 4x 2 при ограничениях: 3 x 1 + 4 x 2 ≥ 18, 3 x 1 - x 2 ≥ 3, x 1 - x 2 ≤ 2, x 2 ≤ 6, x 1 ≤ 5, x 1 ≥ 0 x 2 ≥ 0. Решение: 1) Рассмотрим первое неравенство системы ограничений. 3 x 1 + 4 x 2 ≥ 18. 13 Построим прямую: 3 x 1 + 4 x 2 = 18. Пусть x 1 =0 => 4 x 2 = 18 => x 2 = 9/2. Пусть x 2 =0 => 3 x 1 = 18 => x 1 = 6. Найдены координаты двух точек (0, 9/2) и (6, 0). Соединяем их и получаем прямую (1). 2) Рассмотрим второе неравенство системы ограничений. 3 x 1 - x 2 ≥ 3. Построим прямую: 3 x 1 - x 2 = 3. Пусть x 1 =0 => - x 2 = 3 => x 2 = -3. Пусть x 2 =0 => 3 x 1 = 3 => x 1 = 1. Найдены координаты двух точек (0, -3) и (1, 0). Соединяем их и получаем прямую (2). 3) Рассмотрим третье неравенство системы ограничений. x 1 - x 2 ≤ 2. Построим прямую: x 1 - x 2 = 2. Пусть x 1 =0 => - x 2 = 2 => x 2 = -2. Пусть x 2 =0 => x 1 = 2. Найдены координаты двух точек (0, -2) и (2, 0). Соединяем их и получаем прямую (3). 4) Рассмотрим четвертое неравенство системы ограничений. x 2 ≤ 6. Построим прямую: x 2 = 6. Данная прямая параллельна оси OX 1 и проходит через точку (0, 6), получаем прямую (4). 5) Рассмотрим пятое неравенство системы ограничений. x 1 ≤ 5. Построим прямую: x 1 = 5. Данная прямая параллельна оси OX 2 и проходит через точку (5, 0), получаем прямую (5). 6) Находим общую область решений всех неравенств системы ограничений, получаем ОДР. 7) Строим вектор 𝐶 {3; 4}, координатами которого являются коэффициенты функции L. 8) Предположим, что функция L достигает наименьшего значения в точках A и B одновременно. Проверим это предположение Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений: 3 x 1 + 4 x 2 = 18 => x 1 = 2 3 x 1 - x 2 = 3 x 2 = 3 14 Вычислим значение функции L в точке A (2, 3). L(A) = 3 ∙ 2 + 4 ∙ 3 = 18. Точка B одновременно принадлежит прямым (1) и (3). Составим систему уравнений: 3 x 1 + 4 x 2 = 18 => x 1 = 26/7 x 1 - x 2 = 2 x 2 = 12/7 Вычислим значение функции L в точке B (26/7, 12/7). L(B) = 3 ∙26/7 2 + 4 ∙ 12/7 = 18. L(A) = L(B), следовательно, предположение оказалось верным. Тогда можно сделать вывод, что и в любой точке отрезка AB функция L достигает своего наименьшего значения. Ответ: x 1 = 2 ∙ t + 26/7 ∙ ( 1 - t ), x 2 = 3 ∙ t + 12/7 ∙ ( 1 - t ), где 0≤ t ≤1, F min = 18. (Замечание: изменяя параметр t можно получить координаты любой точки отрезка AB). 15 Глава 2. Практическое применение графического метода решения задач линейного программирования Пример 1. Задача оптимального использования ресурсов. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице. Исходный продукт Расход исходных продуктов на 1 кг мороженого Запас, кг Сливочное Шоколадное Молоко 0,8 0,5 400 Наполнители 0,4 0,8 365 Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного мороженого 14 ден. ед. Требуется определить, какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным? Решение. Введем обозначения: x 1 — суточный объем выпуска сливочного мороженого, кг, x 2 — суточный объем выпуска шоколадного мороженого, кг. Составим математическую модель задачи. Целевая функция будет иметь вид: 𝐿 = 16𝑥 1 + 14𝑥 2 → 𝑚𝑎𝑥 при ограничениях: Решим задачу графическим методом. 1) Рассмотрим первое неравенство системы ограничений. 8/10 x 1 + 5/10 x 2 ≤ 400. Построим прямую: 8/10 x 1 + 5/10 x 2 = 400. 16 Пусть x 1 =0 => 5/10 x 2 = 400 => x 2 = 800. Пусть x 2 =0 => 8/10 x 1 = 400 => x 1 = 500. Найдены координаты двух точек (0, 800) и (500, 0). Соединяем их и получаем прямую (1). 2) Рассмотрим второе неравенство системы ограничений. 4/10 x 1 + 8/10 x 2 ≤ 365. Построим прямую: 4/10 x 1 + 8/10 x 2 = 365. Пусть x 1 =0 => 8/10 x 2 = 365 => x 2 = 1825/4. Пусть x 2 =0 => 4/10 x 1 = 365 => x 1 = 1825/2. Найдены координаты двух точек (0, 1825/4) и (1825/2, 0). Соединяем их и получаем прямую (2). 3) Рассмотрим третье неравенство системы ограничений. x 1 - x 2 ≤ 100. Построим прямую: x 1 - x 2 = 100. Пусть x 1 =0 => - x 2 = 100 => x 2 = -100. Пусть x 2 =0 => x 1 = 100. Найдены координаты двух точек (0, -100) и (100, 0). Соединяем их и получаем прямую (3). 4) Рассмотрим четвертое неравенство системы ограничений. x 2 ≤ 350 Построим прямую: x 2 = 350. Данная прямая параллельна оси OX 1 и проходит через точку (0, 350), получаем прямую (4). 5) Находим общую область решений всех неравенств системы ограничений, получаем ОДР. 6) Строим вектор 𝐶 {16; 14}, его координатами являются коэффициенты функции L. Линия уровня L имеет уравнение 16x 1 + 14x 2 = сonst. 7) Перемещаем линию уровня по направлению вектора 𝐶 . Точкой выхода линии уровня L из области допустимых решений является точка A. Функция L достигает наибольшего значения в точке A. Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений: Решая систему, получим координаты точки A(312,5; 300), в которой и будет оптимальное решение, т. е. x 1 = 312,5; x 2 = 300. L (A) = 16 ∙ 312,5 + 14 ∙ 300 = 9200 ден. ед. Следовательно, L max = 9200 ден. ед. 17 Ответ. Максимальный доход от реализации составит 9200 ден. ед. в сутки при выпуске 312,5 кг сливочного и 300 кг шоколадного мороженого. Пример 2. Задача оптимального выбора рациона питания. На ферме имеются корма для животных двух видов K I и K 2 , содержащие питательные вещества трех типов В 1 , В 2 , и В 3 . Содержание питательных веществ в 1 кг корма каждого вида и норма потребления в день питательных веществ каждого типа приведены в таблице. Питательные вещества Число единиц питательных веществ в 1 кг корма Норма потребления питательных веществ в день K I K 2 В 1 3 1 9 В 2 1 2 8 В 3 1 6 12 Стоимость 1 кг корма K I равна 12 ден. ед., стоимость 1 кг корма K 2 равна 18 ден. ед. Необходимо составить дневной рацион питания животных, имеющий минимальную стоимость, и содержащий питательные вещества каждого типа не менее установленной нормы потребления. Решение. Введем обозначения: x 1 — количество корма K I в день, кг, 18 x 2 — количество корма K 2 в день, кг. Составим математическую модель задачи. Целевая функция будет иметь вид: 𝐿 = 12𝑥 1 + 18𝑥 2 → 𝑚𝑖𝑛 при ограничениях: { 3𝑥 1 + 𝑥 2 ≥ 9, 𝑥 1 + 2𝑥 2 ≥ 8, 𝑥 1 + 6𝑥 2 ≥ 12, 𝑥 1 ≥ 0, 𝑥 2 ≥ 0. Решим задачу графическим методом. 1) Рассмотрим первое неравенство системы ограничений. 3 x 1 + x 2 ≥ 9. Построим прямую: 3 x 1 + x 2 = 9. Пусть x 1 =0 => x 2 = 9. Пусть x 2 =0 => 3 x 1 = 9 => x 1 = 3. Найдены координаты двух точек (0, 9) и (3, 0). Соединяем их и получаем прямую (1). 2) Рассмотрим второе неравенство системы ограничений. x 1 + 2 x 2 ≥ 8. Построим прямую: x 1 + 2 x 2 = 8. Пусть x 1 =0 => 2 x 2 = 8 => x 2 = 4. Пусть x 2 =0 => x 1 = 8. Найдены координаты двух точек (0, 4) и (8, 0). Соединяем их и получаем прямую (2). 3) Рассмотрим неравенство 3 системы ограничений. x 1 + 6 x 2 ≥ 12. Построим прямую: x 1 + 6 x 2 = 12. Пусть x 1 =0 => 6 x 2 = 12 => x 2 = 2. Пусть x 2 =0 => x 1 = 12. Найдены координаты двух точек (0, 2) и (12, 0). Соединяем их и получаем прямую (3). 4) Находим общую область решений всех неравенств системы ограничений, получаем ОДР. 5) Строим вектор 𝐶 {12; 18}, его координатами являются коэффициенты функции L. Линия уровня L имеет уравнение 12x 1 + 18x 2 = сonst. 6) Перемещаем линию уровня по направлению вектора 𝐶 . Точкой входа линии уровня L в область допустимых решений является точка A. Функция L достигает наименьшего значения в точке A. 19 Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений: { 3𝑥 1 + 𝑥 2 = 9, 𝑥 1 + 2𝑥 2 = 8. Решая систему, получим координаты точки A(2; 3), в которой и будет оптимальное решение, т. е. x 1 = 2; x 2 = 3. L (A) = 12 ∙ 2 + 18 ∙ 3 = 78 ден. ед. Следовательно, L min = 78 ден. ед. Ответ. Минимальная стоимость дневного рациона питания животных составит 78 ден. ед. в сутки при условии, что он будет включать 2 кг корма K I и 3 кг корма K 2 Пример 3. Задача оптимального состава инвестиций. Собственные средства банка в сумме с депозитами составляют 100 млн руб. Эти средства банк может разместить в кредиты по ставке 16% годовых и в государственные ценные бумаги по ставке 12% годовых. При этом должны выполняться следующие условия: 1) Не менее 35% всех имеющихся средств необходимо разместить в кредитах. 2) Ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах. Определить такое размещение средств в кредиты и ценные бумаги, при котором прибыль банка будет наибольшей. 20 Решение. Введем обозначения: x 1 — средства размещенные в кредитах, млн руб., x 2 — средства размещенные в ценных бумагах, млн руб. Составим математическую модель задачи. Целевая функция будет иметь вид: 𝐿 = 0,16𝑥 1 + 0,12𝑥 2 → 𝑚𝑎𝑥 при ограничениях: { 𝑥 1 + 𝑥 2 ≤ 100, 𝑥 1 ≥ 35, −3𝑥 1 + 7𝑥 2 ≥ 0, 𝑥 1 ≥ 0, 𝑥 2 ≥ 0. Решим задачу графическим методом. 1) Рассмотрим первое неравенство системы ограничений. x 1 + x 2 ≤ 100. Построим прямую: x 1 + x 2 = 100. Пусть x 1 =0 => x 2 = 100. Пусть x 2 =0 => x 1 = 100. Найдены координаты двух точек (0, 100) и (100, 0). Соединяем их и получаем прямую (1). 2) Рассмотрим второе неравенство системы ограничений. x 1 ≥ 35. Построим прямую: x 1 = 35. Данная прямая параллельна оси OX 2 и проходит через точку (35, 0), получаем прямую (2). 3) Рассмотрим третье неравенство системы ограничений. - 3 x 1 + 7 x 2 ≥ 0. Построим прямую: - 3 x 1 + 7 x 2 = 0. Пусть x 1 =0 => x 2 = 0. Пусть x 1 =1 => -3 + 7 x 2 = 0 => x 2 = 3/7. Найдены координаты двух точек (0, 0) и (1, 3/7). Соединяем их и получаем прямую (3). 4) Находим общую область решений всех неравенств системы ограничений, получаем ОДР. 5) Строим вектор 𝐶 {0,16; 0,12}, его координатами являются коэффициенты функции L. Линия уровня L имеет уравнение 0,16x 1 + 0,12x 2 = сonst. 6) Перемещаем линию уровня по направлению вектора 𝐶 . Точкой выхода линии уровня L из области допустимых решений является точка A. Функция L достигает наибольшего значения в точке A. 21 Точка A одновременно принадлежит прямым (1) и (3). Составим систему уравнений: { 3𝑥 1 + 𝑥 2 = 9, 𝑥 1 + 2𝑥 2 = 8. Решая систему, получим координаты точки A(70; 30), в которой и будет оптимальное решение, т. е. x 1 = 70; x 2 = 30. L (A) = 0,16 ∙ 70 + 0,12 ∙ 30 = 14,8 млн руб. Следовательно, L max = 14,8 млн руб. Ответ. Максимальный годовой доход банка составит 14,8 млн руб. при условии размещения 70 млн руб. в кредитах и 30 млн руб. в ценных бумагах. 22 Заключение В представленной работе проведено исследование теоретических основ и практических результатов применения графического метода решения задач линейного программирования. В процессе выполнения работы были решены следующие задачи: 1) изучены основные понятия и определения линейного программирования; 2) изучены теоретические основы графического метода решения задач линейного программирования; 3) рассмотрены примеры решения задач линейного программирования графическим методом; 4) определена область применения графического метода решения задач линейного программирования; 5) рассмотрены примеры практического применения графического метода для решения экономических задач оптимизации. Изучив теоретические основы графического метода решения задач линейного программирования, установив область его применения, а также оценив практические результаты применения графического метода для решения прикладных экономических задач, можно сделать следующие выводы. В линейном программировании изучаются методы отыскания экстремальных значений линейной функции, называемой целевой, на аргументы которой наложены линейные ограничения, составляющие систему ограничений. Математическая модель экономической задачи оптимизации – совокупность, содержащая целевую функцию и систему ограничений. Графический метод используется для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции. Задачи линейной оптимизации решаются графическим методом в два этапа: построение области допустимых решений и нахождение в ее пределах оптимального решения. Достоинствами графического метода являются: наглядность, простота алгоритма решения и отсутствие большой трудоемкости вычислений. Основным его недостатком является ограниченность применения, так как решения задач выполняются на плоскости, что определяет число возможных переменных, их не может быть более двух. Прикладные задачи, связанные с отысканием оптимума заданной целевой функции при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования. Графический метод используется для решения практических экономических задач оптимизации. В этом случае составляется математическая модель, где 23 переменные – это некоторые экономические ресурсы, оптимальную величину которых необходимо найти для получения наилучшего результата экономической деятельности. Рассмотренные примеры практического применения графического метода для решения экономических задач оптимизации (использования ресурсов, выбора рациона питания, состава инвестиций) подтверждают выдвинутую гипотезу о том, что математическими методами успешно решаются экономические задачи. Таким образом, задачи выполнены, и поставленная цель исследовательской работы достигнута. Знания, приобретенные в процессе выполнения работы актуальны, и будут мной использованы для продолжения образования в ВУЗе, а также в будущей профессиональной деятельности. 24 Список литературы 1. Красс М. С., Чупрынов Б. П. Математика для экономистов: учебное пособие. — СПб.: Питер, 2007. (Серия «Учебное пособие») 2. Красс М. С., Чупрынов Б. П. Математические методы и модели для магистрантов экономики. — СПб.: Питер, 2010. (Серия «Учебное пособие»). 3. Кузнецов Б. Т. Математика для студентов вузов, обучающихся по спецальностям экономики и управления. — М.:ЮНИТИ-ДАНА, 2004. (Серия «Высшее профессиональное образование: Экономика и управление») 4. Печерских И. А., Семенов А. Г. Математические модели в экономике: учебное пособие. — Кемерово: КемТИПП, 2011 5. Интернет ресурсы: http://reshmat.ru |