42.Постановка и математич модель зцлп.

В задачах с неделимыми объектами на переменные накладываются условия целочисленности. Иногда эти условия распространяются на все переменные, иногда—на часть переменных.Рассматривают полностью целочисленную задачу

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xj≥0, j=1,n

xi-целое,j=1,n

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

1.Методы отсечения

2.Комбинаторные

3.Приближенные методы..

Формирование отсекающего неравенства. Идея решения ЗЦЛП методом отсечения и его геометрическая иллюстрация.

Идея методов отсечения состоит в следующем: задача решается без учета условия целочисленности.Если полученое решение не является целочисленным, то к условию задачи добавляют новое ограничение, кот называется правильным отсечением. Оно должно удовлетворять 3 условиям:

1.Ограничение должно быть линейным

2.Оно должно отсекать найденное целочисленное решение

3.Оно не должно отсекать не одного целочисленного плана.

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

Xk=βk-(n-m,s=1)∑αkm+sXm+s

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

Xk=([βk]-(n-m,s=1)∑[αkm+s]Xm+s)+({βk}-(n-m,s=1)∑ {αkm+s}Xm+s)

Сумма в первых скобках-целое число, во вторых-дробное.Для того, чтобы Хк было целым, надо,что и сумма во вторых скобках была целой. Обозначим ее

Sk={βk}-(n-m,s=1)∑ {αkm+s}Xm+s

Чтобы s было целым оно должно быть не положительным

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk} (1)

43.Формирование отсекающего неравенства.

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

1.Ограничение должно быть линейным

2.Оно должно отсекать найденное целочисленное решение

3.Оно не должно отсекать не одного целочисленного плана.

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

БП	1	СП
		-Xm+1	-Xm+2	….	-Xn
X1=	β1
X2=	β2
…
Xk=	βk
…
Xm	βm
F=

Пусть среди элементов единичного столбца этой матрицы есть дробные-βk.запишем соответствующее ему уравнение

Xk=βk-(n-m,s=1)∑αkm+sXm+s

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

Xk=([βk]-(n-m,s=1)∑[αkm+s]Xm+s)+({βk}-(n-m,s=1)∑ {αkm+s}Xm+s)

Сумма в первых скобках-целое число, во вторых-дробное.Для того, чтобы Хк было целым, надо,что и сумма во вторых скобках была целой. Обозначим ее

Sk={βk}-(n-m,s=1)∑ {αkm+s}Xm+s

Чтобы s было целым оно должно быть не положительным

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk} (1)

Полученное неравенство—правильное отсечение.