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

Рассмотренные выше примеры задач линейного программи­рования позволяют сформулировать общую задачу линейного программирования.

Дана система m линейных уравнений и неравенств с n пере­менными

(1.20)

. (1.22)

и линейная функция . (1.21)

Необходимо найти такое решение Х = (х ₁, х ₂, …, x_j,…,x_n), при котором линейная функция (1.21) принимает оптималь­ное (т.е. максимальное или минимальное) значение.

Система (1.20) называется системой ограничений, а функция F - линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

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

.

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х = (х ₁, х ₂, … ,x_n)системы ограничений (1.20), удовлетворяющее условию (1.22), при котором линейная функция (1.21) принимает опти­мальное (максимальное или минимальное) значение.

Термины "решение" и "план" - синонимы, однако первый чаще используется, когда речь идет о формальной стороне за­дачи (ее математическом решении), а второй — о содержа­тельной стороне (экономической интерпретации).

При условии, что все переменные неотрицательны система ограничений (1.20) состоит лишь из одних неравенств, такая задача линейного программирования называется стандартной, если система ограничений состоит из одних уравнений, то задача называется канонической (в ряде работ по математическому программированию стандартную задачу называют симметричной, а каноническую задачу — основной). Так, в приведенных выше примерах задач линейного программиро­вания задачи 1 и 2 — стандартные, задача 4 — каноническая, а задача 3 — общая.

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

Теорема 1.1. Всякому решению (a ₁, a ₂, … ,a_n) неравенства (1.23) соответствует определенное решение (a ₁, a ₂, … ,a_n; а_{n +1}) уравнения (1.24) в котором (1.25) и наоборот, каждому решению (a ₁, a ₂, … ,a_n; а_{n +1}) уравнения (1.24) и неравенства (1.25) соответствует определенное реше­ние (a ₁, a ₂, … ,a_n) неравенства (1.23).

Используя эту теорему, представим, в качестве примера, стандартную задачу (1.4) — (1.6), в каноническом виде. С этой целью в каждое из m неравенств системы ограничений (1.4) введем дополнительные неотрицательные переменные и система ограничений (1.4) примет вид:

(1.26)

Таким образом, стандартная задача (1.4) - (1.6) в канонической форме примет вид: найти такое решение Х = (х ₁, х ₂, … ,x_n), удовлетворяющее системе (1.26) и условию (1.5), при ко­тором функция (1.6) принимает максимальное значение.

Замечание. В рассматриваемой задаче все неравенства вида " ", поэтому дополнительные неотрицательные переменные вводились со знаком "+". В случае неравенств вида " " соответствующие дополнительные переменные следовало бы ввести со знаком "-".