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

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

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

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

при ограничивающих условиях.

где a,-, bj, Xj — заданные постоянные величины.

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

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (2.1) при выполнении условий неравенств (2.2) — нетривиальных и (2.4) — тривиальных.

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

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

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

В базисном решении все (п — т) свободные переменные равны нулю.

Допустимое базисное решение (опорный план) содержит только неотрицательные базисные переменные, а свободные равны нулю.

Допустимое базисное решение является невырожденным, если все базисные переменные строго положительны, и вырожденным — в противном случае.

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

Совокупность чисел X = (х_х, х₂,… х_п), удовлетворяющих тривиальным и нетривиальным ограничениям задачи, называется допустимым решением (в экономических задачах — планом). Совокупность допустимых решений формирует область допустимых решений (ОДР).

План X* = (, Г|*, х₂, …, х,*), при котором целевая функция (2.1) задачи принимает экстремальное значение, называется оптимальным.

В случае когда требуется найти минимум функции F (X) = = (СХ + с₂х₂ + … + с"х"), можно перейти к нахождению максимума функции 1'(Х) = -F (X) — -(f.'i-Ti + с₂х₂ + … + c_ttx"), так как minF (X) = -F{X), тогда полученное решение целевой функции следует записать с обратным знаком.

Контрольные вопросы и задания.

• 1. Каковы особенности задач линейного программирования?
• 2. Какое решение системы линейных уравнений является планом?
• 3. Что называют планом ОЗЛП, опорным планом, оптимальным планом?
• 4. Какой опорный план называется вырожденным, невырожденным?
• 5. Как привести к канонической форме ОЗЛП: а) если требуется найти минимум линейной функции цели; б) если функциональные ограничения заданы в виде неравенств разного вида > и