Линейное программирование (стр. 1 из 8)
Министерство образования РФ
Южно-Уральский государственный университет
Кафедра Автоматики и управления
Реферат
по математическим основам теории систем
на тему
Линейное программирование
Выполнил:
Группа: ПС-263
Проверил: Разнополов О. А.
Челябинск
2003
При постановке задачи организационного управления, прежде всего, важно
1. Определить цель, преследуемую субъектом управления.
2. Установить, значениями каких переменных исследуемой системы можно варьировать.
Под целью будем понимать тот конечный результат, который необходимо получить путём выбора и реализации тех или иных управляющих воздействий на исследуемую систему. В производственно-коммерческой сфере цель заключается в том, чтобы либо максимизировать прибыль, либо минимизировать расходы.
Когда цель определена, оптимальным считается такой способ действий, который в наибольшей степени способствует достижению этой цели. Однако «качество» реализации процедуры выбора зависит от того, насколько полно известны допустимые альтернативы управляющих воздействий. Требуется выявить полное множество так называемых управляемых переменных. Важным моментом при принятии управляющих решений является идентификация неуправляемых переменных, то есть субъекта управления. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений управляемых переменных. Как цель, так и ограничения должны быть представлены в виде функций от управляемых переменных. Анализ модели должен привести к определению наилучшего управляющего воздействия на объект управления при выполнении всех установленных ограничений. При упрощённом описании реальных систем, на основе которого будет строиться та или иная модель, прежде всего следует идентифицировать доминирующие переменные, параметры и ограничения. Модель, будучи дальнейшим упрощением образа системы-оригинала, представляет собой наиболее существенные для описания системы соотношения в виде целевой функции и совокупности ограничений.
Наиболее важным типом моделей являются математические модели. В основе их построения лежит допущение о том, что все релевантные переменные, параметры и ограничения, а также целевая фукция количественно измеримы. Поэтому если
представляет собой
управляемых переменных и условия функционирования исследуемой системы хаарктеризуются 
ограничениями, то математическая модель может быть записана в следующем виде:Найти оптимум
(целевая функция) при ограничениях
Ограничения
– условия неотрицательности. Нахождение оптимума осуществляется для определения наилучшего значения целевой функции (максимума прибыли или минимума затрат, например). Полученное с помощью некоторой модели конкретное оптимальное решение является наилучшим только в рамках использования только этой модели. Не следует считать, что найденный оптимум – это действительно самое лучшее решение анализируемой задачи. Оно является наилучшим из всех возможных тогда, когда выбранный критерий оптимизации можно считать полностью адекватным конечным целям организации, в которой возникла исследуемая проблемная ситуация.2. Основные понятия теории оптимизации
2.1. Общая постановка задачи оптимизации
В общей задаче требуется найти вектор
из допустимой области
, который обращает в минимум целевую функцию q(x), т.е. такой 
, для которого 
(1)Если
существует, то он определяет слабый, глобальный (абсолютный) минимум q*(x) в допустимой . Слабый, т.к. удовлетворяет нестрогому неравенству. Глобальный, т.к. неравенство справедливо для любых x из области X. Минимум при 
сильный, если 
для 
. Если поменять знаки неравенств – получим сильный и слабый максимумы. Минимум в точке называется локальным (относительным), если найдётся такая окрестность O(x*) точки , что для всех 
имеет место . Если 
дифференцируема, то задача отыскания локальных минимумов сводится к нахождению стационарных точек, в которых обращаются в ноль частные производные q(x): 
(2)(2) – необходимое, но не достаточное условие. Достаточным условием существования в стационарной точке относительного минимума является положительная определённость квадратичной формы.
2.2. Ограничения на допустимое множество
Теорема Вейерштрасса: непрерывная функция, определённая на непустом замкнутом ограниченном множестве, достигает минимума (максимума) по крайней мере в одной из точек этого множества.
2.3. Классическая задача оптимизации
Состоит в нахождении минимума целевой функции
, где 
– точка в пространстве 
при начальных ограничениях типа равенств 
(3)Если (3) имеют место, то минимум q(x) называется условным минимумом. Если ограничения (3) отсутствуют, то говорят о безусловном минимуме.
Классический способ решения данной задачи состоит в том, что (3) используют для исключения из рассмотрения
переменных. При этом целевая функция приводится к виду 
(4),где через
обозначены неисключаемые переменные. Задача теперь состоит в нахождении значений , которые обращают в минимум q1 и на которые не наложено ограничений (задача на безусловный экстремум).2.4. Функция Лагранжа
Введём в рассмотрение вектор
и исследуем свойства функции 
(5) 
– функция Лагранжа, 
- множители Лагранжа. – функция n+m переменных 
.Рассмотрим стационарные точки функции
, которые получим, приравняв к нулю частные производные по 
и по 
: 
(6) 
(7)Если в стационарной точке (x*, y*) функция
достигает минимума, то обеспечивает минимум функции q(x) и при выполнении ограничений (3), т.е. даёт решение задачи.Задача на условный минимум целевой функции q(x) при наличии ограничений типа равенств сводится к задаче на определение стационарных точек функции Лагранжа
.3. Линейное программирование: формулировка задач и их графическое решение