В векторной форме

В координатной форме целевая функция F(x)

Каноническая форма задачи линейного программирования

Тема 5 Линейное программирования. Способы решения

В общем виде задачи линейного программирования формулируются следующим образом: найти max линейной функции F при заданной системе ограничений. Множества решений такой системы можно представить геометрически в виде n-мерного полупространства. А множество решений системы линейных неравенств и допустимых решений системы уравнений выпуклым многоугольником или выпуклой многогранной областью. Последнее заключение весьма важно, т.к. принципы линейного программирования основаны на свойствах выпуклых многогранников. Очень важно при поиске решения установить взаимно однозначное соответствие между угловыми точками многогранника и допустимыми адресными решениями данной системы уравнений. Данное соответствие наглядно отображается при геометрическом решении задачи линейного программирования. Однако Геометрический метод не является универсальным решением для любой задачи линейного программирования. Можно получить при помощи симплексного метода решения задачи линейного программирования.

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

СХ – скалярное произведение векторов

Дата добавления: 2014-01-11