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

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

Среди точек х = (х ₁,…, х_n)Î Eⁿ, удовлетворяющихограничениям:

а_ij x_j £ b_{i ,} i = 1: k; (6.1)

а_ijx_j = b_i, i = (k +1): m; (6.2)

x _j ³ 0, j = 1: n (6.3)

найти те, в которых функция

¦(х) = c _j x _j

принимает минимальное значение, и определить это значение. Это общая или произвольная форма записи.

Отметим, что в условии задачи линейного программирования могут содержаться неравенства и противоположного, чем в (6.2), знака, однако такие неравенства легко сводятся к виду (6.2) умножением на − 1.

Если в условии задачи линейного программирования не содержаться ограничения − равенства (6.1), то эта форма записи называется симметричной или стандартной.

Если в условии задачи линейного программирования не содержаться ограничения − неравенства (6.2), то есть в (6.1) l = m, то она называется задачей линейного программирования в каноническом (основном) виде.

Ограничения – неравенства

преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) переменных х_{n + i} ≥ 0, i = 1: k. Ограничения − неравенства (6.2) можно записать в виде равенств:

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

f (x) = (6.4)

а_ij x_j = b_{i ,} i = 1: m, (6.5)

x_j ≥ 0, j = 1: n. (6.6)

Если переменная х_n не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и , приняв х_n = − , ≥ 0, ≥ 0.

Часто используется векторная запись задачи (6.3)…(6.5):

f (x) = (c, x) min,

Ax = b, (6.7)

х ≥ 0,

где х = ( х ₁,…, х_n)^Т– векторнезависимых переменных, с = (с₁,…, с _n)^Т – вектор коэффициентов целевой функции из (6.3), А = (а_ij) – прямоугольная матрица размера m ´ n, b = (b ₁,…, b _m ) ^Т– вектор правых частей (ограничений) системы (6.4), а х ³ 0 − краткая запись условий неотрицательности (6.3).

Ограничения вида х_j ≥ 0 или х _j £ 0, или d_j £ x_j £ p_j (двусторонние ограничения) для всех или некоторых j (j = 1: n) называют прямыми ограничениями на переменные. Методы решения задач линейного программирования построены, как правило, с учетом вида прямых ограничений.

Обозначив а_ijx_j = g_i (x), условимся ограничение g_i (x) £ 0 называть активным в точке x ₀, если это неравенство при x = x ₀ обращается в равенство, т.е. если g_i (x ₀) = 0. В случае строгого неравенства g_i (x ₀) < 0 данное ограничение называют неактивным в точке x ₀. На рис. 6.1 изображены точка x ₀, в которой оба ограничения активны, и точка х ¢, в которой оба ограничения неактивны.

Рис. 6.1. Графическая иллюстрация активного и неактивного ограничений

Задача линейного программирования, которая имеет допустимые решения (т.е. система ограничений совместна) называется допустимой; задача с несовместной системой ограничений – недопустимой.

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

План х * = (х ₁*,…, х_n * ), при котором целевая функция задачи (6.1)…(6.3) принимает свое минимальное (максимальное) значение, называется оптимальным.

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

Чтобы имело смысл говорить об отыскании оптимального плана задачи система (6.1)…(6.3) должна быть совместна и иметь не единственное неотрицательное решение. Это возможно в случае, если ранг r системы (число линейно независимых уравнений) меньше числа неизвестных n (r < n), при r = n – система допускает единственное решение, и вопрос о выборе оптимального решения отпадает. Случай r > n вообще невозможен.

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

а) f (x) = 6 х ₁ + 5 х ₂ min

Решение. Заменяем функцию f (x) на . Из левых частей ограничений типа ≥ вычитаем неотрицательные переменные х ₃, х ₄, _,х ₅, к левым частям ограничений типа ≤ прибавляем неотрицательные переменные х ₆, х _7. Получаем модель задачи в канонической форме:

,

б) f (x) = 2 х ₁ − 3 х ₂ + 5 х ₃ − х ₄ max,

Решение. Эта задача не является канонической из-за того, что не от всех переменных требуется неотрицательность. Представим переменные х ₂, х ₄ в виде разностей , , где . Подставляя эти разности в значение функции и ограничения, получим каноническую задачу:

f (x) = 2 х ₁− 3() + 5 х ₃ − max,