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



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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

                                                                                                          (2)

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

                                                                                              (3)

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

,                                                                                                 (1’)

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

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

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

 


Дата добавления: 2018-05-12; просмотров: 858; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!