Линейного программирования

Лекция 6. Общая постановка оптимальной задачи при

проектировании информационных систем. Основная задача

Задача принятия решений, в том числе и по ИС, характеризуется:

- множеством переменных, значения которых выбирает лицо, принимающее

решение (ЛПР). Будем называть их стратегиями или управляющими перемен-

ными и будем обозначать ;

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

- множеством переменных, значения которых не регулируются ЛПР. Эти переменные могут быть внутренними переменными и тогда их называют параметрами системы ;

- в других случаях эти переменные могут быть внешними, которые изменяются независимо от ЛПР, и тогда их называют возмущениями или внешней средой ;

- ограничения на управляющие и выходные переменные, а также ресурсы системы, которые задаются в виде ресурсных функций от управляющих и выходных переменных;

- целевая функция – критерий эффективности , который зависит от принятых стратегий параметров системы и возмущений .

Оптимальная задача выбора решений ставится следующим образом:

надо найти

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

, .

Очень часто вместо ограничений , используются ограничения .

Выбор метода и алгоритма решения.

Переменные в целевой функции и ограничениях можно зафиксировать, так как они от нас не зависят, т.е. принимаем либо максиминные решения либо усредненные решения по методу Байеса-Лапласа. Тогда оптимизацию можно проводить только по параметрам .Для нахождения оптимального решения сформулированной выше оптимальной задачи в зависимости от вида и структуры целевой функции и ограничений используют те или другие методы теории оптимальных решений (методы математического программирования). К ним относятся:

-линейное программирование, если целевая функция и ограничения линейны по ,

-нелинейное программирование, если целевая функция и ограничения нелинейны по .

Итак, для выбора варианта построения ИС необходимо решать оптимальные задачи, которые могут быть сформулированы так:

максимизировать при ограничениях

, …, .

Среди разных разделов математического программирования наиболее развитым и законченным является линейное программирование (ЛП).

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

Рассмотрим один пример: определения оптимального ассортимента.

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

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

максимизировать при ограничениях , .

Общая постановка задачи линейного программирования. Имеется ряд неотрицательных переменных . Требуется так выбрать значения этих переменных, чтобы: 1) выполнялись некоторые ограничения, имеющие вид линейных неравенств или равенств относительно переменных ; 2) некоторая линейная функция тех же переменных обращалась в максимум (минимум). Математический аппарат линейного программирования предназначен специально для решения таких задач. Может возникнуть вопрос: а нужен ли такой специальный аппарат? Нельзя ли просто продифференцировать целевую функцию по аргументам , приравнять производные нулю и решить полученную систему уравнений? Нет, оказывается, сделать этого нельзя. Так как функция линейна, производные от нее по всем аргументам постоянны и нигде в нуль не обращаются. Максимум (или минимум) функции , если он существует, достигается всегда где-то на границе области возможных значений , т.е. там, где начинают действовать ограничения. Математический аппарат линейного программирования позволяет нам последовательно, в кратчайшие сроки, обследовать границы области возможных значений и найти на этих границах то решение, которое является оптимальным, т.е. такую совокупность значений , при которой линейная функция обращается в максимум или минимум.

Основная задача линейного программирования.

Дата добавления: 2014-01-06