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

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции

max(min) Z (30)

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

a₁₁×x₁ + a₁₂×x₂ + … + a_1n×x_n ,

a₂₁×x₁ + a₂₂×x₂ + … + a_2n×x_n

..................... (31)

a_m1×x₁ + a_m2×x₂ + … + a_mn×x_{n .}

(32)

где , b_i, c_i, m, n – заданные постоянные величины.

Так записывается общая задача линейного программирования в развернутой форме; знак означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или другую сторону).

Систему ограничений (31) называют функциональными ограничениями ЗЛП, а ограничения (32) – прямыми.

Вектор X, удовлетворяющий системе ограничений (31), (32), называется допустимым решением или планом ЗЛП, т.е. ограничения (31), (32) определяют область допустимых решений, или планов задачи линейного программирования (область определения ЗЛП).

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

Матричная форма записи задач линейного программирования имеет следующий вид:

A×X X

Здесь С = (с₁, c₂, …, c_n) – вектор оценок задачи линейного программирования; A – матрица коэффициентов ; B – вектор ресурсов.

.

К математическим задачам линейного программирования приводят исследования конкретных производственных ситуаций, которые в том или ином виде

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

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