III. Методы линейного программирования

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

В самом общем виде задача математически записывается так:

U = f(X)  max; X  W,
Где X = (Х1, Х2,…, Хn);

W – область допустимых значений переменных Х1, Х2,…, Хn;

f(X) – целевая функция.

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать X()  W такое, что f(X())  f(X), при любом X  W, или для случая минимизации - что f(X()) ≤ f(X), при любом X  W.

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешима, если целевая функция f(X) не ограничена сверху на допустимом множестве W.

Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

• 
  задачи линейного программирования, если f(X) и W линейны;
  
• 
  задачи целочисленного программирования, если ставится условие целочисленности переменных Х1, Х2,…, Хn;
  
• 
  задачи нелинейного программирования, если форма f(X) носит нелинейный характер.