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

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

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

Раздел 1. Методы и модели

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

В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны.

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

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

Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными.

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

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

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

В целом экономико-математическая формулировка и модель общей задачи линейного программирования имеет следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

(1.1.1)

при условиях-ограничениях:

где заданные постоянные величины.

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1.1.1) при выполнении условий (1.1.2) и (1.1.4).

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1.1.1) при выполнении условий (1.1.3) и (1.1.4).

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

План , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции

,

можно перейти к нахождению максимума функции

, т.к. .

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

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

Запишем в основной задаче линейного программирования ограничение (1.1.3) в векторной форме

, (1.1.5)

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

План называется опорным планом основной задачи линейного программирования, если система векторов , входящих в разложение (1.1.5) с положительными коэффициентами линейно независима.

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

Опорный план называется невырожденным, если он содержит ровно т положительных компонент. Если в опорном плане число положительных компонент меньше т, то план является вырожденным.