Задания к лабораторной работе № 3

 

 

Решить транспортную задачу, заданную матрицами: А - запасов; В - потребностей; С - тарифов.

 

№ вар Задание

 

 

Контрольные вопросы

1. Дайте общую характеристику распределительной задачи.

2. В чем заключается транспортная задача?

 

 

Лабораторная работа № 4

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

 

Цель работы

1. Рассмотреть постановку задачи нелинейного программирования.

2. Рассмотреть примеры задач нелинейного программирования.

3. Решить задачу нелинейного программирования средствами табличного процессора Excel.

 

Теоретическое введение

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

Задачи нелинейного программирования – это задачи, в которых (как и в задачах линейного программирования) требуется найти значения переменных x1, x2, …, xN, обеспечивающие максимальное или минимальное значение некоторой целевой функции при соблюдении системы ограничений. При этом целевая функция и/или некоторые из ограничений являются нелинейными, т.е. содержат нелинейные составляющие, например, x12, x1 x2, и т.д.

Как и в задачах программирования, любые значения переменные x1, x2, …, ХN, удовлетворяющие ограничениям задачи, называются допустимыми решениями, а все множество допустимых решений – областью допустимых решений (ОДР). Допустимые значения переменных x1, x2, …, ХN, при которых целевая функция принимает экстремальное значение, представляют собой оптимальное решение. В задачах нелинейного программирования оптимальное решение может находиться как на границе, как и внутри ОДР.

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

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

Классификация методов нелинейного программирования

Таблица 4.1

Признак классификации Классы методов Описание
Используемый математический аппарат Аналитические (классические) Поиск решения на основе использования необходимых и достаточных условий экстремумов функций (например, равенства нулю производных)
Численные Поиск решения на основе постепенного сужения диапазона, в котором ищется решение
Покоординатные Поиск решения на основе поочередного поиска экстремума целевой функции по каждой из переменных
Градиентные Поиск решения на основе использования градиента целевой функции
Случайного поиска Поиск решения на основе многократного случайного выбора возможных решений
Решаемые задачи Методы решения задач без ограничений Предназначены для решения задач, в которых требуется найти экстремум нелинейной функции без ограничений на значения переменных
Методы квадратичного программирования Предназначены для решения задач с линейными ограничениями и квадратичной целевой функцией, т.е. целевой функцией, содержащей квадраты переменных (например, Х12) и/или их попарные произведения (например, Х1Х2)
Методы сепарабельного программирования Предназначены для решения задач, в которых ограничения и целевая функция является сепарабельными, т.е. могут быть представлены в виде сумм функций одной переменной