Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП)
Цель работы
1. Изучить понятие математической модели.
2. Рассмотреть примеры задач линейного программирования.
3. Усвоить графический метод решения задач линейного программирования.
4. Научиться приведению задач линейного программирования к стандартной форме.
Теоретическое введение
Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП)
Линейное программирование – это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные. Методами линейного программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и т.п.
Любое описание некоторой задачи в виде формул, алгоритмов называется математической моделью этой задачи.
Построение математической модели задачи включает следующие этапы:
1) выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Переменными задачиназываются величины х1, х2, …хn, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора A = (х1, х2, …хn).
Система ограниченийвключает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий.
Целевой функциейназывают функцию переменных задачи, которая характеризует качество выполнения задачи, и экстремум которой требуется найти.
Общая задача математического программирования формулируется следующим образом:
найти экстремум целевой функции и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.
Функция (1.1) называется целевой функцией, а ограничения (1.2) – системой ограничений задачи.
Если по условию задачи требуется найти такие значения переменных, при которых целевая функция (1.1) будет иметь максимальное значение, то говорят, что целевая функция подлежит максимизации (или направлена на максимум). Если требуется, чтобы целевая функция принимала минимальное значение, то говорят, что она подлежит минимизации (направлена на минимум).
Обратите внимание на полученный результат. Целевая функция является линейной функцией переменных х1, х2, …хn; сами ограничения на значения переменных х1, х2, …хn имеют вид линейных неравенств. Все это и определило название этого класса задач – задачи линейного программирования.
В большинстве задач (но не всегда) требуется, чтобы переменные принимали неотрицательные значения (ограничение на неотрицательность); в некоторых задачах требуется, чтобы переменные принимали целочисленные значения (ограничения на целочисленность).
Линейная математическая модель может быть построена для многих задач, решаемых на практике.
Любые значения переменных, удовлетворяющие ограничениям задачи (1.2), называются допустимыми решениями (независимо от того, какое значение при этом принимает целевая функция). Большинство задач имеет бесконечно много допустимых решений. Все множество допустимых решений представляет собой область допустимых решений (ОДР).
Допустимые значения переменных, при которых целевая функция принимает максимальное или минимальное значение (в зависимости от постановки задачи), т.е. достигает экстремума, представляют собой оптимальное решение.