МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

В.И. Рюмкин

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Томск

2007

УДК 519.6

Рюмкин В.И. Методы решения задач нелинейного программирования: Учебное пособие. – Томск: ТГУ, 2006. – 56 с.

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

Учебное пособие разработано для студентов экономического факультета дневной и вечерней форм обучения ТГУ и студентов Высшей школы бизнеса ТГУ.

УДК 519.6

Рецензент – профессор С.Н. Колупаева

© Рюмкин В.И.

Введение

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

Критерий эффективности выражается некоторой функцией , называемой целевой, аргументами которой являются как действующие факторы , так и элементы решения :

.

Тогда задача математического программирования может быть представлена в следующей записи:

(*)

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

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

1. Основы математического программирования

1.1. Постановка задачи математического программирования

Задачей математического программирования (ЗМП), или оптимизационной задачей, называется любая задача вида

, (1.1)

, (1.2)

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

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

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

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

1.2. Разновидности змп

Приведем в порядке возрастания сложности решения несколько классов ЗМП.

а) ЗМП при отсутствии ограничений.

. (1.3)

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

б) ЗМП с ограничениями-равенствами:

(1.4)

(1.5)

Для задач этого класса допустимое множество определяется как множество решений системы уравнений:

.

в) ЗМП с ограничениями-неравенствами:

(1.6)

(1.7)

Для задач этого класса допустимое множество определяется как множество решений системы неравенств:

.

г) ЗМП со смешанными ограничениями (ограничениями смешанного типа):

(1.8)

(1.9)

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

.

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

ЗМП называется задачей линейного программирования (ЗЛП), если целевая функции является линейной функцией, а область ограничений представляет собой выпуклый многогранник. В противном случае ЗМП называется задачей нелинейного программирования (ЗНЛП).

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