Главная > Разное > Математика в биологии и медицине
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

В большинстве организационных задач, решаемых методами исследования операций, существенную роль играют экономические аспекты. Эти аспекты могут быть выражены более или менее неявно, как в только что рассмотренном случае, где речь шла об экономии времени клиентов и об экономичном использовании рабочего времени обслуживающего устройства. Если бы потерю времени клиентами и обслуживающим устройством можно было выразить какими-то денежными показателями, то удалось бы провести общий анализ, показывающий чистые издержки для общества. Однако в общем случае отыскание наилучшего соотношения между противоречивыми требованиями, которые трудно выразить количественно в единой шкале, основывается на интуитивном суждении.

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

Пусть имеется различных видов товаров, и пусть выпуск товара за некоторый определенный промежуток времени составляет единиц. Если прибыль на единицу товара равна то выражение для общей прибыли z имеет вид

Если какое-либо значение отрицательно, то соответствующий товар продается с убытком.

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

Допустим далее, что общий объем имеющихся ресурсов постоянен и составляет b человеко-часов и что для производства одной единицы товара необходимо а, человеко-часов. Следовательно, общее количество ресурсов, необходимое для производства количеств товара равно

не может превышать b, т. е.

Аналогичные соображения применимы также к числу часов машинного времени определенного станка, запасам различных материалов, ресурсам, имеющимся для распределения и продажи, и т. д. Если имеется всего линейных ограничений, то их можно выразить в виде следующего обобщения формулы (4.9):

(4.10)

Таким образом, математическая задача состоит в том, чтобы максимизировать функцию z, заданную формулой (4.7), при ограничениях, налагаемых выражениями (4.8) и (4.10). В этом довольно простом варианте задачи, часто встречающейся на практике, как функция z, так и ограничивающие условия являются линейными функциями Такая модель называется моделью линейного программирования. Для решения задач такого рода существует множество стандартных методов, но если число переменных или ограничений велико, то на практике может потребоваться значительный объем алгебраических выкладок.

К счастью, разработаны программы для электронных вычислительных машин, позволяющие получить решение таких задач.

Мы не будем рассматривать здесь в деталях теорию построения моделей линейного программирования, хотя приводимая далее геометрическая интерпретация может оказаться очень полезной для наглядного представления некоторых важных особенностей этой задачи. (Исчерпывающее изложение теории линейного программирования читатель может найти в любом руководстве по данному предмету, например в книге Гарвина [28].) Допустим вначале, что имеются только два различных товара в количествах Все возможные количества товаров можно изобразить на плоскости точками с координатами Так как необходимо, чтобы и сразу же ограничиваемся рассмотрением положительного квадранта плоскости. Рассмотрим далее линейное ограничение b). Все точки, в которых удовлетворяется это неравенство, лежат в полуплоскости, расположенной по одну сторону прямой (там же, где и начало координат, если Легко показать, что в общем случае все решения, допускаемые при этих ограничениях, лежат внутри многоугольника, образованного прямыми:

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

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

Мы умышленно выбрали пример, когда функция z и соответствующие ограничения являются линейными. Однако в экономике часто действует закон уменьшения прибыли, согласно которому увеличение производства какого-либо товара в какой-то момент приводит к уменьшению прибыли на единицу продукции.

Кроме того, может случиться, что прибыли, получаемые при сбыте различных товаров, не независимы, как молчаливо здесь предполагалось, а определенным образом связаны друг с другом. Для того чтобы учесть влияние таких факторов, необходимо выбирать функцию z более общего вида. Если z можно выразить как квадратическую функцию от на которую налагаются определенные ограничения, являющиеся по-прежнему линейными, то в этом случае говорят, что получена модель квадратического программирования.

В более общем случае условие линейности ограничений можно ослабить и рассматривать модель математического программирования в следующем виде:

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

Еще более сложная задача, имеющая большое значение для практики, состоит в том, чтобы найти оптимальную стратегию для определенного промежутка времени. Допустим, известно, что условия изменяются от месяца к месяцу. Казалось бы, что в этом случае можно решать задачу линейного программирования для каждого месяца в отдельности. Но на самом деле нет никакой уверенности в том, что такой метод вообще даст наилучший результат, так как способ производства в один из месяцев может повлиять в ту или другую сторону на условия работы в следующем месяце. Для решения такого рода задач можно использовать метод динамического программирования, основные принципы которого разработаны главным образом в работах Р. Веллмана.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление