ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Линейное программированиеТермин "линейное программирование" возник из неточного перевода английского словосочетания "linear programming" -"планирование на основе линейных соотношений" [13]. Теория ЛП занимается созданием методов, позволяющих оптимизировать линейную функцию, на которую наложены линейные ограничения. В основном задачи ЛП ставятся в теории планирования и управления экономическими процессами, реже - в технических задачах. С точки зрения классической математики подобные задачи представляют собой оптимизационные задачи на условный экстремум. Каноническая форма задачи ЛП выглядит следующим образом: найти Z=c1x1+c2x2+...+cnxn → min (целевая функция) при выполнении ограничений: a11x1+a12x2+...+a1nxn=b1 a21x1+a22x2+...+a2nxn=b2 ......................………….. am1x1+am2x2+...+amnxn=bm на переменные могут быть также наложены ограничения неотрицательности: X1≥0, x2≥0,..., xn≥0 Различные постановки задач ЛП могут приводить к разной математической записи (в ограничениях могут быть как знаки равенств, так и неравенств). Переход от разных формулировок к канонической записи нужен для того, чтобы пользоваться стандартными программами, реализованными на компьютерах (а они, в свою очередь, ориентированы на реализацию известного симплекс-метода решения задачи ЛП). Однако для использования графического метода решения лучше использовать стандартную форму записи, в которой ограничения представлены в форме нестрогих неравенств. Для анализа задача ЛП введем некоторые определения. Совокупность значений (х1, х2, …,хn), удовлетворяющих ограничениям, называется допустимым (возможным) решением. Множество всех допустимых решений называют областью допустимых решений (ОДР). Допустимое решение, для которого целевая функция достигает максимума (или минимума), называется оптимальным. Используя приведенные определения, задачу ЛП можно сформулировать следующим образом: необходимо из совокупности допустимых решений выбрать то, которое соответствует минимуму целевой функции. Пример постановки задачи ЛП: Фабрика выпускает мороженое по 2 рецептам. Норма расхода исходных продуктов на 1 т мороженого, их запасы, себестоимость и цена представлены в таблице:
Необходимо найти такой план выпуска продукции, который обеспечит максимальную прибыль при имеющихся ресурсах. Обозначим х1 - количество выпускаемого мороженого по 1 рецепту, х2 - по 2-му рецепту. Задача формулируется в виде: х1(1-0.65) + х2 (1,2-0,7)→max 650х1 + 569х2≤ З000 100x1 + 50x2≤5700 87х1 + 120х2≤ 13800 163х1 +101x2≤ 13500 Усложнение примера: по 1 рецепту должно быть выпущено не менее 15 тн, а по 2-му - не менее 45 тн: х1≥15, х2≥45 Усложнение примера: максимальное время работы фасовочного автомата 400 часов, автомат расфасовывает 1 тн мороженого за 4,5 часа: 4,5 (х1 + х2)≤400 Для перехода от одного вида записи зада ЛП к другой необходимо использовать следующие приемы: 1)переход от задачи максимизации к минимизации и наоборот: z1=c1x1+c2x2+...+cnxn → max z2= -z1=-c1x1-c2x2-...-cnxn → min 2) переход от ограничений-неравенств к равенствам. Для этого в задачу вводится дополнительная переменная xn+1, которая является фиктивной и в целевую функцию входит с коэффициентом нуль: a11x1+a12x2+...+a1nxn≤b1 → переход к a11x1+a12x2+...+a1nxn+xn+1=b1 3) представление ограничения-равенства в виде неравенства. В этом случае равенство представляется в виде двух неравенств, т.е. увеличивается размерность задачи: a11x1+a12x2+...+a1nxn=b1 → переход к a11x1+a12x2+...+a1nxn≤b1 a11x1+a12x2+...+a1nxn≥b1 4)переход от переменных, ограниченных снизу, к неотрицательным переменным: xi ≥ bi → заменив xi = yi + bi, получим yi ≥0 5) наложение на переменные ограничения неотрицательности, если это условие не выполняется. Для этого необходимую переменную хj представим в виде разности двух новых переменных: хj = хj'- хj'', хj' ≥ 0, хj '' ≥ 0. С помощью таких приемов можно привести задачу ЛП к канонической или стандартной форме. Для точного решения задачи ЛП применяется симплекс-метод, разработанный советским математиком Л.В.Канторовичем и американским Дж.Данцигом [8,11]. Основная идея метода состоит в нахождении точки пересечения n линейно независимых гиперплоскостей, задаваемых ограничениями-равенствами, и последовательном переходе к другой точке с уменьшением целевой функции. Такие точки можно представить вершинами некоего многогранника, являющегося пересечением конечного числа полупространств - допустимых решений. Главное преимущество симлекс-метода - универсальность и простота реализации на компьютере Не нашли, что искали? Воспользуйтесь поиском:
|