Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 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 рецепт  
Молоко      
Молоко сухое      
Масло сливочное      
Сахар      
Себестоимость шт. (в грн) 0,65 0,7  
Продажная цена (в грн)   1,2  

 

Необходимо найти такой план выпуска продукции, который обеспечит максимальную прибыль при имеющихся ресурсах. Обозначим х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 линейно независимых гиперплоскостей, задаваемых ограничениями-равенствами, и последовательном переходе к другой точке с уменьшением целевой функции. Такие точки можно представить вершинами некоего многогранника, являющегося пересечением конечного числа полупространств - допустимых решений. Главное преимущество симлекс-метода - универсальность и простота реализации на компьютере






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных