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

1. Основная и симметричная задача

Основной задачей ЛП (ОЗЛП) называется такая задача: найти переменные x₁, x₂,... x_n которые доставляют максимум целевой функции

F(х) = c₁ x₁ + c₂ x₂ +.... c_n x_n = (cx) ®max (4)

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

Û Ax = b (5)

и ограничениях-неравенствах: x ³ 0 (6)

Допустимым вектором (планом) ОЗЛП называется всякий вектор x, удовлетворяющий уравнениям (5) и неравенствам (6). Допустимый вектор, доставляющий максимум целевой функции F(х), называется решением задачи линейного программирования.

Стандартной (симметричной) задачей линейного программирования называется следующая задача:

Найти вектор x, доставляющий максимум(минимум) целевой функции

F(х) = c₁ x₁ + c₂ x₂ +.... c_n x_n = (cx)®max

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

(в матричной форме – Ax £ b)

и требованиях неотрицательности[1]:

x₁ ³ 0, x₂ ³ 0,... x_n ³ 0 Û x ³ 0

Всякую симметричную задачу можно превратить в основную, вводя новые неотрицательные переменные – невязки неравенств y_i= b_i – åa_ij x_j Например:

3x₁ + 5x₂ ≤ 4 3x₁ + 5x₂ + 1y₁ + 0y₂ = 4

2x₁ – 5x₂ ≤ 6 2x₁ – 5x₂ + 0y₁ + 1y₂ = 6

x₁ ≥0 x₂ ≥0 x₁ ≥0 x₂ ≥0 y₁ ≥0 y₂ ≥0

В общем случае: симметричная задача

Ax £ b превращается в основную задачу

Ax +Еу = b

x ³ 0 x ³ 0 у ³ 0

2. Геометрические соображения