Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
37.Постановка и математич модель ЗЦЛП.
В задачах с неделимыми объектами на переменные накладываются условия целочисленности. Иногда эти условия распространяются на все переменные, иногда—на часть переменных.Рассматривают полностью целочисленную задачу
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.Приближенные методы..
37.Формирование отсекающего неравенства. Идея решения ЗЦЛП методом отсечения и его геометрическая иллюстрация.
Идея методов отсечения состоит в следующем: задача решается без учета условия целочисленности.Если полученое решение не является целочисленным, то к условию задачи добавляют новое ограничение, кот называется правильным отсечением. Оно должно удовлетворять 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)
38.Формирование отсекающего неравенства.
Если полученое симпл методом решение задачи не является целочисленным, то к условию задачи добавляют новое ограничение, кот называется правильным отсечением. Оно должно удовлетворять 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)
Полученное неравенство—правильное отсечение.
39.Алгоритм метода Гомори.
1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2
2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле
(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}
3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом
4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.
Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах.Метод Гомори имеет ограниченое применение. С его помощью целесообразно решать небольшие задачи, т.к. число интераций может быть очень большим.
40.Метод ветвей и границ решения целочисленных задач.
Этот метод относится к группе комбинаторных.Применение этих методов заменяет полный перебор планов их частным перебором. Идея метода: пусть дана ЗЦЛП
f=(n,j=1)∑CjXi max
(n,j=1)∑AijXj=bi, i=1,m
xj≥0, j=1,n
xi-целое,j=1,n
Сначала в ОДЗ этой задачи определяется оптимальный план без учета условия целочисленности. Если в полученном решении некоторые переменные имеют дробное значение, то выбирают любую из дробных переменных и разветвляют исходную задачу на 2 подзадачи
f =∑CjXj max f =∑CjXj max
(n,j=1)∑AijXj≤bi, i=1,m (n,j=1)∑AijXj≤bi, i=1,m
Xk≤[Xk˚] Xk≥[Xk˚]+1
Xj≥0 Xj≥0
Xj-целое,j=1,n Xj-целое,j=1,n
Если после решения этих подзадач неизвестные не будут целочисленные, то выбирается задача с большим значением целевой функции и по неизвестной
Задача разбивается на 2 новые подзадачи. На каждом последующем шаге сравниваются целевые функции неразветвленных задач и ветвиться задача с большим значением целевой функции.