Введение в линейное программирование
Математические теории и методы играют важную роль во многих науках, начиная с физики и кончая психологией и лингвистикой. В конце XIX и начале XX вв. развитие математики складывалось главным образом под влиянием запросов физики и техники. Математический аппарат преимущественно использовался как инструмент расчета. Однако современная экономическая ситуация потребовала ответов на вопросы: как управлять созданной техникой, расходовать имеющееся сырье, ресурсы. Эти вопросы оказались актуальны и важны. Ясно, что рациональное использование имеющихся ресурсов может дать экономический эффект гораздо выше, чем создание новых. Поэтому развитие экономики поставило задачи оптимального управления производством и планирования. Возникла потребность в новых математических методах и дисциплинах, которые позволили бы разрешать эти важные экономические проблемы. Такие задачи привели к появлению новых математических дисциплин: линейного и нелинейного программирования, теории игр, теории массового обслуживания и т.д. А развитие современной вычислительной техники, персональных компьютеров и информационных технологий дало мощный толчок к применению математических методов и программных продуктов, реализующих эти алгоритмы.
В самых разных областях нашей жизни мы постоянно сталкиваемся по сути дела с одним и тем же классом задач. Нам известна полностью или частично ситуация, в которой мы находимся, и множество возможных альтернативных вариантов нашего дальнейшего поведения. Естественно возникает вопрос: какой из вариантов выбрать, а от каких отказаться. Грубо говоря, в решении этого вопроса и заключается проблема управления. Она с равным основанием может относиться к поведению отдельного человека или группы людей, к развитию тех или иных хозяйственных процессов или экономики в целом, к разработке каких-либо операций и т. п. Итак, необходимо остановиться на одном из допустимых вариантов, отыскать план. Здравый смысл подсказывает нам, что нужно выбрать «наилучший» вариант, который принесет наибольшую выгоду.
Сам по себе вопрос: какой вариант выбрать, ни на йоту не приближает нас к решению задачи управления, он даже не формулирует ее, поскольку абсолютно не ясно, что означают слова «наилучший вариант», «наилучшая выгода». Определение этого и составляет одну из важных проблем, без решения которой невозможны ни постановка, ни решение задачи управления. По существу речь идет о проблеме цели развития управляемой системы.
Цели, вообще говоря, могут быть разными. Применительно к хозяйственному объекту, в качестве цели могут выступать требования обеспечить максимум выпускаемой продукции при известном объеме имеющихся ресурсов, минимум затрат на производство фиксированной продукции, максимум получаемой прибыли, минимум транспортных расходов для оказания каких-либо услуг и т. д. Если цель сформулирована, то понятие «наилучший» становится четко определенным. «Наилучший» или, обычно говорят, оптимальный вариант отвечает двум требованиям: во-первых, он является одним из допустимых (или возможных) и, во-вторых, обеспечивает максимум или минимум (по смыслу) поставленной цели.
Таким образом, общий смысл широкого круга задач управления прост. Постановка задачи управления средствами математического программирования заключается в следующем. Формально записывается совокупность условий деятельности управляемого объекта, которая называется системой ограничений. Например, для производственного предприятия задаются объемы ресурсов, которые можно использовать (не обязательно полностью), возможности производственных мощностей и т. д. Вводятся переменные задачи, которые по своему физическому смыслу неотрицательны. Совокупность условий деятельности объекта записывается в виде системы уравнений и неравенств, которая определяет множество допустимых вариантов. Выбор оптимального варианта осуществляется с помощью, так называемой целевой функции, которая определяет цель развития объекта управления.
Если заданы система ограничений и целевая функция, – это значит, что задача управления поставлена. Те задачи, в которых целевая функция связана с переменными линейной зависимостью и область ограничений задана линейными уравнениями и неравенствами, называются задачами линейного программирования (ЗЛП). Слово «программирование» первоначально отнюдь не означало какую-то связь с ЭВМ, языками программирования и т. д. Оно означало, что в результате решения задачи вы получите некоторую программу действий – оптимальный план для достижения «наилучшего» результата. Хотя сейчас, конечно, все реальные задачи решаются на компьютере и необходимые программы, реализующие известные алгоритмы, написаны.
Основоположником линейного программирования как научного направления в нашей стране стал выдающийся советский математик и экономист лауреат Ленинской и Нобелевской премий академик А.В. Канторовича. В его работе «Математические методы организации и планирования производства» (1939 г.) впервые была сформулирована задача ЛП, описывающая реальную экономическую ситуацию, и разработан алгоритм ее решения. В США исследование операций началось в годы Второй мировой войны, прежде всего для решения военных вопросов. Казалось бы, невинные задачи, о составлении смесей орехов, первоначально возникли при планировании военных операций. Позже появились и их мирные приложения, когда выяснилось, что использование линейного программирования способно дать большой экономический эффект для решения разнообразных вопросов. Из американских математиков, внесших вклад в развитие ЛП, нужно отметить Дж. Данцига («Линейное программирование, его применения и обобщения». – М.: Прогресс, 1966).
Как же решать задачи линейного программирования?
Простейший метод, казалось бы, напрашивается сразу. Стоит рассмотреть все допустимые варианты, подсчитать, какую целесообразность имеет каждый из них, и станет ясно, какой вариант наилучший. Однако на поверку, этот метод оказывается самым сложным, а иногда – нереален, так как число допустимых вариантов необозримо и бесконечно. Но перебирать варианты – не столь уж абсурдная идея, именно она легла в основу многих алгоритмов, в частности симплекс-метода. Только перебор этот предлагается осуществлять определенным образом: выбрав некоторое допустимое решение, в дальнейшем из огромного числа вариантов остальных решений, рассматриваем только то, которое заведомо лучше уже найденного. Такой целенаправленный перебор сравнительно быстро приводит к оптимальному решению. В этом и состоит идея симплексного метода.
ГЛАВА II
Основные типы задач линейного
программирования и методы их решения