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

Методы математического программирования представляют собой класс моделей, применяемых для формализации задач планирования целенаправленной деятельности, предусматривающих распределение ограниченного количества ресурсов разных видов. Подобного рода задачи решаются в различных отраслях деятельности: в экономике, при разработке проектов, составлении расписаний, планировании во­енных операций и т.п. Модели математического программирования относятся к категории детерминированных моделей. Термин програм­мирование в применении к рассматриваемому типу задач понимается как поиск наилучших планов (от английского слова programming - со­ставление плана, программы действий). Когда говорят о задачах ма­тематического программирования, имеют в виду задачи, цель которых состоит в повышении эффективности промышленных, транспортных систем, систем управления деятельностью учебных, проектных, на­учных организаций.

Математическое программирование подразделяется на линейное, целочисленное, нелинейное, динамическое программирование. Рас­смотрим некоторые постановки задач, методы и алгоритмы их реше­ния.

5.1. Математические постановки задач, приводящие

к моделям линейного программирования

Задачи линейного программирования относятся к категории опти­мизационных. Они находят широкое применение в различных облас­тях практической деятельности: при организации работы транспорт­ных систем, в управлении промышленными предприятиями, при состав­лении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального плани­рования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку: найти значения переменных , доставляющие оптимум заданной линейной формы при выполнении системы огра­ничений, представляющих собой также линейные формы.

Рассмотрим примеры конкретных постановок задач, формализация которых приводит к моделям линейного программирования. Вначале рассмотрим задачу определения оптимального ассортимента. Имеет­ся p видов ресурсов в количествах и q видов изделий. Задана матрица , где a_ij характеризует нормы расхода i-го ре­сурса на единицу j-го изделия (j=1, 2, …, q). Эффективность выпуска единицы j-го изделия характеризуется показателем с_j, удовлетворяю­щим условию линейности. Требуется определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффек­тивности принимает наибольшее значение. Обозначим количество еди­ниц j-го изделия, выпускаемых предприятием, через х_j, тогда матема­тическая модель задачи будет иметь следующий вид:

Кроме указанных ограничений по ресурсам в модель могут быть введены дополнительные ограничения на планируемый выпуск продук­ции x_j  x_j0, условия комплектности изделий и т.п.

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

Задача составления титульного списка. Сформулирован пере­чень задач, решаемых на первом этапе автоматизации. После состав­ления перечня задач, включаемых в первый этап разработки, необхо­димо оценить требуемый состав ресурсов на их разработку и требуе­мое время для их внедрения. Пусть время, требуемое на разработку задач, превышает заданный срок ввода первой очереди в эксплуатацию, тогда возникает проблема составления титульного списка, т.е. возни­кает необходимость ограничения перечня задач, автоматизируемых на первом этапе. Проблема выбора комплекса задач из сформированного перечня в условиях дефицита времени и ресурсов на разработку всего перечня задач, выполняемых на первом этапе автоматизации, называ­ется задачей составления титульного списка. Таким образом, форму­лировка задачи будет выглядеть так: требуется сформировать перечень задач, подлежащих автоматизации (титульный список), с учетом име­ющихся материальных, временных, трудовых и прочих ресурсов.

Задача определения оптимальной очередности разработки встает перед проектировщиками на следующем этапе проектирования после составления титульного списка задач, подлежащих автоматиза­ции. Суть задачи состоит в распределении ресурсов, выделяемых на разработку системы, между задачами и упорядочении процесса разра­ботки задач во времени. Формализованная постановка данной задачи будет выглядеть следующим образом: необходимо оптимизировать некоторый функционал при выполнении ограничений на потребление ре­сурсов, выделяемых на разработку проекта, не больше заданного объе­ма в заданном временном интервале.

При выполнении оговоренных условий и обозначений задача распре­деления ресурсов между операциями проекта обычно формулируется следующим образом: имеется комплекс операций, для которых опре­делены отношения частичного порядка, задаваемые в виде графа G. Необходимо распределить ресурсы, заданные в количестве R_j(t), меж­ду операциями комплекса таким образом, чтобы некоторая целевая функция достигла своего экстремального значения.

Рассмотрим еще одну постановку задачи, возникающей при орга­низации деятельности транспортных предприятий, так называемую транспортную задачу. В некоторых пунктах a₁ a₂,..., а_n находятся склады, в которых хранятся товары в количествах X_1,X₂.,..,X_n соот­ветственно. В пунктах b₁ ,b₂,...,b_m находятся потребители, которым необходимо поставить эти товары в количествах, не меньших, чем Y_{1 ,}Y₂,,..,Y_m соответственно. Обозначим через c_ij стоимость перевозки еди­ницы груза из пункта а_i. в пункт b_j , x_ij - количество товара, перевозимо­го из пункта а_i в пункт b_j. Для того, чтобы удовлетворить запросы по­требителей, необходимо, чтобы выполнялась система неравенств

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

Удовлетворить сформулированным условиям можно бесконечным числом способов. Для того, чтобы выбрать оптимальное правило пе­ревозок, необходимо сформулировать критерий, который будет отражать представления о цели функционирования транспортного предприятия. В данной задаче одним из возможных критериев может выступать сто­имость перевозок, тогда вид функционала будет определяться очевид­ным образом:

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