 |
|
Постановка задачи линейного программирования
Предположим, что имеется m линейных уравнений и неравенств с n неизвестными:
, 
(2.1)
, 
(2.2)
Также имеются условия неотрицательности переменных:
, 
, 
(2.3)
Дана целевая функция вида:
(2.4)
Определение 2.1. Общей задачей ЛП называется задача нахождения 
, удовлетворяющего системе ограничений (2.1)-(2.3), такого, что функция (2.4) принимает оптимальное (максимальное или минимальное) значение.
Определение 2.2. Стандартной задачей ЛП называется задача нахождения , удовлетворяющего системе ограничений (2.1), (2.3), где k=m, s=n, такого, что функция (2.4) принимает оптимальное (максимальное или минимальное) значение.
Определение 2.3. Канонической задачей ЛП называется задача нахождения , удовлетворяющего системе ограничений (2.2), (2.3), где k=0, s=n, m<n, такого, что функция (2.4) принимает оптимальное (максимальное или минимальное) значение.
Определение 2.4. Решение задачи (2.1)-(2.3) называется допустимым решением.
Определение 2.5. Допустимое решение, доставляющее оптимальное значение целевой функции называется оптимальным
Все три формы задачи ЛП являются эквивалентными. Покажем это.
Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов 
на противоположные, так как 
.
Ограничения-неравенства (2.1) можно записать в виде равенств путем введения дополнительных неотрицательных переменных следующим образом.
Ограничение-неравенство вида 
преобразуется в ограничение-равенство 
, 
, а ограничение-неравенство вида 
- в ограничение-равенство 
, .
Каждое ограничение-равенство (2.2) можно записать в виде двух неравенств 
.
Задачу ЛП можно решать различными методами, которые можно разбить на два основных класса: геометрический метод ЛП и аналитические методы ЛП. Рассмотрим вначале геометрический метод.