1.Основные понятия

Широкий класс задач экономики может быть сформулирован в виде ли­нейных задач оптимизации, характерной чертой кото­рых является линейность целевых функций и ограничений. Ос­нов­ным ме­тодом решения линейных за­дач служит симплекс-метод.

В данном разделе приводятся основные понятия и опре­де­ле­ния, которые используются в последующих разделах.

1.1. Постановка и формы записи задачи лп

Общая задача линейного программирования (ЛП) формулируется сле­­дующим образом:

(1)

(2)

Вектор , удовлетворяющий условиям задачи (2), на­зы­ва­ется допустимым решением (планом) задачи; множество всех допустимых решений задачи будем обозначать через . Допус­ти­­мое решение , доставляющее максимуму (минимуму)це­ле­вой функции (1) , называется оп­тимальным решением задачи; множество всех оптимальных решений обозначим через .

Задача (1)-(2) разрешима, если , в противном слу­чае различают два типа неразрешимости: НР1- множество допустимых решений пусто , т.е. ; НР2 - целевая фу­нк­ция не ограничена на множестве допустимых решений, т.е. .

Выделяют две формы задачи линейного программирования: стандартную и каноническую. Если ввести обозначения:

- матрица ограничений задачи размера mn,

- вектор свободных членов,

- вектор коэффициентов целевой функции,

тогда эти формы задачи имеют вид:

стандартная форма ,

каноническая форма ,

1.2. Правила преобразования задач

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

1) чтобы перейти от минимизации целевой функции к максимизации, достаточно умножить целевую функцию на «-1» и ис­пользовать очевидное равенство ;

2) чтобы изменить тип ограничения-неравенства, нужно умно­жить его на «-1» :

;

3) чтобы перейти от ограничений-неравенств к равенствам нужно ввести дополнительную ( слабую ) переменную :

4) чтобы перейти от ограничений-равенств к неравенствам ну­ж­но заменить это ограничение на два противоположных не­ра­венства

5) если переменная свободная (нет ограничение на знак),то вводят новые переменные и делают замену .

Пример 1. Привести к канонической форме следующую задачу:

Исходная задача		Каноническая форма

Другой способ приведения состоит в том, что из второго урав­не­ния находим , а затем исключаем переменную из остальных ограничений и целевой функции:

(после исключения )		Каноническая форма

▀