51

Раздел 1

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1. Предмет математического программирования

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

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

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

1.1. Модель задачи математического программирования

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

Математическая модель – это символическая запись (в виде уравнений, неравенств, систем уравнений, функций и т.д.), отражающая определенные особенности, свойства изучаемых реальных явлений, процессов или объектов.

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

Модель задачи математического программирования включает:

1) план задачи (вектор управления, решение, стратегия, поведение и др.) – совокупность неизвестных величин , действуя на которые, систему можно совершенствовать;

2) целевую функцию (показатель эффективности, критерий оптимальности, функционал задачи и др.) – функция, экстремальное значение которой нужно найти в условиях экономических возможностей. Целевую функцию обозначим . Это может быть прибыль, объем выпуска или реализации, затраты производства, уровень обслуживания, число комплектов, отходы и т.д.;

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

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

Найти план , доставляющий экстремальное значение целевой функции , т.е.

при ограничениях

.

Из экономических или физических соображений на план задачи или некоторые его компоненты (координаты), как правило, налагаются условия неотрицательности

,

иногда – целочисленности.

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