Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Оптимизация и математические методы принятия решений
Теория:
Задача линейного программирования и различные формы ее записи. Приведение общей задачи ЛП к симметричной форме записи.
Если целевая функция и система ограничений линейны, то задача математического программирования называется задачей линейного программирования (ЗЛП).
Формулировка ЗЛП.
* означает "³", "£" или "=".
Основная форма ЗЛП
Симметричная форма ЗЛП
Общая задача линейного программирования
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1, X2, Xn, удовлетворяющих ограничениям в виде равенств:
A11X1 + A12X2 + … + A1nXn = B1;
A21X1 + A22X2 + … + A2nXn = B2;
……………………………………
Am1X1 + Am2X2 + … + AmnXn = Bm;
Xj ≥ 0, j=1,…,n
и обращающих в максимум линейную функцию этих переменных:
E = C1X1 + C2X2 + … + CnXn Þ max
При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:
Bj ≥ 0, j=1,…,n
Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:
перейти от минимизации целевой функции к ее максимизации;
изменить знаки правых частей ограничений;
перейти от ограничений-неравенств к равенствам;
избавиться от переменных, не имеющих ограничений на знак.
Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности.
Дата публикования: 2015-11-01; Прочитано: 3754 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!