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

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Постановка задачи. Как уже упоминалось во введении, предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далеко не всегда адекватно природе моделируемого объекта. Например, в рассмотренных в главе 1 моделях цена товара считается независимой от количества произведенного продукта, однако в повседневной жизни мы постоянно сталкиваемся с тем, что она может зависеть от объема партии товара. Аналогичные замечания могут быть сделаны и по поводу технологических ограничений: расход определенных видов сырья и ресурсов происходит не линейно, а скачкообразно (в зависимости от объема производства). Попытки учесть эти факторы приводят к формулировке более общих и сложных оптимизационных задач. Изучение методов их решения составляет предмет научной области, получившей названия нелинейного программирования.

Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x₁, х_2,..., x_n) на множестве D, определяемом системой ограничений

где хотя бы одна из функций f или g_i является нелинейной.

По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде

Также очевидно, что вопрос о типе оптимизации не является принципиальным. Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации.

Как и в ЗЛП, вектор х* = (x₁^*,x₂^*,...,x_n^*) D называется допустимым планом, а если для любого x D выполняется неравенство f(x*) ≥ f(x), то х* называют оптимальным планом. В этом случае х*является точкой глобального максимума.

С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а g_i(х) ≤ 0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (а_iх – b_i ≤ 0).

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

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

Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:

либо, добавив фиктивные переменные у, к системе уравнений:

Перечислим свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

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

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

28 Метод множителей Лагранжа, метод нахождения условного экстремума функции  , где  , относительно   ограничений  , где   меняется от единицы до 

Задание. Имеется два способа производства некоторого продукта. Издержки производства при каждом способе зависят от произведенных y₁ и у₂ следующим образом: g(y₁)= 9y₁ + y₁², g(y₂)=6y₂ + y₂² . За месяц необходимо произвести 3×50 единиц продукции, распределив ее между двумя способами так, чтобы минимизировать общие издержки (при решении используйте сервис метод множителей Лагранжа).

Решение  Найдем экстремум функции F(X) = 9•x₁+x₁²+6•x₂+x₂², используя функцию Лагранжа:    где   - целевая функция вектора  .   - ограничения в неявном виде (i=1..1)  В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:  F(X) = 9•x₁+x₁²+6•x₂+x₂²  Перепишем ограничение задачи в неявном виде:    Составим вспомогательную функцию Лагранжа:    Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х_i и неопределенному множителю λ.  Составим систему:  ∂L/∂x₁ = 2•x₁+λ+9 = 0  ∂L/∂x₂ = λ+2•x₂+6 = 0  ∂F/∂λ = x₁+x₂ -150= 0  Систему решаем с помощью метода Гаусса или используя формулы Крамера.

Запишем систему в виде:    Для удобства вычислений поменяем строки местами:    Добавим 2-ую строку к 1-ой:    Умножим 2-ую строку на (2). Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:    Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:    Из 1-ой строки выражаем x₃    Из 2-ой строки выражаем x₂    Из 3-ой строки выражаем x₁ 

29 Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).

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

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

Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений^[1]или «эффективного метода»^[2]; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга. В методологии алгоритм является базисным понятием и получает качественно новое понятие как оптимальности по мере приближения к прогнозируемому абсолюту. В современном мире алгоритм в формализованном выражении составляет основу образования на примерах, по подобию.