Математическая формулировка задач дискретного программирования

1 0,28 0,20 0,28 (1,0,0) (1,0,0,0)

2 0,53 0,33 0,53 (1,1,0) (1,1,0,0)

3 0,70 0,42 0,73 (2,1,0) (1,1,0,1)

4 0,90 0,48 0,90 (3,1,0) (2,1,0,1)

Или (3,1,0,0)

5 1,06 0,53 1,10 (3,2,0,) (3,1,0,1)

6 1,21 0,56 1,26 (3,2,0) (3,2,0,1)

7 1,35 0,58 1,41 (3,3,1) (3,2,1,1)

8 1,48 0,60 1,55 (4,3,1) (3,3,1,1)

9 1,60 0,60 1,68 (5,3,1) (3,3,1,2)

Или (3,3,3) или (4.3,1,1)

10 1,73 0,60 1,81 (4,3,3) (4,3,1,2)

------------------------------------------------------------------------------------------------------------------

Исследование операций

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

Исследование операций – научный метод, который дает в распоряжение инженера или руководителя количественные методы для принятия решений по управлению процессов оптимизации и видами человеческой деятельности.

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

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

Важность изучения таких задач определяется их актуальностью в различных сферах человеческой деятельности. К таким задачам относятся: задачи планирования, проектирования сложных систем.

Математическая формулировка задач дискретного программирования

Записываются целевая функция и условия ограничений в виде математических выражений.

В общей форме математическая модель задачи имеет вид:

Получить экстремальное значение целевой функции (F):

F: extrem z = f(x, w)

x,w

При ограничениях (D):

X є Rⁿ, w є z^p

D = g_i(x,w)<=0

I=1,m

Где:

Z – целевая функция

X – вектор непрерывных оптимизационных переменных размерности n

W – вектор целочисленных оптимизационных переменных размерностью p

D - множество допустимых решений

Rⁿ - n-мерное евклидовое пространство

Z^p - p-мерное множество целых чисел.

g_i - условие ограничения, накладываемое на оптимизационные переменные.

I - порядковый номер и, соответственно, общее количество оптимизационных переменных.

Можно предположить, что ЗДП можно решить зная общие методы решения непрерывных оптимизационных задач, а именно:

§ Сначала отбросить условия дискретности и решить обычную непрерывную задачу.

§ Округлить полученное решение с целью обеспечения условия дискретности.

Графический метод. Основные понятия. Алгоритм метода

Графический метод решения задач всегда обладал для специалистов прикладников большой привлекательностью.

Не смотря на большую погрешность результатов графический метод по сравнению с аналитическим остается полезным. И на это имеются веские причины:

Во 1-х их наглядность дает наилучшее представление о структуре задачи и ее решении.

Во 2-х эти методы, несмотря на ограниченную точность можно использовать для

предварительных выкладок, например, для поиска области решения, в которой

затем решают задачу более точными методами.

В 3-х часто в графике содержится значительная информация, которая позволяет

специалисту разобраться в сущности проблемы.

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

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

Линией уровня функции называется множество точек из ее области определения в которых функция принимает одно и то же фиксированное значение.

Градиентом функции f(x) называют вектор f(x),

f(x)=(∂f/∂x1; ∂f/∂x2;.. ∂f/∂xn), который указывает направление наиболее быстрого возрастания функции, и следовательно ориентирован перпендикулярно линии уровня этой функции.