ВВЕДЕНИЕ

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

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

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

2) необходимо, чтобы судно было максимально устойчивым при сильном волнении и сильном ветре;

3) необходимо, чтобы судно имело наименьшую осадку (в случае, если судно предназначается для эксплуатации на мелких водоемах).

Задачи такого характера, получившие название экстремальных задач возникают в самых различных областях человеческой деятельности. В настоящем пособии вы познакомитесь с некоторыми этапом историк зарождения теории экстремальных значений величин, получивших в дальнейшем развитие и обобщение. Содержание рассматриваемых в пособии задач самое разнообразное, разнообразны и методы их решения. Однако общее в решении экстремальных задач заключается в самом характере применения того или иного математического метода. Дело в том, что по самой своей природе математические методы не могут прилагаться непосредственно к действительности, а применяются только к математическим моделям того или иного явления. Что же такое математическая модель?

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

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

В последние 20—25 лет в прикладной математике огромное внимание стало уделяться новому классу задач оптимизации, заключающихся-в нахождении в заданной области точек наибольшего или наименьшего значения некоторой целевой функции, зависящей от большого числа переменных. Те задачи, в которых целевая функция связана с переменными линейной зависимостью и область точек задана линейными ограничениями, принято называть задачами линейного программирования. Построению математической модели различных типов задач линейного программирования и математическим методам ее исследования посвящается § 5 настоящего пособия. Кроме цели ознакомления с одним из важнейших современных направлений прикладной математики — линейным программированием, этот параграф существенно расширяет представления о теории систем линейных уравнений и неравенств и их прикладных аспектах.

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

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

На помощь человеку приходят специальные математические методы теории линейного программирования. Например, идею симплексного метода линейного программирования можно представить следующим образом. В некоторой урне находится миллион пронумерованных шаров. Задача заключается в том, чтобы за возможно меньшее число попыток вынуть шар, имеющий номер I 000 000. Естественно, шар выбирается вслепую. Нетрудно догадаться, что в самом худшем случае придется сделать миллион попыток. Если же в провесе вынимания шаров внести одно условие, заключающееся в том, что все шары с номерами, меньшими чем номер только что вынутого шара, сразу из урны исчезают, то решение задачи сводится к 20—30 попыткам. Аналогичная идея заложена и в алгоритме симплексного метода. Получив некоторое решение, мы в дальнейшем рассматриваем из возможного огромного набора остальных решений только то, которое лучше этого. Таким образом осуществляется сравнительно быстро последовательный переход к оптимальному решению.