Задача целочисленного программирования, методы ее решения

Метод наискорейшего спуска

1. выбирают любую точку X0, удовлетворяющую области решений (в дальнейшем эта точка Xk)

2. Находят частные производные, а затем градиент функции в точке.

3. определяют шаг лямбда

4.по формулам 1. Xk+1= Xk+”лямбда”*1 и 2. Xk+1= Xk+”лямбда”*”обратная дельта’Z(Xk) находят точку Xk+1

5. проверяют, находиться ли точка Xk+1 внутри области решений.

6. проверяют, точку Xk+1 на оптимальность. Если точка не является оптимальным решением повторяют пункты 2-6

Определение сепарабельной функции

Класс ЗНЛП значительно шире класса задач линейного программирования. Основные результаты в нелинейном программировании получены при рассмотрении задач, в которых система ограничений линейная, а целевая функция нелинейная. Даже в таких задачах оптимальное решение может быть найдено только для узкого класса целевых функций. частные случаи, когда целевая функция сепарабельная (является суммой n функций f_j (x_j))

Кусочно-линейная аппроксимация

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

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

Задача целочисленного программирования, методы ее решения

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

Задача о ранце. Имеется m ограниченных ресурсов b= (b ₁, b ₂, …, b_m), которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j -й груз (j =1, 2, …, n) характеризуется следующими свойствами:

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

· полезностью c_j ;

· расходом i- го ресурса для перевозки единицы j -го груза a_ij, (i =1, 2, …, m; j =1, 2, …, n).

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

Обозначим через x_j — количество выбранных для транспортировки предметов и запишем математическую модель этой задачи. Очевидно, требованию неделимости соответствует условие:

x_j ³0, x_j — целые, j =1, 2, …, n. (1)

Сопоставление расхода ресурсов каждого типа для транспортировки единицы груза и наличия ресурсов приводит к ограничению

(2)

Общую полезность рейса определяет значение функции

(3)

Частным случаем задачи (1—3) является задача о ранце, в которой любой из заданного набора предметов j =1, 2, …, n может быть выбран или нет, т.е. для каждого из x_j допустимыми значениями является 0 (предмет не выбирается) или 1 (предмет выбирается). Это приводит к тому, что условие (1) задачи (1—3) заменяется требованием

, (1’)

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

определить такие составляющие вектора решения x= (x₁, x₂, …, x_n), которые максимизируют функцию

Известно, что дискретная величина, принимающая лишь значения 0 или 1, называется булевой. Поэтому задачи, в которых на переменные накладывается условие вида (1’), получили название задач с булевыми переменными.

Дата добавления: 2015-11-14