Формы представления задач линейного программирования

Задачи линейного программирования являются разновидностью задач математического программирования. В задачах линейного программирования допустимая область задается в виде системы неравенств и/или равенств, причем все функции в этих ограничениях, а также целевая функция линейны:

, или, в векторной форме: ,

где - матрица размера , а - вектор условий (равенств и/или неравенств).

Задачи линейного программирования можно бы было считать разновидностью задач нелинейного программирования, если из определения задачи нелинейного программирования исключить слова о том, что хотя бы одна из фигурирующих в ее формулировке функций нелинейна. Нетрудно видеть, что ни в одной из приведенных в разделе 3.4 теорем данное ограничение не фигурировало. Поэтому все результаты, относящиеся к задачам нелинейного программирования, справедливы и для задач линейного программирования.

Как уже упоминалось, задачи нелинейного программирования выделены в отдельный класс, потому что для них разработаны методы, позволяющие успешно решать практически все задачи данного класса.

Различают три основные формы представления (вида) задач линейного программирования:

Стандартный вид задачи на максимум:

, или, в векторной форме: , (4.1)

где , , , .

Стандартный вид задачи на минимум:

, или, в векторной форме: . (4.2)

Канонический вид задачи:

, или, в векторной форме: . (4.3)

Отметим, что любая задача линейного программирования может быть представлена в любом из видов (4.1) – (4.3).

Действительно, пусть какое-либо из ограничений имеет вид неравенства . Если его нужно представит в виде неравенства с противоположным знаком, достаточно умножить левую и правую части на "-1": . Если нужно иметь все ограничения в виде равенств, то к левой части неравенства достаточно прибавить некоторую неотрицательную переменную , так называемую невязку, уравнивающую левую и правую части: При этом размерность задачи увеличится на единицу.

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

Если исходное ограничение представлено в виде равенства , то его можно представить в виде системы двух неравенств , или .

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

Если в задаче требуется максимизировать целевую функцию: , то умножением ее на "-1" можно свести данную задачу к задаче на минимум: , и наоборот.

Поиск по сайту: