Нелинейное программирование

Нелинейное программирование - раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями.

В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов: например, из-за деления издержек производства на предприятиях на переменные и условно-постоянные; из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую; из-за влияния экстерналий (и т. д.).

В краткой форме задачу нелинейного программирования можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0,

где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

Решение задачи нелинейного программирования (глобальный максимум или минимум), может принадлежать либо границе, либо внутренней части допустимого множества.

Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейны; и целевая функция, и ограничения нелинейны.

Задачи, в которых число переменных и (или) число ограничений бесконечно, называются задачами бесконечномерного нелинейного программирования. Задачи, в которых целевая функция и (или) функции ограничений содержат случайные элементы, называются задачами стохастического нелинейного программирования.

Например, задачу для двух переменных (выпуск продукта x и выпуск продукта y) и вогнутой целевой функции (прибыль Р) можно геометрически представить на чертеже. Эта задача реалистично отражает распространенное в экономике явление: рост прибыли с ростом производства до определенного (оптимального) уровня, а затем ее снижение (например, вследствие затоваривания продукцией или исчерпания наиболее эффективных ресурсов).

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

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

Среди вычислительных алгоритмов нелинейного программирования большое место занимают градиентные методы. Универсального же метода для нелинейных задач нет и, по-видимому, может не быть, поскольку они чрезвычайно разнообразны. Особенно трудно решаются многоэкстремальные задачи. Для некоторых типов задач выпуклого программирования (вид нелинейного) разработаны эффективные численные методы оптимизации.

В задаче нелинейного программирования требуется найти значение многомерной переменной х=(), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств, i=1,2,…,m, а переменные, т.е. компоненты вектора х, неотрицательны.

Иногда в формулировке задачи ограничения имеются противоположные знаки неравенств. Учитывая, однако, что всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например, то их можно представить в виде пары неравенств, сохранив тем самым типовую формулировку задачи.

Для решения задачи нелинейного программирования было предложено много методов, которые можно классифицировать по различным признакам.

По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:

• однокритериальные,
• многокритериальные.

По длине вектора методы делятся на:

• однопараметрические или одномерные (n=1),
• многопараметрические или многомерные (n>1).

По наличию ограничений методы нелинейного программирования делятся на:

• без ограничений (безусловная оптимизация),
• с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

• методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения;
• градиентные методы первого порядка, в которых при поиске экстремума функции используются значения ее первых производных;
• градиентные методы второго порядка, в которых при поиске экстремума функции наряду с первыми производными используются и вторые производные.

Ни один метод нелинейного программирования не является универсальным. В каждом конкретном случае необходимо приспосабливать применяемый метод к особенностям решаемой задачи.

Предприятие “Элиза” специализируется на производстве свадебных платьев.

Товар, который производит предприятие - это недорогие и качественные свадебные платья из различных видов тканей и разнообразные по фасону, в зависимости от желания и предпочтений клиента.

Контингент покупателей и заказчиков - это люди со средним достатком, которые не могут позволить себе приобретать свадебные платья в дорогих салонах, но которые требовательны к качеству и ценящие индивидуальность в своем стиле.

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

Дом, в котором расположено ателье, находится недалеко от остановки, что также имеет большое значение для успешного развития предприятия.

Помещения ателье:

1) 2 мастерские;

2) кабинет;

3) склад;

4) место для продажи и подбора тканей;

5) примерочная;

6) кабинет дизайнера.

Предприятие “Элиза” специализируется на производстве свадебных платьев, а также оказания услуг по ремонту свадебных платьев: установка кнопок и блочек, раскрой тканей, декоративные отделки, машинная вышивка, оформление стразами, консультации и т.д.

Все материалы, необходимые для производства, закупаются оптовыми партиями в торговой сети оптовой продажи.

Шитье производится на швейных машинах известной французской фирмы Digital. Они выполняют моментально множество мелких необходимых функций благодаря механическому управлению. Самое главное то, что весь заказ выполняется в самые короткие сроки (с учетом высоких требований к качеству). Вид продукции напрямую зависит от требований и предложений заказчиков. Вид тканей определяет сам клиент. Модели и стили выполнения работы можно выбрать в фирменном каталоге предприятия. Несомненно, все модели имеют современный стильный дизайн, покрой производится исключительно с учетом затрат и количества тканей (ткань можно приобрести у нас на складе или же заказчик может предоставить свои расцветки и фасоны).

Для создания моделей свадебных платьев, подготовки чертежей и выкроек существуют различные системы автоматизированного проектирования одежды (САПР). Они обычно состоят из компьютера, принтера, плоттера, которые в сочетание с программным обеспеченьем позволяют автоматизировать этап проектирования и существенно сократить время на разработку моделей.