2,02 Mb. страница2/10Дата конвертации28.09.2011Размер2,02 Mb.Тип Смотрите также: 2 ^ ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ P 1.1.P ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ P 1.1.1. Формы задачи линейного программирования. В общем виде задача линейного программирования* (в дальней]шем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции P P на некотором множестве D | Rn, где х ~ D удовлетворяют сис]теме ограничений P P и, возможно, ограничениям х1 0, х2 0,..., хj 0,..., хn 0. (1.3) * Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении. P Не умаляя общности, можно считать, что в системе (1.2) пер]вые m ограничений являются неравенствами, а последующие l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направ]ления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противопо]ложный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме нера]венств, но в силу особой структуры их обычно выделяют от]дельно и называют условиями неотрицательности (или три]виальными ограничениями). Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относитель]ный характер. Так, задача поиска максимума функции P P эквивалентна задаче поиска минимума функции P P Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращен]ной матричной форме P f(x) = сх max, Ax b, х 0, (1.6) P где с и х векторы из пространства Rn, b вектор из простран]ства Rm, а А матрица размерности m х n. Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного програм]мирования (ОЗЛП). Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные хj наложены усло]вия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матрич]ной форме КЗЛП можно записать в следующем виде: P Поскольку любая оптимизационная задача однозначно оп]ределяется целевой функцией f и областью D, на которой отыс]кивается оптимум (максимум), будем обозначать эту задачу парой (D, f). Условимся относительно терминологии, которая использу]ется в дальнейшем и является общепринятой в теории линейно]го программирования. ^ Планом ЗЛП называется всякий вектор х из пространства Rn. Допустимым планом называется такой план ЗЛП, кото]рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае максимального) значения, т. е. план, удовлетворяющий условию P max f(x) = f(x*). P Величина f* =f(х*) называется оптимальным значением целевой функции. Решением задачи называется пара (х*, f*), состоящая из oптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП. ^ 1.1.2. Переход к канонической форме. Подавляющее боль]шинство известных методов решения задач линейного програм]мирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного про]граммирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче. Общая идея перехода от ОЗЛП к КЗЛП достаточно проста: PPPPP ограничения в виде неравенств преобразуются в уравне]ния за счет добавления фиктивных неотрицательных переменных хi, (i ~ 1:m), которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение; PPPPP переменные, на которые не наложено условие неотрица]тельности, представляются в виде разности двух новых неотрицательных переменных: - = - = хj = хj хj, (xj 0, хj 0). P Проиллюстрируем применение описанных выше рекоменда]ций
Краткий курс P математические методы исследования операций в экономике P
ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ - Краткий курс P математические методы исследования операций в экономике P
Комментариев нет:
Отправить комментарий