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

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

Общая задача линейной оптимизации состоит в нахождении максимума (минимума) линейной функции

(1)

при ограничениях (2)

(3)

(4)

(5)

(6)

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

(7)

(8)

(9)

(10)

(11)

(12)

где - заданные действительные числа, функцию Z называют целевой функцией.

Стандартной задачей называют задачи:

максимизации минимизации

(13) (16)

(14) (17)

(15) (18)

Канонической задачей линейной оптимизации называют задачу:

(19)

(20)

(21)

Совокупность значений неизвестных , удовлетворяющих условиям задачи (7)—(12), называется решением (или планом ).

Решение называется оптимальным, если оно обеспечи­вает максимальное (минимальное) значение целевой функции (7).

Замечание: Целевая функция и все ограничения линейные. Свойство линейности предполагает:

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

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