Математическое программирование

Методы оптимальных решений – учебная дисциплина, в которой рассматриваются задачи поиска оптимального (минимального или максимального значения функции при заданных ограничениях на переменные). Такие задачи относятся к задачам математического программирования. 1. Математическое программирование Основные определения Математическое программирование – раздел математики, в котором изучаются и разрабатываются теоретические положения и конкретные численные методы для решения планово-экономических задач (или на языке математики – экстремальных задач с ограничениями). Определение 1. Функция F, экстремальное значение которой необходимо найти, называется целевой или ценовой, или показателем эффективности. Характер экстремума обозначается следующим образом: Определение 2. Условие, описывающее реальную ситуацию и представленное в виде математических выражений, называют системой или областью ограничений. Определение 3. Целевая функция в совокупности с системой ограничений, выраженные математическими символами, образуют математическую модель задачи. В математическую модель, как правило, входят неизвестные величины, определяющие характер целевой функции и системы ограничений. Определение 4. Группы чисел, которые, будучи подставленными вместо неизвестных, дают конкретное числовое значение целевой функции, называются решением или планом задачи. Определение 5. Решение (или план) называется допустимым, если все его значения удовлетворяют системе ограничений. Определение 6. Решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным. В зависимости от вида целевой функции и математических выражений, входящих в систему ограничений, математическое программирование разделяют на разные типы. Некоторые из них: 1. Если целевая функция и все выражения системы ограничений являются линейными (содержат неизвестные только первой степени), то математическое программирование, рассматривающее такие задачи, называется линейным программированием. 2. Если в математической модели целевая функция или хотя бы одно из ограничений системы нелинейны, программирование называется нелинейным. 3. Если на искомое решение налагается условие целочисленности неизвестных, то такой раздел называется целочисленное программирование. 4. Если известно, что за конкретный промежуток времени параметры математической модели изменяются, то такое программирование называется динамическим. 2. Линейное программирование Примеры математических моделей задач линейного программирования Наиболее разработанной и простой частью математического программирования является линейное программирование в силу достаточной изученности линейных функций и возможности прогнозирования их поведения. Итак, соотношения (1.15) и (1.16) составляют математическую модель задачи. Пример 2. Задача об использовании или распределении ресурсов Мебельная фабрика выпускает 3 вида изделий: шкафы, столы и стулья. В процессе их изготовления используются фрезерные, сверлильные и шлифовальные станки. Причем в процессе изготовления шкафа фрезерный станок работает 0,25 ч, сверлильный – 0,18 ч, шлифовальный – 0,24 ч; стола: фрезерный – 0,2 ч, сверлильный – 0,13 ч, шлифовальный – 0,19 ч; стула: фрезерный 0,3 ч, сверлильный – 0,11 ч, шлифовальный – 0,14 ч. Ресурс рабочего времени станков: фрезерного – 250 ч, сверлильного – 300 ч, шлифовального – 320 ч. Согласно плановому заданию, необходимо изготовить не менее 150 шкафов, столов – не менее 200, стульев – не менее 400. Прибыль за каждый шкаф составляет 5 ден. ед., за стол – 3 ден. ед., за стул – 2 ден. ед. Требуется составить такой план выпуска изделий, при котором требуемые объемы по каждому виду изделий были бы выполнены, ресурсы времени по каждому виду оборудования не превышены, полученная прибыль была бы максимальной. Решение. Пусть х1 – количество шкафов, х2 – количество столов, х3 – количество стульев. Построим математическую модель задачи. Прибыль (целевая функция) составляет: . Система ограничений примет вид работа на фрезерном станке работа на сверлильном станке работа на шлифовальном станке ограничение по количеству шкафов ограничение по количеству столов ограничение по количеству стульев переменные могут принимать только целые значения Пример 3. Задача составления смесей На свиноферме производится откорм свиней. Известно, что каждая должна получать не менее 6 единиц вещества M1, не менее 8 – M2, не менее 12 – М3. Существуют 3 вида кормов. Информация по стоимости этих кормов и содержанию единиц каждого вещества в единице корма находится в таблице: Вид корма Вещества Стоимость вида корма M1 М2 M3 1 2 1 3 2 2 1 2 4 3 3 3 1,5 2 2,5 Требуется обеспечить наиболее дешевый рацион питания животных в виде комбикорма. Решение. Пусть х1, х2, х3 – количество единиц корма каждого вида. Тогда математическая модель задачи имеет вид Целевая функция (затраты на покупку кормов): . количество вещества М1 в рационе количество вещества М2 в рационе количество вещества М3 в рационе неотрицательность переменных