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

Математические теории и методы играют важную роль во многих науках, начиная с физики и кончая психологией и лингвистикой. В конце XIX и начале XX вв. развитие математики складывалось главным образом под влиянием запросов физики и техники. Математический аппарат преимущественно использовался как инструмент расчета. Однако современная экономическая ситуация потребовала ответов на вопросы: как управлять созданной техникой, расходовать имеющееся сырье, ресурсы. Эти вопросы оказались актуальны и важны. Ясно, что рациональное использование имеющихся ресурсов может дать экономический эффект гораздо выше, чем создание новых. Поэтому развитие экономики поставило задачи оптимального управления производством и планирования. Возникла потребность в новых математических методах и дисциплинах, которые позволили бы разрешать эти важные экономические проблемы. Такие задачи привели к появлениюновых математических дисциплин: линейного и нелинейного программирования, теории игр, теории массового обслуживания и т.д. А развитие современной вычислительной техники, персональных компьютеров и информационных технологий дало мощный толчок к применению математических методов и программных продуктов, реализующих эти алгоритмы.

В самых разных областях нашей жизни мы постоянно сталкиваемся по сути дела с одним и тем же классом задач. Нам известна полностью или частично ситуация, в которой мы находимся, и множество возможных альтернативных вариантов нашего дальнейшего поведения. Естественно возникает вопрос: какой из вариантов выбрать, а от каких отказаться. Грубо говоря, в решении этого вопроса и заключается проблема управления. Она с равным основанием может относиться к поведению отдельного человека или группы людей, к развитию тех или иных хозяйственных процессов или экономики в целом, к разработке каких-либо операций и т. п. Итак, необходимо остановиться на одном из допустимых вариантов, отыскать план. Здравый смысл подсказывает нам, что нужно выбрать «наилучший» вариант, который принесет наибольшую выгоду.

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

Цели, вообще говоря, могут быть разными. Применительно к хозяйственному объекту, в качестве цели могут выступать требования обеспечить максимум выпускаемой продукции при известном объеме имеющихся ресурсов, минимум затрат на производство фиксированной продукции, максимум получаемой прибыли, минимум транспортных расходов для оказания каких-либо услуг и т. д. Если цель сформулирована, то понятие «наилучший» становится четко определенным. «Наилучший» или, обычно говорят, оптимальный вариант отвечает двум требованиям: во-первых, он является одним из допустимых (или возможных) и, во-вторых, обеспечивает максимум или минимум (по смыслу) поставленной цели.

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

Если заданы система ограничений и целевая функция, – это значит, что задача управления поставлена. Те задачи, в которых целевая функция связана с переменными линейной зависимостью и область ограничений задана линейными уравнениями и неравенствами, называются задачами линейного программирования (ЗЛП). Слово «программирование» первоначально отнюдь не означало какую-то связь с ЭВМ, языками программирования и т. д. Оно означало, что в результате решения задачи вы получите некоторую программу действий – оптимальный план для достижения «наилучшего» результата. Хотя сейчас, конечно, все реальные задачи решаются на компьютере и необходимые программы, реализующие известные алгоритмы, написаны