2015-02-04
803
1. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
(10.10)
при условиях
(10.11)
(10.12)
. (10.13)
Функция (10.10) называется целевой функцией (или линейной формой) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.
2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.
3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.
| Каноническая (основная) форма | Стандартная (симметричная) форма | Общая форма |
| 1) ограничения | ||
Уравнения
  .
| Неравенства
  .
| Уравнения и неравенств
 .
|
| 2) условия неотрицательности | ||
Все переменные
 , 
| Все переменные
,
| Часть переменных
,  ,  .
|
3) цель задачи
| ||
| max F (x) или min F (x) | max F (x) [min F (x)] | max F (x) или min F (x) |
max F (x) = – min[– F (x)], min F (x) = – max[– F (x)].
Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них может быть преобразована к форме другой. Совокупность чисел 
, удовлетворяющих ограничениям (10.11) – (10.13), называется допустимым решением (или планом).
Запишем основную задачу линейного программирования в векторной форме. Найти максимум (минимум) функции
при условиях
, (10.14)
где 
– скалярное произведение; 
и 
– m -мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи.
План Х называется опорным планом основной задачи линейного программирования, если система векторов 
, входящих в разложение (10.14) с положительными коэффициентами 
, линейно независима.
Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он является вырожденным.
План 
, при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.
