2 Алгоритм Флойда. Постановка задачи
1 Постановка задач линейного программирования (ЗЛП). Примеры экономических задач, сводящихся к ЗЛП. Допустимые и оптимальные решения
В общем виде задача линейного программирования (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции
(1)
на некотором множестве DÌRn ,где xÎDудовлетворяют системе ограничений
Возможно вы искали - Реферат: Задачи синтеза оптимальных систем управления
(2)
и, возможно, ограничениям
Похожий материал - Реферат: Законодательные и нормативные документы по использованию ИКТ в образовании
(3)
He умаляя общности, можно считать, что в системе (2) первые т ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).
Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции
эквивалентна задаче поиска минимума функции
Очень интересно - Реферат: Записи в языке Turbo Pascal
Часто условия задачи (1) - (3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме
где с и x — векторы из пространства Rn , b — вектор из пространства Rm , a А — матрица размерности m´ п.
Задачу линейного программирования, записанную в форме (1) - (3), называют общей задачей линейного программирования (ОЗЛП).
Вам будет интересно - Реферат: Засоби векторної трасировки растрових зображень в Corel Drow
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные xj наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:
Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).
Условимся относительно терминологии, которая используется в дальнейшем и является общепринятой в теории линейного программирования.
Планом ЗЛП называется всякий вектор х из пространства Rn .
Похожий материал - Курсовая работа: Засоби виводу інформації на принтер в об’єктно-орієнтованому середовищі програмування Delphi
Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область Dназывается при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию
maxf(x) = f(x* ).
Величина f* = f(x* ) называется оптимальным значением целевой функции.
Решением задачи называется пара (х* , f* ), состоящая из оптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.