1. Математическое моделирование

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

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

Наиболее изучены линейные постановки, среди которых выделяют задачи:

Линейного программирования

Max{Cx: Ax£ B, X³ 0};

целочисленного программирования

Max{Cx: Ax£ B, X³ 0, целые};

Частично-целочисленного (или смешанного) программирования

Max (cx + hy);

Ax + Gy £ b;

X³ 0;

Y³ 0, целые;

Булевого программирования

Max{Cx: Ax£ B, XÎ{0,1}N}.

Комбинаторная постановка задачи в общем случае имеет вид

.

Если целевая функция или/и ограничения нелинейны, то такая модель называется Нелинейной.

Приведем несколько примеров построения математических моделей.

Булева задача о ранце (ЗР).

Задано число B и множество предметов {1,…,N}, для каждого из которых известна его ценность CJ и вес AJ.

Требуется выбрать подмножество предметов суммарный вес которых не превосходит B, а суммарная ценность максимальна.

Введем переменные XJ = 1, Если предмет J выбран, и XJ = 0 в противном случае. Тогда допустимая область задается условиями

А функционал имеет вид

.

Для комбинаторной постановки задачи обозначим множетсво предметов N, а подмножество выбранных предметов – S. Тогда задача о ранце запишется

Следующая >